A partial pivoting strategy for sparse symmetric matrix decomposition

ABSTRACT

It is well known that the partial pivoting strategy by Bunch and Kaufman is very effective for factoring dense symmetric indefinite matrices using the diagonal pivoting method. In this paper, we study a threshold version of the strategy for sparse symmetric matrix decomposition. The use of this scheme is explored in the multifrontal method of Duff and Reid for sparse indefinite systems. Experimental results show that it is at least as effective as the existing pivoting strategy used in the current multifrontal implementation.

REFERENCES

• 1: BUNCH, J. R., AND KAUFMAN, L. Some stable methods for calculating inertia and solving symmetric linear equations. Math. Comput. 31 (1977), 163-179.
• 2: BUNCH, J. R., AND PARLETT, B.N. Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8 (1971), 639-655.
• 3: DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, 1979.
• 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: DUFF, I. S., AND REID, J. K. MA27--A set of FORTRAN subroutines for solving sparse symmetric sets of linear equations. Rep. AERE R 10533, Harwell, England, 1982.
• 6: 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]
• 7: DUFF, I. S., REID, J. K., MUNKSGAARD, N., AND NIELSON, H.B. Direct solution of sets of linear equations whose matrix is large, symmetric and indefinite. J. }nst. Math. Appl. 23 (1979), 235-250.
• 8: FLETCHER, R. Factorizing symmetric indefinite matrices. Linear Alg. Appl. 14 (1976), 257-272.
• 9: GOLUB, G., AND VAN LOAN, C. Matrix Computations. Johns Hopkins Press, Baltimore, Md., 1983.
• 10: IRONS, B.M. A frontal solution program for finite element analysis. Int. J. Numer. Meth. Eng. 2 (1970), 5-32.
• 11: LIU, J. W.H. On threshold pivoting in the multifrontal method for sparse indefinite systems. Tech. Rep. CS-86-06, Dept. of Computer Science, York Univ., 1986.

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:
diagonal pivoting, indefinite symmetric matrix, mutlifrontal method, sparse matrix, threshold partial pivoting