Document Open Access Logo

Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers

Authors Dean Doron, François Le Gall, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.41.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Dean Doron
François Le Gall
Amnon Ta-Shma

Cite As Get BibTex

Dean Doron, François Le Gall, and Amnon Ta-Shma. Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.41

Abstract

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of  nearly linear time Laplacian solvers, approximating the solution of a linear system Lx=b, where L is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem. Surprisingly we are able to show a probabilistic, logspace algorithm solving the problem. We further extend the algorithm to other families of graphs like Eulerian graphs (and directed regular graphs) and graphs that mix in polynomial time.

Our approach is to pseudo-invert the Laplacian, by first "peeling-off" the problematic kernel of the operator, and then to approximate the inverse of the remaining part by using a Taylor series. We approximate the Taylor series using a previous work and the special structure of the problem. For directed graphs we exploit in the analysis the Jordan normal form and results from matrix functions.

Subject Classification

Keywords
  • Laplacian solvers
  • Randomized logspace
  • Bounded-space complexity classes
  • Random walks
  • Matrix computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, pages 218-223, 1979. Google Scholar
  2. Carme Alvarez and Raymond Greenlaw. A compendium of problems complete for symmetric logarithmic space. Computational Complexity, 9(2):123-145, 2000. Google Scholar
  3. Frank Bauer. Normalized graph laplacians for directed graphs. Linear Algebra and its Applications, 436(11):4193-4222, 2012. Google Scholar
  4. Adi Ben-Israel and Thomas N. E. Greville. Generalized inverses: theory and applications, volume 15. Springer, 2003. Google Scholar
  5. Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147-150, 1984. URL: http://dx.doi.org/10.1016/0020-0190(84)90018-8.
  6. Anders Björner and László Lovász. Chip-firing games on directed graphs. Journal of Algebraic Combinatorics, 1(4):305-328, 1992. Google Scholar
  7. Allan Borodin, Joachim von zur Gathen, and John E. Hopcroft. Fast parallel matrix and GCD computations. Information and Control, 52(3):241-256, 1982. URL: http://dx.doi.org/10.1016/S0019-9958(82)90766-5.
  8. Richard Bronson. Matrix Methods: an Introduction. Gulf Professional Publishing, 1991. Google Scholar
  9. William Clough Brown. A Second Course in Linear Algebra. Wiley-Interscience, 1988. Google Scholar
  10. Fan R. K. Chung. Laplacian of graphs and cheeger’s inequalities. Combinatorics, Paul Erdos is Eighty, 2(157-172):13-2, 1996. Google Scholar
  11. Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997. Google Scholar
  12. Fan R. K. Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, 9(1):1-19, 2005. Google Scholar
  13. Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science, pages 583-592, 2016. Google Scholar
  14. Laszlo Csanky. Fast parallel matrix inversion algorithms. SIAM Journal of Computing, 5(6):618-623, 1976. Google Scholar
  15. James W. Demmel. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997. Google Scholar
  16. Dean Doron, Amir Sarid, and Amnon Ta-Shma. On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Computational Complexity, pages 1-28, 2016. Google Scholar
  17. Dean Doron and Amnon Ta-Shma. On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 419-431, 2015. Google Scholar
  18. Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. arXiv preprint arXiv:1604.01384, 2016. Google Scholar
  19. Peter W. Glynn. Upper bounds on poisson tail probabilities. Operations Research Letters, 6(1):9-14, 1987. Google Scholar
  20. Chris Godsil. Eigenvalues of graphs and digraphs. Linear Algebra and its Applications, 46:43-50, 1982. Google Scholar
  21. Chris Godsil and Gordon F. Royle. Algebraic Graph Theory. Springer, 2013. Google Scholar
  22. Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, USA, 3rd edition, 1996. Google Scholar
  23. Nicholas J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  24. Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the 45th Annual Symposium on Theory of Computing, pages 911-920, 2013. URL: http://dx.doi.org/10.1145/2488608.2488724.
  25. Adam R. Klivans and Dieter Van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. Google Scholar
  26. Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19(2):161-187, 1982. Google Scholar
  27. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  28. Noam Nisan. RL⊆SC. Computational Complexity, 4(1):1-11, 1994. Google Scholar
  29. Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In Proceedings of the 46th Annual Symposium on Theory of Computing, pages 333-342, 2014. URL: http://dx.doi.org/10.1145/2591796.2591832.
  30. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4), 2008. Google Scholar
  31. Michael E. Saks and Shiyu Zhou. BP_HSPACE(S) ⊆ DSPACE(S^3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. Google Scholar
  32. Russell A. Smith. The condition numbers of the matrix eigenvalue problem. Numerische Mathematik, 10(3):232-240, 1967. Google Scholar
  33. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual Symposium on Theory of Computing, pages 81-90, 2004. URL: http://dx.doi.org/10.1145/1007352.1007372.
  34. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. URL: http://dx.doi.org/10.1137/08074489X.
  35. Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing, 42(1):1-26, 2013. URL: http://dx.doi.org/10.1137/080744888.
  36. Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35(3):835-885, 2014. URL: http://dx.doi.org/10.1137/090771430.
  37. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the 45th Annual Symposium on Theory of Computing, pages 881-890, 2013. URL: http://dx.doi.org/10.1145/2488608.2488720.
  38. Vladimir Trifonov. An O(log nlog log n) space algorithm for undirected st-connectivity. SIAM Journal on Computing, 38(2):449-483, 2008. Google Scholar
  39. Nisheeth K. Vishnoi. Lx = b - Laplacian Solvers and their Algorithmic Applications. Now publishers, 2013. Google Scholar
  40. John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences, 59(2):281-326, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact