Computing selected eigenvalues of sparse unsymmetric matrices using subspace iteration

ABSTRACT

This paper discusses the design and development of a code to calculate the eigenvalues of a large sparse real unsymmetric matrix that are the rightmost, leftmost, or are of the largest modulus. A subspace iteration algorithm is used to compute a sequence of sets of vectors that converge to an orthonormal basis for the invariant subspace corresponding to the required eigenvalues. This algorithm is combined with Chebychev acceleration if the rightmost or leftmost eigenvalues are sought, or if the eigenvalues of largest modulus are known to be the rightmost or leftmost eigenvalues. An option exists for computing the corresponding eigenvectors. The code does not need the matrix explicitly since it only requires the user to multiply sets of vectors by the matrix. Sophisticated and novel iteration controls, stopping criteria, and restart facilities are provided. The code is shown to be efficient and competitive on a range of test problems.

REFERENCES

• 1: ASHBY, S. F. Chebycode: A Fortran implementation of Manteuffel's adaptive Chebyshev algorithm. M.Sc. Thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, 1985.
• 2: BJOkCK, A. Solving linear least squares problems by Gram Schmidt orthogonahzation. BIT 7, (1967), 1 21.
• 3: 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]
• 4: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 5: DUFF, I. S. MA28 a set of Fortran subroutines for sparse unsymmetric matrices. Harwell Report AERE R 8730, HMSO, London, 1977.
• 6: GARRATT, T.J. Private communication, 1991
• 7: GARRATT, T. J., MOORE, G., AND SPENCE, A. Two methods for the numerical detection of Hopf bifurcations In Bzfurcatzon and Chaos: Analyszs, Algorzthms and Apphcatzons, R. Seydel, F. W. Schneider, and H. Troger, Eds., Blrkhauser, 1991, 119-123.
• 8: GODET-THOBIE, S. Private commumcatiom 1991.
• 9: GOLTm, G. H. AND VAN LOAN, C F Matrix Computatzons. Second Edition Johns Hopkins University Press, London, 1989.
• 10: HEINEMANN, R. F. AND POORE, A.B. Multiphcity, stability, and oscillatory dynamics of the tubular reactor. Chem. Eng. Sol. 36, (1981), 1411 1419.
• 11: Ho, D. Tcbebychev acceleration technique for large scale nonsymmetric matrices. Numer. Math. 56, 721 734.
• 12: Ho, D., CHATEL~N. F., AND BENNANL M. Arnoldi-Tchebychev procedure for large scale nonsymmetric matrices. Math. Model. Numer. Anal. 24, (1990), 53-65.
• 13: MANTEUFFEL, T. A. An iterative method for solving nonsymmetric linear systems w~th dynamic estimation of parameters. Ph.D. Thesis, Tech. Rep. UIUCDCS-75-758 Dept. of Computer Science, Univ. of Ilhnois at Urbana-Champaign, 1975.
• 14: MANTfiUFFEL~ T. A. The Tchebyahev iteration for nonaymmetric linear ayaten, a. l~*err~r. Math. 28, (1977), 307 327.
• 15: MANTEUFFEL, T.A. Adaptive procedure for estimating parameters for the nonsymmetric Tchebyshev lteratmn. Numer. Math. 31, (1978), 183-208.
• 16: PETERS, G., AND WILKINSON, J.H. E~genvectors of real and complex matrices by LR and QR triangularizations. Numer. Math. 16, (1970), 181-204.
• 17: RUTISHAUSER, H. Computational aspects of F. L. Bauer's simultaneous iteration method. Numer. Math. 13, (1969), 4 13.
• 18: SAID, Y. Variations on Arnoldfs method for computing eigenelements of large unsymmetric matrices Linear Alg. Appl. 34, (1980), 269 295
• 19: S~D, Y. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math. Comput. 42, (1984), 567-588.
• 20: S~,~D, Y. Numerical solution of large nonsymmetric eigenvalue problems. Comput. Phys. Commun. 53, (1989), 71-90.
• 21: S~D, Y. Private communication, 1990.
• 22: SADKANE, M. On the solution of large sparse unsymmetric eigenvalue problems. Tech. Rep. TR/PA/91/47, CERFACS, Toulouse, 1991.
• 23: STEWART, G.W. Methods of simultaneous iteration for calculating eigenvectors of matrices. In Topics in Numerical Analys~s H, J. H. H. Miller, Ed., Academic Press, 1975, 169-185.
• 24: STEWART, G.W. Simultaneous iteration for computing invariant subspaces of non~Hermitian matrices. Numer. Math. 25, (1976), 123-136.
• 25: G. W. Stewart, Algorithm 506: HQR3 and EXCHNG: Fortran Subroutines for Calculating and Ordering the Eigenvalues of a Real Upper Hessenberg Matrix [F2], ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.275-280, Sept. 1976 [doi>10.1145/355694.355700]
• 26: STEWART, G. W. SRRIT--A FORTRAN subroutine to calculate the dominant invariant subspaces of a real matrix. Tech. Rep. TR-514, Univ. of Maryland, 1978.
• 27: William J. Stewart , Alan Jennings, A Simultaneous Iteration Algorithm for Real Matrices, ACM Transactions on Mathematical Software (TOMS), v.7 n.2, p.184-198, June 1981 [doi>10.1145/355945.355948]
• 28: VAN LOAN, C.F. Private communication, 1989.
• 29: WILKINSON, J. H. AND REINSCH, C. Handbook for Automatic Computation. Vol. II, Springer- Verlag, 1971.

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:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design

Keywords:
Chebychev acceleration, eigenvalues, eigenvectors, large sparse matrices, real unsymmetric matrices, subspace iteration