Ordering symmetric sparse matrices for small profile and wavefront

The ordering of large sparse symmetric matrices for small profile and wavef ront or for small bandwidth is important for the efficiency of frontal and variable-band solvers. In this paper, we look at the computation of pseudop eripheral nodes and compare the effectiveness of using an algorithm based o n level-set structures with using the spectral method as the basis of the R everse Cuthill-McKee algorithm for bandwidth reduction. We also consider a number of ways of improving the performance and efficiency of Sloan's algor ithm for profile and wavefront reduction, including the use of different we ights, the use of super-variables, and implementing the priority queue as a binary heap. We also examine the use of the spectral ordering in combinati on with Sloan's algorithm. The design of software to implement the reverse Cuthill-McKee algorithm and a modified Sloan's algorithm is discussed. Exte nsive numerical experiments that justify our choice of algorithm are report ed on. Copyright (C) 1999 John Wiley & Sons, Ltd.