Ordering symmetric sparse matrices for small profile and wavefront

The ordering of large sparse symmetric matrices for small pro"le and wavefront or for small bandwidth is important for the e$ciency of frontal and variable-band solvers. In this paper, we look at the computation of pseudoperipheral nodes and compare the e!ectiveness of using an algorithm based on level-set structures with using the spectral method as the basis of the Reverse Cuthill}McKee algorithm for bandwidth reduction. We also consider a number of ways of improving the performance and e$ciency of Sloanʹs algorithm for pro"le and wavefront reduction, including the use of di!erent weights, the use of supervariables, and implementing the priority queue as a binary heap. We also examine the use of the spectral ordering in combination with Sloanʹs algorithm. The design of software to implement the reverse Cuthill}McKee algorithm and a modi"ed Sloanʹs algorithm is discussed. Extensive numerical experiments that justify our choice of algorithm are reported on