Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

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.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 3: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 4: Marshall Bern , John R. Gilbert , Bruce Hendrickson , Nhat Nguyen , Sivan Toledo, Support-Graph Preconditioners, SIAM Journal on Matrix Analysis and Applications, v.27 n.4, p.930-951, 2006 [doi>10.1137/S0895479801384019]
• 5: E. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-weight-basis preconditioners. to appear in Numerical Linear Algebra and Applications.
• 6: Erik G. Boman , Bruce Hendrickson, Support Theory for Preconditioning, SIAM Journal on Matrix Analysis and Applications, v.25 n.3, p.694-717, 2003 [doi>10.1137/S0895479801390637]
• 7: E. Boman and B. Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001.
• 8: 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.
• 9: 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.
• 10: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 11: Z. Furedi and J. Komlos. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233--241, 1981.
• 12: G. H. Golub , M. L. Overton, The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems, Numerische Mathematik, v.53 n.5, p.571-593, August 1988 [doi>10.1007/BF01397553]
• 13: K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, CMU-CS-96-123, 1996.
• 14: Keith D. Gremban , Gary L. Miller , Marco Zagha, Performance evaluation of a new parallel preconditioner, Proceedings of the 9th International Symposium on Parallel Processing, p.65-69, April 25-28, 1995
• 15: B. Hendrickson and R. Leland. The Chaco user's guide, version 2. 0. Tech. Rep. SAND94-2692, Sandia National Labs, Albuquerque, NM, Oct. 1994.
• 16: Anil Joshi, Topics in optimization and sparse linear systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 17: G. Karypis and V. Kumar. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4. 0, Sept. 1998.
• 18: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 19: R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16(2):346--358, Apr. 1979.
• 20: Lovasz and Simonovits. Random walks in a convex body and an improved volume algorithm. RSA: Random Structures & Algorithms, 4:359--412, 1993.
• 21: B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo. Solving symmetric diagonally-dominant systems by preconditioning. 2002.
• 22: J. Reif. Efficient approximate solution of sparse linear systems. Computers and Mathematics with Applications, 36(9):37--58, 1998.
• 23: Daniel A. Spielman , Shang-Hua Teng, Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31), Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.416, October 11-14, 2003
• 24: 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.
• 25: 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Theory

Keywords:
graph partitioning, graph sparsification, preconditioners