×

On the infinite-dimensional QR algorithm. (English) Zbl 07088063

The determination of spectra of operators over infinite-dimensional spaces is well known to be a very hard computational problem. In spite of several investigations over the past many decades, one cannot determine whether a given class of operators is amenable towards computation of its spectra and eigenvectors, supplemented by results on convergence rates and error estimates. One may observe that such problems arise frequently in one application problem or the other warranting a theoretical study as well as computational procedures. The authors of this very interesting work address the question as to which classes of operators allow for computations of spectra along with a study on convergence rates and error control. As an answer, they prove a generalization of the QR algorithm for infinite matrices satisfying the condition that each column has finitely many nonzero entries. The proposed algorithm is executable on a finite machine and it is shown that one may recover the extremal parts of the spectrum and the corresponding eigenvectors, together with results on convergence rates and error control. A variety of numerical illustrations are presented and a comparative study is made. Examples include Toeplitz/Laurent operators and their perturbations, PT-symmetry in quantum mechanics, Hopping sign models in sparse neural networks and a NSA Anderson model in superconductors. The proposed infinite dimensional QR algorithm is shown to perform better than what is predicted theoretically, in some cases.

MSC:

65J10 Numerical solutions to equations with linear operators
47A10 Spectrum, resolvent
46N40 Applications of functional analysis in numerical analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amir, A., Hatano, N., Nelson, D.R.: Non-Hermitian localization in biological networks. Phys. Rev. E 93(4), 042310 (2016) · doi:10.1103/PhysRevE.93.042310
[2] Anderson, P.W.: Absence of diffusion in certain random lattices. Phys. Rev. 109(5), 1492 (1958) · doi:10.1103/PhysRev.109.1492
[3] Aronszajn, N.: Approximation methods for Eigenvalues of completely continuous symmetric operators. In: Proceedings of the Symposium on Spectral Theory and Differential Problems, pp. 179-202 (1951)
[4] Arveson, W.: Improper filtrations for \[C^*C\]∗-algebras: spectra of unilateral tridiagonal operators. Acta Sci. Math. (Szeged) 57(1-4), 11-24 (1993) · Zbl 0819.46044
[5] Arveson, W.: Noncommutative spheres and numerical quantum mechanics. In: Operator Algebras, Mathematical Physics, and Low-dimensional Topology (Istanbul, 1991), Research Notes in Mathematics, vol. 5, A K Peters, Wellesley, pp. 1-10 (1993)
[6] Arveson, \[W.: C^*C\]∗-algebras and numerical linear algebra. J. Funct. Anal. 122(2), 333-360 (1994) · Zbl 0802.46069 · doi:10.1006/jfan.1994.1072
[7] Arveson, W.: The role of \[C^\ast C\]*-algebras in infinite-dimensional numerical linear algebra. \[In: C^\ast C\]*-algebras: 1943-1993 (San Antonio, TX, 1993), Contemporary Mathematics, vol. 167, Amer. Math. Soc., Providence, RI, pp. 114-129 (1994) · Zbl 0817.46051
[8] Ben-Artzi, J., Colbrook, M.J., Hansen, A.C., Nevanlinna, O., Seidel, M.: On the Solvability Complexity Index Hierarchy and Towers of Algorithms (Preprint) (2018)
[9] Ben-Artzi, J., Hansen, A.C., Nevanlinna, O., Seidel, M.: New barriers in complexity theory: on the solvability complexity index and the towers of algorithms. Comput. Rend. Math. 353(10), 931-936 (2015) · Zbl 1343.68078 · doi:10.1016/j.crma.2015.08.002
[10] Bender, C.M.: Making sense of non-Hermitian Hamiltonians. Rep. Prog. Phys. 70(6), 947 (2007) · doi:10.1088/0034-4885/70/6/R03
[11] Bender, C.M., Boettcher, S.: Real spectra in non-Hermitian Hamiltonians having PT symmetry. Phys. Rev. Lett. 80(24), 5243 (1998) · Zbl 0947.81018 · doi:10.1103/PhysRevLett.80.5243
[12] Billy, J., Josse, V., Zuo, Z., Bernard, A., Hambrecht, B., Lugan, P., Clément, D., Sanchez-Palencia, L., Bouyer, P., Aspect, A.: Direct observation of Anderson localization of matter waves in a controlled disorder. Nature 453(7197), 891-894 (2008) · doi:10.1038/nature07000
[13] Bögli, S., Brown, B.M., Marletta, M., Tretter, C., Wagenhofer, M.: Guaranteed resonance enclosures and exclosures for atoms and molecules. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 470, no. 2171 (2014) · Zbl 1371.81347
[14] Böttcher, A.: Pseudospectra and singular values of large convolution operators. J. Integral Equ. Appl. 6(3), 267-301 (1994) · Zbl 0819.45002 · doi:10.1216/jiea/1181075815
[15] Böttcher, A.: Infinite matrices and projection methods. In: Lectures on Operator Theory and Its Applications (Waterloo, ON, 1994), Fields Institute Monographs, vol. 3, Amer. Math. Soc., Providence, pp. 1-72 (1996) · Zbl 0842.65032
[16] Böttcher, A., Brunner, H., Iserles, A., Nørsett, S.P.: On the singular values and eigenvalues of the Fox-Li and related operators. N. Y. J. Math. 16, 539-561 (2010) · Zbl 1233.47022
[17] Böttcher, A., Chithra, A.V., Namboodiri, M.N.N.: Approximation of approximation numbers by truncation. Integral Equ. Oper. Theory 39(4), 387-395 (2001) · Zbl 1021.47009 · doi:10.1007/BF01203320
[18] Böttcher, A., Silbermann, B.: Introduction to Large Truncated Toeplitz Matrices. Springer, New York (1999) · Zbl 0916.15012 · doi:10.1007/978-1-4612-1426-7
[19] Böttcher, A., Spitkovsky, I.M.: A gentle guide to the basics of two projections theory. Linear Algebra Appl. 432(6), 1412-1459 (2010) · Zbl 1189.47073 · doi:10.1016/j.laa.2009.11.002
[20] Boulton, L.: Projection methods for discrete Schrödinger operators. Proc. Lond. Math. Soc. 88(2), 526-544 (2004) · Zbl 1063.47023 · doi:10.1112/S0024611503014448
[21] Brown, N.: Quasi-diagonality and the finite section method. Math. Comput. 76(257), 339-360 (2007) · Zbl 1113.65057 · doi:10.1090/S0025-5718-06-01893-X
[22] Brunner, H., Iserles, A., Nørsett, S.P.: The computation of the spectra of highly oscillatory Fredholm integral operators. J. Integral Equ. Appl. 23(4), 467-519 (2011) · Zbl 1238.65123 · doi:10.1216/JIE-2011-23-4-467
[23] Chandler-Wilde, S., Chonchaiya, R., Lindner, M.: Eigenvalue problem meets Sierpinski triangle: computing the spectrum of a non-self-adjoint random operator. Oper. Matrices 5(4), 633-648 (2011) · Zbl 1301.47050 · doi:10.7153/oam-05-46
[24] Colbrook, M.J., Roman, B., Hansen, A.: How to Compute Spectra with Error Control (Preprint) (2019)
[25] Davies, E.B.: Spectral enclosures and complex resonances for general self-adjoint operators. LMS J. Comput. Math. 1, 42-74 (1998) · Zbl 0931.47021 · doi:10.1112/S1461157000000140
[26] Davies, E.B.: Linear Operators and Their Spectra, vol. 106. Cambridge University Press, Cambridge (2007) · Zbl 1138.47001 · doi:10.1017/CBO9780511618864
[27] Dean, C., Wang, L., Maher, P., Forsythe, C., Ghahari, F., Gao, Y., Katoch, J., Ishigami, M., Moon, P., Koshino, M., et al.: Hofstadter’s butterfly and the fractal quantum Hall effect in moire superlattices. Nature 497(7451), 598-602 (2013) · doi:10.1038/nature12186
[28] Deift, P., Li, L., Tomei, C.: Toda flows with infinitely many variables. J. Funct. Anal. 64(3), 358-402 (1985) · Zbl 0615.58016 · doi:10.1016/0022-1236(85)90065-5
[29] Digernes, T., Varadarajan, V.S., Varadhan, S.: Finite approximations to quantum systems. Rev. Math. Phys. 6(04), 621-648 (1994) · Zbl 0855.47046 · doi:10.1142/S0129055X94000213
[30] Doyle, P., McMullen, C.: Solving the quintic by iteration. Acta Math. 163(3-4), 151-180 (1989) · Zbl 0705.65036 · doi:10.1007/BF02392735
[31] Feinberg, J., Zee, A.: Non-Hermitian localization and delocalization. Phys. Rev. E 59(6), 6433 (1999) · doi:10.1103/PhysRevE.59.6433
[32] M. C. T. for MATLAB 4.5.3.12856. Advanpix LLC., Yokohama, Japan
[33] Goldsheid, I.Y., Khoruzhenko, B.A.: Distribution of eigenvalues in non-Hermitian Anderson models. Phys. Rev. Lett. 80(13), 2897 (1998) · doi:10.1103/PhysRevLett.80.2897
[34] Gray, R.M., et al.: Toeplitz and circulant matrices: a review. Found. Trends Commun. Inf. Theory 2(3), 155-239 (2006) · Zbl 1115.15021 · doi:10.1561/0100000006
[35] Hagen, R., Roch, S., Silbermann, \[B.: C^*C\]∗-algebras and numerical analysis. In: Monographs and Textbooks in Pure and Applied Mathematics, vol. 236, Marcel Dekker Inc., New York (2001) · Zbl 0964.65055
[36] Hansen, A.C.: On the approximation of spectra of linear operators on Hilbert spaces. J. Funct. Anal. 254(8), 2092-2126 (2008) · Zbl 1138.47002 · doi:10.1016/j.jfa.2008.01.006
[37] Hansen, A.C.: Infinite-dimensional numerical linear algebra: theory and applications. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 466(2124), 3539-3559 (2010) · Zbl 1211.65046 · doi:10.1098/rspa.2009.0617
[38] Hansen, A.C.: On the solvability complexity index, the n-pseudospectrum and approximations of spectra of operators. J. Am. Math. Soc. 24(1), 81-124 (2011) · Zbl 1210.47013 · doi:10.1090/S0894-0347-2010-00676-5
[39] Hatano, N., Nelson, D.R.: Localization transitions in non-Hermitian quantum mechanics. Phys. Rev. Lett. 77(3), 570 (1996) · doi:10.1103/PhysRevLett.77.570
[40] Holz, D.E., Orland, H., Zee, A.: On the remarkable spectrum of a non-Hermitian random matrix model. J. Phys. A Math. Gen. 36(12), 3385 (2003) · Zbl 1038.15016 · doi:10.1088/0305-4470/36/12/330
[41] Kato, T.: Perturbation Theory for Linear Operators, vol. 132. Springer, Berlin (2013)
[42] Krein, M., Krasnoselski, M.: Fundamental theorems concerning the extension of Hermitian operators and some of their applications to the theory of orthogonal polynomials and the moment problem. Uspekhi Mat. Nauk. 2, 60-106 (1947)
[43] Levitin, M., Shargorodsky, E.: Spectral pollution and second-order relative spectra for self-adjoint operators. IMA J. Numer. Anal. 24(3), 393-416 (2004) · Zbl 1060.65056 · doi:10.1093/imanum/24.3.393
[44] Lindner, M.: Infinite matrices and their finite sections. In: Frontiers in Mathematics: An Introduction to the Limit Operator Method, Birkhäuser Verlag, Basel (2006) · Zbl 1107.47001
[45] Makris, K.G., El-Ganainy, R., Christodoulides, D.N., Musslimani, Z.H.: Beam dynamics in PT symmetric optical lattices. Phys. Rev. Lett. 100(10), 103904 (2008) · doi:10.1103/PhysRevLett.100.103904
[46] Marletta, M.: Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum. IMA J. Numer. Anal. 30(4), 917-939 (2010) · Zbl 1206.65245 · doi:10.1093/imanum/drp017
[47] Marletta, M., Scheichl, R.: Eigenvalues in spectral gaps of differential operators. J. Spectr. Theory 2(3), 293-320 (2012) · Zbl 1256.65079 · doi:10.4171/JST/30
[48] Mattis, D.C.: The few-body problem on a lattice. Rev. Mod. Phys. 58(2), 361 (1986) · doi:10.1103/RevModPhys.58.361
[49] McMullen, C.: Families of rational maps and iterative root-finding algorithms. Ann. Math. 125(3), 467-493 (1987) · Zbl 0634.30028 · doi:10.2307/1971408
[50] McMullen, C.: Braiding of the attractor and the failure of iterative algorithms. Invent. Math. 91(2), 259-272 (1988) · Zbl 0654.58023 · doi:10.1007/BF01389368
[51] Mogilner, A.: Hamiltonians in solid state physics as multiparticle discrete Schrödinger operators. Adv. Soc. Math. 5, 139-194 (1991) · Zbl 0741.34055
[52] Nelson, D.R., Shnerb, N.M.: Non-Hermitian localization and population biology. Phys. Rev. E 58(2), 1383 (1998) · doi:10.1103/PhysRevE.58.1383
[53] Olver, S.: ApproxFun.jl v0.8. github (online). https://github.com/JuliaApproximation/ApproxFun.jl (2018)
[54] Olver, S., Townsend, A.: A fast and well-conditioned spectral method. SIAM Rev. 55(3), 462-489 (2013) · Zbl 1273.65182 · doi:10.1137/120865458
[55] Olver, S., Townsend, A.: A practical framework for infinite-dimensional linear algebra. In: Proceedings of the 1st First Workshop for High Performance Technical Computing in Dynamic Languages, HPTCDL ’14, Piscataway, NJ, USA, IEEE Press, pp. 57-62 (2014)
[56] Olver, S., Webb, M.: SpectralMeasures.jl. github (online). https://github.com/JuliaApproximation/SpectralMeasures.jl (2018)
[57] Parlett, B.N.: The Symmetric Eigenvalue Problem, vol. 20. siam, Bangkok (1998) · Zbl 0885.65039 · doi:10.1137/1.9781611971163
[58] Pokrzywa, A.: Method of orthogonal projections and approximation of the spectrum of a bounded operator. Stud. Math. 65(1), 21-29 (1979) · Zbl 0437.47004 · doi:10.4064/sm-65-1-21-29
[59] Ponomarenko, L., Gorbachev, R., Yu, G., Elias, D., Jalil, R., Patel, A., Mishchenko, A., Mayorov, A., Woods, C., Wallbank, J., et al.: Cloning of Dirac fermions in graphene superlattices. Nature 497(7451), 594-597 (2013) · doi:10.1038/nature12187
[60] Regensburger, A., Bersch, C., Miri, M.-A., Onishchukov, G., Christodoulides, D.N., Peschel, U.: Parity-time synthetic photonic lattices. Nature 488(7410), 167-171 (2012) · doi:10.1038/nature11298
[61] Riddell, R.: Spectral concentration for self-adjoint operators. Pac. J. Math. 23(2), 377-401 (1967) · Zbl 0153.16803 · doi:10.2140/pjm.1967.23.377
[62] Schmidt, P., Spitzer, F.: The Toeplitz matrices of an arbitrary Laurent polynomial. Math. Scand. 8(1), 15-38 (1960) · Zbl 0101.09203 · doi:10.7146/math.scand.a-10588
[63] Seidel, M.: On \[(N,\epsilon )(N\],ϵ)-pseudospectra of operators on Banach spaces. J. Funct. Anal. 262(11), 4916-4927 (2012) · Zbl 1307.47005 · doi:10.1016/j.jfa.2012.03.019
[64] Seidel, M., Silbermann, B.: Finite sections of band-dominated operators—norms, condition numbers and pseudospectra. In: Operator Theory, Pseudo-differential Equations, and Mathematical Physics, Operator Theory: Advances and Applications, vol. 228, Birkhauser/Springer Basel AG, Basel, pp. 375-390 (2013) · Zbl 1280.47022
[65] Shargorodsky, E.: Geometry of higher order relative spectra and projection methods. J. Oper. Theory 44(1), 43-62 (2000) · Zbl 0994.47003
[66] Shargorodsky, E.: On the limit behaviour of second order relative spectra of self-adjoint operators. J. Spectr. Theory 3, 535-552 (2013) · Zbl 1327.47003 · doi:10.4171/JST/55
[67] Shivakumar, P., Sivakumar, K., Zhang, Y.: Infinite Matrices and Their Recent Applications. Springer, Berlin (2016) · Zbl 1355.15001 · doi:10.1007/978-3-319-30180-8
[68] Simon, B.: The classical moment problem as a self-adjoint finite difference operator. Adv. Math. 137(1), 82-203 (1998) · Zbl 0910.44004 · doi:10.1006/aima.1998.1728
[69] Smale, S.: The fundamental theorem of algebra and complexity theory. Bull. Am. Math. Soc. (N.S.) 4(1), 1-36 (1981) · Zbl 0456.12012 · doi:10.1090/S0273-0979-1981-14858-8
[70] Szabo, A., Ostlund, N.S.: Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. Courier Corporation, Chelmsford (2012)
[71] Teschl, G.: Jacobi Operators and Completely Integrable Nonlinear Lattices. American Mathematical Soc, Providence (2000) · Zbl 1056.39029
[72] Trefethen, L.N., Embree, M.: Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, Princeton (2005) · Zbl 1085.15009
[73] Webb, M., Olver, S.: Spectra of Jacobi Operators Via Connection Coefficient Matrices. arXiv preprint. arXiv:1702.03095 (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.