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

被引：10

作者：

Sabelfeld, Karl ^{[1
,2
]}

机构：

[1] Russian Acad Sci, Inst Computat Math & Math Geophys, Lavrentiev Prosp 6, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Novosibirsk, Russia

来源：

APPLIED MATHEMATICS LETTERS | 2022年 / 126卷

基金：

俄罗斯科学基金会;

关键词：

Randomized matrix vector; multiplication; M-matrices; Vector random estimator; Random walk on boundary; Pologij iterations; MATRICES;

D O I：

10.1016/j.aml.2021.107830

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2021 Elsevier Ltd. All rights reserved.

引用

页数：9

共 16 条

[1]

[Anonymous], 1991, Monte Carlo Methods in Boundary Value Problems

[2]

Bermudez A. J., 1994, SAVMA Symposium 1994 Proceedings., P1

[3]

Ermakov S., 1982, STAT SIMULATION

[4] First passage Monte Carlo algorithms for solving coupled systems of diffusion-reaction equations [J].