The multifrontal method and paging in sparse Cholesky factorization

ABSTRACT

In this paper, we show that the multifrontal method can have significant advantage over the conventional sparse column-Cholesky scheme on a paged virtual memory system. A more than tenfold reduction in paging activities can be achieved, which saves as much as 20 percent in factorization time. We also introduce a hybrid sparse factorization method, which uses a mixture of column-Cholesky and submatrix-Cholesky operations. By switching to the use of frontal matrices from column-Cholesky operations at appropriate columns, we demonstrate that the proposed hybrid scheme has an advantage over the sparse column-Cholesky method in reducing paging activities and over the multifrontal method in its adaptability to the amount of available working storage.

REFERENCES

• 1: ASHCRAFT, C. A vector implementation of the multifrontal method for large sparse, symmetric positive definite linear systems. Tech. Rep. ETA-TR-51, Engineering Technology Applications Division, Boeing Computer Services, Seattle, Wash., 1987.
• 2: DONGARRA, J. J., GUSTAVSON, F. G., AND KARP, A. Implementing linear algebra algorithms for dense matrices on a vector pipeline machine. SIAM Rev. 26 (1984), 91-112.
• 3: DUFF, I.S. Full matrix techniques in sparse Gaussian elimination. In Lecture Notes in Mathematics 912. G. A. Watson, Ed. Springer-Verlag, New York, 1982, pp. 71-84.
• 4: DUFF, I.S. The solution of sparse linear equations on the CRAY-1. CSS 125, Computer Sciences and Systems Division, AERE Harwell, Oxfordshire, England, 1983.
• 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: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 7: 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]
• 8: EISENSTAT, S. C., GURSKY, M. C., SCHULTZ, M. H., AND SHERMAN, A.H. The Yale sparse matrix package, I. The symmetric code. Int. J. Numer. Meth. Eng. 18 (1982), 1145-1151.
• 9: GENTLEMAN, W. M., AND GEORGE, J.A. Sparse matrix software. In Sparse Matrix Computat/ons, J. R. Bunch and D. J. Rose, Eds. Academic Press, Orlando, Fla., 1976, pp. 243-261.
• 10: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 11: GEORGE, J. A., HEATH, M., AND LIU, J. W.H. Parallel Cholesky factorization on a sharedmemory multiprocessor. Linear Algebra and Its Application 77 (1986), 165-187.
• 12: 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]
• 13: Joseph W. H. Liu, Equivalent sparse matrix reordering by elimination tree rotations, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.424-444, May 1988 [doi>10.1137/0909029]
• 14: Joseph W. H. Liu, On the storage requirement in the out-of-core multifrontal method for sparse factorization, ACM Transactions on Mathematical Software (TOMS), v.12 n.3, p.249-264, Sept. 1986 [doi>10.1145/7921.11325]
• 15: 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]
• 16: Joseph W. H. Liu, A note on sparse factorization in a paging environment, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1085-1088, November 1, 1987 [doi>10.1137/0908087]
• 17: LIu, J. W.H. A collection of routines for an implementation of the multifrontal method. Tech. Rep. CS-87-10, Dept. of Computer Science, York University, North York, Ontario, Canada, 1987.
• 18: MUNKSGAARD, N. New factorization codes for sparse symmetric and positive definite matrices. BIT 19 (1979), 43-65.
• 19: REID, J. K. TREESOLVE, a Fortran package for solving large sets of linear finite element equations. CSS 155, Computer Sciences and Systems Division, AERE Harwell, Oxfordshire, England, 1984.
• 20: 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]
• 21: Andrew Harry Sherman, On the efficient solution of sparse systems of linear and nonlinear equations., 1975

INDEX TERMS

Primary 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)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

General Terms:
Algorithms, Design, Experimentation, Performance