MC67: Refine a profile-reducing permutation of a symmetric matrix

Given the sparsity pattern of an \(n \times n\) symmetric matrix \(\mathbf{A}\) and a symmetric permutation that reduces the profile of \(\mathbf{A}\), this routine computes a new symmetric permutation with a smaller profile. The exchange algorithms of Hager are used to refine the given permutation.

Any zeros on the diagonal of \(\mathbf{A}\) are regarded as nonzero. If \(m_i\) is the column index of the first nonzero in row \(i\) (\(m _i \le i\)), the length of row \(i\) is \(i - m _i + 1\) and the profile of \(\mathbf{A}\) is the sum of the lengths of the rows.

MC61 (or MC60) may be used to obtain an initial symmetric permutation.