More Web Proxy on the site http://driver.im/

research-article

A Simple and Efficient Parallel Laplacian Solver

Authors:

Sushant Sachdeva,

Yibin ZhaoAuthors Info & Claims

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 315 - 325

https://doi.org/10.1145/3558481.3591101

Published: 17 June 2023 Publication History

Abstract

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers.

In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with O(m log3 nlog log n) or O((m + n log5 n)log n log log n) work and O(log2 n log log n) depth using the ideas of block Cholesky factorization from Kyng et al. (2016). Compared to the best known parallel Laplacian solvers that achieve polylogarithmic depth due to Lee et al. (2015), our solver achieves both better depth and, for dense graphs, better work.

Supplemental Material

MP4 File

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with state-of-the-art parallel runtime for dense graphs using the ideas of block Cholesky factorization from Kyng et al. (2016). We show how to bypass the limitations of previous parallel Laplacian solvers in generating sparse Schur complement approximations using a simple random walk based sampling algorithm.

Download
62.92 MB

References

[1]

David J. Aldous. 1990. The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees. SIAM Journal on Discrete Mathematics 3, 4 (1990), 450--465. https://doi.org/10.1137/0403039 arXiv:https://doi.org/10.1137/0403039

Digital Library

[2]

Owe Axelsson. 1996. Iterative solution methods. Cambridge university press.

Digital Library

[3]

Mikhail Belkin, Irina Matveeva, and Partha Niyogi. 2004. Regularization and semi- supervised learning on large graphs. In International Conference on Computational Learning Theory. Springer, 624--638.

[4]

Guy E. Blelloch and Bruce M. Maggs. 2010. Parallel Algorithms (2 ed.). Chapman & Hall/CRC, 25.

Digital Library

[5]

Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis. 2008. Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners. SIAM J. Numerical Analysis 46, 6 (2008), 3264--3284.

Digital Library

[6]

A. Broder. 1989. Generating Random Spanning Trees. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (SFCS '89). IEEE Computer Society, USA, 442--447. https://doi.org/10.1109/SFCS.1989.63516

Digital Library

[7]

Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. 2011. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC '11). Association for Computing Machinery, New York, NY, USA, 273--282. https: //doi.org/10.1145/1993636.1993674

Digital Library

[8]

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD Linear Systems in Nearly Mlog1/2n Time. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, New York) (STOC '14). Association for Computing Machinery, New York, NY, USA, 343--352. https://doi.org/10.1145/ 2591796.2591833

Digital Library

[9]

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. 2015. Uniform Sampling for Matrix Approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Rehovot, Israel) (ITCS '15). Association for Computing Machinery, New York, NY, USA, 181--190. https://doi.org/10.1145/2688073.2688113

Digital Library

[10]

Samuel I. Daitch and Daniel A. Spielman. 2008. Faster Approximate Lossy Generalized Flow via Interior Point Algorithms. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (Victoria, British Columbia, Canada) (STOC '08). Association for Computing Machinery, New York, NY, USA, 451--460. https://doi.org/10.1145/1374376.1374441

Digital Library

[11]

David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng. 2019. Fully Dynamic Spectral Vertex Sparsifiers and Applications. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Phoenix, AZ, USA) (STOC 2019). Association for Computing Machinery, New York, NY, USA, 914--925. https://doi.org/10.1145/3313276.3316379

Digital Library

[12]

David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. 2017. Sampling Random Spanning Trees Faster than Matrix Multiplication. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Montreal, Canada) (STOC 2017). Association for Computing Machinery, New York, NY, USA, 730--742. https://doi.org/10.1145/3055399.3055499

Digital Library

[13]

David Durfee, John Peebles, Richard Peng, and Anup B. Rao. 2017. Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 926--937. https://doi.org/10.1109/FOCS.2017.90

[14]

Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. 2022. Minor Sparsifiers and the Distributed Laplacian Paradigm. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 989--999. https://doi.org/10.1109/FOCS52979.2021.00099

[15]

Yu Gao, Yang P. Liu, and Richard Peng. 2022. Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 516--527. https://doi.org/10.1109/ FOCS52979.2021.00058

[16]

Lorenz Hübschle-Schneider and Peter Sanders. 2019. Parallel Weighted Random Sampling. In 27th Annual European Symposium on Algorithms (ESA 2019), Vol. 144. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 59.

[17]

Arun Jambulapati and Aaron Sidford. 2021. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (Virtual Event, Virginia) (SODA '21). Society for Industrial and Applied Mathematics, USA, 540--559.

Digital Library

[18]

Jonathan A. Kelner and Aleksander Madry. 2009. Faster Generation of Random Spanning Trees. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 13--21. https://doi.org/10.1109/FOCS.2009.75

[19]

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. 2013. A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (Palo Alto, California, USA) (STOC '13). Association for Computing Machinery, New York, NY, USA, 911--920. https://doi.org/10.1145/2488608.2488724

Digital Library

[20]

Ioannis Koutis, Alex Levin, and Richard Peng. 2015. Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices. ACM Trans. Algorithms 12, 2, Article 17 (12 2015), 16 pages. https://doi.org/10.1145/2743021

Digital Library

[21]

Ioannis Koutis, Gary L. Miller, and Richard Peng. 2011. A Nearly-m Log n Time Solver for SDD Linear Systems. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. 590--598. https://doi.org/10.1109/FOCS.2011.85

Digital Library

[22]

Ioannis Koutis, Gary L. Miller, and Richard Peng. 2014. Approaching Optimality for Solving SDD Linear Systems. SIAM J. Comput. 43, 1 (2014), 337--354. https: //doi.org/10.1137/110845914 arXiv:https://doi.org/10.1137/110845914

Digital Library

[23]

Rasmus Kyng. 2017. Approximate gaussian elimination. Ph. D. Dissertation. PhD thesis. Yale University page.

[24]

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and Multigrid Solvers for Connection Laplacians. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (Cambridge, MA, USA) (STOC '16). Association for Computing Machinery, New York, NY, USA, 842--850. https://doi.org/10.1145/2897518.2897640

Digital Library

[25]

Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva. 2017. A Framework for Analyzing Resparsification Algorithms. 2032--2043. https://doi.org/10.1137/1.9781611974782.132 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.132

[26]

Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 573--582. https://doi.org/10.1109/ FOCS.2016.68

[27]

Yin Tat Lee, Richard Peng, and Daniel A Spielman. 2015. Sparsified cholesky solvers for SDD linear systems. arXiv preprint arXiv:1506.08204 (2015).

[28]

Yin Tat Lee and Aaron Sidford. 2014. Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 424--433. https://doi.org/10.1109/FOCS.2014.52

Digital Library

[29]

Aleksander Madry. 2013. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 253--262.

Digital Library

[30]

Aleksander Madry, Damian Straszak, and Jakub Tarnawski. 2014. Fast Generation of Random Spanning Trees and the Effective Resistance Metric. 2019--2036. https://doi.org/10.1137/1.9781611973730.134 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611973730.134

[31]

Lorenzo Orecchia and Nisheeth K Vishnoi. 2011. Towards an SDP-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 532--545.

[32]

Richard Peng and Daniel A. Spielman. 2014. An Efficient Parallel Solver for SDD Linear Systems. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, New York) (STOC '14). Association for Computing Machinery, New York, NY, USA, 333--342. https://doi.org/10.1145/ 2591796.2591832

[33]

Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.

[34]

Aaron Schild. 2018. An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles, CA, USA) (STOC 2018). Association for Computing Machinery, New York, NY, USA, 214--227. https: //doi.org/10.1145/3188745.3188852

Digital Library

[35]

Daniel A Spielman and Nikhil Srivastava. 2011. Graph sparsification by effective resistances. SIAM J. Comput. 40, 6 (2011), 1913--1926.

Digital Library

[36]

Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (Chicago, IL, USA) (STOC '04). Association for Computing Machinery, New York, NY, USA, 81--90. https://doi.org/10.1145/1007352.1007372

Digital Library

[37]

G. Strang. 1986. Introduction to Applied Mathematics. Wellesley-Cambridge Press. https://books.google.com/books?id=Lr9YKrCANWwC

[38]

Joel Tropp. 2011. Freedman's inequality for matrix martingales. Electronic Communications in Probability 16, none (2011), 262--270. https://doi.org/10. 1214/ECP.v16--1624

[39]

Joel A Tropp. 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12, 4 (2012), 389--434.

[40]

Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. 2022. Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Rome, Italy) (STOC 2022). Association for Computing Machinery, New York, NY, USA, 543--556. https://doi.org/10.1145/3519935.3520068

Digital Library

[41]

David Bruce Wilson. 1996. Generating Random Spanning Trees More Quickly than the Cover Time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (Philadelphia, Pennsylvania, USA) (STOC '96). Association for Computing Machinery, New York, NY, USA, 296--303. https: //doi.org/10.1145/237814.237880

Digital Library

[42]

Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. 2004. Learning with local and global consistency. Advances in neural information processing systems 16, 16 (2004), 321--328.

Digital Library

[43]

Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03). 912--919.

Digital Library

Cited By

Baumann YKyng RAgrawal KPetrank E(2024)A Framework for Parallelizing Approximate Gaussian EliminationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659987(195-206)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659987
Dabeer SBagchi ANarain R(2024)GPU-LSolve: An Efficient GPU-Based Laplacian Solver for Million-Scale Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00158(890-899)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00158

Index Terms

A Simple and Efficient Parallel Laplacian Solver

Recommendations

An efficient parallel solver for SDD linear systems
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse ...
Sparsified Cholesky and multigrid solvers for connection laplacians
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use ...
Efficient parallel factorization and solution of structured and unstructured linear systems

This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 2023

504 pages

ISBN:9781450395458

DOI:10.1145/3558481

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
Julian Shun
MIT, USA

Copyright © 2023 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was co-authored by an affiliate of the Crown in Right of Canada. As such, the Crown in Right of Canada retains an equal interest in the copyright. Reprint requests should be forwarded to ACM, and reprints must include clear attribution to ACM and Crown in Right of Canada.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Data Availability

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with state-of-the-art parallel runtime for dense graphs using the ideas of block Cholesky factorization from Kyng et al. (2016). We show how to bypass the limitations of previous parallel Laplacian solvers in generating sparse Schur complement approximations using a simple random walk based sampling algorithm. https://dl.acm.org/doi/10.1145/3558481.3591101#SPAA-fp191.mp4

Funding Sources

Natural Sciences and Engineering Research Council of Canada (NSERC)
Ontario Ministry of Research Innovation and Science

Conference

SPAA '23

Sponsor:

SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 17 - 19, 2023

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
81
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Baumann YKyng RAgrawal KPetrank E(2024)A Framework for Parallelizing Approximate Gaussian EliminationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659987(195-206)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659987
Dabeer SBagchi ANarain R(2024)GPU-LSolve: An Efficient GPU-Based Laplacian Solver for Million-Scale Graphs2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00158(890-899)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00158

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents