On computing condition numbers for the nonsymmetric eigenproblem

ABSTRACT

We review the theory of condition numbers for the nonsymmetric eigenproblem and give a tabular summary of bounds for eigenvalues, means of clusters of eigenvalues, eigenvectors, invariant subspaces, and related quantities. We describe the design of new algorithms for estimating these condition numbers. Fortran subroutines implementing these algorithms are in the LAPACK library [1].

REFERENCES

• 1: ANDERSON, E., BAI, Z., BISCHOF, C , DEMMEL, J., DONGARRA, J., DuCROZ, J., GREENBAUM, A., HAMMARLING, S., MCKENNEY, A., OSTROUCHOV~ S , AND SORENSEN, D. LAPACI~ Users' Gltlde. SIAM, Philadelphia, Pa., 1992.
• 2: BAI, Z., AND DEMMEL, J. On a direct algorithm for computing invariant subspaces with specified eigenvalues. To appear in L{rl. Alg. Appl.
• 3: R. H. Bartels , G. W. Stewart, Solution of the matrix equation AX + XB = C [F4], Communications of the ACM, v.15 n.9, p.820-826, Sept. 1972 [doi>10.1145/361573.361582]
• 4: BAUER, F L., AND FIKE. C T. Norms and exclusion theorems. ~urner. ~Jath. 2 (1960), 137 141.
• 5: BJORCK, A., AND GOLUB, G. H. Numerical methods for computing angles between linear subspaces. Math. Comput. 27 (1973), 579 594.
• 6: BYERS, R. A LINPACK-style condition estimator for the equation AX XBT = C. IEEE Trans. Automat. Control AC-29 (1984), 926-928.
• 7: S. P. Chan , R. Feldman , B. N. Parlett, Algorithm 517: A Program for Computing the Condition Numbers of Matrix Eigenvalues Without Computing Eigenvectors [F2], ACM Transactions on Mathematical Software (TOMS), v.3 n.2, p.186-203, June 1977 [doi>10.1145/355732.355741]
• 8: CHATELIN, F. Valeurs propres de matrices. Masson, Pans, 1988.
• 9: DEMMEL, J.W. The condition number of equivalence transformations that block diagonalize matrix pencils. SIAM J. Num. Areal. 20 (1983), 599-610.
• 10: DEMMEL, J.W. Computing stable eigendecomposition of matrices. Lin. Alg. Appl. 79 (1986), 163-193,
• 11: J. W. Demmel, On condition numbers and the distance to the nearest III-posted problem, Numerische Mathematik, v.51 n.3, p.251-289, July 1987 [doi>10.1007/BF01400115]
• 12: DONO^RRA, J., BUNCH, J. R., MOLER, C. B., AND STEWART, G. W LINPACK User's Guzde. SIAM, Philadelphia, Pa., 1979.
• 13: 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]
• 14: Jack J. Dongarra , Sven Hammarling , James H. Wilkinson, Numerical considerations in computing invariant subspaces, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.145-161, Jan. 1992 [doi>10.1137/0613013]
• 15: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 16: GOLUB, G., AND WILKINSON, J.H. Ill-conditioned eigensystem and computation of the Jordan canonical form. SIAM Rev. 18 (1976), 578-619.
• 17: GOLUB, G., NASH, S., AND VAN LOAN, C. A Hessenberg-Schur method for the problem AX + XB = C. IEEE Trans. Automat. Control AC~24 (1979), 909-913.
• 18: HAGER, W.W. Condition estimators. SIAMJ. Sct. Stat. Comput. 5 (1984), 311 316.
• 19: Nicholas J. Highham, A survey of condition number estimation for triangular matrices, SIAM Review, v.29 n.4, p.575-596, December 1, 1987 [doi>10.1137/1029112]
• 20: Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
• 21: HIGHAM, N. J. Perturbation theory and backward error for AX- XB = C. IMA preprint series 933. Univ. of Minn., Minneapolis, Minn., 1992.
• 22: KAHAN, W. Conserving confluence curbs ill-condition. Computer Science Dept. Report. Univ. of California, Berkeley, 1972.
• 23: KATO, T. Perturbation Theory of Linear Operators. Springer-Verlag, Berlin, 1966.
• 24: NG, K. C., AND PARLETT, B.N. Development of an accurate algorithm for EXP(Bt), Part I, Programs to swap diagonal block, Part II. CPAM-294. Univ. of California, Berkeley, Calif., 1988.
• 25: RUHE, A. An algorithm for numerical determination of the structure of a general matrix. BITIO (1970), 196-216.
• 26: SMITH, B. T., BOYLE, J. M., IKEBE, Y., KLEMA, V. C., AND MOLER, C.B. Matrix Eigensystem Routines: EISPACK Guide. 2d ed. Springer-Verlag, New York, 1970.
• 27: STEWART, G. W. Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Rev. 15 (1973), 727-764.
• 28: 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]
• 29: STEWART, G. W., AND SUN, J. Matrix Perturbatzon Theory. Academic Press, New York, 1990.
• 30: TREFETHEN, L.N. Approximation theory and numerical linear algebra. In Algorzthms for Approximation H, J. C. Mason and M. G. Cox, Eds. Chapman and Hall, London. 1990.
• 31: VAN LOAN, C. On estimating the condition of eigenvalues and eigenvectors. Lin. Alg. Appl. 88/89 (1987), 715-732.
• 32: VARAH, J.M. On the separation of two matrices. SIAM J. Numer Anal. 16 (1979), 216 222.
• 33: WmK~NSON, J.H. The Algebraic Eigenvalue Problem. Oxford University Press, Oxford, U.K., 1965.
• 34: WmKINSON, J.H. Sensitivity of eigenvalues. Utilitas Math. 25 (1984), 5 76.

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: Reliability and robustness; Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Measurement, Reliability

Keywords:
LAPACK, Schur decomposition, Sylvester equation, condition numbers, invariant subspace, nonsymmetric