Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves

ABSTRACT

The supernodal method for sparse Cholesky factorization represents the factor L as a set of supernodes, each consisting of a contiguous set of columns of L with identical nonzero pattern. A conventional supernode is stored as a dense submatrix. While this is suitable for sparse Cholesky factorization where the nonzero pattern of L does not change, it is not suitable for methods that modify a sparse Cholesky factorization after a low-rank change to A (an update/downdate, Ā = A ± WW^T). Supernodes merge and split apart during an update/downdate. Dynamic supernodes are introduced which allow a sparse Cholesky update/downdate to obtain performance competitive with conventional supernodal methods. A dynamic supernodal solver is shown to exceed the performance of the conventional (BLAS-based) supernodal method for solving triangular systems. These methods are incorporated into CHOLMOD, a sparse Cholesky factorization and update/downdate package which forms the basis of x = A\b MATLAB when A is sparse and symmetric positive definite.

REFERENCES

• 1: 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
• 2: Ashcraft, C. C. and Grimes, R. G. 1999. SPOOLES: An object-oriented sparse matrix library. In Proceedings of the SIAM Conference on Parallel Processing for Scientific Computing.
• 3: Christian H. Bischof , C.-T. Pan , Ping Tak Peter Tang, A Cholesky up- and downdating algorithm for systolic and SIMD architectures, SIAM Journal on Scientific Computing, v.14 n.3, p.670-676, May 1993 [doi>10.1137/0914042]
• 4: Carlson, N. A. 1973. Fast triangular factorization of the square root filter. AIIA J. 11, 1259--1265.
• 5: Yanqing Chen , Timothy A. Davis , William W. Hager , Sivasankaran Rajamanickam, Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate, ACM Transactions on Mathematical Software (TOMS), v.35 n.3, p.1-14, October 2008 [doi>10.1145/1391989.1391995]
• 6: Timothy A. Davis, Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms 2), Society for Industrial and Applied Mathematics, Philadelphia, PA, 2006
• 7: 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]
• 8: 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]
• 9: 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]
• 10: 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]
• 11: Dobrian, F., Kumfert, G. K., and Pothen, A. 2000. The design of sparse direct solvers using object oriented techniques. In Advances in Software Tools in Scientific Computing. Springer, 89--131.
• 12: Dongarra, J. J., Bunch, J. R., Moler, C., and Stewart, G. W. 1978. LINPACK Users Guide. SIAM, Philadelphia, PA.
• 13: 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]
• 14: 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]
• 15: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 16: 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]
• 17: Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comput. 28, 126, 505--535.
• 18: Goto, K. and van de Geijn, R. 2002. On reducing TLB misses in matrix multiplication. TR-2002-55, University Texas at Austin, Department of Computer Sciences.
• 19: 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]
• 20: W. W. Hager, Updating the inverse of a matrix, SIAM Review, v.31 n.2, p.221-239, June 1989 [doi>10.1137/1031049]
• 21: 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]
• 22: 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]
• 23: Joseph W. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Transactions on Mathematical Software (TOMS), v.12 n.2, p.127-148, June 1986 [doi>10.1145/6497.6499]
• 24: 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]
• 25: Joseph W. H. Liu , Esmond G. Ng , Barry W. Peyton, On finding supernodes for sparse matrix computations, SIAM Journal on Matrix Analysis and Applications, v.14 n.1, p.242-252, Jan. 1993 [doi>10.1137/0614019]
• 26: 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]
• 27: Pan, C.-T. 1990. A modification to the LINPACK downdating algorithm. BIT 30, 707--722.
• 28: 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]
• 29: 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]
• 30: Robert Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.256-276, Sept. 1982 [doi>10.1145/356004.356006]
• 31: 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]
• 32: Stewart, G. W. 1979. The effects of rounding error on an algorithm for downdating a Cholesky factorization. J. Inst. Math. Appl. 23, 203--213.
• 33: Stewart, G. W. 1998. Matrix Algorithms, Volume 1: Basic Decompositions. SIAM, Philadelphia, PA.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Cholesky factorization, linear equations, sparse matrices