Algorithm 849: A concise sparse Cholesky factorization package

ABSTRACT

The LDL software package is a set of short, concise routines for factorizing symmetric positive-definite sparse matrices, with some applicability to symmetric indefinite matrices. Its primary purpose is to illustrate much of the basic theory of sparse matrix algorithms in as concise a code as possible, including an elegant method of sparse symmetric factorization that computes the factorization row-by-row but stores it column-by-column. The entire symbolic and numeric factorization consists of less than 50 executable lines of code. The package is written in C, and includes a MATLAB interface.

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: Patrick R. Amestoy , Enseeiht-Irit , Timothy A. Davis , Iain S. Duff, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.381-388, September 2004 [doi>10.1145/1024074.1024081]
• 3: Alan George , Joseph W. H. Liu, The Design of a User Interface for a Sparse Matrix Package, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.139-162, June 1979 [doi>10.1145/355826.355829]
• 4: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 5: 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]
• 6: 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]
• 7: Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.
• 8: 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]
• 9: 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]
• 10: Joseph W. H. Liu, A generalized envelope method for sparse factorization by rows, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.112-129, March 1991 [doi>10.1145/103147.103159]
• 11: Esmond Ng , Barry W. Peyton, A supernodal Cholesky factorization algorithm for shared-memory multiprocessors, SIAM Journal on Scientific Computing, v.14 n.4, p.761-769, July 1993 [doi>10.1137/0914048]
• 12: 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]
• 13: Stewart, G. W. 2003. Building an old-fashioned sparse solver. Tech. rep. University of Maryland, College Park, MD. Go online to www.umd.cs.edu/~stewart.

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