An Arnoldi code for computing selected eigenvalues of sparse, real, unsymmetric matrices

ABSTRACT

Arnoldi methods can be more effective than subspace iteration methods for computing the dominant eigenvalues of a large, sparse, real, unsymmetric matrix. A code, EB12, for the sparse, unsymmetric eigenvalue problem based on a subspace iteration algorithm, optionally combined with Chebychev acceleration, has recently been described by Duff and Scott and is included in the Harwell Subroutine Library. In this article we consider variants of the method of Arnoldi and discuss the design and development of a code to implement these methods. The new code, which is called EB13, offers the user the choice of a basic Arnoldi algorithm, an Arnoldi algorithm with Chebychev acceleration, and a Chebychev preconditioned Arnoldi algorithm. Each method is available in blocked and unblocked form. The code may be used to compute either the rightmost eigenvalues, the eigenvalues of largest absolute value, or the eigenvalues of largest imaginary part. The performance of each option in the EB13 package is compared with that of subspace iteration on a range of test problems, and on the basis of the results, advice is offered to the user on the appropriate choice of method. —Author's Abstract

REFERENCES

• 1: ANon4. 1993. Harwell Subroutine Library. A catalogue of subroutines (release 11). Theoretical Studies Dept., AEA Technology.
• 2: ARNOLDI, W. E. 1959. The principle of minimized iteration in the solution of matrix eigenvalue problems. Appl. Math. 9, 17 29.
• 3: BRACONNIER, T 1993. The Arnoldi-Tchebycheff algorithm for solving large nonsymmetric eigenproblems. Tech. Rep. TR/PA/93/95, CERFACS, Toulouse, France.
• 4: CHATELIN, F. AND FRAYSS}~, V. 1993. Qualitative computing: Elements of a theory for fimtepremsion computation. Lecture notes for the Comett European Course.
• 5: DANIEL, J. W., GRAGG, W. B., KAUFMAN, L., AND STEWART, G. W. 1976. Reorthogonalizatlon and stable algorithms for updating the Gram-Schmldt QR factorization. Math. Comput. 30, 772-795.
• 6: A. Deif, A relative backward perturbation theorem for the Eigenvalue problem, Numerische Mathematik, v.56 n.6, p.625-626, Dec. 1989 [doi>10.1007/BF01396348]
• 7: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 8: 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]
• 9: DUFF, I. S. AND REID, J. K. 1993. MA48, a Fortran code for direct solution of sparse unsymmetnc hnear systems of equations. Tech Rep RAt 93-072, Rutherford Appleton Laboratory, Oxon, U.K.
• 10: I. S. Duff , J. A. Scott, Computing selected eigenvalues of sparse unsymmetric matrices using subspace iteration, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.137-159, June 1993 [doi>10.1145/152613.152614]
• 11: DUFF, I. S., GRIMES, R. G, AND LEWIS, J. G. 1992. User's guide for the Harwell-Boeing sparse matrix collection (release 1). Tech. Rep. RAt 92-086, Rutherford Appleton Laboratory, Oxon, U.K.
• 12: GARRATT, T. J. 1991. The numerical detection of Hopf bifurcation in large systems arising in fluid mechanics. Ph.D thesis, Univ of Bath, Bath, U.K
• 13: GARRATT, T. J., MOORE, G., AND SFENCE, A. 1991. Two methods for the numerical detection of Hopf bifurcations. In B~furcatmn and Chaos. Analysis, Algorithms and Applications, R. Seydel, F. W. Schneider, and H. Troger, Eds. Birkhauser, Cambridge, Mass., 119-123
• 14: GODET-THOBIE, S. 1992. Eigenvalues of large highly nonnormal matrices. Ph.D. thesm, Umv. Paris IX Dauphin~, France.
• 15: Ho, D. 1990 Tchebychev acceleration technique for large scale nonsymmetric matrices Numerische Math. 56, 721-734.
• 16: Ho, n., CHATELIN, F., AND BENNANI, M. 1990. Arnoldi-Tchebychev procedure for large scale nonsymmetric matrices. Math. Model. Num. Anal. 24, 53-65.
• 17: W. Kerner, Large-scale complex eigenvalue problems, Journal of Computational Physics, v.85 n.1, p.1-85, Nov. 1989 [doi>10.1016/0021-9991(89)90200-3]
• 18: LEHOUCQ, R. B, SORENSEN, D. C., AND VU, P. 1994. ARPACK: An ~mplementation of the implicitly re-started Arnoldi iteration that computes some of the eigenvalues and eigenvectors of a large sparse matrix Avafiable from NETLIB(~ORNL.GOV under the directory SCALA- PACK.
• 19: MANTEUFFEL, T. A. 1975. An iteratlve method for solving nonsymmetric linear systems with dynamic estimation of parameters. Ph.D. thesis, Tech. Rep. UIUCDCS-75-758
• 20: MANTEUFFEL, T. A. 1977. The Tchebyshev iteration for nonsymmetric linear systems. Numer~sche Math. 28, 307-327.
• 21: NAG. 1993. NAG Fortran L~brary Mark 15. NAG Ltd., Oxford, U.K.
• 22: PARLETT, B. N. AND SAAD, Y 1985 Complex shift and invert strategies for real matmces. Tech. Rep YALEU/DCS~RR-424, Dept. of Computer Science, Yale Umv., New Haven, Conn.
• 23: PETERS, G. AND WILKINSON, J. I-I. 1970. Elgenvectors of real and complex matrices by LR and QR faetorizations. Numemsche Math 16, 181 204.
• 24: SAAD, Y. 1980. Variations on Arnoldl's method for computing mgenelements of large unsymmetric matrices. Lm. Alg. Appl 34, 269-295.
• 25: SAAD, Y. 1984. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math. Comput. 42, 567 588.
• 26: SAAD, Y. 1989. Numerical solution of large nonsymmetric eigenvalue problems. Comput. Phys. Commun. 53, 71-190
• 27: SADKANE, M. 1991a. A block Arnoldi-Chebychev method for computing the leading eigenpairs of large sparse unsymmetric matrices. Tech. Rep. TR/PA/91/146, CERFACS, Toulouse, France.
• 28: SADKANE, M. 1991b. On the solution of large sparse unsymmetric eigenvalue problems. Tech. Rep. TR/PA/91/147, CERFACS, Toulouse, France.
• 29: SCOTT, J. A. 1993. An Arnoldi code for computing selected eigenvalues of sparse real unsymmetric matrices. Rep. RAL-93-097, Rutherford Appleton Laboratory, Oxon, U.K.
• 30: SMrTH, R. A. 1967. The condition numbers of the matrix eigenvalue problem. Numerische Math. 10, 232-240.
• 31: D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.357-385, Jan. 1992 [doi>10.1137/0613025]
• 32: STEWART, G. W. 1978. SRRIT--A FORTRAN subroutine to calculate the dominant invariant subspaces of a real matrix. Tech. Rep. TR-514, Univ. of Maryland, College Park~ Md.

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.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms

Keywords:
Arnoldi's method, Chebyshev acceleration, large sparse matrices, real unsymmetric matrices