On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators

Hansen, Anders

doi:10.1090/S0894-0347-2010-00676-5

On the Solvability Complexity Index, the $n$-pseudospectrum and approximations of spectra of operators
HTML articles powered by AMS MathViewer

by Anders C. Hansen

J. Amer. Math. Soc. 24 (2011), 81-124

DOI: https://doi.org/10.1090/S0894-0347-2010-00676-5

Published electronically: July 12, 2010

PDF | Request permission

Abstract:

We show that it is possible to compute spectra and pseudospectra of linear operators on separable Hilbert spaces given their matrix elements. The core in the theory is pseudospectral analysis and in particular the $n$-pseudospectrum and the residual pseudospectrum. We also introduce a new classification tool for spectral problems, namely, the Solvability Complexity Index. This index is an indicator of the “difficultness” of different computational spectral problems.

References

William Arveson, Discretized CCR algebras, J. Operator Theory 26 (1991), no. 2, 225–239. MR 1225515
William Arveson, Improper filtrations for $C^*$-algebras: spectra of unilateral tridiagonal operators, Acta Sci. Math. (Szeged) 57 (1993), no. 1-4, 11–24. MR 1243265
William Arveson, $C^*$-algebras and numerical linear algebra, J. Funct. Anal. 122 (1994), no. 2, 333–360. MR 1276162, DOI 10.1006/jfan.1994.1072
William Arveson, The role of $C^\ast$-algebras in infinite-dimensional numerical linear algebra, $C^\ast$-algebras: 1943–1993 (San Antonio, TX, 1993) Contemp. Math., vol. 167, Amer. Math. Soc., Providence, RI, 1994, pp. 114–129. MR 1292012, DOI 10.1090/conm/167/1292012
Erik Bédos, On filtrations for $C^*$-algebras, Houston J. Math. 20 (1994), no. 1, 63–74. MR 1272561
Erik Bédos, On Følner nets, Szegő’s theorem and other eigenvalue distribution theorems, Exposition. Math. 15 (1997), no. 3, 193–228. MR 1458766
Carl M. Bender, Properties of non-Hermitian quantum field theories, Proceedings of the International Conference in Honor of Frédéric Pham (Nice, 2002), 2003, pp. 997–1008 (English, with English and French summaries). MR 2033507, DOI 10.5802/aif.1971
Carl M. Bender, Making sense of non-Hermitian Hamiltonians, Rep. Progr. Phys. 70 (2007), no. 6, 947–1018. MR 2331294, DOI 10.1088/0034-4885/70/6/R03
Albrecht Böttcher, Pseudospectra and singular values of large convolution operators, J. Integral Equations Appl. 6 (1994), no. 3, 267–301. MR 1312518, DOI 10.1216/jiea/1181075815
Albrecht Böttcher, $C^*$-algebras in numerical analysis, Irish Math. Soc. Bull. 45 (2000), 57–133. MR 1832325
A. Böttcher, A. V. Chithra, and M. N. N. Namboodiri, Approximation of approximation numbers by truncation, Integral Equations Operator Theory 39 (2001), no. 4, 387–395. MR 1829276, DOI 10.1007/BF01203320
Albrecht Böttcher and Sergei M. Grudsky, Spectral properties of banded Toeplitz matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. MR 2179973, DOI 10.1137/1.9780898717853
Albrecht Böttcher and Bernd Silbermann, Analysis of Toeplitz operators, 2nd ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2006. Prepared jointly with Alexei Karlovich. MR 2223704
Lyonell Boulton, Projection methods for discrete Schrödinger operators, Proc. London Math. Soc. (3) 88 (2004), no. 2, 526–544. MR 2032518, DOI 10.1112/S0024611503014448
Lyonell Boulton, Limiting set of second order spectra, Math. Comp. 75 (2006), no. 255, 1367–1382. MR 2219033, DOI 10.1090/S0025-5718-06-01830-8
B. M. Brown and M. Marletta, Spectral inclusion and spectral exactness for singular non-self-adjoint Hamiltonian systems, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 459 (2003), no. 2036, 1987–2009. MR 1993665, DOI 10.1098/rspa.2002.1106
L. G. Brown, Lidskiĭ’s theorem in the type $\textrm {II}$ case, Geometric methods in operator algebras (Kyoto, 1983) Pitman Res. Notes Math. Ser., vol. 123, Longman Sci. Tech., Harlow, 1986, pp. 1–35. MR 866489
Nathanial P. Brown, AF embeddings and the numerical computation of spectra in irrational rotation algebras, Numer. Funct. Anal. Optim. 27 (2006), no. 5-6, 517–528. MR 2246575, DOI 10.1080/01630560600790785
Nathanial P. Brown, Quasi-diagonality and the finite section method, Math. Comp. 76 (2007), no. 257, 339–360. MR 2261025, DOI 10.1090/S0025-5718-06-01893-X
H. O. Cordes and J. P. Labrousse, The invariance of the index in the metric space of closed operators, J. Math. Mech. 12 (1963), 693–719. MR 0162142, DOI 10.1017/s0022112062000440
E. B. Davies, Semi-classical states for non-self-adjoint Schrödinger operators, Comm. Math. Phys. 200 (1999), no. 1, 35–41. MR 1671904, DOI 10.1007/s002200050521
E. B. Davies, Spectral properties of random non-self-adjoint matrices and operators, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 457 (2001), no. 2005, 191–206. MR 1843941, DOI 10.1098/rspa.2000.0662
E. B. Davies, Non-self-adjoint differential operators, Bull. London Math. Soc. 34 (2002), no. 5, 513–532. MR 1912874, DOI 10.1112/S0024609302001248
E. B. Davies and A. B. J. Kuijlaars, Spectral asymptotics of the non-self-adjoint harmonic oscillator, J. London Math. Soc. (2) 70 (2004), no. 2, 420–426. MR 2078902, DOI 10.1112/S0024610704005381
E. B. Davies and M. Plum, Spectral pollution, IMA J. Numer. Anal. 24 (2004), no. 3, 417–438. MR 2068830, DOI 10.1093/imanum/24.3.417
P. Deift, L. C. Li, and C. Tomei, Toda flows with infinitely many variables, J. Funct. Anal. 64 (1985), no. 3, 358–402. MR 813206, DOI 10.1016/0022-1236(85)90065-5
Nils Dencker, Johannes Sjöstrand, and Maciej Zworski, Pseudospectra of semiclassical (pseudo-) differential operators, Comm. Pure Appl. Math. 57 (2004), no. 3, 384–415. MR 2020109, DOI 10.1002/cpa.20004
Trond Digernes, V. S. Varadarajan, and S. R. S. Varadhan, Finite approximations to quantum systems, Rev. Math. Phys. 6 (1994), no. 4, 621–648. MR 1290691, DOI 10.1142/S0129055X94000213
Nelson Dunford and Jacob T. Schwartz, Linear operators. Part I, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1988. General theory; With the assistance of William G. Bade and Robert G. Bartle; Reprint of the 1958 original; A Wiley-Interscience Publication. MR 1009162
Bent Fuglede and Richard V. Kadison, Determinant theory in finite factors, Ann. of Math. (2) 55 (1952), 520–530. MR 52696, DOI 10.2307/1969645
Uffe Haagerup and Hanne Schultz, Brown measures of unbounded operators affiliated with a finite von Neumann algebra, Math. Scand. 100 (2007), no. 2, 209–263. MR 2339369, DOI 10.7146/math.scand.a-15023
Roland Hagen, Steffen Roch, and Bernd Silbermann, $C^*$-algebras and numerical analysis, Monographs and Textbooks in Pure and Applied Mathematics, vol. 236, Marcel Dekker, Inc., New York, 2001. MR 1792428
Anders C. Hansen, On the approximation of spectra of linear operators on Hilbert spaces, J. Funct. Anal. 254 (2008), no. 8, 2092–2126. MR 2402104, DOI 10.1016/j.jfa.2008.01.006
—, Infinite-dimensional numerical linear algebra: theory and applications, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science (2010).
N. Hatano and D. R. Nelson, Localization transitions in non-Hermitian quantum mechanics, Phys. Rev. Lett. 77 (1996), no. 3, 570–573.
—, Vortex pinning and non-Hermitian quantum mechanics, Phys. Rev. B 56 (1997), no. 14, 8651–8673.
W. K. Hayman and P. B. Kennedy, Subharmonic functions. Vol. I, London Mathematical Society Monographs, No. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0460672
Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452, DOI 10.1007/978-3-642-66282-9
Michael Levitin and Eugene Shargorodsky, Spectral pollution and second-order relative spectra for self-adjoint operators, IMA J. Numer. Anal. 24 (2004), no. 3, 393–416. MR 2068829, DOI 10.1093/imanum/24.3.393
Marco Marletta, Roman Shterenberg, and Rudi Weikard, On the inverse resonance problem for Schrödinger operators, Comm. Math. Phys. 295 (2010), no. 2, 465–484. MR 2594334, DOI 10.1007/s00220-009-0928-8
O. Nevanlinna, Computing the spectrum and representing the resolvent, Numer. Funct. Anal. Optim. 30 (2009), no. 9-10, 1025–1047. MR 2589763, DOI 10.1080/01630560903393162
Eugene Shargorodsky, Geometry of higher order relative spectra and projection methods, J. Operator Theory 44 (2000), no. 1, 43–62. MR 1774693
E. Shargorodsky, On the level sets of the resolvent norm of a linear operator, Bull. Lond. Math. Soc. 40 (2008), no. 3, 493–504. MR 2418805, DOI 10.1112/blms/bdn038
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
Steve Smale, Complexity theory and numerical analysis, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 523–551. MR 1489262, DOI 10.1017/S0962492900002774
G. Szegő, Beiträge zur Theorie der Toeplitzschen Formen, Math. Z. 6 (1920), no. 3-4, 167–202 (German). MR 1544404, DOI 10.1007/BF01199955
Lloyd N. Trefethen, Computation of pseudospectra, Acta numerica, 1999, Acta Numer., vol. 8, Cambridge Univ. Press, Cambridge, 1999, pp. 247–295. MR 1819647, DOI 10.1017/S0962492900002932
Lloyd N. Trefethen and S. J. Chapman, Wave packet pseudomodes of twisted Toeplitz matrices, Comm. Pure Appl. Math. 57 (2004), no. 9, 1233–1264. MR 2059680, DOI 10.1002/cpa.20034
Lloyd N. Trefethen and Mark Embree, Spectra and pseudospectra, Princeton University Press, Princeton, NJ, 2005. The behavior of nonnormal matrices and operators. MR 2155029, DOI 10.1515/9780691213101
Sergei Treil, An operator Corona theorem, Indiana Univ. Math. J. 53 (2004), no. 6, 1763–1780. MR 2106344, DOI 10.1512/iumj.2004.53.2640
Maciej Zworski, Resonances in physics and geometry, Notices Amer. Math. Soc. 46 (1999), no. 3, 319–328. MR 1668841