Version 2.8.1
17th February 2023 User documentation
 Recent Changes

Code Download
 Single
 Double
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 8byte arithmetic is recommended.