Stochastic Preconditioning for Diagonally Dominant Matrices

DOI10.1137/07068713XMaRDI QIDQ3630366zbMATH OpenOpenAlexFDO

Authors Haifeng Qian, Sachin S. Sapatnekar

Publication date 28 May 2009

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609672

zbMATH Keywords

random walkiterative solverincomplete factorizationlarge sparse matricesirreducibly diagonally dominantKrylov-subspace iterative solverstochastic preconditioning

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Abstract: This paper presents a new stochastic preconditioning approach. For symmetric diagonally-dominant M-matrices, we prove that an incomplete LDL factorization can be obtained from random walks, and used as a preconditioner for an iterative solver, e.g., conjugate gradient. It is argued that our factor matrices have better quality, i.e., better accuracy-size tradeoffs, than preconditioners produced by existing incomplete factorization methods. Therefore the resulting preconditioned conjugate gradient (PCG) method requires less computation than traditional PCG methods to solve a set of linear equations with the same error tolerance, and the advantage increases for larger and denser sets of linear equations. These claims are verified by numerical tests, and we provide techniques that can potentially extend the theory to more general types of matrices.

Recommendations

• Preconditioning algorithm for symmetric diagonally dominant linear systems
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Stochastic Matrices and L_p Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations
• Diagonally compensated reduction and related preconditioning methods
• Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices

Cited in

(8)

• Stochastic matrix-free equilibration
• A Kronecker product approximate preconditioner for SANs
• Additive Preconditioning for Matrix Computations
• Maximum‐weight‐basis preconditioners
• Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
• A method for constructing diagonally dominant preconditioners based on Jacobi rotations
• A Markov chain-based multi-elimination preconditioner for elliptic PDE problems
• Difference filter preconditioning for large covariance matrices

This page was built for publication: Stochastic Preconditioning for Diagonally Dominant Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3630366)