Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method

Sabelfeld K. and Mozartova N.
Additional contact information
Sabelfeld K.: Institute of Computational Mathematics and Mathem. Geophysics, Russian Acad. Sci., Lavrentieva str., 6, 630090 Novosibirsk, Russia. Email: karl@osmf.sscc.ru
Mozartova N.: Novosibirsk State University, Pirogova str., 2, 630090 Novosibirsk, Russia. Email: nmozartova@mail.ru

Monte Carlo Methods and Applications, 2009, vol. 15, issue 3, 257-284

Abstract: Sparsified Randomization Monte Carlo (SRMC) algorithms for solving large systems of linear algebraic equations are presented. We construct efficient stochastic algorithms based on a probabilistic sampling of small size sub-matrices, or a randomized evaluation of a matrix-vector product and matrix iterations via a random sparsification of the matrix. This approach is beyond the standard Markov chain based Neumann–Ulam method which has no universal instrument to decrease the variance. Instead, in the new method, first, the variance can be decreased by increasing the number of the sampled columns of the matrix in play, and second, it is free of the restricted assumption of the Neumann–Ulam scheme that the Neumann series converges. We apply the developed methods to different stochastic iterative procedures. Application to boundary integral equation of the electrostatic potential theory is given where we develop a SRMC algorithm for solving the approximated system of linear algebraic equations, and compare it with the standard Random Walk on Boundary method.

Keywords: Random Sparsification; sampling with and without replacement; standard isotropic Random Walk on Boundary process; randomization of iterative methods (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1515/MCMA.2009.015 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:15:y:2009:i:3:p:257-284:n:5

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/MCMA.2009.015

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().