A new randomized vector algorithm for iterative solution of large linear systems

Standard

A new randomized vector algorithm for iterative solution of large linear systems. / Sabelfeld, Karl.

In: Applied Mathematics Letters, Vol. 126, 107830, 04.2022.

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

BibTeX

@article{2035f88a0987455b975142a41a570cdd,

title = "A new randomized vector algorithm for iterative solution of large linear systems",

abstract = "In this letter we suggest a new randomized scalable stochastic-matrix-based algorithms for calculation of large matrix iterations. Special focus is on positive or irreducible nonnegative class of matrices. As an application, a new randomized vector algorithm for iterative solution of large linear systems of algebraic equations governed by M-matrices is constructed. The idea behind these stochastic methods is in a randomized vector representation of matrix iterations. The iterations are performed by sampling random columns only, thus avoiding not only matrix but also matrix vector multiplications. As a result, the algorithm is highly efficient for solving linear equations of high dimension, its computational cost depends linearly on the dimension. Extensions of the suggested randomized iteration method to general classes of matrices are also discussed.",

keywords = "M-matrices, Pologij iterations, Random walk on boundary, Randomized matrix vector multiplication, Vector random estimator",

author = "Karl Sabelfeld",

note = "Funding Information: The work is supported by the Russian Science Foundation , Grant 19-11-0001 , in the part of stochastic simulation theory development, and Russian Fund of Basic Research , under Grant 20-51-18009 , in the part of randomized algorithms implementation. Publisher Copyright: {\textcopyright} 2021 Elsevier Ltd",

year = "2022",

month = apr,

doi = "10.1016/j.aml.2021.107830",

language = "English",

volume = "126",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - A new randomized vector algorithm for iterative solution of large linear systems

AU - Sabelfeld, Karl

N1 - Funding Information: The work is supported by the Russian Science Foundation , Grant 19-11-0001 , in the part of stochastic simulation theory development, and Russian Fund of Basic Research , under Grant 20-51-18009 , in the part of randomized algorithms implementation. Publisher Copyright: © 2021 Elsevier Ltd

PY - 2022/4

Y1 - 2022/4

N2 - In this letter we suggest a new randomized scalable stochastic-matrix-based algorithms for calculation of large matrix iterations. Special focus is on positive or irreducible nonnegative class of matrices. As an application, a new randomized vector algorithm for iterative solution of large linear systems of algebraic equations governed by M-matrices is constructed. The idea behind these stochastic methods is in a randomized vector representation of matrix iterations. The iterations are performed by sampling random columns only, thus avoiding not only matrix but also matrix vector multiplications. As a result, the algorithm is highly efficient for solving linear equations of high dimension, its computational cost depends linearly on the dimension. Extensions of the suggested randomized iteration method to general classes of matrices are also discussed.

AB - In this letter we suggest a new randomized scalable stochastic-matrix-based algorithms for calculation of large matrix iterations. Special focus is on positive or irreducible nonnegative class of matrices. As an application, a new randomized vector algorithm for iterative solution of large linear systems of algebraic equations governed by M-matrices is constructed. The idea behind these stochastic methods is in a randomized vector representation of matrix iterations. The iterations are performed by sampling random columns only, thus avoiding not only matrix but also matrix vector multiplications. As a result, the algorithm is highly efficient for solving linear equations of high dimension, its computational cost depends linearly on the dimension. Extensions of the suggested randomized iteration method to general classes of matrices are also discussed.

KW - M-matrices

KW - Pologij iterations

KW - Random walk on boundary

KW - Randomized matrix vector multiplication

KW - Vector random estimator

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

U2 - 10.1016/j.aml.2021.107830

DO - 10.1016/j.aml.2021.107830

M3 - Article

AN - SCOPUS:85120704048

VL - 126

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

M1 - 107830

ER -

ID: 34952367