Computing the MDMT decomposition

ABSTRACT

The MDMT factorization of an n×n symmetric indefinite matrix A can be used to solve a linear system with A as the coefficient matrix. This factorization can be computed efficiently using an algorithm given in 1977 by Bunch and Kaufman. The LAPACK project has been implementing block versions of well-known algorithms for solving dense linear systems and eigenvalue problems. The block version of the MDMT decomposition algorithm in LAPACK requires the user to specify a block size b by supplying an n×b scratch array. It then makes (n/b−2)2/2 invocations of a matrix-matrix product subroutine with one matrix no larger than b×b, n2/(2b)−b invocations of a matrix-vector product routine with a matrix no larger than b×b, and between n−n/b and 2(n−n/b) invocations of a matrix-vector product routine with matrices with less than b columns. Because the user can query LAPACK about an optimal block size, our concern is focused on users who cannot change the amount of available scratch space or who neglect to use this facility and are unaware of a performance degradation with small block sizes. This article suggests two alternative algorithms. The first is a block algorithm requiring b×b scratch space and is about 5% slower than LAPACK's current block algorithm with large b. The user does not have to specify the block size. The second algorithm is a rejuvenation of an old implementation of the MDMT decomposition algorithm that requires n matrix-vector products. The performance of the various algorithms on a specific machine is dependent on the manufacturer's implementation of the different basic linear algebra subroutines that they each invoke. Our data indicate that on the Cray Y-MP, Alliant, and Convex the time for the rejuvenated algorithm is either less than or within 10% of that of LAPACK's block algorithm with large b.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: BUNCH, J. R. AND KAUFMAN, L. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comput. 31, 135 (Jan.), 163-179.
• 3: BUNCH, J. R., KAUFMAN, L., AND PARLETT, B. 1976. Decomposition of a symmetric matrix. Numer. Math. 27, l, 95 109.
• 4: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 5: DONGARRA, ,J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G. W. 1979. LINPACK User's Guide. SIAM, Philadelphia, Pa.
• 6: Mark T. Jones , Merrell L. Patrick, Factoring Symmetric Indefinite Matrices on High-Performance Architectures, SIAM Journal on Matrix Analysis and Applications, v.15 n.1, p.273-283, Jan. 1994 [doi>10.1137/S089547989018008X]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

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

General Terms:
Algorithms, Performance

Keywords:
LAPACK, block factorization, linear systems (direct methods), symmetric indefinite