* News


Monte Carlo Linear Solvers

Ashok Srinivasan
Assistant Professor, Dept. of Computer Science
Florida State University

Tuesday, March 29, 2005
DCC 330 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Monte Carlo (MC) linear solvers can be thought of as stochastic realizations of deterministic stationary iterative processes. That is, they estimate the result of a stationary iterative technique for solving linear systems. They are suitable for obtaining approximate solutions fast, since, counter-intuitively, an estimate of the solution can be obtained in constant time, independent of the size of the matrix, if we ignore some pre-processing overhead. There are two sources of errors:
(i) those from the underlying deterministic iterative process and (ii) those from the MC process that performs the estimation. While MC linear solvers have a long history (dating back to the work of von Neumann and Ulam, described by Forsythe and Leibler in 1950), their application has been limited due to high errors. Much progress has been made to reduce the stochastic errors of the MC process. However, little attention has been paid to reducing the error from the underlying deterministic iterative process in MC linear solvers. MC linear solvers suffer from the drawback that they are essentially stochastic realizations of the Jacobi method, which has poor convergence properties. The reason for this limitation is that it is believed that an MC implementation requires this for efficiency in space and time.
In this talk, we will describe an efficient MC realization of a different iterative process, and show how the bottlenecks to an efficient MC implementation can be overcome.
Bio sketch: Ashok Srinivasan got his PhD from the University of California in Santa Barbara. He is currently an Assistant Professor at Florida State University. His research interests are in high performance computing, scientific computing, and mathematical software. In particular, he is currently working on computational nanotechnology and Monte Carlo linear algebra. He currently has funding from NSF and DoD.

Last updated: February 22, 2005