An out-of-core sparse Cholesky solver

ABSTRACT

Direct methods for solving large sparse linear systems of equations are popular because of their generality and robustness. Their main weakness is that the memory they require usually increases rapidly with problem size. We discuss the design and development of the first release of a new symmetric direct solver that aims to circumvent this limitation by allowing the system matrix, intermediate data, and the matrix factors to be stored externally. The code, which is written in Fortran and called HSL_MA77, implements a multifrontal algorithm. The first release is for positive-definite systems and performs a Cholesky factorization. Special attention is paid to the use of efficient dense linear algebra kernel codes that handle the full-matrix operations on the frontal matrix and to the input/output operations. The input/output operations are performed using a separate package that provides a virtual-memory system and allows the data to be spread over many files; for very large problems these may be held on more than one device.

Numerical results are presented for a collection of 30 large real-world problems, all of which were solved successfully.

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: Bjarne S. Andersen , John A. Gunnels , Fred G. Gustavson , John K. Reid , Jerzy Waśniewski, A fully portable high performance minimal storage hybrid format Cholesky algorithm, ACM Transactions on Mathematical Software (TOMS), v.31 n.2, p.201-227, June 2005 [doi>10.1145/1067967.1067969]
• 4: BCSLIB-EXT. 2003. BCSLIB-EXT—award winning sparse-matrix package. http://www.boeing.com/phantom/bcslib-ext/.
• 5: Andrew R. Conn , Nicholas I. M. Gould , Philippe L. Toint, Trust-region methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 6: Davis, T. 2007. The University of Florida Sparse Matrix Collection. Tech. rep. University of Florida, Gainesville, FL. http://www.cise.ufl.edu/~davis/techreports/matrices.pdf.
• 7: Dobrian, F. and Pothen, A. 2003. A comparison between three external memory algorithms for factorising sparse matrices. In Proceedings of the SIAM Conference on Applied Linear Algebra.
• 8: 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]
• 9: Duff, I. 1984. Design features of a frontal code for solving sparse unsymmetric linear systems out-of-core. SIAM J. Sci. Statist. Comput. 5, 270--280.
• 10: Iain S. Duff, MA57---a code for the solution of sparse symmetric definite and indefinite systems, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.118-144, June 2004 [doi>10.1145/992200.992202]
• 11: Duff, I. and Reid, J. 1982. MA27—A set of Fortran subroutines for solving sparse symmetric sets of linear equations. Report AERE R10533. Her Majesty's Stationery Office, London, U.K.
• 12: 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]
• 13: I. S. Duff , J. K. Reid, Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.227-257, June 1996 [doi>10.1145/229473.229480]
• 14: I. S. Duff , J. A. Scott, The design of a new frontal code for solving sparse, unsymmetric systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.30-45, March 1996 [doi>10.1145/225545.225550]
• 15: Nicholas I. M. Gould , Jennifer A. Scott, A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.300-325, September 2004 [doi>10.1145/1024074.1024077]
• 16: 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]
• 17: Guermouche, A. and L'Excellent, J.-Y. 2004. Optimal memory minimization algorithms for the multifrontal method. Tech. rep. RR5179. INRIA, Rocquencourt, France.
• 18: Abdou Guermouche , Jean-Yves L'excellent, Constructing memory-minimizing schedules for multifrontal methods, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.17-32, March 2006 [doi>10.1145/1132973.1132975]
• 19: HSL. 2007. A collection of Fortran codes for large-scale scientific computation. http://www.cse.scitech.ac.uk/nag/hsl/.
• 20: Irons, B. 1970. A frontal solution program for finite-element analysis. Int. J. Numer. Meth. Eng. 2, 5--32.
• 21: ISO/IEC. 2001. TR 15581(E): Information technology—programming languages—Fortran—enhanced data type facilities (second edition), M. Cohen, Tech. rep., ISO/IEC, Geneva, Switzerland.
• 22: Karypis, G. and Kumar, V. 1998. METIS—family of multilevel partitioning algorithms. http://glaros.dtc.umn.edu/gkhome/views/metis.
• 23: 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]
• 24: 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]
• 25: 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]
• 26: MUMPS. 2007. MUMPS: A multifrontal massively parallel sparse direct solver. http://mumps.enseeiht.fr/.
• 27: Reid, J. 1984. TREESOLV, a Fortran package for solving large sets of linear finite-element equations. Report CSS 155. AERE Harwell, Harwell, U.K.
• 28: John K. Reid , Jennifer A. Scott, Algorithm 891: A Fortran virtual memory system, ACM Transactions on Mathematical Software (TOMS), v.36 n.1, p.1-12, March 2009 [doi>10.1145/1486525.1486530]
• 29: Reid, J. and Scott, J. 2009b. An efficient out-of-core multifrontal solver for large-scale unsymmetric element problems. Int. J. Numer. Meth. Eng. 77, 7, 901--921.
• 30: Edward Rothberg , Robert Schreiber, Efficient Methods for Out-of-Core Sparse Cholesky Factorization, SIAM Journal on Scientific Computing, v.21 n.1, p.129-144, Aug.-Sept. 1999 [doi>10.1137/S1064827597322975]
• 31: 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]
• 32: Tinney, W. and Walker, J. 1967. Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE 55, 1801--1809.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design, Performance

Keywords:
Cholesky, multifrontal, out-of-core solver, sparse symmetric linear systems