The factorization of sparse symmetric indefinite matrices.

*(English)*Zbl 0739.65018The Harwell multifrontal code MA27 is designed to solve symmetric indefinite systems of linear equations such as those that arise from least-squares and constrained optimization algorithms. The method employed in the subroutine involves a preliminary analysis phase to chose a tentative pivot sequence from the sparsity pattern alone. The strategy assumes that the matrix is definite so that all the diagonal entries are nonzero and suitable as \(1\times 1\) pivots.

For the indefinite case, this tentative pivot sequence is modified in the factorization phase to maintain stability by delaying the use of a pivot if it is too small or by replacing two pivots by a \(2\times 2\) block pivot. The penalty paid for reanalysis during factorization can be quite large, amounting to a factor of three or more in actual floating arithmetic over the predicted floating arithmetic in examples presented in this paper. Furthermore, the penalty for this strategy over one more suitale for indefinite matrices is more than a factor of a hundred in some examples in the paper.

The authors present several pivoting strategies based on \(1\times 1\) pivots and two special types of \(2\times 2\) pivots: oxo pivots and tile pivots. Tile pivot blocks are of the form \[ \left[{h\atop a}{a\atop 0}\right] \] and oxo pivot blocks are of the form \[ \left[{0\atop a}{a\atop 0}\right]. \] The strategies are compared among themselves and with the original method for a selection of matrices. The best of the new strategies show dramatic improvements over the original method.

For the indefinite case, this tentative pivot sequence is modified in the factorization phase to maintain stability by delaying the use of a pivot if it is too small or by replacing two pivots by a \(2\times 2\) block pivot. The penalty paid for reanalysis during factorization can be quite large, amounting to a factor of three or more in actual floating arithmetic over the predicted floating arithmetic in examples presented in this paper. Furthermore, the penalty for this strategy over one more suitale for indefinite matrices is more than a factor of a hundred in some examples in the paper.

The authors present several pivoting strategies based on \(1\times 1\) pivots and two special types of \(2\times 2\) pivots: oxo pivots and tile pivots. Tile pivot blocks are of the form \[ \left[{h\atop a}{a\atop 0}\right] \] and oxo pivot blocks are of the form \[ \left[{0\atop a}{a\atop 0}\right]. \] The strategies are compared among themselves and with the original method for a selection of matrices. The best of the new strategies show dramatic improvements over the original method.

Reviewer: Myron Sussman (Bethel Park)

##### MSC:

65F05 | Direct numerical methods for linear systems and matrix inversion |

65F50 | Computational methods for sparse matrices |

65F20 | Numerical solutions to overdetermined systems, pseudoinverses |

65K05 | Numerical mathematical programming methods |