English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Robust and Practical Solution of Laplacian Equations by Approximate Elimination

Gao, Y., Kyng, R., & Spielman, D. A. (2023). Robust and Practical Solution of Laplacian Equations by Approximate Elimination. Retrieved from https://arxiv.org/abs/2303.00709.

Item is

Files

show Files
hide Files
:
arXiv:2303.00709.pdf (Preprint), 871KB
Name:
arXiv:2303.00709.pdf
Description:
File downloaded from arXiv at 2023-03-02 09:38
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Gao, Yuan1, Author           
Kyng, Rasmus2, Author
Spielman, Daniel A.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Mathematics, Numerical Analysis, math.NA,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Mathematical Software, cs.MS,Computer Science, Numerical Analysis, cs.NA
 Abstract: We introduce a new algorithm and software for solving linear equations in
symmetric diagonally dominant matrices with non-positive off-diagonal entries
(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate
gradient (PCG) to solve the system of linear equations. Our preconditioner is a
variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS
2016). Our factorization approach is simple: we eliminate matrix rows/columns
one at a time and update the remaining matrix using sampling to approximate the
outcome of complete Cholesky factorization. Unlike earlier approaches, our
sampling always maintains a connectivity in the remaining non-zero structure.
Our algorithm comes with a tuning parameter that upper bounds the number of
samples made per original entry. We implement our algorithm in Julia, providing
two versions, AC and AC2, that respectively use 1 and 2 samples per original
entry. We compare their single-threaded performance to that of current
state-of-the-art solvers Combinatorial Multigrid (CMG),
BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic
Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).
Our evaluation uses a broad class of problems, including all large SDDM
matrices from the SuiteSparse collection and diverse programmatically generated
instances. Our experiments suggest that our algorithm attains a level of
robustness and reliability not seen before in SDDM solvers, while retaining
good performance across all instances. Our code and data are public, and we
provide a tutorial on how to replicate our tests. We hope that others will
adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our
solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our
benchmarking data and tutorial are available at:
https://rjkyng.github.io/SDDM2023/

Details

show
hide
Language(s): eng - English
 Dates: 2023-03-012023
 Publication Status: Published online
 Pages: 51 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2303.00709
URI: https://arxiv.org/abs/2303.00709
BibTex Citekey: Yuan_2303.00709
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show