Let be an matrix with a symmetric sparsity pattern. HSL_MC73 has entries to compute the (approximate) Fiedler vector of the unweighted or weighted Laplacian matrix of and to compute a symmetric permutation that reduces the proﬁle and wavefront of by using a multilevel algorithm. A number of proﬁle reduction algorithms are oﬀered:
In each case, an option exists to reﬁne 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 proﬁles and wavefronts than the spectral ordering (2). For some problems, (1) yields smaller proﬁles 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 proﬁle and wavefront.
Precision: At least 8-byte arithmetic is recommended.