Ordering symmetric sparse matrices for small profile and wavefront. (English) Zbl 0959.65059
Summary: The ordering of large sparse symmetric matrices for small profile and wavefront or for small bandwidth is important for the efficiency of frontal and variable-band solvers. In this paper, we look at the computation of pseudoperipheral nodes and compare the effectiveness 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 efficiency of S. W. Sloan’s algorithm [ibid. 23, 239-251 (1986; Zbl 0601.65027)] for profile and wavefront reduction, including the use of different 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 modified Sloan’s algorithm is discussed. Extensive numerical experiments that justify our choice of algorithm are reported.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65F50 | Computational methods for sparse matrices |
Keywords:
symmetric pattern; profile reduction; Sloan algorithm; reverse Cuthill-McKee algorithm; spectral method; ordering; large sparse symmetric matrices; bandwidth reduction; performance; numerical experimentsCitations:
Zbl 0601.65027Software:
HSLReferences:
| [1] | Paulino, Communications in Numerical Methods in Engineering 10 pp 913– (1994) |
| [2] | Sloan, International Journal for Numerical Methods in Engineering 23 pp 239– (1986) |
| [3] | Sloan, International Journal for Numerical Methods in Engineering 28 pp 2651– (1989) |
| [4] | Duff, International Journal for Numerical Methods in Engineering 28 pp 2555– (1989) |
| [5] | Kumfert, BIT 18 pp 559– (1997) |
| [6] | Barnard, Numerical Linear Algebra with Applications 2 pp 317– (1995) |
| [7] | Gibbs, SIAM Journal for Numerical Analysis 13 pp 236– (1976) |
| [8] | Everstine, International Journal for Numerical Methods in Engineering 14 pp 837– (1979) |
| [9] | Direct Methods for Sparse Matrices. Oxford University Press: London, 1986. · Zbl 0604.65011 |
| [10] | Duff, ACM Transactions on Mathematical Software 22 pp 30– (1996) |
| [11] | Gibbs, ACM Transactions on Mathematical Software 2 pp 378– (1976) |
| [12] | Sloan, International Journal for Numerical Methods in Engineering 19 pp 1153– (1983) |
| [13] | George, ACM Transactions on Mathematical Software 5 pp 284– (1979) |
| [14] | Lewis, ACM Transactions on Mathematical Software 8 pp 180– (1982) |
| [15] | Reducing the bandwidth of sparse symmetric matrices. Proceedings 24th National Conference of the Association for Computing Machinery, Brandon Press: NJ, 1969; 157-172. |
| [16] | Computer implementation of the finite-element method. Report STAN CS-71-208, Ph.D. Thesis, Department of Computer Science, Stanford University, Stanford, CA, 1971. |
| [17] | Paulino, International Journal for Numerical Methods in Engineering 37 pp 1511– (1994) |
| [18] | The Chaco user’s guide: Version 2.0, Technical Report SAND94-2692, Sandia National Laboratories, Albuquerque, NM, 1995. |
| [19] | Armstrong, International Journal for Numerical Methods in Engineering 21 pp 1785– (1985) |
| [20] | HSL. Harwell Subroutine Library Catalogue (Release 12). AEA Technology: Harwell, 1995. |
| [21] | Duff, ACM Transactions on Mathematical Software 22 pp 227– (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
