Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-06T03:56:59.622Z Has data issue: false hasContentIssue false
  • English
  • Français

Computation of pseudospectra

Published online by Cambridge University Press:  07 November 2008

Lloyd N. Trefethen
Lloyd N. Trefethen
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, England E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

There is more to the computation of pseudospectra than the obvious algorithm of computing singular value decompositions on a grid and sending the results to a contour plotter. Other methods may be hundreds of times faster. The state of the art is reviewed, with emphasis on methods for dense matrices, and a Matlab code is given.

Type
Research Article
Information
Acta Numerica , Volume 8 , January 1999 , pp. 247 - 295
Copyright
Copyright © Cambridge University Press 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Anderson, E. et al. , (1995), LAPACK Users' Guide, 2nd edn, SIAM, Philadelphia.Google Scholar
Baggett, J. S. (1994), ‘Pseudospectra of an operator of Hille and Phillips’, Res. Rep. 94-15, Interdisc. Proj. Ctr. Supercomp., Swiss Federal Institute of Technology, Zürich.Google Scholar
Barrett, R. et al. , (1994), Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia.CrossRefGoogle Scholar
Bau, D. III, and Trefethen, L. N. (1997), Numerical Linear Algebra, SIAM, Philadelphia.Google Scholar
Bayer, D. and Diaconis, P. (1992), ‘Trailing the dovetail shuffle to its lair’, Ann. Appl. Prob. 2, 294–313.CrossRefGoogle Scholar
Bekas, C. and Gallopoulos, E. (1998), ‘COBRA: A hybrid method for computing the matrix pseudospectrum’, abstract, Copper Mountain Conf. on Iterative Methods.Google Scholar
Bekas, C. and Gallopoulos, E. (1999), ‘COBRA: Parallel path following for computing the matrix pseudospectrum’, manuscript in preparation.Google Scholar
Borba, D. et al. (1994), ‘The pseudospectrum of the resistive magnetohydrodynamics operator: resolving the resistive Alfvén paradox’, Phys. Plasmas 1, 3151–3160.CrossRefGoogle Scholar
Böttcher, A. (1994), ‘Pseudospectra and singular values of large convolution operators’, J. Int. Eqs. Appl. 6, 267–301.Google Scholar
Boyd, S. and Desoer, C. A. (1985), ‘Subharmonic functions and performance bounds on linear time-invariant feedback systems’, IMA J. Math. Control Inform. 2, 153–170.CrossRefGoogle Scholar
Braconnier, T. (1996), Fvpspack: A Fortran and PVM package to compute the field of values and pseudospectra of large matrices, Numer. Anal. Rep. 293, Manchester Ctr. Comp. Maths., Manchester, England.Google Scholar
Braconnier, T. (1997), ‘Complete iterative method for computing pseudospectra’, preprint.Google Scholar
Braconnier, T., Chatelin, F. and Dunyach, J.-C. (1995), ‘Highly nonnormal eigenvalue problems in the aeronautical industry’, Japan J. Ind. Appl. Math. 12, 123–136.CrossRefGoogle Scholar
Braconnier, T. and Higham, N. J. (1996), ‘Computing the field of values and pseudospectra using the Lanczos method with continuation’, BIT 36, 422–440.CrossRefGoogle Scholar
Braconnier, T., McCoy, A. and Toumazou, V. (1997), ‘Using the field of values for pseudospectra generation’, Technical Report TR/PA/97/28, CERFACS.Google Scholar
Brühl, M. (1996), ‘A curve tracing algorithm for computing the pseudospectrum’, BIT 36, 441–454.CrossRefGoogle Scholar
Butler, K. M. and Farrell, B. F. (1992), ‘Three-dimensional optimal perturbations in viscous shear flow’, Phys. Fluids A 4, 1637–1650.CrossRefGoogle Scholar
Canuto, C., Hussaini, M. Y., Quarteroni, A. and Zang, T. A. (1988), Spectral Methods in Fluid Dynamics, Springer, New York.CrossRefGoogle Scholar
Carpraux, J. F., Erhel, J. and Sadkane, M. (1994), ‘Spectral portrait for non-Hermitian large sparse matrices’, Computing 53, 301–310.CrossRefGoogle Scholar
Chaitin-Chatelin, F. and Frayssé, V. (1996), Lectures on Finite Precision Computations, SIAM, Philadelphia.CrossRefGoogle Scholar
Chatelin, F. (1983), Spectral Approximation of Linear Operators, Academic Press, London.Google Scholar
Cochran, J. A. and Hinds, E. W. (1974), ‘Eigensystems associated with the complex-symmetric kernels of laser theory’, SIAM J. Appl. Math. 26, 776–786.CrossRefGoogle Scholar
Cossu, C. and Chomaz, J. M. (1997), ‘Global measures of local convective instabilities’, Phys. Rev. Lett. 78, 4387–4390.CrossRefGoogle Scholar
Darmofal, D.L. and Schmid, P. J. (1996), ‘The importance of eigenvectors for local preconditioners of the Euler equations’, J. Comput. Phys. 127, 346–362.CrossRefGoogle Scholar
Davidson, E. R. (1975), ‘The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices’, J. Comput. Phys. 17, 87–94.CrossRefGoogle Scholar
Davies, E. B. (1999a), ‘Pseudospectra, the harmonic oscillator and complex resonances’, Proc. Royal Soc. London A 455, 585–599.CrossRefGoogle Scholar
Davies, E. B. (1999b), ‘Pseudospectra of differential operators’, J. Operator Theory, to appear.Google Scholar
Demmel, J. W. (1987), ‘A counterexample for two conjectures about stability’, IEEE Trans. Autom. Control AC-32, 340–342.CrossRefGoogle Scholar
Diaconis, P. (1996), ‘The cutoff phenomenon in finite Markov chains’, Proc. Nat. Acad. Sci. USA 93, 1659–1664.CrossRefGoogle ScholarPubMed
Diaconis, P., Graham, R. L. and Morrison, J. A. (1990), ‘Asymptotic analysis of a random walk on a hypercube with many dimensions’, Random Struct. Alg. 1, 51–72.CrossRefGoogle Scholar
Donato, J. M. (1991), Iterative Methods for Scalar and Coupled Systems of Elliptic Equations, PhD thesis, Dept. of Math., U. of California, Los Angeles.Google Scholar
Dongarra, J. J., Duff, I. S., Sorensen, D. C. and van der Vorst, H. A. (1998), Numerical Linear Algebra for High-Performance Computers, SIAM, Philadelphia.CrossRefGoogle Scholar
van Dorsselaer, J. L. M. (1997), ‘Pseudospectra for matrix pencils and stability of equilibria’, BIT 37, 833–845.CrossRefGoogle Scholar
van Dorsselaer, J. L. M., Kraaijevanger, J. F. B. M. and Spijker, M. N. (1993), ‘Linear stability analysis in the numerical solution of initial value problems’, in Vol. 2 of Acta Numerica, Cambridge University Press, pp. 199–237.Google Scholar
Driscoll, T. A. and Trefethen, L. N. (1996), ‘Pseudospectra for the wave equation with an absorbing boundary’, J. Comput. Appl. Math. 69, 125–142.CrossRefGoogle Scholar
Farrell, B. F. and Ioannou, P. J. (1996), ‘Generalized stability theory. Part I: autonomous operators and Part II: Nonautonomous Operators’, J. Atmos. Sci. 53, 2025–2040 and 2041–2053.2.0.CO;2>CrossRefGoogle Scholar
Flaherty, J., Seyler, C. E. and Trefethen, L. N. (1999), ‘Large-amplitude transient growth in the linear evolution of equatorial spread F in the presence of shear’, J. Geophys. Research, to appear.CrossRefGoogle Scholar
Fokkema, D. R. (1996), Subspace methods for Linear, Nonlinear, and Eigen Problems, PhD thesis, U. of Utrecht, 1996.Google Scholar
Fokkema, D. R., Sleijpen, G. L. G. and van der Vorst, H. A. (1999), ‘Jacobi- Davidson style QR and QZ algorithms for the reduction of matrix pencils’, SIAM J. Sci. Comput. 20, 94–125.CrossRefGoogle Scholar
Fornberg, B. (1996), A Practical Guide to Pseudospectral Methods, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Fornberg, B. and Sloan, D. M. (1994), ‘A review of pseudospectral methods for solving partial differential equations’, in Vol. 3 of Acta Numerica, Cambridge University Press, pp. 203–267.Google Scholar
Frayssé, V., Giraud, L. and Toumazou, V. (1996), ‘Parallel computation of spectral portraits on the Meiko CS2’, High-Performance Computing and Networking (Liddell, H., Colbrook, A., Hertzberger, B. and Sloot, P., eds), Springer, pp. 312–318.CrossRefGoogle Scholar
Frayssé, V., Gueury, M., Nicoud, F. and Toumazou, V. (1996), ‘Spectral portraits for matrix pencils’, Technical Report TR/PA/96/19, CERFACS.Google Scholar
Frayssé, V. and Toumazou, V. (1998), ‘A note on the normwise perturbation theory for the regular generalized eigenproblem’, Numer. Lin. Alg. Appl. 5, 1–10.3.0.CO;2-X>CrossRefGoogle Scholar
Freund, R. W. (1992), ‘Quasi-kernel polynomials and their use in non-Hermitian matrix iterations’, J. Comput. Appl. Math. 43, 135–158.CrossRefGoogle Scholar
, E. Gallestey (1998a), ‘Computing spectral value sets using the subharmonicity of the norm of rational matrices’, BIT 38, 22–33.CrossRefGoogle Scholar
Gallestey, E. (1998b), Theory and Numerics of Spectral Value Sets, PhD thesis, U. Bremen.Google Scholar
Godunov, S. K. (1992), Spectral portraits of matrices and criteria for spectrum Dichotomy, Proc. Third IMACS-GAMM Symp. Comput. Arith. Sci. Comput. (SCAN-91), (Atanassova, L. and Herzberger, J., eds), North-Holland, Amsterdam.Google Scholar
Godunov, S. K. (1997), Modern Aspects of Linear Algebra, Nauchnaya Kniga, Novosibirsk. In Russian.Google Scholar
Godunov, S. K., Antonov, A., Kiriljuk, O. P. and Kostin, V. I. (1993), Guaranteed Accuracy in Numerical Linear Algebra, Kluwer.CrossRefGoogle Scholar
Godunov, S. K., Kiriljuk, O. P. and Kostin, V. I. (1990), Spectral portraits of matrices, Technical Report 3, Inst. of Math., Acad. Sci. USSR, Novosibirsk.Google Scholar
Godunov, S. K. and Sadkane, M. (1996), ‘Elliptic dichotomy of a matrix spectrum’, Lin. Alg. Appl. 248, 205–232.CrossRefGoogle Scholar
Greenbaum, A. (1997), Iterative Methods for Solving Linear Systems, SIAM, Philadelphia.CrossRefGoogle Scholar
Greenbaum, A. and Trefethen, L. N. (1993), ‘Do the pseudospectra of a matrix determine its behavior?’, Technical Report 93–1371, Dept. Comput. Sci., Cornell U.Google Scholar
Henrici, P. (1962), ‘Bounds for iterates, inverses, spectral variation and field of values of nonnormal matrices’, Numer. Math. 4, 24–40.CrossRefGoogle Scholar
Heuveline, V., Philippe, B. and Sadkane, M. (1997), ‘Parallel computation of spectral portrait of large matrices by Davidson type methods’, Numer. Algs. 16, 55–75.CrossRefGoogle Scholar
Higham, D. J. and Owren, B. (1996), ‘Non-normality effects in a discretised nonlinear reaction-convection-convection-diffusion equation’, J. Comput. Phys. 124, 309–323.CrossRefGoogle Scholar
Higham, D. J. and Trefethen, L. N. (1993), ‘Stiffness of ODEs’, BIT 33, 285–303.CrossRefGoogle Scholar
Higham, N. J. (1995), ‘The Test Matrix Toolbox for MATLAB (Version 3.0)’, Numer. Anal. Rep. 276, Manchester Ctr. Comp. Maths., Manchester, England; available online at http://www.maths.man.ac.uk/~higham/.Google Scholar
Higham, N. J. and Tisseur, F. (1999), ‘A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra’, Numer. Anal. Rep. 341, Manchester Ctr. Comp. Maths., Manchester, England.Google Scholar
Hinrichsen, D. and Kelb, B. (1993), ‘Spectral value sets: a graphical tool for robustness analysis’, Systems Control Lett. 21, 127–136.CrossRefGoogle Scholar
Hinrichsen, D. and Pritchard, A. J. (1992), ‘On spectral variations under bounded real matrix perturbations’, Numer. Math. 60, 509–524.CrossRefGoogle Scholar
Hinrichsen, D. and Pritchard, A. J. (1994), ‘Stability of uncertain systems’, in Systems and Networks: Mathematical Theory and Applications, Vol. I, Akademie-Verlag, Berlin, pp. 159–182.Google Scholar
Jónsson, G. F. and Trefethen, L. N. (1998), ‘A numerical analyst looks at the "cutoff phenomenon" in card shuffling and other Markov chains’, in Numerical Analysis 1997 (Griffiths, D. F., Higham, D. J. and Watson, G. A., eds), Longman, Harlow, Essex, England.Google Scholar
Kato, T. (1976), Perturbation Theory for Linear Operators, 2nd edn, Springer, New York.Google Scholar
Kostin, V. (1991), ‘On definition of matrices' spectra’, in High Performance Computing II (Durand, M. and El Dabaghi, F., eds), Elsevier.Google Scholar
Kreiss, H. O. (1962), ‘Über die Stabilitätsdefinition für Differenzengleichun- gen die partielle Differenzialgleichungen approximieren’, BIT 2, 153–181.CrossRefGoogle Scholar
Landau, H. J. (1975), ‘On Szegő's eigenvalue distribution theory and non-Hermitian kernels’, J. d'Analyse Math. 28, 335–357.CrossRefGoogle Scholar
Landau, H. J. (1976), ‘Loss in unstable resonators’, J. Opt. Soc. Amer. 66, 525–529.CrossRefGoogle Scholar
Landau, H. J. (1977), ‘The notion of approximate eigenvalues applied to an integral equation of laser theory’, Quart. Appl. Math. 35, 165–172.CrossRefGoogle Scholar
László, L. (1994), ‘An attainable lower bound for the best normal approximation’, SIAM J. Matrix Anal. Appl. 15, 1035–1043.CrossRefGoogle Scholar
Lavallée, P. and Sadkane, M. (1997), ‘Une méthode stable de bloc-diagonalisation de matrices: Application au calcul de portrait spectral’, Technical Report 3141, INRIA, Rennes, 1997.Google Scholar
Lehoucq, R. B., Sorensen, D. C. and Yang, C. (1998), ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM, Philadelphia.CrossRefGoogle Scholar
Lui, S. H. (1997), ‘Computation of pseudospectra by continuation’, SIAM J. Sci. Comput. 18, 567–573.CrossRefGoogle Scholar
Lumsdaine, A. and Wu, D. (1997), ‘Spectra and pseudospectra of waveform relaxation operators’, SIAM J. Sci. Comput. 18, 286–304.CrossRefGoogle Scholar
Marques, O. and Toumazou, V. (1995a), ‘Spectral portrait computation by Lanczos method (augmented matrix method)’, TR/PA/95/05, CERFACS.Google Scholar
Marques, O. and Toumazou, V. (1995b), ‘Spectral portrait computation by Lanczos method (normal equation method)’, TR/PA/95/02, CERFACS.Google Scholar
McCoy, R. A. and Toumazou, V. (1997), PRECISE User's Guide – Version 1.0, Technical Report TR/PA/97/38, CERFACS, 1997.Google Scholar
Nachtigal, N. M., Reichel, L. and Trefethen, L. N. (1992), ‘A hybrid GMRES algorithm for nonsymmetric linear systems’, SIAM J. Matrix Anal. Appl. 13, 796–825.CrossRefGoogle Scholar
Olsson, P. J. and Henningson, D. S. (1995), ‘Optimal disturbance growth in watertable flow’, Stud. Appl. Math. 94, 183–210.CrossRefGoogle Scholar
Pazy, A. (1983), Semigroups of Linear Operators and Applications to Partial Differential Equations, Springer, New York.CrossRefGoogle Scholar
Plato, R. (1997), ‘Resolvent estimates for Abel integral operators and the regularization of associated first kind integral equations’, J. Int. Eqs. Appl. 9, 253–278.Google Scholar
Reddy, S. C. (1993), ‘Pseudospectra of Wiener-Hopf integral operators and constant-coefficient differential operators’, J. Int. Eqs. Appl. 5, 369–403.Google Scholar
Reddy, S. C. and Henningson, D. S. (1993), ‘Energy growth in viscous channel flows’, J. Fluid Mech. 252, 209–238.CrossRefGoogle Scholar
Reddy, S. C., Schmid, P. J. and Henningson, D. S. (1993), ‘Pseudospectra of the Orr-Sommerfeld operator’, SIAM J. Appl. Math. 53, 15–47.CrossRefGoogle Scholar
Reddy, S. C. and Trefethen, L. N. (1990), ‘Lax-stability of fully discrete spectral methods via stability regions and pseudo-eigenvalues’, Comput. Meth. Appl. Mech. Engr. 80, 147–164.CrossRefGoogle Scholar
Reddy, S. C. and Trefethen, L. N. (1994), ‘Pseudospectra of the convection-diffusion operator’, SIAM J. Appl. Math. 54, 1634–1649.CrossRefGoogle Scholar
Reichel, L. and Trefethen, L. N. (1992), ‘Eigenvalues and pseudo-eigenvalues of Toeplitz matrices’, Lin. Alg. Appl. 162–164, 153–185.Google Scholar
Riedel, K. (1994), ‘Generalized epsilon-pseudospectra’, SIAM J. Numer. Anal. 31, 1219–1225.CrossRefGoogle Scholar
Ruhe, A. (1994), ‘The rational Krylov algorithm for large nonsymmetric eigenvalues - mapping the resolvent norms (pseudospectrum)’, unpublished manuscript.Google Scholar
Ruhe, A. (1998), ‘Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils’, SIAM J. Sci. Comput. 19, 1535–1551.CrossRefGoogle Scholar
Saad, Y. (1992), Numerical Methods for Large Eigenvalue Problems, Manchester U. Press, Manchester, England.Google Scholar
Schmid, P. J., Henningson, D. S., Khorrami, M. and Malik, M. (1993), ‘A sensitivity study of hydrodynamic stability operators’, Theor. Comput. Fluid Dyn. 4, 227–240.CrossRefGoogle Scholar
Simoncini, V. and Gallopoulos, E. (1998), ‘Transfer functions and resolvent norm approximation of large matrices’, Elec. Trans. Numer. Anal. 7, 190–201.Google Scholar
Sleijpen, G. L. G. and van der Vorst, H. A. (1996), ‘A Jacobi-Davidson iteration method for linear eigenvalue problems’, SIAM J. Matrix Anal. Appl. 17, 401–425.CrossRefGoogle Scholar
Smith, B.T. et al. (1976), Matrix Eigensystem Routines – EISPACK Guide, Springer, Berlin.CrossRefGoogle Scholar
Toh, K.-C. and Trefethen, L. N. (1994), ‘Pseudozeros of polynomials and pseudospectra of companion matrices’, Numer. Math. 68, 403–425.CrossRefGoogle Scholar
Toh, K.-C. and Trefethen, L. N. (1996), ‘Computation of pseudospectra by the Arnoldi iteration’, SIAM J. Sci. Comput. 17, 1–15.CrossRefGoogle Scholar
Toh, K.-C. and Trefethen, L. N. (1999a), ‘The Chebyshev polynomials of a matrix’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Toh, K.-C. and Trefethen, L. N. (1999b), ‘The Kreiss matrix theorem on a general complex domain’, SIAM J. Matrix Anal. Appl., to appear.CrossRefGoogle Scholar
Toumazou, V. (1996), Portraits Spectraux de Matrices: Un Outil d'Analyse de la Stabilité, PhD thesis, U. Raymond Poincaré, Nancy I, Technical Report TH/PA/96/46, CERFACS.Google Scholar
Trefethen, A. E. et al. (1996), ‘MultiMatlab: Matlab on multiple processors’, Tech. Rep. CTC96TR293, Cornell Theory Center, http://cs-tr.cs.Cornell.edu:80/Dienst/UI/l.0/Display/ncstrl.cornell/TR96-1586.Google Scholar
Trefethen, A. E., Trefethen, L. N. and Schmid, P. J. (1999), ‘Spectra and pseu-dospectra for pipe Poiseuille flow’, Comput. Meth. Appl. Mech. Engr., to appear.Google Scholar
Trefethen, L. N. (1990), ‘Approximation theory and numerical linear algebra’, in Algorithms for Approximation II (Mason, J. C. and Cox, M. G., eds), Chapman and Hall, London.Google Scholar
Trefethen, L. N. (1992), ‘Pseudospectra of matrices’, in Numerical Analysis 1991 (Griffiths, D. F. and Watson, G. A., eds), Longman Scientific and Technical, Harlow, Essex, England, pp. 234–266.Google Scholar
Trefethen, L. N. (1997), ‘Pseudospectra of linear operators’, SIAM Review 39, 383–406.CrossRefGoogle Scholar
Trefethen, L. N. (1999), ‘Spectra and pseudospectra: The behavior of non-normal matrices and operators’, in The Graduate Student's Guide to Numerical Analysis, Vol. 26 of SSCM series (Ainsworth, M., Levesley, J. and Marletta, M., eds), Springer, Berlin, to appear.Google Scholar
Trefethen, L. N. and Bau, D. III (1997), Numerical Linear Algebra, SIAM, Philadelphia.CrossRefGoogle Scholar
Trefethen, L. N., Trefethen, A. E., Reddy, S. C. and Driscoll, T. A. (1993), ‘Hydrodynamic stability without eigenvalues’, Science 261, 578–584.CrossRefGoogle ScholarPubMed
Varah, J. M. (1979), ‘On the separation of two matrices’, SIAM J. Numer. Anal. 16, 216–222.CrossRefGoogle Scholar
Wilkinson, J. H. (1965), The Algebraic Eigenvalue Problem, Clarendon Press, Oxford.Google Scholar