Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

2025/11/20 by Farfan, Angelo, Ghadiri, Mehrdad, Yang, Junzhao
#65F10 #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2511.16570

Abstract

We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, \boldsymbolL and a nonnegative vector \boldsymbolb, computes an entrywise approximation to the solution of \boldsymbolL \boldsymbolx = \boldsymbolb in O(m n^o(1)) time with high probability, where m is the number of nonzero entries and n is the dimension of the system.

Citations

• Entrywise Approximation for Matrix Inversion and Linear Systems
• Robust and Practical Solution of Laplacian Equations by Approximate Elimination
• Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
• Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and\n Simple
• Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
• An Efficient Parallel Solver for SDD Linear Systems
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
• A Simple, Combinatorial Algorithm for Solving SDD Systems in\n Nearly-Linear Time
• Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
• A nearly-mlogn time solver for SDD linear systems
• Approaching optimality for solving SDD systems
• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Related

• A nearly-mlogn time solver for SDD linear systems
• Entrywise Approximation for Matrix Inversion and Linear Systems
• Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^1.31)
• A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix
• A Simple, Combinatorial Algorithm for Solving SDD Systems in\n Nearly-Linear Time