Algorithm 529: Permutations To Block Triangular Form [F1]
Iain S. Duff, John K. Reid · ACM Transactions on Mathematical Software · 1978
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]).The subroutine is evoked by the Fortran statement CALL MC13D(N,ICN,LICN,IP,LENR,IOR, IB,NUM,IW)where the parameters are described in the listing given here.The subroutine is based on Tarjan's depth first search algorithm [3], and its design is described in detail in Duff and Reid [2].They also discuss experimental results from using this subroutine which has been tested on a wide range of both structured and randomly generated matrices.This routine has been written in ANSI Fortran.Special comment cards have been included so that Harwell subroutine OE94A can be used to make an I B M Fortran version that uses half-length integers ( I N T E G E R * 2 ) for all the arrays except IP.This approximately halves the core requirements at the cost of restricting the order of the system to 2 i5 --1.