Analysis of Monte Carlo accelerated iterative methods for sparse linear systems

Michele Benzi; Thomas M. Evans; Steven P. Hamilton; Massimiliano Lupo Pasini; Stuart R. Slattery

doi:10.1002/nla.2088

Analysis of Monte Carlo accelerated iterative methods for sparse linear systems

Michele Benzi, Thomas M. Evans, Steven P. Hamilton, Massimiliano Lupo Pasini, Stuart R. Slattery

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

We consider hybrid deterministic-stochastic iterative algorithms for the solution of large, sparse linear systems. Starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. We establish sufficient conditions for the convergence of the hybrid schemes, and we investigate different types of preconditioners including sparse approximate inverses. Numerical experiments on linear systems arising from the discretization of partial differential equations are presented.

Original language	English
Article number	e2088
Journal	Numerical Linear Algebra with Applications
Volume	24
Issue number	3
DOIs	https://doi.org/10.1002/nla.2088
State	Published - May 1 2017

Funding

This manuscript has been authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. We would also like to thank Miroslav Tåma for providing the AINV code used in some of the numerical experiments. This study was supported by the Department of Energy (Office of Science)ERKJ247.

Funders	Funder number
United States Government
U.S. Department of Energy
Office of Science	ERKJ247

Keywords

Monte Carlo methods
Richardson iteration
iterative methods
preconditioning
resilience
sparse approximate inverses
sparse linear systems

Access to Document

10.1002/nla.2088

Cite this

@article{6e879c184fae462db16875ac7a407d03,

title = "Analysis of Monte Carlo accelerated iterative methods for sparse linear systems",

abstract = "We consider hybrid deterministic-stochastic iterative algorithms for the solution of large, sparse linear systems. Starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. We establish sufficient conditions for the convergence of the hybrid schemes, and we investigate different types of preconditioners including sparse approximate inverses. Numerical experiments on linear systems arising from the discretization of partial differential equations are presented.",

keywords = "Monte Carlo methods, Richardson iteration, iterative methods, preconditioning, resilience, sparse approximate inverses, sparse linear systems",

author = "Michele Benzi and Evans, {Thomas M.} and Hamilton, {Steven P.} and Massimiliano Lupo Pasini and Slattery, {Stuart R.}",

note = "Publisher Copyright: Copyright {\textcopyright} 2017 John Wiley & Sons, Ltd.",

year = "2017",

month = may,

day = "1",

doi = "10.1002/nla.2088",

language = "English",

volume = "24",

journal = "Numerical Linear Algebra with Applications",

issn = "1070-5325",

publisher = "wiley",

number = "3",

}

TY - JOUR

T1 - Analysis of Monte Carlo accelerated iterative methods for sparse linear systems

AU - Benzi, Michele

AU - Evans, Thomas M.

AU - Hamilton, Steven P.

AU - Lupo Pasini, Massimiliano

AU - Slattery, Stuart R.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - We consider hybrid deterministic-stochastic iterative algorithms for the solution of large, sparse linear systems. Starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. We establish sufficient conditions for the convergence of the hybrid schemes, and we investigate different types of preconditioners including sparse approximate inverses. Numerical experiments on linear systems arising from the discretization of partial differential equations are presented.

AB - We consider hybrid deterministic-stochastic iterative algorithms for the solution of large, sparse linear systems. Starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. We establish sufficient conditions for the convergence of the hybrid schemes, and we investigate different types of preconditioners including sparse approximate inverses. Numerical experiments on linear systems arising from the discretization of partial differential equations are presented.

KW - Monte Carlo methods

KW - Richardson iteration

KW - iterative methods

KW - preconditioning

KW - resilience

KW - sparse approximate inverses

KW - sparse linear systems

UR - http://www.scopus.com/inward/record.url?scp=85014488371&partnerID=8YFLogxK

U2 - 10.1002/nla.2088

DO - 10.1002/nla.2088

M3 - Article

AN - SCOPUS:85014488371

SN - 1070-5325

VL - 24

JO - Numerical Linear Algebra with Applications

JF - Numerical Linear Algebra with Applications

IS - 3

M1 - e2088

ER -

Analysis of Monte Carlo accelerated iterative methods for sparse linear systems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this