Daniel A. Spielman
ABSTRACT
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.
- D. Achlioptas and F. McSherry. Fast computation of low rank matrix approximations. In 33rd ACM STOC, pages 611--618, 2001. Google Scholar
Digital Library
- N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k -server problem. SIAM Journal on Computing, 24(1):78--100, Feb. 1995. Google ScholarDigital Library
- A. A. Benczur and D. R. Karger. Approximating s-t minimum cuts in O(n2) time. In 28th ACM STOC, pages 47--55, 1996. Google ScholarDigital Library
- M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. submitted to SIAM J. Matrix Anal. & Appl. Google ScholarDigital Library
- E. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-weight-basis preconditioners. to appear in Numerical Linear Algebra and Applications.Google Scholar
- E. Boman and B. Hendrickson. Support theory for preconditioning. submitted to SIAM J. Matrix Anal. & Appl (Revised 10/02). Google ScholarDigital Library
- E. Boman and B. Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001.Google Scholar
- W. E. Donath and A. J. Hoffman. Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15(3):938--944, 1972.Google Scholar
- W. E. Donath and A. J. Hoffman. Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5):420--425, Sept. 1973.Google ScholarDigital Library
- A. Frieze, R. Kannan, and S. Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. In 39th IEEE FOCS, pages 370--378, 1998. Google ScholarDigital Library
- Z. Furedi and J. Komlos. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233--241, 1981.Google ScholarCross Ref
- G. H. Golub and M. Overton. The convergence of inexact Chebychev and Richardson iterative methods for solving linear systems. Numerische Mathematik, 53:571--594, 1988. Google ScholarDigital Library
- K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, CMU-CS-96-123, 1996.Google Scholar
- K. Gremban, G. Miller, and M. Zagha. Performance evaluation of a new parallel preconditioner. In 9th IPPS, pages 65--69, 1995. Google ScholarDigital Library
- B. Hendrickson and R. Leland. The Chaco user's guide, version 2. 0. Tech. Rep. SAND94-2692, Sandia National Labs, Albuquerque, NM, Oct. 1994.Google Scholar
- A. Joshi. Topics in Optimization and Sparse Linear Systems. PhD thesis, UIUC, 1997. Google ScholarDigital Library
- G. Karypis and V. Kumar. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4. 0, Sept. 1998.Google Scholar
- T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787--832, Nov. 1999. Google ScholarDigital Library
- R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16(2):346--358, Apr. 1979.Google ScholarDigital Library
- Lovasz and Simonovits. Random walks in a convex body and an improved volume algorithm. RSA: Random Structures & Algorithms, 4:359--412, 1993.Google ScholarCross Ref
- B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo. Solving symmetric diagonally-dominant systems by preconditioning. 2002.Google Scholar
- J. Reif. Efficient approximate solution of sparse linear systems. Computers and Mathematics with Applications, 36(9):37--58, 1998.Google ScholarCross Ref
- D. Spielman and S. -H. Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1. 31). In 44th Annual IEEE FOCS, pages 416--427, 2003. Most recent version available at http://arxiv. org/cs. DS/0310036. Google ScholarDigital Library
- D. A. Spielman and S. -H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. available at http://arxiv. org/abs/cs. DS/0310051, 2003.Google Scholar
- 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.Google Scholar
Index Terms
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Recommendations
Approaching Optimality for Solving SDD Linear Systems
† Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$ produces an incremental sparsifier $\hat{G}$ with $n-1 + m/k$ edges, such that the relative condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{...
Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
We present a randomized algorithm that on input a symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ nonzero entries and an $n$-vector $b$ produces an ${\tilde{x}} $ such that $\|{\tilde{x}} - A^{\dagger} {b} \|_{A} \leq \epsilon \|A^{\...
Comments