On the storage requirement in the out-of-core multifrontal method for sparse factorization

ABSTRACT

Two techniques are introduced to reduce the working storage requirement for the recent multifrontal method of Duff and Reid used in the sparse out-of-core factorization of symmetric matrices. For a given core size, the reduction in working storage allows some large problems to be solved without having to use auxiliary storage for the working arrays. Even if the working arrays exceed the core size, it will reduce the amount of input-output traffic necessary to manipulate the working vectors. Experimental results are provided to demonstrate significant storage reduction on practical problems using the proposed techniques.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: 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]
• 3: DUFF, .I.S., AND REID, J.K. MA27--a set of Fortran subroutines for solving sparse symmetric sets of linear equations. AERE R-10533, Computer Science and Systems Div., AERE Harwell, Oxfordshire, 1982.
• 4: 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]
• 5: DUFF, I. S., AND REID, J.K. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Stat. Comput. 5 (1984), 633-641.
• 6: 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, 1979, 135-153.
• 7: GEORGE, J.A. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10 (1973), 345-363.
• 8: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 9: LENGAUER, T., AND TARJAN, R.E. The space complexity of pebble games on trees. Inf. Process. Lett. 10 (1980), 184-188.
• 10: Joseph W H Liu, On general row merging schemes for sparse given transformations, SIAM Journal on Scientific and Statistical Computing, v.7 n.4, p.1190-1211, Oct. 1986 [doi>10.1137/0907081]
• 11: LIu, J. W.H. An adaptive out-of-core Cholesky factorization scheme. Tech. Rep. CS-85-05, Dept. of Computer Science, York Univ., 1985. To appear in SIAM J. Sci. Star. Comput.
• 12: LIu, J. W.H. An application of generalized tree pebbling to sparse matrix factorization. Tech. Rep. CS-86-02, Dept. of Computer Science, York Univ., 1986.
• 13: LouI, M.C. The space complexity of two pebble games on trees. Tech. Rep. MIT/LCSfrM- 133, Laboratory for Computer Science, MIT, Cambridge, Mass., 1979.
• 14: REID, J. K. TREESOLVE, a Fortran package for solving large sets of linear finite element equations. CSS 155, Computer Sciences and Systems Div., AERE Harwell, Oxfordshire, 1984.

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: Algorithm design and analysis

General Terms:
Algorithms, Performance