Pseudoergodic operators and periodic boundary conditions

Colbrook, Matthew

doi:10.1090/mcom/3475

Pseudoergodic operators and periodic boundary conditions
HTML articles powered by AMS MathViewer

by Matthew J. Colbrook HTML | PDF

Math. Comp. 89 (2020), 737-766 Request permission

Abstract:

There is an increasing literature on random non-self-adjoint infinite matrices with motivations ranging from condensed matter physics to neural networks. Many of these operators fall into the class of “pseudoergodic” operators, which allows the elimination of probabilistic arguments when studying spectral properties. Parallel to this is the increased awareness that spectral properties of non-self-adjoint operators, in particular stability, may be better captured via the notion of pseudospectra as opposed to spectra. Although it is well known that the finite section method applied to these matrices does not converge to the spectrum, it is often found in practice that the pseudospectrum behaves better with appropriate boundary conditions. We make this precise by giving a simple proof that the finite section method with periodic boundary conditions converges to the pseudospectrum of the full operator. Our results hold in any dimension (not just for banded bi-infinite matrices) and can be considered as a generalisation of the well-known classical result for banded Laurent operators and their circulant approximations. Furthermore, we numerically demonstrate a convergent algorithm for the pseudospectrum, including cases where periodic boundary conditions converge faster than the method of uneven sections. Finally, we show that the result carries over to pseudoergodic operators acting on $l^p$ spaces for $p\in [1,\infty ]$.

References

Ariel Amir, Naomichi Hatano, and David R. Nelson, Non-Hermitian localization in biological networks, Phys. Rev. E 93 (2016), no. 4, 042310, 20. MR 3704458, DOI 10.1103/physreve.93.042310
P. W. Anderson, Absence of diffusion in certain random lattices, Physical Review 109 (1958), no. 5, 1492.
P. W. Anderson, Localized magnetic states in metals, Phys. Rev. (2) 124 (1961), 41–53. MR 129917
W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 (1951), 17–29. MR 42792, DOI 10.1090/S0033-569X-1951-42792-9
William Arveson, Noncommutative spheres and numerical quantum mechanics, Operator algebras, mathematical physics, and low-dimensional topology (Istanbul, 1991) Res. Notes Math., vol. 5, A K Peters, Wellesley, MA, 1993, pp. 1–10. MR 1259055
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
Siegfried Beckus, Daniel Lenz, Marko Lindner, and Christian Seifert, On the spectrum of operator families on discrete groups over minimal dynamical systems, Math. Z. 287 (2017), no. 3-4, 993–1007. MR 3719524, DOI 10.1007/s00209-017-1856-5
Jonathan Ben-Artzi, M. J. Colbrook, Anders C. Hansen, Olavi Nevanlinna, and Markus Seidel, On the Solvability Complexity Index hierarchy and towers of algorithms, arXiv:1508.03280v2 (2019).
Matthew J. Colbrook and Anders C. Hansen, On the infinite-dimensional QR algorithm, Numer. Math. 143 (2019), no. 1, 17–83. MR 3987167, DOI 10.1007/s00211-019-01047-5
Christine Bernardi and Yvon Maday, Approximations spectrales de problèmes aux limites elliptiques, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 10, Springer-Verlag, Paris, 1992 (French, with French summary). MR 1208043
M. V. Berry, Mode degeneracies and the Petermann excess-noise factor for unstable lasers, Journal of Modern Optics 50 (2003), no. 1, 63–81.
M. V. Berry and J. P. Keating, The Riemann zeros and eigenvalue asymptotics, SIAM Rev. 41 (1999), no. 2, 236–266. MR 1684543, DOI 10.1137/S0036144598347497
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
A. Böttcher, M. Embree, and M. Lindner, Spectral approximation of banded Laurent matrices with localized random perturbations, Integral Equations Operator Theory 42 (2002), no. 2, 142–165. MR 1870436, DOI 10.1007/BF01275512
A. Böttcher, M. Embree, and V. I. Sokolov, The spectra of large Toeplitz band matrices with a randomly perturbed entry, Math. Comp. 72 (2003), no. 243, 1329–1348. MR 1972739, DOI 10.1090/S0025-5718-03-01505-9
A. Böttcher, M. Embree, and V. I. Sokolov, Infinite Toeplitz and Laurent matrices with localized impurities, Linear Algebra Appl. 343/344 (2002), 101–118. Special issue on structured and infinite systems of linear equations. MR 1878938, DOI 10.1016/S0024-3795(01)00343-3
A. Böttcher, M. Embree, and V. I. Sokolov, On large Toeplitz band matrices with an uncertain block, Linear Algebra Appl. 366 (2003), 87–97. Special issue on structured matrices: analysis, algorithms and applications (Cortona, 2000). MR 1987715, DOI 10.1016/S0024-3795(02)00501-3
Albrecht Böttcher, Mark Embree, and Lloyd N. Trefethen, Piecewise continuous Toeplitz matrices and operators: slow approach to infinity, SIAM J. Matrix Anal. Appl. 24 (2002), no. 2, 484–489. MR 1951133, DOI 10.1137/S0895479800376971
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
A. Böttcher, S. M. Grudsky, and B. Silbermann, Norms of inverses, spectra, and pseudospectra of large truncated Wiener-Hopf operators and Toeplitz matrices, New York J. Math. 3 (1997), 1–31. MR 1443134
Albrecht Böttcher and Bernd Silbermann, Introduction to large truncated Toeplitz matrices, Universitext, Springer-Verlag, New York, 1999. MR 1724795, DOI 10.1007/978-1-4612-1426-7
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, Infinite matrices and projection methods, Lectures on operator theory and its applications (Waterloo, ON, 1994) Fields Inst. Monogr., vol. 3, Amer. Math. Soc., Providence, RI, 1996, pp. 1–72. MR 1364444
E. Brézin and A. Zee, Non-Hermitean delocalization: multiple scattering and bounds, Nuclear Phys. B 509 (1998), no. 3, 599–614. MR 1487025, DOI 10.1016/S0550-3213(97)00652-4
PW Brouwer, PG Silvestrov, and CWJ Beenakker, Theory of directed localization in one dimension, Physical Review B 56 (1997), no. 8, R4333.
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
Simon N. Chandler-Wilde, Ratchanikorn Chonchaiya, and Marko Lindner, Eigenvalue problem meets Sierpinski triangle: computing the spectrum of a non-self-adjoint random operator, Oper. Matrices 5 (2011), no. 4, 633–648. MR 2906853, DOI 10.7153/oam-05-46
Simon N. Chandler-Wilde, Ratchanikorn Chonchaiya, and Marko Lindner, On the spectra and pseudospectra of a class of non-self-adjoint random matrices and operators, Oper. Matrices 7 (2013), no. 4, 739–775. MR 3154570, DOI 10.7153/oam-07-43
Simon N. Chandler-Wilde and Marko Lindner, Coburn’s lemma and the finite section method for random Jacobi operators, J. Funct. Anal. 270 (2016), no. 2, 802–841. MR 3425904, DOI 10.1016/j.jfa.2015.09.019
Simon N. Chandler-Wilde and E. Brian Davies, Spectrum of a Feinberg-Zee random hopping matrix, J. Spectr. Theory 2 (2012), no. 2, 147–179. MR 2913876, DOI 10.4171/JST/25
James A. Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936), no. 3, 396–414. MR 1501880, DOI 10.1090/S0002-9947-1936-1501880-4
Mathew J. Colbrook, Bogdan Roman, and Anders C. Hansen, How to compute spectra with error control, Physical Review Letters 122 (2019), no. 25, 201–250.
K. A. Dahmen, D. R. Nelson, and N. M. Shnerb, Population Dynamics and Non-Hermitian Localization, Statistical mechanics of biocomplexity, Springer, 1999, pp. 124–151.
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, Spectral theory of pseudo-ergodic operators, Comm. Math. Phys. 216 (2001), no. 3, 687–704. MR 1815722, DOI 10.1007/s002200000352
E. B. Davies, Non-self-adjoint differential operators, Bull. London Math. Soc. 34 (2002), no. 5, 513–532. MR 1912874, DOI 10.1112/S0024609302001248
Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
J. Feinberg and A. Zee, Non-Hermitian localization and delocalization, Physical Review E 59 (1999), no. 6, 6433.
J. Feinberg and A. Zee, Spectral curves of non-Hermitian Hamiltonians, Nuclear Phys. B 552 (1999), no. 3, 599–623. MR 1704620, DOI 10.1016/S0550-3213(99)00246-1
J. Globevnik, On complex strict and uniform convexity, Proc. Amer. Math. Soc. 47 (1975), 175–178. MR 355564, DOI 10.1090/S0002-9939-1975-0355564-9
J. Globevnik, Norm-constant analytic functions and equivalent norms, Illinois J. Math. 20 (1976), no. 3, 503–506. MR 448044
I. Y. Goldsheid and B. A. Khoruzhenko, Distribution of eigenvalues in non-Hermitian Anderson models, Physical Review Letters 80 (1998), no. 13, 2897.
Ilya Ya. Goldsheid and Boris A. Khoruzhenko, Eigenvalue curves of asymmetric tridiagonal random matrices, Electron. J. Probab. 5 (2000), no. 16, 28. MR 1800072, DOI 10.1214/EJP.v5-72
R. Hagger, Fredholm Theory with Applications to Random Operators, Ph.D. thesis, Technische Universität Hamburg, 2016.
Raffael Hagger, On the spectrum and numerical range of tridiagonal random operators, J. Spectr. Theory 6 (2016), no. 2, 215–266. MR 3485943, DOI 10.4171/JST/124
Raffael Hagger, Marko Lindner, and Markus Seidel, Essential pseudospectra and essential norms of band-dominated operators, J. Math. Anal. Appl. 437 (2016), no. 1, 255–291. MR 3451966, DOI 10.1016/j.jmaa.2015.11.060
Anders C. Hansen, On the solvability complexity index, the $n$-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc. 24 (2011), no. 1, 81–124. MR 2726600, DOI 10.1090/S0894-0347-2010-00676-5
N. Hatano and D. R. Nelson, Localization transitions in non-Hermitian quantum mechanics, Physical Review Letters 77 (1996), no. 3, 570.
N. Hatano and D. R. Nelson, Vortex pinning and non-Hermitian quantum mechanics, Physical Review B 56 (1997), no. 14, 8651.
Naomichi Hatano, Takahiro Watanabe, and Junko Yamasaki, Localization, resonance and non-Hermitian quantum mechanics, Phys. A 314 (2002), no. 1-4, 170–176. Horizons in complex systems (Messina, 2001). MR 1961700, DOI 10.1016/S0378-4371(02)01070-1
Julien M. Hendrickx and Alex Olshevsky, Matrix $p$-norms are NP-hard to approximate if $p\neq 1,2,\infty$, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2802–2812. MR 2740634, DOI 10.1137/09076773X
D. E. Holz, H. Orland, and A. Zee, On the remarkable spectrum of a non-Hermitian random matrix model, J. Phys. A 36 (2003), no. 12, 3385–3400. Random matrix theory. MR 1986425, DOI 10.1088/0305-4470/36/12/330
G. F. Jónsson and L. N. Trefethen, A numerical analyst looks at the “cutoff phenomenon” in card shuffling and other Markov chains, Numerical analysis 1997 (Dundee), Pitman Res. Notes Math. Ser., vol. 380, Longman, Harlow, 1998, pp. 150–178. MR 1636951
Tosio Kato, Perturbation theory for linear operators, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR 0203473
D. Krejčiřík, P. Siegl, M. Tater, and J. Viola, Pseudospectra in non-Hermitian quantum mechanics, J. Math. Phys. 56 (2015), no. 10, 103513, 32. MR 3416732, DOI 10.1063/1.4934378
Gorazd Lešnjak, Complex convexity and finitely additive vector measures, Proc. Amer. Math. Soc. 102 (1988), no. 4, 867–873. MR 934858, DOI 10.1090/S0002-9939-1988-0934858-9
Marko Lindner, A note on the spectrum of bi-infinite bi-diagonal random matrices, Anal. Appl. (Singap.) 7 (2009), no. 3, 269–278. MR 2542739, DOI 10.1142/S0219530509001396
Marko Lindner, The finite section method and stable subsequences, Appl. Numer. Math. 60 (2010), no. 4, 501–512. MR 2607806, DOI 10.1016/j.apnum.2009.11.006
Marko Lindner and Steffen Roch, Finite sections of random Jacobi operators, SIAM J. Numer. Anal. 50 (2012), no. 1, 287–306. MR 2888314, DOI 10.1137/100813877
Marko Lindner, Infinite matrices and their finite sections, Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2006. An introduction to the limit operator method. MR 2253942
Marco Marletta, Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum, IMA J. Numer. Anal. 30 (2010), no. 4, 917–939. MR 2727810, DOI 10.1093/imanum/drp017
Marco Marletta and Rob Scheichl, Eigenvalues in spectral gaps of differential operators, J. Spectr. Theory 2 (2012), no. 3, 293–320. MR 2947289, DOI 10.4171/jst/30
Madan Lal Mehta, Random matrices, 3rd ed., Pure and Applied Mathematics (Amsterdam), vol. 142, Elsevier/Academic Press, Amsterdam, 2004. MR 2129906
Robb J. Muirhead, Aspects of multivariate statistical theory, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1982. MR 652932
D. R. Nelson and N. M. Shnerb, Non-Hermitian localization and population biology, Physical Review E 58 (1998), no. 2, 1383.
Steffen Roch and Bernd Silbermann, $C^*$-algebra techniques in numerical analysis, J. Operator Theory 35 (1996), no. 2, 241–280. MR 1401690
Markus Seidel, On $(N,\epsilon )$-pseudospectra of operators on Banach spaces, J. Funct. Anal. 262 (2012), no. 11, 4916–4927. MR 2913691, DOI 10.1016/j.jfa.2012.03.019
Markus Seidel, Fredholm theory for band-dominated and related operators: a survey, Linear Algebra Appl. 445 (2014), 373–394. MR 3151282, DOI 10.1016/j.laa.2013.11.048
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
David R. Nelson and Nadav M. Shnerb, Non-Hermitian localization and population biology, Phys. Rev. E (3) 58 (1998), no. 2, 1383–1403. MR 1637117, DOI 10.1103/PhysRevE.58.1383
Lloyd N. Trefethen, Pseudospectra of linear operators, SIAM Rev. 39 (1997), no. 3, 383–406. MR 1469941, DOI 10.1137/S0036144595295284
Lloyd N. Trefethen, Marco Contedini, and Mark Embree, Spectra, pseudospectra, and localization for random bidiagonal matrices, Comm. Pure Appl. Math. 54 (2001), no. 5, 595–623. MR 1811128, DOI 10.1002/cpa.4.abs
Lloyd N. Trefethen and Mark Embree, Spectra and pseudospectra, Princeton University Press, Princeton, NJ, 2005. The behavior of nonnormal matrices and operators. MR 2155029