Algorithm 529: Permutations To Block Triangular Form [F1]

Abstract

Given the column numbers of the nonzeros in each row of a sparse matrix, this subroutine finds a symmetric permutation that makes the matrix block lower triangular. I t can also be interpreted as accepting the row numbers of the nonzeros in each column and symmetrically permuting to block upper triangular form. If the user submits a matrix with zeros on the diagonal, subroutine MC13D might give a block triangular form which could be further reduced by unsymmetric permutations. To obtain the best results, the user is advised first to permute the matrix so that it has a zero-free diagonal. This can be done by Harwell subroutine MC21A (Duff [1]).