The Design and Use of Algorithms for Permuting Large Entries to the
Diagonal of Sparse Matrices

Iain S. Duff and Jacko Koster
Department of Computation and Information
Atlas Centre
Rutherford Appleton Laboratory
Oxon OX11 0QX


We consider techniques for permuting a sparse matrix so that the diagonal of thepermuted matrix has entries of large absolute value. We discuss various criteria for this and consider their implementation as computer codes. We then indicate several cases where such a permutation can be useful. These include the solution of sparse equations by a direct method and by an iterative technique. We also consider its use in generating a preconditioner for an iterative method. We see that the effect of these reorderings can be dramatic although the best {\it a priori} strategy is by no means clear.

Contributed March 8, 1998.