Asymptotic complexity of the collisions estimator for solving linear systems (Q1975767)

The authors continue the study of the complexity of stochastic algorithms for solving sets of linear algebraic equations. An analysis of the complexity of the collisions estimator is carried out in the Neumann-Ulam adjoint scheme for solving a set of linear algebraic equations. It is shown that the considered stochastic method has not only a better asymptotic order of complexity than iterative methods, but, in some cases, is asymptotically optimal. For example, the indicated optimality property appears in sets of grid equations for certa in boundary value problems of mathematical physics.