Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

ABSTRACT

This paper presents the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector x such that Ax - A^+b ≤ ε • A^+b in O(m log^O(1) n log 1/ε) work and O(m^1/3+θ log 1/ε) depth for any fixed θ > 0.

The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in polylogarithmic depth and O(|E|) work, partitions a graph into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch O(n^α) in O(n^1+α) work and O(n^α) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(|E|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver.

By using the linear system solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, min-cost flow, and approximate max-flow.

References

1. Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly tight low stretch spanning trees. In FOCS, pages 781--790, 2008.
2. Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78--100, 1995.
3. Baruch Awerbuch. Complexity of network synchronization. J. Assoc. Comput. Mach., 32(4):804--823, 1985.
4. S. Boyd and L. Vandenberghe. Convex Optimization. Camebridge University Press, 2004.
5. V. Chvátal. The tail of the hypergeometric distribution. Discrete Mathematics, 25(3):285--287, 1979.
6. E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. In Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pages 648--658, Washington, DC, USA, 1993. IEEE Computer Society.
7. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47(1):132--166, 2000.
8. Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. CoRR, abs/0803.0988, 2008.
9. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 494--503, New York, NY, USA, 2005. ACM Press.
10. Keith Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, October 1996. Carnegie Mellon University CS Tech Report Carnegie Mellon University-CS-96-123.
11. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Press, 3rd edition, 1996.
12. Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13--30, 1963.
13. Joseph JáJá. An Introduction to Parallel Algorithms. Addison-Wesley, 1992.
14. Ioannis Koutis and Gary L. Miller. A linear work, O(n1/6) time, parallel algorithm for solving planar laplacians. In SODA, pages 1002--1011, 2007.
15. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In FOCS, pages 235--244, 2010.
16. Ioannis Koutis. Combinatorial and algebraic algorithms for optimal multilevel algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, May 2007. Carnegie Mellon University CS Tech Report Carnegie Mellon University-CS-07-131.
17. Philip N. Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25(2):205--220, 1997.
18. F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.
19. Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. In Silvio Micali, editor, Randomness and Computation, pages 47--72. JAI Press, Greenwich, Connecticut, 1989. Vol. 5.
20. James Renegar. A mathematical view of interior-point methods in convex optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.
21. Matthew Skala. Hypergeometric tail inequalities: ending the insanity, 2009.
22. Daniel A. Spielman. Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicians, 2010.
23. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In STOC, pages 563--568, 2008.
24. Daniel A. Spielman and Shang-Hua Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1.31). In FOCS, pages 416--427, 2003.
25. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/0607105, 2006.
26. Shang-Hua Teng. The Laplacian Paradigm: Emerging Algorithms for Massive Graphs. In Theory and Applications of Models of Computation, pages 2--14, 2010.
27. Y. Ye. Interior point algorithms: theory and analysis. Wiley, 1997.

Index Terms

• Theory of computation

  • Design and analysis of algorithms