A framework for symmetric band reduction

ABSTRACT

We develop an algorithmic framework for reducing the bandwidth of symmetric matrices via orthogonal similarity transformations. This framework includes the reduction of full matrices to banded or tridiagonal form and the reduction of banded matrices to narrower banded or tridiagonal form, possibly in multiple steps. Our framework leads to algorithms that require fewer floating-point operations than do standard algorithms, if only the eigenvalues are required. In addition, it allows for space-time tradeoffs and enables or increases the use of blocked transformations.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: Ch. H. Bischof , Ph. G. Lacroute, An adaptive blocking strategy for matrix factorizations, Proceedings of the joint international conference on Vector and parallel processing, p.210-221, September 1990, Zurich, Switzerland
• 4: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 5: BISCHOF, C., LANG, B., AND SUN, X. 1994. Parallel tridiagonalization through two-step band reduction. In Proceedings of the Conference on Scalable High-Performance Computing (Washington, D.C.). IEEE Press, Piscataway, NJ, 23-27.
• 6: Christian H. Bischof , Bruno Lang , Xiaobai Sun, Algorithm 807: The SBR Toolbox—software for successive band reduction, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.602-616, Dec. 2000 [doi>10.1145/365723.365736]
• 7: BOJANCZYK,A.AND BRENT, R. P. 1987. Tridiagonalization of a symmetric matrix on a square array of mesh-connected processors. J. Parallel Distrib. Comput. 8, 2-13.
• 8: DONGARRA,J.J.,HAMMARLING,S.J.,AND SORENSEN, D. C. 1989. Block reduction of matrices to condensed forms for eigenvalue computations. J. Comput. Appl. Math. 27, 215-227.
• 9: GARBOW,B.S.,BOYLE,J.M.,DONGARRA,J.J.,AND MOLER, C. B. 1977. Matrix Eigensystem Routines-EISPACK Guide Extension. Springer-Verlag, Berlin, Germany.
• 10: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 11: Roger G. Grimes , Horst D. Simon, Solution of large, dense symmetric generalized eigenvalue problems using secondary storage, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.241-256, Sept. 1988 [doi>10.1145/44128.44130]
• 12: IPSEN, I. 1984. Singular value decompositions with systolic arrays. In Proceedings of the Conference on SPIE. 13-21.
• 13: KAGSTROM, B., LING, P., AND VAN LOAN, C. 1995. GEMM-based level 3 BLAS: Installation, tuning, and use of the model implementations and the performance evaluation benchmark. Tech. Rep. S-901.87. Department of Computing Science, Univ. of Ume~, Ume~, Sweden.
• 14: Linda Kaufman, Banded Eigenvalue Solvers on Vector Machines, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.73-85, March 1984 [doi>10.1145/356068.356074]
• 15: Linda Kaufman, Band reduction algorithms revisited, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.551-567, Dec. 2000 [doi>10.1145/365723.365733]
• 16: Bruno Lang, A parallel algorithm for reducing symmetric banded matrices to tridiagonal form, SIAM Journal on Scientific Computing, v.14 n.6, p.1320-1338, Nov. 1993 [doi>10.1137/0914078]
• 17: Bruno Lang, Using Level 3 BLAS in Rotation-Based Algorithms, SIAM Journal on Scientific Computing, v.19 n.2, p.626-634, March 1998 [doi>10.1137/S1064827595280211]
• 18: LEDERMAN, S., TSAO, A., AND TURNBULL, T. 1991. A parallelizable eigensolver for real diagonalizable matrices with real eigenvalues. Tech. Rep. TR-91-042. Supercomputing Research Center, Institute for Defense Analysis, Bowie, MD.
• 19: MURATA,K.AND HORIKOSHI, K. 1975. A new method for the tridiagonalization of the symmetric band matrix. Inf. Proc. Jap. 15, 108-112.
• 20: RUTISHAUSER, H. 1963. On Jacobi rotation patterns. In Proceedings of the Symposium on Applied Mathematics: Experimental Arithmetic, High Speed Computing and Mathematics. American Mathematical Society, Boston, MA, 219-239.
• 21: SCHREIBER, R. 1990. Bidiagonalization and symmetric tridiagonalization by systolic arrays. J. VLSI Signal Process. 1, 279-285.
• 22: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 23: SCHWARZ, H. R. 1968. Tridiagonalization of a symmetric band matrix. Numer. Math. 12, 231-241.
• 24: SMITH,B.T.,BOYLE,J.M.,DONGARRA,J.J.,GARBOW,B.S.,IKEBE, Y., KLEMA,V.C.,AND MOLER, C. B. 1976. Matrix Eigensystem Routines: EISPACK Guide. 2nd ed. Springer Lecture Notes in Computer Science, vol. 6. Springer-Verlag, New York, NY.
• 25: R. C J.Dongarra, Automatically Tuned Linear Algebra Software, University of Tennessee, Knoxville, TN, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

  G. Mathematics of Computing

General Terms:
Algorithms, Performance

Keywords:
blocked Householder transformations, symmetric matrices, tridiagonalization