## Version 2.5.0

14th November 2013

Recent Changes

• Single
• Double

### HSL_MC73 Sparse symmetric matrix: compute Fiedler vector and permute to reduce the proﬁle and wavefront

Let $A$ be an $n×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 $A$ and to compute a symmetric permutation that reduces the proﬁle and wavefront of $A$ by using a multilevel algorithm. A number of proﬁle reduction algorithms are oﬀered:

(1) The multilevel Sloan algorithm,
(2) A multilevel spectral ordering algorithm, and
(3) A hybrid algorithm that reﬁnes the multilevel spectral ordering (2) using MC60.

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.