A generalized envelope method for sparse factorization by rows

ABSTRACT

A generalized form of the envelope method is proposed for the solution of large sparse symmetric and positive definite matrices by rows. The method is demonstated to have practical advantages over the conventional column-oriented factorization using compressed column storage or the multifrontal method using full frontal submatrices.

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: Cleve Ashcraft , Roger Grimes, The influence of relaxed supernode partitions on the multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.15 n.4, p.291-309, Dec. 1989 [doi>10.1145/76909.76910]
• 3: ASHCRAFT, C., GRIMES, R., LEWIS, J., PEYTON, B., AND SIMON, $. Progress in sparse matrix methods for large sparse linear systems on vector supercomputers Int. J. Supercomput. Appl., 1, 4 (1987), 10-30.
• 4: Randolph E. Bank , R. Kent Smith, General sparse elimination requires no permanent integer storage, SIAM Journal on Scientific and Statistical Computing, v.8 n.4, p.574-584, July 1, 1987 [doi>10.1137/0908052]
• 5: DUFF, I. S. Full matrix techniques in sparse Gaussian elimination. In Lecture Notes ~n Mathemattcs (912), G. A Watson, Ed Springer-Verlag, 1982.
• 6: 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]
• 7: DUFF, I. S., AND REID, J. K. MA27--A set of FORTRAN subroutines for solving sparse symmetric set~ of linear equations. Report AERE R 10533, Harwell, 1982.
• 8: 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]
• 9: EISENSTAT, S. C., GURSKY, M. C., SCHULTZ, M. H., AND SHERMAN, A H. The Yale Sparse Matrix Package, I. The symmetric code. Internat. J. Numer. Meth. Engrg. 18 (1982) 1145-1151.
• 10: GEORGE, J. A., HEATH, M., AND LIU, J. W. H. Parallel Cholesky factorization on a shared-memory multiprocessor. Linear Algebra and its Appl. 77 (1986) 165-187.
• 11: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 12: GILBERT, J. R., AND PEIERLS, T. Sparse partial pivoting in time proportional to arithmetic operations. SlAM J. Sci. Stat. Comput. 9 (1988) 862-874.
• 13: Kincho H. Law , Steven J. Fenives, A node-addition model for symbolic factorization, ACM Transactions on Mathematical Software (TOMS), v.12 n.1, p.37-50, March 1986 [doi>10.1145/5960.5963]
• 14: 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]
• 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: 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, 1987.
• 17: 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]
• 18: Liu, J. W.H. A generalized envelope method for sparse factorization by rows. Tech. Rep. CS-88-09, Dept. of Computer Science, York University, North York, Ontario, 1988.
• 19: MUNKSGAARD, N. New factorization codes for sparse symmetric and positive definite matrices. BIT, 19 (1979) 43-65.
• 20: PETERS, F. J. Sparse matrices and substructures. Mathematical Centre Tracts 119, Matematisch Centrum, Amsterdam, The Netherlands, 1979.
• 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

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:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
elimination tree, envelope method, factorization by rows, sparse matrices