RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems

DOI10.1137/20M1380624zbMath1480.65003arXiv2011.07769MaRDI QIDQ5021403

George Biros, Tianyu Liang, Chao Chen

Publication date: 13 January 2022

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

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

zbMATH Keywords

sparse matrix; random sampling; graph Laplacian; incomplete Cholesky factorization; randomized numerical linear algebra; symmetric diagonally dominant matrix

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

15A23: Factorization of matrices

65Y05: Parallel numerical computation

65-04: Software, source code, etc. for problems pertaining to numerical analysis

65F08: Preconditioners for iterative methods

Uses Software

• ParMETIS
• LAMG
• ILUT
• PyAMG
• HSL_MI28
• CSparse
• GitHub
• ParILUT
• rchol
• Laplacians.jl

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of ordering on preconditioned conjugate gradients
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• Parallel Hybrid Preconditioning: Incomplete Factorization with Selective Sparse Approximate Inversion
• A Max-Plus Approach to Incomplete Cholesky Factorization Preconditioners
• ParILUT---A New Parallel Threshold ILU Factorization
• Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
• An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• An Approximate Minimum Degree Ordering Algorithm
• ILUT: A dual threshold incomplete LU factorization
• An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
• Scalable Asynchronous Domain Decomposition Solvers
• Fine-Grained Parallel Incomplete LU Factorization
• HSL_MI28
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Nested Dissection of a Regular Finite Element Mesh
• A survey of direct methods for sparse linear systems