Implementing Hager's exchange methods for matrix profile reduction

ABSTRACT

Hager recently introduced down and up exchange methods for reducing the profile of a sparse matrix with a symmetric sparsity pattern. The methods are particularly useful for refining orderings that have been obtained using a standard profile reduction algorithm, such as the Sloan method. The running times for the exchange algorithms reported by Hager suggested their cost could be prohibitive for practical applications. We examine how to implement the exchange algorithms efficiently. For a range of real test problems, it is shown that the cost of running our new implementation does not add a prohibitive overhead to the cost of the original reordering.

REFERENCES

• 1: Barnard, S., Pothen, A., and Simon, H. 1995. A spectral algorithm for envelope reduction of sparse matrices. Numer. Linear Algebra Appl. 2, 317--198.
• 2: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 3: James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
• 4: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 5: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 6: Duff, I., Reid, J., and Scott, J. 1989. The use of profile reduction algorithms with a frontal code. Int. J. Numer. Meth. Eng. 28, 2555--2568.
• 7: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 8: Norman E. Gibbs, Algorithm 509: A Hybrid Profile Reduction Algorithm [F1], ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.378-387, Dec. 1976 [doi>10.1145/355705.355713]
• 9: Hager, W. 2000. Minimizing the profile of a matrix. Department of Mathematics, University of Florida (www.math.ufl.edu/∼hager/). SIAM J. Sci. Comput. (to appear).
• 10: Y. F. Hu , J. A. Scott, A Multilevel Algorithm for Wavefront Reduction, SIAM Journal on Scientific Computing, v.23 n.4, p.1352-1375, 2001 [doi>10.1137/S1064827500377733]
• 11: Gary Kumfert , Alex Pothen, Two Improved Algorithms for Envelope and Wavefront Reduction, Institute for Computer Applications in Science and Engineering (ICASE), 1997
• 12: John G. Lewis, Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.180-189, June 1982 [doi>10.1145/355993.355998]
• 13: Paulino, G., Menezes, I., Gattass, M., and Mukherjee, S. 1994a. Node and element resequencing using the Laplacian of a finite element graph: Part I---General concepts and algorithm and numerical results. Int. J. Numer. Meth. Eng. 37, 1531--1555.
• 14: Paulino, G., Menezes, I., Gattass, M., and Mukherjee, S. 1994b. Node and element resequencing using the Laplacian of a finite element graph: Part II---Implementation and numerical results. Int. J. Numer. Meth. Eng. 37, 1531--1555.
• 15: Reid, J. and Scott, J. 1999. Ordering symmetric sparse matrices for small profile and wavefront. Int. J. Numer. Meth. Eng. 45, 1737--1755.
• 16: Sloan, S. 1986. An algorithm for profile and wavefront reduction of sparse matrices. Int. J. Numer. Meth. Eng. 23, 1315--1324.
• 17: Sloan, S. 1989. A FORTRAN program for profile and wavefront reduction. Int. J. Numer. Meth. Eng. 28, 2651--2679.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms, Performance

Keywords:
Sparse symmetric matrices, exchange method, matrix profile