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

Name:    Prof. Michael Mascagni                 
Address: Department of Computer Science and
         Department of Mathematics and
	 Department of Scientific Computing and
         Graduate Program in Molecular Biophysics	
         Florida State University
         Tallahassee, FL  32306-4530  USA
         AND
         Information Technology Laboratory
         Applied and Computational Mathematics Division
         100 Bureau Drive M/S 8910
         National Institute of Standards and Technology (NIST)
         Gaithersburg, MD  20899-8910  USA

Offices: 498 Dirac Science Library/207A Love Building (FSU) Building 225/Room B154 (NIST)
Phone:   +1.850.644.3290 (FSU) +1.301.975.2051 (NIST)
FAX:     +1.850.644.0058
e-mail:  mascagni@fsu.edu (FSU) mascagni@nist.gov (NIST)

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

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.

This is joint work with Dr. Yaohang Li and Mr. Hoa Ji of the Department of Computer Science at Old Dominion University in Norfolk, VA, USA.