MC62: Generate a row ordering for a row-by-row frontal solver

Given an \(n \times n\) matrix \(\mathbf{A} = a _{ij}\) with an unsymmetric sparsity pattern, this subroutine generates a row ordering for a row-by-row frontal solver (for example, the HSL packages MA42 and MA43).

MC62 generates a row ordering that is designed to reduce the maximum and mean row and column frontsizes, the maximum and mean frontal matrix size, and the sum of the lifetimes, which in turn reduce storage requirements and operation counts for the frontal solver. Only the pattern of the matrix is used. MC62 is not recommended if \(\mathbf{A}\) has one or more rows that are full or have a large number of nonzeros.

MC62 offers the option of generating the row graph of an \(m \times n\) matrix \(\mathbf{A}\). The nodes of the row graph are the rows of \(\mathbf{A}\) and two rows \(i\) and \(j\) (\(i \ne j\)) are defined to be adjacent if and only if there is at least one column \(k\) of \(\mathbf{A}\) for which \(a _{ik}.a_{jk} \ne 0\).