
News
Colloquia
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, counterintuitively, an estimate of the solution can be obtained in constant time, independent of the size of the matrix, if we
ignore some preprocessing 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

