×

Engineering a combinatorial Laplacian solver: lessons learned. (English) Zbl 1461.68263

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 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.

MSC:

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

Citations:

Zbl 1293.68145
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jasak, H.; OpenFOAM: Open source CFD in research and industry; Int. J. Nav. Archit. Ocean Eng.: 2009; Volume 1 ,89-94.
[2] Spielman, D.A.; Teng, S.; Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems; Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC): ; ,81-90. · Zbl 1192.65048
[3] Vaidya, P.M.; ; Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners: Urbana, IL, USA 1990; .
[4] Boman, E.; Hendrickson, B.; Vavasis, S.; Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners; SIAM J. Numer. Anal.: 2008; Volume 46 ,3264-3284. · Zbl 1180.65145
[5] Christiano, P.; Kelner, J.A.; Madry, A.; Spielman, D.A.; Teng, S.H.; Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs; Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC): ; ,273-282. · Zbl 1288.94127
[6] Meyerhenke, H.; Nöllenburg, M.; Schulz, C.; Drawing Large Graphs by Multilevel Maxent-Stress Optimization; Graph Drawing and Network Visualization—23rd International Symposium, GD 2015, Revised Selected Papers: Berlin/Heidelberg, Germany 2015; Volume Volume 9411 ,30-43. · Zbl 1471.68206
[7] Spielman, D.A.; Srivastava, N.; Graph Sparsification by Effective Resistances; SIAM J. Comput.: 2011; Volume 40 ,1913-1926. · Zbl 1237.05129
[8] Kelner, J.A.; Madry, A.; Faster Generation of Random Spanning Trees; Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS): ; ,13-21. · Zbl 1292.05248
[9] Diekmann, R.; Frommer, A.; Monien, B.; Efficient schemes for nearest neighbor load balancing; Parallel Comput.: 1999; Volume 25 ,789-812. · Zbl 0930.68163
[10] Meyerhenke, H.; Schamberger, S.; A Parallel Shape Optimizing Load Balancer; Proceedings of the 12th International Euro-Par Conference (Euro-Par 2006): ; ,232-242.
[11] Grady, L.; Schwartz, E.L.; Isoperimetric graph partitioning for image segmentation; IEEE Trans. Pattern Anal. Mach. Intell.: 2006; Volume 28 ,469-475.
[12] Kelner, J.A.; Orecchia, L.; Sidford, A.; Zhu, Z.A.; A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-linear Time; Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing: ; ,911-920. · Zbl 1293.68145
[13] Reif, J.; Efficient approximate solution of sparse linear systems; Comput. Math. Appl.: 1998; Volume 36 ,37-58. · Zbl 0934.65033
[14] Spielman, D.A.; Woo, J.; A Note on Preconditioning by Low-Stretch Spanning Trees; 2009; .
[15] Koutis, I.; Levin, A.; Peng, R.; Improved spectral sparsification and numerical algorithms for SDD matrices; Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS): ; ,266-277. · Zbl 1245.68147
[16] Koutis, I.; Miller, G.L.; Peng, R.; Approaching Optimality for Solving SDD Linear Systems; SIAM J. Comput.: 2014; Volume 43 ,337-354. · Zbl 1310.68274
[17] Spielman, D.A.; Laplacian Linear Equations, Graph Sparsification, Local Clustering, Low-Stretch Trees, etc.; ; .
[18] Peng, R.; Spielman, D.A.; An Efficient Parallel Solver for SDD Linear Systems; Proceedings of the 46th Annual ACM Symposium on Theory of Computing: ; ,333-342. · Zbl 1315.65028
[19] Koutis, I.; Simple parallel and distributed algorithms for spectral graph sparsification; Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA): ; ,61-66.
[20] Alon, N.; Karp, R.M.; Peleg, D.; West, D.; A Graph-Theoretic Game and its Application to the k-Server Problem; SIAM J. Comput.: 1995; Volume 24 ,78-100. · Zbl 0818.90147
[21] Elkin, M.; Emek, Y.; Spielman, D.A.; Teng, S.H.; Lower-stretch Spanning Trees; Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC): ; ,494-503. · Zbl 1192.05028
[22] Abraham, I.; Bartal, Y.; Neiman, O.; Nearly Tight Low Stretch Spanning Trees; Proceedings of the 49th Annual Symposium on Foundations of Computer Science: ; ,781-790.
[23] Abraham, I.; Neiman, O.; Using Petal-decompositions to Build a Low Stretch Spanning Tree; Proceedings of the 44th ACM Symposium on Theory of Computing: ; ,395-406. · Zbl 1286.05028
[24] Papp, P.A.; Low-Stretch Spanning Trees; Bachelor Thesis: Budapest, Hungary 2014; .
[25] Koutis, I.; Miller, G.L.; Tolliver, D.; Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing; Comput. Vis. Image Underst.: 2011; Volume 115 ,1638-1646.
[26] Livne, O.E.; Brandt, A.; Lean algebraic multigrid (LAMG): Fast Graph Laplacian Linear Solver; SIAM J. Sci. Comput.: 2012; Volume 34 ,B499-B522. · Zbl 1253.65045
[27] Dell’Acqua, P.; Frangioni, A.; Serra-Capizzano, S.; Accelerated multigrid for graph Laplacian operators; Appl. Math. Comput.: 2015; Volume 270 ,193-215. · Zbl 1410.65099
[28] Dell’Acqua, P.; Frangioni, A.; Serra-Capizzano, S.; Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems; Calcolo: 2015; Volume 52 ,425-444. · Zbl 1329.65069
[29] Boman, E.G.; Deweese, K.; Gilbert, J.R.; Evaluating the Dual Randomized Kaczmarz Laplacian Linear Solver; Informatica: 2016; Volume 40 ,95-107.
[30] Hoske, D.; Lukarski, D.; Meyerhenke, H.; Wegner, M.; Is Nearly-Linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver; Proceedings of the 14th International Symposium on Experimental Algorithms (SEA 2015): ; ,205-218.
[31] Harel, D.; Tarjan, R.E.; Fast Algorithms for Finding Nearest Common Ancestors; SIAM J. Comput.: 1984; Volume 13 ,338-355. · Zbl 0535.68022
[32] Bender, M.A.; Farach-Colton, M.; The LCA Problem Revisited; LATIN 2000: Theoretical Informatics: Berlin/Heidelberg, Germany 2000; Volume Volume 1776 ,88-94. · Zbl 0959.68133
[33] Sleator, D.D.; Tarjan, R.E.; A data structure for dynamic trees; J. Comput. Syst. Sci.: 1983; Volume 26 ,362-391. · Zbl 0509.68058
[34] Staudt, C.L.; Sazonovs, A.; Meyerhenke, H.; NetworKit: A Tool Suite for Large-scale Complex Network Analysis; Netw. Sci.: 2016; .
[35] Hoske, D.; Lukarski, D.; Meyerhenke, H.; Wegner, M.; Implementation of KOSZ solver; ; . · Zbl 1461.68263
[36] Guennebaud, G.; Jacob, B.; Eigen v3; 2011; .
[37] Lukarski, D.; Paralution—Library for Iterative Sparse Methods; 2015; .
[38] Barabási, A.L.; Albert, R.; Emergence of Scaling in Random Networks; Science: 1999; Volume 286 ,509-512. · Zbl 1226.05223
[39] Browne, S.; Dongarra, J.; Garner, N.; Ho, G.; Mucci, P.; A Portable Programming Interface for Performance Evaluation on Modern Processors; Int. J. High Perform. Comput. Appl.: 2000; Volume 14 ,189-204.
[40] Demmel, J.W.; ; Applied Numerical Linear Algebra: Philadelphia, PA, USA 1997; . · Zbl 0879.65017
[41] Marquardt, D.; An Algorithm for Least-Squares Estimation of Nonlinear Parameters; J. Soc. Ind. Appl. Math.: 1963; Volume 11 ,431-441. · Zbl 0112.10505
[42] Saad, Y.; ; Iterative Methods for Sparse Linear Systems: Philadelphia, PA, USA 2003; . · Zbl 1031.65046
[43] Axelsson, O.; Vassilevski, P.; A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning; SIAM J. Matrix Anal. Appl.: 1991; Volume 12 ,625-644. · Zbl 0748.65028
[44] Briggs, W.L.; Henson, V.E.; McCormick, S.F.; ; A Multigrid Tutorial: Philadelphia, PA, USA 2000; . · Zbl 0958.65128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.