Asymptotic complexity of Monte Carlo methods for solving linear systems (Q1973275)

The authors study and compare the complexity of two methods for solving a system of \(d\) linear equations \(x = Ax +g\) where the spectral radius \(\rho (|A |)\) of the matrix \(|A |\) with elements \(|a_{ij} |\) is less than 1. The complexity of the (deterministic) method of successive iteration is the number \(T_I (\varepsilon, A) \) of arithmetic operations needed to calculate an approximate solution of accuracy \(\leq \varepsilon \). The complexity of the von Neumann-Ulam Monte Carlo method is defined as the average number \(ET(A,\varepsilon)\) of arithmetic operations required to get a confidence interval for the solution with width \(\varepsilon\). The main result of the paper shows that for symmetric matrices \(A\) with \(\geq Cd^{1+\alpha}\), \(\alpha >0,\) non-zero elements and \(\rho(A)\leq q <1\) the ratio \(ET(A,\varepsilon)/T_I(\varepsilon,A)\) is of order \(O(\log d /\varepsilon^2 d^2)\) as \(d \to \infty\). Thus, for small dimensions the stochastic algorithm gives with the same computational effort less accuracy than the deterministic method, but as the dimension becomes large the attainable accuracy \(\varepsilon\) improves nearly with the order \(d^{-1}\).