Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate

ABSTRACT

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AA^T, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLAB^TM interfaces. It appears in MATLAB 7.2 as x = A\b when A is sparse symmetric positive definite, as well as in several other sparse matrix functions.

REFERENCES

• 1: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 2: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: Ashcraft, C. C. and Grimes, R. G. 1999. SPOOLES: an object-oriented sparse matrix library. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Philadelphia.
• 4: Ronald F. Boisvert , Roldan Pozo , Karin Remington , Richard F. Barrett , Jack J. Dongarra, Matrix market: a web resource for test matrix collections, Proceedings of the IFIP TC2/WG2.5 working conference on Quality of numerical software: assessment and enhancement, p.125-137, January 1997, Oxford, United Kingdom
• 5: Davis, T. A. 1994. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse. NA Digest, vol 92, no. 42.
• 6: Timothy A. Davis, Algorithm 849: A concise sparse Cholesky factorization package, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.587-591, December 2005 [doi>10.1145/1114268.1114277]
• 7: Timothy A. Davis, Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms 2), Society for Industrial and Applied Mathematics, Philadelphia, PA, 2006
• 8: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004 [doi>10.1145/1024074.1024079]
• 9: Timothy A. Davis , William W. Hager, Modifying a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.606-627, July 1999 [doi>10.1137/S0895479897321076]
• 10: Timothy A. Davis , William W. Hager, Multiple-Rank Modifications of a Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.997-1013, 2000 [doi>10.1137/S0895479899357346]
• 11: Timothy A. Davis , William W. Hager, Dual multilevel optimization, Mathematical Programming: Series A and B, v.112 n.2, p.403-425, November 2007 [doi>10.1007/s10107-006-0022-3]
• 12: Timothy A. Davis , William W. Hager, A sparse proximal implementation of the LP dual active set algorithm, Mathematical Programming: Series A and B, v.112 n.2, p.275-301, November 2007 [doi>10.1007/s10107-006-0017-0]
• 13: Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw., to appear.
• 14: Dobrian, F., Kumfert, G. K., and Pothen, A. 2000. The design of sparse direct solvers using object oriented techniques. In Advances in Software Tools for Scientific Computing, H. P. Langtangen, A. M. Bruaset, and E. Quak, Eds. Lecture Notes in Computational Science and Engineering, vol. 10. Springer-Verlag, Berlin, 89--131.
• 15: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 16: Jack J. Dongarra , Jeremy Croz and Sven Hammarling and Richard J. Hanson, Corrigenda: “An Extended Set of FORTRAN Basic Linear Algebra Subprograms”, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.399, Dec. 1988 [doi>10.1145/50063.356256]
• 17: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 18: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 19: Gilbert, J. R., Li, X. S., Ng, E. G., and Peyton, B. W. 2001. Computing row and column counts for sparse QR and LU factorization. BIT 41, 4, 693--710.
• 20: John R. Gilbert , Cleve Moler , Robert Schreiber, Sparse matrices in matlab: design and implementation, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.333-356, Jan. 1992 [doi>10.1137/0613024]
• 21: John R. Gilbert , Esmond G. Ng , Barry W. Peyton, An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1075-1091, Oct. 1994 [doi>10.1137/S0895479892236921]
• 22: Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comp. 28, 126, 505--535.
• 23: Gochman, S., Mendelson, A., Naveh, A., and Rotem, E. 2006. Introduction to the Intel core duo processor architecture. Intel Techn. J. 10, 2, 89--98.
• 24: Kazushige Goto , Robert Van De Geijn, High-performance implementation of the level-3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.35 n.1, p.1-14, July 2008 [doi>10.1145/1377603.1377607]
• 25: Gould, N. I. M., Hu, Y., and Scott, J. A. 2006. Complete results from a numerical evaluation of sparse direct solvers for the solution of large sparse, symmetric linear systems of equations. Tech. Rep. Internal report 2005-1 (revision 2), CCLRC, Rutherford Appleton Laboratory. (Mar.)
• 26: Nicholas I. M. Gould , Jennifer A. Scott , Yifan Hu, A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.33 n.2, p.10-es, June 2007 [doi>10.1145/1236463.1236465]
• 27: Gupta, A., Joshi, M., and Kumar, V. 2001. WSMP: A high-performance serial and parallel sparse linear solver. Tech. Rep. RC 22038 (98932), IBM T.J. Watson Research Center.
• 28: Anshul Gupta , George Karypis , Vipin Kumar, Highly Scalable Parallel Algorithms for Sparse Matrix Factorization, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.502-520, May 1997 [doi>10.1109/71.598277]
• 29: W. W. Hager, Updating the inverse of a matrix, SIAM Review, v.31 n.2, p.221-239, June 1989 [doi>10.1137/1031049]
• 30: P. Hénon , P. Ramet , J. Roman, PASTIX: a high-performance parallel direct solver for sparse symmetric positive definite systems, Parallel Computing, v.28 n.2, p.301-321, February 2002 [doi>10.1016/S0167-8191(01)00141-7]
• 31: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 32: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 33: Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
• 34: Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.134-172, January 1990 [doi>10.1137/0611010]
• 35: Moler, C. June 2007. Cleve’s corner: parallel MATLAB: multiple processors and multiple cores. MATLAB News and Notes.
• 36: Esmond G. Ng , Barry W. Peyton, Block sparse Cholesky algorithms on advanced uniprocessor computers, SIAM Journal on Scientific Computing, v.14 n.5, p.1034-1056, Sept. 1993 [doi>10.1137/0914063]
• 37: Pellegrini, F., Roman, J., and Amestoy, P. R. 2000. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurrency: Pract. Exp. 12, 68--84.
• 38: Edward Rothberg , Stanley C. Eisenstat, Node Selection Strategies for Bottom-Up Sparse Matrix Ordering, SIAM Journal on Matrix Analysis and Applications, v.19 n.3, p.682-695, July 1998 [doi>10.1137/S0895479896302692]
• 39: Edward Rothberg , Anoop Gupta, Efficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchy, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.313-334, Sept. 1991 [doi>10.1145/114697.116809]
• 40: Vladimir Rotkin , Sivan Toledo, The design and implementation of a new out-of-core sparse cholesky factorization method, ACM Transactions on Mathematical Software (TOMS), v.30 n.1, p.19-46, March 2004 [doi>10.1145/974781.974783]
• 41: Jennifer A. Scott , Yifan Hu, Experiences of sparse direct symmetric solvers, ACM Transactions on Mathematical Software (TOMS), v.33 n.3, p.18-es, August 2007 [doi>10.1145/1268769.1268772]
• 42: Stewart, G. W. 1979. The effects of rounding error on an algorithm for downdating a Cholesky factorization. J. Inst. Math. Appl. 23, 203--213.
• 43: Stewart, G. W. 1998. Matrix algorithms, Volume 1: Basic decompositions. SIAM, Philadelphia.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis

Keywords:
Cholesky factorization, linear equations, sparse matrices