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, and provide a proof. In addition we show some historical connections with this work and the Applied and Computational Mathematics Division at NIST.

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.

Speaker Bio: Michael Mascagni is an internationally recognized expert on all aspects of random number generation and Monte Carlo methods, and has lectured extensively across the globe. He received his undergraduate degrees in Biomedical Engineering and Mathematics at the University of Iowa in 1981, and entered Rockefeller University to study neurobiology. While taking some math courses at NYU he decided to switch to math, and he moved to the Courant Institute in 1983. He graduated in 1987, having worked with Prof. Charlie Peskin on the numerical solution of nerve equations. He then did a post-doc at NIH and worked for many years with the Institute for Defense Analyses. He reentered academia, and in 1999 moved to Florida State University's Computer Science Department. He has published over 100 scholarly articles, has graduated doctoral students in Computer Science, Mathematics, and Scientific Computing, and he currently leads a research group working in high-performance computing aspects of Monte Carlo methods and random number generation. He has been a visiting faculty member at Université de Toulon et du Var, Universität Salzburg, Universität Kaiserslautern, and Universitá degli Studi di Padova. He also spent a sabbatical year visiting the Seminar für Angewandte Mathematik, Departement Mathematik, Eidgenössische Technische Hochschule (ETH-Zürich). He was elected an Association for Computing Machinery (ACM) Distinguished Scientist in 2011, and is currently a Faculty Appointee at the National Institute of Standards and Technology (NIST).

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.