Stochastic Preconditioning for Diagonally Dominant Matrices

DOI10.1137/07068713XzbMATH Open1165.65338arXivmath/0609672OpenAlexW2079431182MaRDI QIDQ3630366FDOQ3630366

Authors: Haifeng Qian, Sachin S. Sapatnekar 

Publication date: 28 May 2009

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

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.

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

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

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)

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)