Block tridiagonalization of "effectively" sparse symmetric matrices

ABSTRACT

A block tridiagonalization algorithm is proposed for transforming a sparse (or "effectively" sparse) symmetric matrix into a related block tridiagonal matrix, such that the eigenvalue error remains bounded by some prescribed accuracy tolerance. It is based on a heuristic for imposing a block tridiagonal structure on matrices with a large percentage of zero or "effectively zero" (with respect to the given accuracy tolerance) elements. In the light of a recently developed block tridiagonal divide-and-conquer eigensolver [Gansterer, Ward, Muller, and Goddard, III, SIAM J. Sci. Comput. 25 (2003), pp. 65--85], for which block tridiagonalization may be needed as a preprocessing step, the algorithm also provides an option for attempting to produce at least a few very small diagonal blocks in the block tridiagonal matrix. This leads to low time complexity of the last merging operation in the block divide-and-conquer method. Numerical experiments are presented and various block tridiagonalization strategies are compared.

REFERENCES

• 1: H. L. Crane, Jr. , Norman E. Gibbs , William G. Poole, Jr. , Paul K. Stockmeyer, Algorithm 508: Matrix Bandwidth and Profile Reduction [F1], ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.375-377, Dec. 1976 [doi>10.1145/355705.355712]
• 2: Cuppen, J. J. M. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177--195.
• 3: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 4: Wilfried N. Gansterer , Dieter F. Kvasnicka , Christoph W. Ueberhuber, Multi-sweep Algorithms for the Symmetric Eigenproblem, Selected Papers and Invited Talks from the Third International Conference on Vector and Parallel Processing, p.20-28, June 21-23, 1998
• 5: Wilfried N. Gansterer , Robert C. Ward , Richard P. Muller, An extension of the divide-and-conquer method for a class of symmetric block-tridiagonal eigenproblems, ACM Transactions on Mathematical Software (TOMS), v.28 n.1, p.45-58, March 2002 [doi>10.1145/513001.513004]
• 6: Wilfried N. Gansterer , Robert C. Ward , Richard P. Muller , William A. Goddard, III, Computing Approximate Eigenpairs of Symmetric Block Tridiagonal Matrices, SIAM Journal on Scientific Computing, v.25 n.1, p.65-85, 2003 [doi>10.1137/S1064827501399432]
• 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: Gibbs, N. E., Poole, W. G., JR., and Stockmeyer, P. K. 1976a. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Numer. Anal 13, 236--250.
• 10: Norman E. Gibbs , William G. Poole, Jr. , Paul K. Stockmeyer, A Comparison of Several Bandwidth and Profile Reduction Algorithms, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.322-330, Dec. 1976 [doi>10.1145/355705.355707]
• 11: 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]
• 12: John G. Lewis, Algorithm 582: The Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms for Reordering Sparse Matrices, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.190-194, June 1982 [doi>10.1145/355993.355999]
• 13: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 14: Pople, J. A. and Beveridge, D. L. 1970. Approximate Molecular Orbital Theory, 1st ed., McGraw-Hill, New York.
• 15: 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.
• 16: 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.
• 17: 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.
• 18: 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, 3829.
• 19: Sloan, S. W. 1986. An algorithm for profile and wavefront reduction of sparse matrices Int. J. Numer. Meth. Eng. 23, 239--251.
• 20: Sloan, S. W. 1989. A FORTRAN program for profile and wavefront reduction. Int. J. Numer. Meth. Eng. 28, 2651--2679.
• 21: Szabo, A. and Ostlund, N. S. 1996. Modern Quantum Chemistry. Dover Publications, Mineola, NY.
• 22: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
Approximations, block divide-and-conquer, block-tridiagonal matrix