Engineering a combinatorial Laplacian solver: lessons learned

DOI10.3390/a9040072zbMath1461.68263OpenAlexW2543566970MaRDI QIDQ1736844

Dimitar Lukarski, Henning Meyerhenke, Daniel Hoske, Michael Wegner

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a9040072

zbMATH Keywords

graph algorithmsalgorithm engineeringlow-stretch spanning treeselectrical graph flowsLaplacian linear systems

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Direct numerical methods for linear systems and matrix inversion (65F05) Flows in graphs (05C21)

Related Items

Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations

Uses Software

• OpenFOAM
• Eigen
• PAPI
• LAMG
• Paralution
• NetworKit

Cites Work

• Accelerated multigrid for graph Laplacian operators
• Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems
• Efficient approximate solution of sparse linear systems
• Engineering a combinatorial Laplacian solver: lessons learned
• A data structure for dynamic trees
• Drawing Large Graphs by Multilevel Maxent-Stress Optimization
• Emergence of Scaling in Random Networks
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• Fast Algorithms for Finding Nearest Common Ancestors
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Lower-stretch spanning trees
• Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A Multigrid Tutorial, Second Edition
• Faster Generation of Random Spanning Trees
• An efficient parallel solver for SDD linear systems
• Using petal-decompositions to build a low stretch spanning tree
• Approaching Optimality for Solving SDD Linear Systems
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Efficient schemes for nearest neighbor load balancing
• Graph Sparsification by Effective Resistances
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Engineering a combinatorial Laplacian solver: lessons learned