An extension of the divide-and-conquer method for a class of symmetric block-tridiagonal eigenproblems

ABSTRACT

A divide-and-conquer method for computing eigenvalues and eigenvectors of a block-tridiagonal matrix with rank-one off-diagonal blocks is presented. The implications of unbalanced merging operations due to unequal block sizes are analyzed and illustrated with numerical examples. It is shown that an unfavorable order for merging blocks in the synthesis phase of the algorithm may lead to a significant increase of the arithmetic complexity. A strategy to determine a good merging order that is at least close to optimal in all cases is given. The method has been implemented and applied to test problems from a quantum chemistry application.

REFERENCES

• 1: 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
• 2: Arbenz, P. 1992. Divide and conquer algorithms for the bandsymmetric eigenvalue problem. Parallel Comput. 18, 1105--1128.
• 3: Arbenz, P., Gander, W., and Golub, G. H. 1988. Restricted rank modification of the symmetric eigenvalue problem: Theoretical considerations. Linear Algebra Appl. 104, 75--95.
• 4: Peter Arbenz , Gene H. Golub, On the spectral decomposition of Hermitian matrices modified by low rank perturbations, SIAM Journal on Matrix Analysis and Applications, v.9 n.1, p.40-58, Jan. 1988 [doi>10.1137/0609004]
• 5: Jesse L. Barlow, Error analysis of update methods for the symmetric eigenvalue problem, SIAM Journal on Matrix Analysis and Applications, v.14 n.2, p.598-618, April 1993 [doi>10.1137/0614042]
• 6: Bunch, J. R., Nielsen, C. P., and Sorensen, D. C. 1978. Rank-one modification of the symmetric eigenproblem. Numer. Math. 31, 31--48.
• 7: Cuppen, J. J. M. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177--195.
• 8: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 9: J. J. Dongarra , D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM Journal on Scientific and Statistical Computing, v.8 n.2, p.139-154, March 1, 1987 [doi>10.1137/0908018]
• 10: Gansterer, W. N., Schneid, J., and Ueberhuber, C. W. 1999. A divide-and-conquer method for symmetric banded eigenproblems. Part II: Complexity analysis. Tech. Rep. AURORA TR1999-14, Vienna University of Technology.
• 11: Gansterer, W. N., Schneid, J., and Ueberhuber, C. W. 2001. A low-complexity divide-and-conquer method for computing eigenvalues and eigenvectors of symmetric band matrices. BIT 41, 967--976.
• 12: Gansterer, W. N., Ward, R. C., and Muller, R. P. 2000. An extension of the divide-and-conquer method for a class of symmetric block-tridiagonal eigenproblems. Tech. Rep. UT-CS-00-447, Department of Computer Science, University of Tennessee, Knoxville, TN.
• 13: Gates, K. and Arbenz, P. 1994. Parallel divide and conquer algorithms for the symmetric tridiagonal eigenproblem. Tech. Rep. 222, Institut für Wissenschaftliches Rechnen, ETH Zürich.
• 14: Golub, G. H. 1973. Some modified matrix eigenvalue problems. SIAM Rev. 15, 318--334.
• 15: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 16: Ming Gu , Stanley C. Eisenstat, A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1266-1276, Oct. 1994 [doi>10.1137/S089547989223924X]
• 17: Ming Gu , Stanley C. Eisenstat, A Divide-and-Conquer Algorithm for the Symmetric TridiagonalEigenproblem, SIAM Journal on Matrix Analysis and Applications, v.16 n.1, p.172-191, Jan. 1995 [doi>10.1137/S0895479892241287]
• 18: Ren Li, Solving secular equations stably and efficiently, University of California at Berkeley, Berkeley, CA, 1993
• 19: Pople, J. A. and Beveridge, D. L. 1970. Approximate Molecular Orbital Theory, 1st ed. McGraw-Hill Book Company, New York.
• 20: Pople, J. A., Beveridge, D. L., and Dobosh, P. A. 1967. Approximate self-consistent molecular orbital theory. V. Intermediate neglect of differential overlap. J. Chem. Physics 47, 2026.
• 21: Pople, J. A., Santry, D. P., and Segal, G. A. 1965. Approximate self-consistent molecular orbital theory. I. Invariant procedures. J. Chem. Physics 43, S129.
• 22: Pople, J. A. and Segal, G. A. 1965. Approximate self-consistent molecular orbital theory. II. Calculations with complete neglect of differential overlap. J. Chem. Physics 43, S136.
• 23: Pople, J. A. and Segal, G. A. 1966. Approximate self-consistent molecular orbital theory. III. CNDO results for ab2 and ab3 systems. J. Chem. Physics 44, 3289.
• 24: Jeffery D. Rutter, A Serial Implementation of Cuppen''s Divide and Conquer Algorithm, University of California at Berkeley, Berkeley, CA, 1991
• 25: D. C. Sorensen , Ping Tak Peter Tang, On the orthogonality of eigenvectors computed by divide-and-conquer techniques, SIAM Journal on Numerical Analysis, v.28 n.6, p.1752-1775, Dec. 1991 [doi>10.1137/0728087]
• 26: Szabo, A. and Ostlund, N. S. 1996. Modern Quantum Chemistry. Dover Publications, Mineola, NY.
• 27: Françoise Tisseur , Jack Dongarra, A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures, SIAM Journal on Scientific Computing, v.20 n.6, p.2223-2236, Nov. 1999 [doi>10.1137/S1064827598336951]

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
Block-tridiagonal matrix, divide-and-conquer method