A compact row storage scheme for Cholesky factors using elimination trees

ABSTRACT

For a given sparse symmetric positive definite matrix, a compact row-oriented storage scheme for its Cholesky factor is introduced. The scheme is based on the structure of an elimination tree defined for the given matrix. This new storage scheme has the distinct advantage of having the amount of overhead storage required for indexing always bounded by the number of nonzeros in the original matrix. The structural representation may be viewed as storing the minimal structure of the given matrix that will preserve the symbolic Cholesky factor. Experimental results on practical problems indicate that the amount of savings in overhead storage can be substantial when compared with Sherman's compressed column storage scheme.

REFERENCES

• 1: 3~o, ~. v., t-tu~t;rtur"r, o. m., ANU ULLMAN, O. t). lJata orructures arm ~tgort~nms. ~uumon- Wesley, Reading, Mass., 1983.
• 2: DUFF, I.S. Full matrix techniques in sparse Gaussian elimination. In Proceedings of the Dundee Conference on Numerical Analysis. Lecture Notes in Mathematics, 912, G. A. Watson, Ed., Springer-Verlag, New York, N.Y. 1982, pp. 71-84.
• 3: DUFF, I.S. Parallel implementation of multifrontal methods. Technical Memorandum No. 49. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 1985.
• 4: Iain Duff , Roger Grimes , John Lewis , Bill Poole, Sparse matrix test problems, ACM SIGNUM Newsletter, v.17 n.2, p.22-22, June 1982 [doi>10.1145/1057588.1057590]
• 5: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 6: EISENSTAT, S. C., SCHULTZ, M. H., AND SHERMAN, A.H. Applications of an element model for Gaussian elimination. In Sparse Matrix Computations, J. R. Bunch and D. J. Rose, Eds., Academic Press, New York, N.Y. 1976, pp. 85-96.
• 7: EISENSTAT, S. C., SCHULTZ, M. H., AND SHERMAN, A. H. Software for sparse Gaussian elimination with limited core storage. In Sparse Matrix Proceedings, I. S. Duff and G. W. Stewart, Eds., SIAM Press, Philadelphia, Pa. 1979, pp. 135-153.
• 8: EISENSTAT, S. C., SCHULTZ, M. H., AND SHERMAN, A.H. Algorithms and data structures for sparse symmetric Gaussian elimination. SIAM J. Sci. Stat. Comput., 2, (1981), 225-237.
• 9: GEORGE, J.A. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal., 10, (1973), 345-363.
• 10: GEORGE, J. A., AND LIU, Z. W.H. A note on fill for sparse matrices. SIAM J. Numer. Anal., 12, (1975), 452-454.
• 11: GEORGE, J. A., AND LIE, J. W.H. An optimal algorithm for symbolic factorization of symmetric matrices. SIAM J. Cornput. 9, (1980), 583-593.
• 12: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 13: JESS, J. A. G., AND KEES, H. G.M. A data structure for parallel L/U decomposition. IEEE Trans. Comput., C-31, (1982), 231-239.
• 14: LIU, J. W.H. On general row merging schemes for sparse Givens transformations. Tech. Rep. CS-83-04, Dept. of Computer Science, York University, Ontario, Canada, 1983. To appear in SIAM J. Sci. Stat. Comput.
• 15: L,U, J. W.H. Computational models and task scheduling for parallel sparse Cholesky factorization. Tech. Rep. CS-85-01, Dept. of Computer Science, York University, Ontario, Canada, 1985. To appear in Parallel Computing.
• 16: 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]
• 17: PARTER, S. The use of linear graphs in Gaussian elimination. SIAM Rev. 3, (1961), 119-130.
• 18: PETERS, F.J. Sparse matrices and substructures. Mathematical Centre Tracts, 119, Mathematisch Centrum, Amsterdam, The Netherlands, 1980.
• 19: ROSE, D.J. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph Theory and Computing, R. C. Read, Ed., Academic Press, New York, N.Y. 1973, 183-217.
• 20: ROSE, D. J., WHITTEN, G. F., SHERMAN, A. l'I., AND TARJAN, R.E. Algorithms and software for in-core factorization of sparse symmetri~: positive definite matrices. Comput. Struct. 11, (1980), 597-608.
• 21: 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]
• 22: Andrew Harry Sherman, On the efficient solution of sparse systems of linear and nonlinear equations., 1975
• 23: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 24: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

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.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory, Verification