Asymptotic complexity of the collisions estimator for solving linear systems

MaRDI QIDQ1975767zbMATH OpenFDO

Authors D. L. Danilov, Sergeĭ Mikhaĭlovich Ermakov

Publication date 4 May 2000

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

asymptotic complexitycollision estimatorlinear algebraic equationsNeumann-Ulam adjoint schemestochastic algorithms

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Iterative numerical methods for linear systems (65F10) Finite difference methods for boundary value problems involving PDEs (65N06) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

• On the asymptotic optimality of the estimation by collisions in the Neuman-Ulam scheme for systems of network equations in the multidimensional Dirichlet problem
• Asymptotic complexity of Monte Carlo methods for solving linear systems
• scientific article; zbMATH DE number 1131701
• scientific article; zbMATH DE number 4140952

Cited in

(2)

• On the asymptotic optimality of the estimation by collisions in the Neuman-Ulam scheme for systems of network equations in the multidimensional Dirichlet problem
• Asymptotic complexity of Monte Carlo methods for solving linear systems

This page was built for publication: Asymptotic complexity of the collisions estimator for solving linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975767)