Stochastic iterative projection methods for large linear systems

Sabelfeld Karl () and Loshchina Nadja ()
Additional contact information
Sabelfeld Karl: Institute of Computational Mathematics and Mathem. Geophysics, Russian Acad. Sci., Lavrentieva str., 6, 630090 Novosibirsk, Russia. E-mail:
Loshchina Nadja: Novosibirsk State University, Pirogova str., 2, 630090 Novosibirsk, Russia. E-mail:

Monte Carlo Methods and Applications, 2010, vol. 16, issue 3-4, 343-359

Abstract: We suggest a randomized version of the projection methods belonging to the class of a “row-action” methods which work well both for systems with quadratic nonsingular matrices and for overdetermined systems. These methods belong to a type known as Projection on Convex Sets methods. Here we present a method beyond the conventional Markov chain based Neumann–Ulam scheme. The main idea is in a random choice of blocks of rows in the projection method so that in average, the convergence is improved compared to the conventional periodic choice of the rows. We suggest an acceleration of the row projection method by using the Johnson–Lindenstrauss (J–L) theorem to find, among the randomly chosen rows, in a sense an optimal row. We extend this randomized method for solving linear systems coupled with systems of linear inequalities. Applied to finite-difference approximations of boundary value problems, the method appears to be an extremely efficient Random Walk algorithm whose convergence is exponential, and the cost does not depend on the dimension of the matrix. In addition, the algorithm calculates the solution in all grid points, and is easily parallelizable.

Keywords: Random projections; random row-action; Kaczmarz's method; random sparsification; overdetermined systems; Johnson–Lindenstrauss theorem (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma.2010.020 (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:16:y:2010:i:3-4:p:343-359:n:13

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

DOI: 10.1515/mcma.2010.020

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 ().