Talk by Michael Mascagni – Monte Carlo for Linear System Solving, ETH Zurich, Dec. 3

Convergence Analysis of Monte Carlo Linear Solvers Using the Ulam-Von Neumann Algorithm: Necessary and Sufficient Conditions

Prof. Michael Mascagni (Department of Computer Science, Florida State University)
December 3, 15:30, ETH Zurich, HG E41

Abstract:

In this talk we consider the Ulam-von Neumann Monte Carlo algorithm for solving linear systems via the Neumann series.  The Ulam-von Neumann method is a way to solve linear systems in the form: x = Hx +b, and is based on representing the solution via Neumann series.  We provide new necessary and sufficient conditions for convergence of the Ulam-von Neumann Monte Carlo algorithm based on an analysis of the transition probability matrix that defines the underlying Markov chain.  We also demonstrate the theory with small, but illustrative examples.

(Joint work with Dr. Yaohang Li and Mr. Hoa Ji of the CS Department at Old Dominion University in Norfolk, VA.)