HSL_MC73: Sparse symmetric matrix: compute Fiedler vector and permute to reduce the profile and wavefront

Let \(\mathbf{A}\) be an \(n \times n\) matrix with a symmetric sparsity pattern. HSL_MC73 has entries to compute the (approximate) Fiedler vector of the unweighted or weighted Laplacian matrix of \(\mathbf{A}\) and to compute a symmetric permutation that reduces the profile and wavefront of \(\mathbf{A}\) by using a multilevel algorithm. A number of profile reduction algorithms are offered:

(1) The multilevel Sloan algorithm,

(2) A multilevel spectral ordering algorithm, and

(3) A hybrid algorithm that refines the multilevel spectral ordering (2) using MC60.

In each case, an option exists to refine the computed ordering using the Hager exchange algorithm (MC67).

If Hager exchanges are not employed, the orderings computed using (1) and (3) generally yield smaller profiles and wavefronts than the spectral ordering (2). For some problems, (1) yields smaller profiles and wavefronts than (3), but for others the converse is true. Algorithm (1) is faster than (3). Using Hager exchanges can substantially increase the ordering cost but can give worthwhile reductions in the profile and wavefront.

Precision: At least 8-byte arithmetic is recommended.