Convergence Analysis of Markov Chain Monte Carlo Linear Solvers Using Ulam--von Neumann Algorithm
Hao Ji, Michael Mascagni, Yaohang Li · SIAM Journal on Numerical Analysis · 2013
The convergence of Markov chain--based Monte Carlo linear solvers using the Ulam--von Neumann algorithm for a linear system of the form $x = Hx + b$ is investigated in this paper. We analyze the convergence of the Monte Carlo solver based on the original Ulam--von Neumann algorithm under the conditions that $\|H\|1$ for every row in $H$ or, more generally, $\rho(H^{+})>1$, where $H^{+}$ is the nonnegative matrix where $H_{ij}^{+}=|H_{ij}|$, we show that transition matrices leading to convergence of the Monte Carlo solver do not exist. Finally, given $H$ and a transition matrix $P$, denoting the matrix $H^{*}$ via $H_{ij}^{*}=H_{ij}^{2}/P_{ij}$, we find that $\rho(H^{*})<1$ is a necessary and sufficient condition for convergence of the Markov chain--based Monte Carlo linear solvers using the Ulam--von Neumann algorithm.