Using tile and oxo pivots to factorize sparse indefinite symmetric matrices
by
John Reid
JKR Associates

Tile pivots are 2 × 2 blocks having the sparsity pattern

× × × 0  or   0 × × ×

and oxo pivots are 2 × 2 blocks having the sparsity pattern

0 × × 0

They can both be very helpful in the preservation of sparsity when factorizing a symmetric matrix with zeros on its diagonal. This is because the fill-in pattern is not a full submatrix.

The code MA47 of the Harwell Subroutine Library uses such pivots in a multifrontal algorithm. It ignores the values of the entries during its analyze phase and applies interchanges for stability as necessary during its factorize phase. Unfortunately, our experience is that the final sparsity is often rather sensitive to such interchanges.

We have therefore decided to write a variant of MA47 that uses the numerical values when choosing its pivots.

In this talk, we will explain how the use of tile and oxo pivots leads to benefits, describe the design of the new code, and present some performance statistics for it.

Date received: July 27, 1999