On threshold pivoting in the multifrontal method for sparse indefinite systems

ABSTRACT

A simple modification to the numerical pivot selection criteria in the multifrontal scheme of Duff and Reid for sparse symmetric matrix factorization is presented. For a given threshold value, the modification allows a broader choice of block 2 X 2 pivots owing to a less restrictive pivoting condition. It also extends the range of permissible threshold values from [0, 1/2) to [0, 0.6404). Moreover, the bound on element growth for stability consideration in the modified scheme is nearly the same as that of the original strategy.

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: DUFF, I. S., AND REID, J. K. MA27--A set of FORTRAN subroutines for solving sparse symmetric sets of linear equations. Tech. Rep. AERE R 10533, Harwell Laboratory, Oxfordshire, England, 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: 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]
• 6: 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. Inst. Maths. Appl. 23, (1979), 235-250.
• 7: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981

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, Measurement, Performance, Theory