{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T17:18:10Z","timestamp":1781630290044,"version":"3.54.5"},"reference-count":44,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2016,10,31]],"date-time":"2016-10-31T00:00:00Z","timestamp":1477872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"MWK Baden-W\u00fcrttemberg","award":["Parallel Analysis of Dynamic Networks"],"award-info":[{"award-number":["Parallel Analysis of Dynamic Networks"]}]},{"DOI":"10.13039\/100004875","name":"DFG","doi-asserted-by":"publisher","award":["ME 3619\/3-1"],"award-info":[{"award-number":["ME 3619\/3-1"]}],"id":[{"id":"10.13039\/100004875","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 Kelner et al. (STOC 2013), 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\u2019s 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.<\/jats:p>","DOI":"10.3390\/a9040072","type":"journal-article","created":{"date-parts":[[2016,10,31]],"date-time":"2016-10-31T11:09:46Z","timestamp":1477912186000},"page":"72","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Engineering a Combinatorial Laplacian Solver: Lessons Learned"],"prefix":"10.3390","volume":"9","author":[{"given":"Daniel","family":"Hoske","sequence":"first","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, Germany"},{"name":"Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitar","family":"Lukarski","sequence":"additional","affiliation":[{"name":"Paralution Labs UG &amp; Co. KG, D-76571 Gaggenau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Wegner","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"ref_1","first-page":"89","article-title":"OpenFOAM: Open source CFD in research and industry","volume":"1","author":"Jasak","year":"2009","journal-title":"Int. J. Nav. Archit. Ocean Eng."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., and Teng, S. (2004, January 13\u201316). 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), Chicago, IL, USA.","DOI":"10.1145\/1007352.1007372"},{"key":"ref_3","unstructured":"Vaidya, P.M. (1990). Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners, University of Illinois at Urbana-Champaign. Technical Report."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3264","DOI":"10.1137\/040611781","article-title":"Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners","volume":"46","author":"Boman","year":"2008","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., and Teng, S.H. (2011, January 6\u20138). Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs. Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), San Jose, CA, USA.","DOI":"10.1145\/1993636.1993674"},{"key":"ref_6","first-page":"30","article-title":"Drawing Large Graphs by Multilevel Maxent-Stress Optimization","volume":"Volume 9411","author":"Meyerhenke","year":"2015","journal-title":"Graph Drawing and Network Visualization\u201423rd International Symposium, GD 2015, Revised Selected Papers"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1137\/080734029","article-title":"Graph Sparsification by Effective Resistances","volume":"40","author":"Spielman","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., and Madry, A. (,  2009). Faster Generation of Random Spanning Trees. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA, USA.","DOI":"10.1109\/FOCS.2009.75"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0167-8191(99)00018-6","article-title":"Efficient schemes for nearest neighbor load balancing","volume":"25","author":"Diekmann","year":"1999","journal-title":"Parallel Comput."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Meyerhenke, H., and Schamberger, S. (September, January 28). A Parallel Shape Optimizing Load Balancer. Proceedings of the 12th International Euro-Par Conference (Euro-Par 2006), Dresden, Germany.","DOI":"10.1007\/11823285_24"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TPAMI.2006.57","article-title":"Isoperimetric graph partitioning for image segmentation","volume":"28","author":"Grady","year":"2006","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Orecchia, L., Sidford, A., and Zhu, Z.A. (2013, January 1\u20134). A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-linear Time. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA.","DOI":"10.1145\/2488608.2488724"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0898-1221(98)00191-6","article-title":"Efficient approximate solution of sparse linear systems","volume":"36","author":"Reif","year":"1998","journal-title":"Comput. Math. Appl."},{"key":"ref_14","unstructured":"Spielman, D.A., and Woo, J. A Note on Preconditioning by Low-Stretch Spanning Trees. Available online: https:\/\/arxiv.org\/abs\/0903.2816."},{"key":"ref_15","unstructured":"Koutis, I., Levin, A., and Peng, R. (March, January 29). Improved spectral sparsification and numerical algorithms for SDD matrices. Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS), Paris, France."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1137\/110845914","article-title":"Approaching Optimality for Solving SDD Linear Systems","volume":"43","author":"Koutis","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_17","unstructured":"Spielman, D.A. Laplacian Linear Equations, Graph Sparsification, Local Clustering, Low-Stretch Trees, etc.. Available online: https:\/\/sites.google.com\/a\/yale.edu\/laplacian\/."},{"key":"ref_18","unstructured":"Peng, R., and Spielman, D.A. (June, January 31). An Efficient Parallel Solver for SDD Linear Systems. Proceedings of the 46th Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Koutis, I. (2014, January 23\u201325). Simple parallel and distributed algorithms for spectral graph sparsification. Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Prague, Czech Republic.","DOI":"10.1145\/2612669.2612676"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","article-title":"A Graph-Theoretic Game and its Application to the k-Server Problem","volume":"24","author":"Alon","year":"1995","journal-title":"SIAM J. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., and Teng, S.H. (2005, January 22\u201324). Lower-stretch Spanning Trees. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060665"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., and Neiman, O. (2008, January 26\u201328). Nearly Tight Low Stretch Spanning Trees. Proceedings of the 49th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA.","DOI":"10.1109\/FOCS.2008.62"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Abraham, I., and Neiman, O. (2012, January 20\u201322). Using Petal-decompositions to Build a Low Stretch Spanning Tree. Proceedings of the 44th ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214015"},{"key":"ref_24","unstructured":"Papp, P.A. (2014). Low-Stretch Spanning Trees. [Bachelor Thesis, E\u00f6tv\u00f6s Lor\u00e1nd University]. Available online: http:\/\/www.cs.elte.hu\/blobs\/diplomamunkak\/bsc_alkmat\/2014\/papp_pal_andras.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1638","DOI":"10.1016\/j.cviu.2011.05.013","article-title":"Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing","volume":"115","author":"Koutis","year":"2011","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"B499","DOI":"10.1137\/110843563","article-title":"Lean algebraic multigrid (LAMG): Fast Graph Laplacian Linear Solver","volume":"34","author":"Livne","year":"2012","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.amc.2015.08.033","article-title":"Accelerated multigrid for graph Laplacian operators","volume":"270","author":"Frangioni","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s10092-014-0123-y","article-title":"Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems","volume":"52","author":"Frangioni","year":"2015","journal-title":"Calcolo"},{"key":"ref_29","first-page":"95","article-title":"Evaluating the Dual Randomized Kaczmarz Laplacian Linear Solver","volume":"40","author":"Boman","year":"2016","journal-title":"Informatica"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Hoske, D., Lukarski, D., Meyerhenke, H., and Wegner, M. (July, January 29). 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), Paris, France.","DOI":"10.1007\/978-3-319-20086-6_16"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast Algorithms for Finding Nearest Common Ancestors","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_32","first-page":"88","article-title":"The LCA Problem Revisited","volume":"Volume 1776","author":"Bender","year":"2000","journal-title":"LATIN 2000: Theoretical Informatics"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A data structure for dynamic trees","volume":"26","author":"Sleator","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Staudt, C.L., Sazonovs, A., and Meyerhenke, H. (2016). NetworKit: A Tool Suite for Large-scale Complex Network Analysis. Netw. Sci., accepted.","DOI":"10.1017\/nws.2016.20"},{"key":"ref_35","unstructured":"Hoske, D., Lukarski, D., Meyerhenke, H., and Wegner, M. Implementation of KOSZ solver. code: Available online: https:\/\/algohub.iti.kit.edu\/parco\/NetworKit\/NetworKit-SDD."},{"key":"ref_36","unstructured":"Guennebaud, G., and Jacob, B. Eigen v3. Available online: http:\/\/eigen.tuxfamily.org."},{"key":"ref_37","unstructured":"Lukarski, D. Paralution\u2014Library for Iterative Sparse Methods. Available online: http:\/\/www.paralution.com."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of Scaling in Random Networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1177\/109434200001400303","article-title":"A Portable Programming Interface for Performance Evaluation on Modern Processors","volume":"14","author":"Browne","year":"2000","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Demmel, J.W. (1997). Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611971446"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0111030","article-title":"An Algorithm for Least-Squares Estimation of Nonlinear Parameters","volume":"11","author":"Marquardt","year":"1963","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Saad, Y. (2003). Iterative Methods for Sparse Linear Systems, SIAM. [2nd ed.].","DOI":"10.1137\/1.9780898718003"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0612048","article-title":"A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning","volume":"12","author":"Axelsson","year":"1991","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Briggs, W.L., Henson, V.E., and McCormick, S.F. (2000). A Multigrid Tutorial, SIAM.","DOI":"10.1137\/1.9780898719505"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/72\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:34:21Z","timestamp":1760211261000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/4\/72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,31]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["a9040072"],"URL":"https:\/\/doi.org\/10.3390\/a9040072","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,31]]}}}