Convergence analysis of Markov chain Monte Carlo linear solvers using Ulam-von Neumann algorithm (Q2855100)

In information processing theory the necessity for handling operations with very large quantities of data has emerged during the latest years. It is necessary particularly often to solve linear systems of the form \(Ax=b\), where \(A\) is a huge matrix. This requirement gave a new chance for Monte Carlo linear solvers, based on sampling. The Ulam-von Neumann algorithm proposed by \textit{G. E. Forsythe} and \textit{R. A. Leibler} [``Matrix inversion by a Monte Carlo method'', Math. Tables Other Aids Comput. 4, 127--129 (1950)] as a Monte Carlo variant for solving linear systems of the form \(x=Hx+b\) becomes an actual possibility to give an acceptable solution in real time and using small memory requirements. The convergence of Monte Carlo linear solvers is analysed in this paper. The Ulam-von Neumann algorithm builds a discrete Markov chain by using random walks on the indices of a matrix \(H\) via the von Neumann series -- characterised by a transition probability matrix \(P\). The main results of paper (listed by authors) are:NEWLINENEWLINE1. The condition \(\rho(H)<1\) (where \(\rho(H)\) is the spectral radius of \(H\)) for the von Neumann series is not a sufficient condition for the convergence of the Ulam-von Neumann algorithm (Section 2, Table 2.1, Rows 2 and 3).NEWLINENEWLINE2. The role of the transition matrix \(P\) is very important; a bad choice of \(P\) may give a divergence of the von Neumann series (Theorem 3.2).NEWLINENEWLINE3. If \(||H||<1\), then there can always be found easily at least one transition matrix \(P\) which guarantees the convergence of the Monte Carlo linear solver (Theorem 3.4).NEWLINENEWLINE4. If \(||H||\geq 1\) and \(\rho(H)<1\), then the Monte Carlo linear solver may or may not converge. Some additional restrictions can be found such that the linear solver cannot converge regardless of the choice of the matrix \(P\) (Theorems 3.5 and 3.7).NEWLINENEWLINE5. The necessary and sufficient condition for the Monte Carlo linear solver to converge is \(\rho(H^*)<1\), where \(H^*_{ij}=H_{ij}^2/P_{ij}\) (Theorem 4.2).NEWLINENEWLINETwo more points can be emphasized:NEWLINENEWLINE\((i)\) The complexity of the problem for finding a transition matrix \(P\) when \(||H||\geq 1\) and \(\rho(H^+)\leq 1\) (where \(H_{ij}^+=|H_{ij|})\) is an open problem.NEWLINENEWLINE\((ii)\) The authors announce for a future publishing a new Monte Carlo linear solver algorithm where the condition \(\rho(H)<1\) is necessary and sufficient for converging.