Engineering a combinatorial Laplacian solver: lessons learned
type: Item
instance of: scholarly article
title: Engineering a combinatorial Laplacian solver: lessons learned
zbMATH Open document ID: 1461.68263
author: Daniel Hoske
author: Dimitar Lukarski
author: Henning Meyerhenke
author: Michael Wegner
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: Linear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a theoretical perspective, but their practical performance was unclear. Here, we address this gap. We provide the first implementation of the combinatorial solver by \textit{J. A. Kelner} et al. [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. New York, NY: Association for Computing Machinery (ACM). 911--920 (2013; Zbl 1293.68145)], which is appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix (which is SDD) corresponds to a graph; solving symmetric Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our experiments are ambivalent. While they confirm the predicted nearly-linear running time, the constant factors make the solver much slower for reasonable inputs than basic methods with higher asymptotic complexity. We were also not able to use the solver effectively as a smoother or preconditioner. Moreover, while spanning trees with lower stretch indeed reduce the solver's running time, we experience again a discrepancy in practice: in our experiments, simple spanning tree algorithms perform better than those with a guaranteed low stretch. We expect that our results provide insights for future improvements of combinatorial linear solvers.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7042381
zbMATH Keywords: Laplacian linear systems
zbMATH Keywords: graph algorithms
zbMATH Keywords: low-stretch spanning trees
zbMATH Keywords: electrical graph flows
zbMATH Keywords: algorithm engineering
describes a project that uses: OpenFOAM
describes a project that uses: LAMG
describes a project that uses: NetworKit
describes a project that uses: Eigen
describes a project that uses: Paralution
describes a project that uses: PAPI
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a9040072
OpenAlex ID: W2543566970
cites work: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
cites work: Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners
cites work: Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
cites work: Drawing Large Graphs by Multilevel Maxent-Stress Optimization
cites work: Graph Sparsification by Effective Resistances
cites work: Faster Generation of Random Spanning Trees
cites work: Efficient schemes for nearest neighbor load balancing
cites work: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
cites work: Efficient approximate solution of sparse linear systems
cites work: Improved spectral sparsification and numerical algorithms for SDD matrices
cites work: Approaching Optimality for Solving SDD Linear Systems
cites work: An efficient parallel solver for SDD linear systems
cites work: A Graph-Theoretic Game and Its Application to the k-Server Problem
cites work: Lower-stretch spanning trees
cites work: Using petal-decompositions to build a low stretch spanning tree
cites work: Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
cites work: Accelerated multigrid for graph Laplacian operators
cites work: Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Q4508365
cites work: A data structure for dynamic trees
cites work: Emergence of Scaling in Random Networks
cites work: Q4348513
cites work: An Algorithm for Least-Squares Estimation of Nonlinear Parameters
cites work: Q4414854
cites work: A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning
cites work: A Multigrid Tutorial, Second Edition
DOI: 10.3390/A9040072
Recommended article: A combinatorial cut-toggling algorithm for solving Laplacian linear systems
Recommended article: Q4737755
Recommended article: An Empirical Comparison of Graph Laplacian Solvers
Recommended article: Solver Composition Across the PDE/Linear Algebra Barrier
Recommended article: Lx = b
Recommended article: A New Approach to Laplacian Solvers and Flow Problems
Recommended article: Q2971253
Recommended article: Enriching Solutions to Combinatorial Problems via Solution Engineering
Recommended article: Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations
description: scientific article; zbMATH DE number 7042381