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

research-article

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

Authors:

Jonathan A. Kelner,

Lorenzo Orecchia,

Zeyuan Allen ZhuAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 911 - 920

https://doi.org/10.1145/2488608.2488724

Published: 01 June 2013 Publication History

Abstract

In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses little of the machinery that previously appeared to be necessary for a such an algorithm. It does not require recursive preconditioning, spectral sparsification, or even the Chebyshev Method or Conjugate Gradient. After constructing a "nice" spanning tree of a graph associated with the linear system, the entire algorithm consists of the repeated application of a simple update rule, which it implements using a lightweight data structure. The algorithm is numerically stable and can be implemented without the increased bit-precision required by previous solvers. As such, the algorithm has the fastest known running time under the standard unit-cost RAM model. We hope the simplicity of the algorithm and the insights yielded by its analysis will be useful in both theory and practice.

References

[1]

I. Abraham, Y. Bartal, and O. Neiman. Nearly tight low stretch spanning trees. CoRR, abs/0808.2017, 2008.

[2]

I. Abraham and O. Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 395--406, New York, NY, USA, 2012. ACM.

Digital Library

[3]

N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the$k\$-server problem. SIAM J. Comput., 24:78--100, February 1995.

Digital Library

[4]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In In 37th Annual Symposium on Foundations of Computer Science, pages 184--193, 1996.

Digital Library

[5]

Y. Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC '98, pages 161--168, New York, NY, USA, 1998. ACM.

Digital Library

[6]

M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. SIAM Journal on Matrix Analysis and Applications, 27(4):930--951, 2006.

Digital Library

[7]

B. Bollobas. Modern Graph Theory. Springer, 1998.

[8]

E. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-weight-basis preconditioners. Numerical linear algebra with applications, 11(8--9):695--721, 2004.

[9]

E. Boman, B. Hendrickson, and S. Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. SIAM Journal on Numerical Analysis, 46(6):3264--3284, 2008.

Digital Library

[10]

E. G. Boman and B. Hendrickson. Support theory for preconditioning. SIAM J. Matrix Anal. Appl., 25:694--717, March 2003.

Digital Library

[11]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004.

Digital Library

[12]

W. L. Briggs, V. E. Henson, and S. F. McCormick. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Digital Library

[13]

P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pages 273--282, New York, NY, USA, 2011. ACM.

Digital Library

[14]

S. I. Daitch and D. A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 451--460, 2008.

Digital Library

[15]

M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng. Lower-stretch spanning trees. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC '05, pages 494--503, 2005.

Digital Library

[16]

R. Escalante and M. Raydan. Alternating Projection Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2011.

Digital Library

[17]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC '03, pages 448--455, New York, NY, USA, 2003. ACM.

Digital Library

[18]

K. D. Gremban, G. L. Miller, and M. Zagha. Performance evaluation of a new parallel preconditioner. In IPPS, pages 65--69, 1995.

Digital Library

[19]

G. T. Herman. Fundamentals of Computerized Tomography: Image Reconstruction from Projections. Springer Publishing Company, Incorporated, 2nd edition, 2009.

Digital Library

[20]

L. Hodgkinson and R. Karp. Algorithms to detect multiprotein modularity conserved during evolution. In J. Chen, J. Wang, and A. Zelikovsky, editors, Bioinformatics Research and Applications, volume 6674 of Lecture Notes in Computer Science, pages 111--122. Springer Berlin / Heidelberg, 2011.

Digital Library

[21]

C. Jordan. Sur les assemblages de lignes. J. Reine Angew Math, 70:185--190, 1869.

[22]

S. Kaczmarz. Angenaherte auflösung von systemen linearer gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, page 335--357, 1937.

[23]

J. Kelner and P. Maymounkov. Electric routing and concurrent flow cutting. Theor. Comput. Sci., 412(32):4123--4135, July 2011.

Digital Library

[24]

J. A. Kelner and A. Madry. Faster generation of random spanning trees. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS '09, pages 13--21, Washington, DC, USA, 2009. IEEE Computer Society.

Digital Library

[25]

J. A. Kelner, G. L. Miller, and R. Peng. Faster approximate multicommodity flow using quadratically coupled flows. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 1--18, New York, NY, USA, 2012. ACM.

Digital Library

[26]

J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. CoRR, abs/1301.6628, 2013.

[27]

I. Koutis, G. L. Miller, and R. Peng. Approaching optimality for solving SDD systems. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, 2010.

Digital Library

[28]

I. Koutis, G. L. Miller, and R. Peng. A nearly-m log n time solver for sdd linear systems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 590 --598, oct. 2011.

Digital Library

[29]

I. Koutis, G. L. Miller, and D. Tolliver. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Computer Vision and Image Understanding, 115(12):1638--1646, 2011.

Digital Library

[30]

J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th international conference on World Wide Web, WWW '08, pages 695--704, New York, NY, USA, 2008. ACM.

Digital Library

[31]

C.-S. Liao, K. Lu, M. Baym, R. Singh, and B. Berger. Isorankn: spectral methods for global alignment of multiple protein networks. Bioinformatics, 25(12):i253--i258, 2009.

Digital Library

[32]

F. Natterer. The mathematics of computerized tomography. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.

Digital Library

[33]

L. Orecchia, S. Sachdeva, and N. K. Vishnoi. Approximating the exponential, the lanczos method and an $\tildeO(m)$-time spectral algorithm for balanced separator. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 1141--1160, New York, NY, USA, 2012. ACM.

Digital Library

[34]

J. Sherman. Breaking the multicommodity flow barrier for O(√ log n) -approximations to sparsest cut. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science, 2009.

Digital Library

[35]

D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362--391, 1983.

Digital Library

[36]

D. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913--1926, 2011.

Digital Library

[37]

D. A. Spielman. Algorithms, graph theory, and the solution of laplacian linear equations. In Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II, ICALP'12, pages 24--26, Berlin, Heidelberg, 2012. Springer-Verlag.

Digital Library

[38]

D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 81--90, New York, NY, USA, 2004. ACM.

Digital Library

[39]

D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs/0809.3232, 2008.

[40]

D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. CoRR, abs/0808.4134, 2008.

[41]

D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/0607105v5, 2012.

[42]

T. Strohmer and R. Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15:262--278, 2009.

[43]

R. E. Tarjan. Applications of path compression on balanced trees. J. ACM, 26(4):690--715, Oct. 1979.

Digital Library

[44]

S.-H. Teng. The laplacian paradigm: Emerging algorithms for massive graphs. In TAMC, pages 2--14, 2010.

Digital Library

[45]

P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990. A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis., 1990.

[46]

N. Vishnoi. Lx=b. Monograph, available at http://research.microsoft.com/en-us/um/people/nvishno/site/Lxb-Web.pdf.

[47]

K. Voevodski, S.-H. Teng, and Y. Xia. Finding local communities in protein networks. BMC Bioinformatics, 10(1):297, 2009.

[48]

V. V. Williams. Multiplying matrices faster than coppersmith-winograd. In STOC, pages 887--898, 2012.

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
Van Den Brand JChen LKyng RLiu YMeierhans SGutenberg MSachdeva S(2024)Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00120(2010-2032)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00120
Lok JRebrova E(2024)A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitationLinear Algebra and its Applications10.1016/j.laa.2024.06.010Online publication date: Jun-2024
https://doi.org/10.1016/j.laa.2024.06.010
Show More Cited By

Index Terms

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms

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 ...
Solving SDD linear systems in nearly mlog^1/2n time
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non-zero entries to a relative error of ε in O(m log^1/2 n log^c n log(1/ε)) time. Our approach follows the recursive preconditioning framework, which aims to ...
A Nearly-m log n Time Solver for SDD Linear Systems
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$ such that $A\bar{x} = b$ for some (unknown) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

118
Total Citations
View Citations
751
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)8

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
Van Den Brand JChen LKyng RLiu YMeierhans SGutenberg MSachdeva S(2024)Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00120(2010-2032)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00120
Lok JRebrova E(2024)A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitationLinear Algebra and its Applications10.1016/j.laa.2024.06.010Online publication date: Jun-2024
https://doi.org/10.1016/j.laa.2024.06.010
Forster Sde Vos TOshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: The Laplacian Paradigm in Deterministic Congested CliqueProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594577(75-78)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594577
de Vos TOshman RNolin AHalldorsson MBalliu A(2023)Brief Announcement: Minimum Cost Maximum Flow in the CONGEST ModelProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594566(71-74)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594566
Vladu ASaha BServedio R(2023)Interior Point Methods with a Gradient OracleProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585142(1876-1889)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585142
Jambulapati ALiu YSidford ASaha BServedio R(2023)Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph SparsificationProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585136(196-206)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585136
Sachdeva SZhao YAgrawal KShun J(2023)A Simple and Efficient Parallel Laplacian SolverProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591101(315-325)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591101
van Den Brand JZhang D(2023)Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00036(493-502)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00036
Henzinger MJin BPeng RWilliamson D(2023)A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear SystemsAlgorithmica10.1007/s00453-023-01154-885:12(3680-3716)Online publication date: 1-Aug-2023
https://doi.org/10.1007/s00453-023-01154-8
Show More Cited By

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