Abstract
Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficientO(nlogn+m) time implementation of the Sloan algorithm, wheren is the number of rows (vertices), andm is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler RCM algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anonymous,Harwell Subroutine Library, A Catalogue of Subroutines (Release 12). 1995.
C. C. Ashcraft,Compressed graphs and the minimum degree algorithm, SIAM J. Sci. Comput., 16 (1995), pp. 1404–1411.
J. E. Atkins, E. G. Boman, and B. Hendrickson,A spectral algorithm for the seriation problem. Tech. Report, Sandia National Lab, Albuquerque, NM.
S. T. Barnard, A. Pothen, and H. D. Simon,A spectral algorithm for envelope reduction of sparse matrices, J. Numerical Linear Algebra with Applications, 2 (1995), pp. 317–334. A shorter version has appeared in Supercomputing '93, IEEE Computer Society Press, pp. 493–502, 1993.
E. G. Boman and B. Hendrickson,A multilevel algorithm for envelope reduction, Preprint, Sandia National Labs, Albuquerque, NM, 1996.
E. H. Cuthill and J. McKee,Reducing the bandwidth of sparse symmetric matrices, in Proceed. 24th Nat. Conf. Assoc. Comput. Mach., ACM Publications, 1969, pp. 157–172.
E. F. D'Azevedo, P. A. Forsyth, and W. P. Tang,Ordering methods for preconditioned conjugate gradients methods applied to unstructured grid problems, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 944–961.
I. Duff and G. Meurant,The effect of ordering on preconditioned conjugate gradients, BIT, 29 (1989), pp. 635–657.
I. S. Duff, A. M. Erisman, and J. K. Reid,Direct Methods for Sparse Matrices, Clarendon Press, Oxford, 1986.
I. S. Duff, R. G. Grimes, and J. G. Lewis,Users' Guide for the Harwell-Boeing Sparse Matrix Collection, 1992.
I. S. Duff, J. K. Reid, and J. A. Scott,The use of profile reduction algorithms with a frontal code, Internat. J. Numer. Meth. Engrg., 28 (1989), pp. 2555–2568.
M. Fiedler,Algebraic connectivity of graphs, Czechoslovak Math. J., 23 (1973), pp. 298–305.
M. Fiedler,A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J., 25 (1975), pp. 619–633.
A. George,Computer implementation of the finite element method, Tech. Report 208, Department of Computer Science, Stanford University, Stanford, CA, 1971.
A. George and J. W-H. Liu,The evolution of the minimum degree algorithm, SIAM Review, 31 (1989), pp. 1–19.
A. George and A. Pothen,An analysis of spectral envelope-reduction via quadratic assignment problems, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 706–732.
N. E. Gibbs,Algorithm 509: A hybrid profile reduction algorithm, ACM Trans. Math. Software, 2 (1976), pp. 378–387.
N. E. Gibbs, W. G. Poole, Jr., and P. K. Stockmeyer,An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. Num. Anal., 13 (1976), pp. 236–249.
J. R. Gilbert, G. L. Miller, and S.-H. Teng,Geometric mesh partitioning: Implementation and experiments, Tech. Report CSL-94-13, Xerox Palo Alto Research Center, CA, 1994.
D. S. Greenberg and S. C. Istrail,Physical mapping with STS hybridization: opportunities and limits, Tech. Report, Sandia National Labs, Albuquerque, NM, 1994.
R. G. Grimes, D. J. Pierce, and H. D. Simon,A new algorithm for finding a pseudoperipheral node in a graph, SIAM J. Math. Anal. Appl., 11 (1990), pp. 323–334.
S. Guattery and G. Miller,On the performance of spectral graph partitioning methods, in 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1995, ACM-SIAM, pp. 233–242.
C. Helmberg, B. Mohar, S. Poljak, and F. Rendl,A spectral approach to band-width and separator problems in graphs. Preprint, Department of Mathematics, University of Ljubljana, Lubljana, Slovenia, 1993.
B. Hendrickson and R. Leland,The Chaco User's Guide, Sandia National Laboratories, Albuquerque, NM, 1993.
B. Hendrickson and R. Leland,A multilevel algorithm for partitioning graphs, Tech. Report SAND 93-0074, Sandia National Laboratories, Albuquerque, NM, 1993.
B. Hendrickson and R. Leland,An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. Sci. Comput., 16 (1995), pp. 452–469.
M. Juvan and B. Mohar,Laplace eigenvalue and bandwidth-type invariants of graphs. Preprint, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia, 1990.
M. Juvan and B. Mohar,Optimal linear labelings and eigenvalues of graphs, Discr. Appl. Math., 36 (1992), pp. 153–168.
J. G. Lewis,Implementations of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms, ACM Trans. Math. Software, 8 (1982), pp. 180–189.
Y. Lin and J. Yuan,Minimum profile of grid networks in structure analysis. Preprint, Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China, 1993.
Y. Lin and J. Yuan,Profile minimization problem for matrices and graphs. Preprint, Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China, 1993.
J. W-H. Liu,A generalized envelope method for sparse factorization by rows, Tech. Report CS-88-09, Department of Computer Science, York University, 1988.
J. W-H. Liu and A. H. Sherman,Comparative analysis of the Cuthill-Mckee and the reverse Cuthill-Mckee ordering algorithms for sparse matrices, SIAM J. Numer. Anal., 13 (1976), pp. 198–213.
G. L. Miller, S. H. Teng, W. Thurston, and S. A. Vavasis,Automatic mesh partitioning, in Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W-H. Liu, eds., The IMA Volumes in Mathematics and its Applications, 56, Springer-Verlag, pp. 57–84.
G. H. Paulino, I. F. M. Menezes, M. Gattass, and S. Mukherjee,Node and element resequencing using the Laplacian of a finite element graph, Part I, Internat. J. Numer. Meth. Engrg., 37 (1994), pp. 1511–1530.
G. H. Paulino, I. F. M. Menezes, M. Gattass, and S. Mukherjee,Node and element resequencing using the Laplacian of a finite element graph, Part II, Internat. J. Numer. Meth. Engrg., 37 (1994), pp. 1531–1555.
A. Pothen, H. D. Simon, and K. P. Liou,Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 430–452.
A. Pothen, H. D. Simon, and L. Wang,Spectral nested dissection, Tech. Report CS-92-01, Computer Science, Pennsylvania State University, University Park, PA, 1992.
S. W. Sloan,An algorithm for profile and wavefront reduction of sparse matrices, Internat. J. Numer. Meth. Engrg., 23 (1986), pp. 239–251.
L. Wang,Spectral Nested Dissection, PhD thesis, The Pennsylvania State University, 1994.
Author information
Authors and Affiliations
Additional information
This work was partially supported by the U. S. National Science Foundation grants CCR-9412698, DMS-9505110, and ECS-9527169, by U. S. Department of Energy grant DE-FG05-94ER25216, and by the National Aeronautics and Space Administration under NASA Contract NAS1-19480 while the second author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA.
Rights and permissions
About this article
Cite this article
Kumfert, G., Pothen, A. Two improved algorithms for envelope and wavefront reduction. Bit Numer Math 37, 559–590 (1997). https://doi.org/10.1007/BF02510240
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02510240