Solution of large, dense symmetric generalized eigenvalue problems using secondary storage

ABSTRACT

This paper describes a new implementation of algorithms for solving large, dense symmetric eigen-problems AX = BX&Lgr;, where the matrices A and B are too large to fit in the central memory of the computer. Here A is assumed to be symmetric, and B symmetric positive definite. A combination of block Cholesky and block Householder transformations are used to reduce the problem to a symmetric banded eigenproblem whose eigenvalues can be computed in central memory. Inverse iteration is applied to the banded matrix to compute selected eigenvectors, which are then transformed back to eigenvectors of the original problem. This method is especially suitable for the solution of large eigenproblems arising in quantum physics, using a vector supercomputer with fast secondary storage device such as the Cray X-MP with SSD. Some numerical results demonstrate the efficiency of the new implementation.

REFERENCES

• 1: ARMSTRONG, J. Optimization of Householder Trans{ormations, Part I: Linear Least Squares. CONVEX Computer Corp., 701 N. Plano Rd., Richardson, TX 75081.
• 2: 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]
• 3: BUNCH, J., DONGARRA, J., MOLER, C., AND STEWART, G. LINPACK User's Guide. SIAM Philadelphia, 1979.
• 4: CUPPEN, J.J. A divide and conquer method for the symmetric tridiagonal eigenvalue problem. Numer. Math. 36 (1981) 177-195.
• 5: 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]
• 6: DONGARRA, J. J., DU CROZ, J., HAMMARLING, S., AND HANSON, R. Extended set of Fortran basic linear algebra subprograms. Argonne National Lab. Rep. ANL-MSC-TM-41 (Revision 3), 1986.
• 7: GARBOW, B. S., BOYLE, J. M., DONGARRA, J. J., AND MOLER, C. B. Matrix eigensystem routines--EISPACK guide extension. In Lecture Notes in Computer Sciences, Vol. 51, Springer- Verlag, Berlin, 1977.
• 8: GRIMES, R. Solving systems of large dense linear equations. Rep. ETA-TR-44, Boeing Computer Services, Seattle, Wash., Feb. 1987; submitted to Supercomputing and Its Applications.
• 9: Roger Grimes , Henry Krakauer , John Lewis , Horst Simon , Su-Hai Wei, The solution of large dense generalized eigenvalue problems on the Cray X-MP/24 with SSD, Journal of Computational Physics, v.69 n.2, p.471-481, April 1987 [doi>10.1016/0021-9991(87)90178-1]
• 10: GRIMES, R., AND SIMON, H. Subroutines for the out-of-core solution of generalized symmetric eigenvalue problems. Rep. ETA-TR-54, Boeing Computer Services, 1987.
• 11: 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]
• 12: KAUFMAN, L., DONGARRA, J., AND HAMMARLING, S. Squeezing the most out of eigenvalue solvers on high-performance computers. Linear Algebra Appl. 77 (1986), 113-136.
• 13: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 14: Sy-Shin Lo , Berfnard Philippe , Ahmed Sameh, A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem, SIAM Journal on Scientific and Statistical Computing, v.8 n.2, p.155-165, March 1, 1987 [doi>10.1137/0908019]
• 15: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 16: SMITH, B. T., BOYLE, J. M., DONGARRA, J. J., GARBOW, B. S., IKEBE, Y., KLEMA, V. C., AND MOLER, C.B. Matrix eigensystem routines--EISPACK guide. In Lecture Notes in Computer Sciences, Vol. 6, Springer-Verlag, Berlin, 1976.
• 17: VectorPak Users Manual. Boeing Computer Services Doc. 20460-0501-R1, 1987.

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.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

  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