Fast Toeplitz eigenvalue computations, joining interpolation-extrapolation matrix-less algorithms and simple-loop theory. (English) Zbl 1503.15040

Bogoya, Manuel; Ekström, Sven-Erik; Serra-Capizzano, Stefano

Numer. Algorithms 91, No. 4, 1653-1676 (2022).

Authors’ abstract: Under appropriate technical assumptions, the simple-loop theory allows to derive various types of asymptotic expansions for the eigenvalues of Toeplitz matrices generated by a function \(f\). Independently and under the milder hypothesis that \(f\) is even and monotone over \([0, \pi]\), matrix-less algorithms have been developed for the fast eigenvalue computation of large Toeplitz matrices, within a linear complexity in the matrix order: behind the high efficiency of such algorithms there are the expansions predicted by the simple-loop theory, combined with the extrapolation idea. Here we focus our attention on a change of variable, followed by the asymptotic expansion of the new variable, and we adapt the matrix-less algorithm to the considered new setting. Numerical experiments show a higher precision (till machine precision) and the same linear computation cost, when compared with the matrix-less procedures already presented in the relevant literature. Among the advantages, we concisely mention the following: (a) when the coefficients of the simple-loop function are analytically known, the algorithm computes them perfectly; (b) while the proposed algorithm is better or at worst comparable to the previous ones for computing the inner eigenvalues, it is vastly better for the computation of the extreme eigenvalues; a mild deterioration in the quality of the numerical experiments is observed when dense Toeplitz matrices are considered, having generating function of low smoothness and not satisfying the simple-loop assumptions.

Reviewer: Anton Iliev (Plovdiv)

MSC:

15B05	Toeplitz, Cauchy, and related matrices
65F15	Numerical computation of eigenvalues and eigenvectors of matrices
65D05	Numerical interpolation
47B35	Toeplitz operators, Hankel operators, Wiener-Hopf operators
15A18	Eigenvalues, singular values, and eigenvectors
41A60	Asymptotic approximations, asymptotic expansions (steepest descent, etc.)

Keywords:

eigenvalue computation; Toeplitz matrix; matrix-less method; asymptotic expansion

References:

[1]	Ekström, S-E; Garoni, C.; Serra-Capizzano, S., Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?, Exper. Math., 27, 4, 478-487 (2018) · Zbl 1405.15037 · doi:10.1080/10586458.2017.1320241
[2]	Ahmad, F.; Al-Aidarous, ES; Alrehaili, DA; Ekström, S-E; Furci, I.; Serra-Capizzano, S., Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?, Numer. Algo., 78, 3, 867-893 (2018) · Zbl 1398.65055 · doi:10.1007/s11075-017-0404-z
[3]	Ekström, S-E; Furci, I.; Garoni, C.; Manni, C.; Serra-Capizzano, S.; Speleers, H., Are the eigenvalues of the B-spline isogeometric analysis approximation of −Δu = λu known in almost closed form?, Numer. Linear Algebra Appl., 25, 5, 2198-34 (2018) · Zbl 1513.65454 · doi:10.1002/nla.2198
[4]	Ekström, S-E; Furci, I.; Serra-Capizzano, S., Exact formulae and matrix-less eigensolvers for block banded Toeplitz-like matrices, BIT, 58, 4, 937-968 (2018) · Zbl 1405.65051 · doi:10.1007/s10543-018-0715-z
[5]	Ekström, S-E; Garoni, C., A matrix-less and parallel interpolation-extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices, Numer. Algor., 80, 819-848 (2019) · Zbl 1455.65051 · doi:10.1007/s11075-018-0508-0
[6]	Bogoya, M.; Böttcher, A.; Grudsky, SM; Maximenko, EA, Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols, J. Math. Anal. Appl., 422, 1308-1334 (2015) · Zbl 1302.65086 · doi:10.1016/j.jmaa.2014.09.057
[7]	Bogoya, M.; Böttcher, A.; Grudsky, SM; Maximenko, EA, Eigenvectors of Hermitian Toeplitz matrices with smooth simple-loop symbols, Linear Algebra Appl., 493, 606-637 (2016) · Zbl 1331.47046 · doi:10.1016/j.laa.2015.12.017
[8]	Böttcher, A.; Bogoya, M.; Grudsky, SM; Maksimenko, EA, Asymptotics of the eigenvalues and eigenvectors of Toeplitz matrices, Mat. Sb., 208, 11, 4-28 (2017) · Zbl 1388.15028
[9]	Barrera, M.; Böttcher, A.; Grudsky, SM; Maximenko, EA, Eigenvalues of even very nice Toeplitz matrices can be unexpectedly erratic, Oper. Theory Adv. Appl., 268, 51-77 (2018)
[10]	Bogoya, M., Serra-Capizzano, S.: Eigenvalue superposition expansion for Toeplitz matrix-sequences, generated by linear combinations of matrix-order dependent symbols, and applications to fast eigenvalue computations. arXiv:2112.11794 (2022)
[11]	Barbarino, G.; Garoni, C.; Serra-Capizzano, S., Block generalized locally Toeplitz sequences: Theory and applications in the multidimensional case, Electron. Trans. Numer. Anal., 53, 113-216 (2020) · Zbl 1434.65033 · doi:10.1553/etna_vol53s113
[12]	Barbarino, G.; Garoni, C.; Serra-Capizzano, S., Block generalized locally Toeplitz sequences: theory and applications in the unidimensional case, Electron. Trans. Numer. Anal., 53, 28-112 (2020) · Zbl 1434.65032 · doi:10.1553/etna_vol53s28
[13]	Böttcher, A.; Silbermann, B., Introduction to large truncated Toeplitz matrices. Universitext, 258-258 (1999), Berlin: Springer, Berlin · Zbl 0916.15012 · doi:10.1007/978-1-4612-1426-7
[14]	Garoni, C.; Serra-Capizzano, S., Generalized locally Toeplitz sequences: theory and applications, vol. I (2017), Berlin: Springer, Berlin · Zbl 1376.15002 · doi:10.1007/978-3-319-53679-8
[15]	Garoni, C.; Serra-Capizzano, S., Generalized locally Toeplitz sequences: theory and applications, vol. II (2018), Berlin: Springer, Berlin · Zbl 1448.47004 · doi:10.1007/978-3-030-02233-4
[16]	Grenander, U.; Szegő, G., Toeplitz forms and their applications. California Monographs in Mathematical Sciences (1984), New York: Chelsea Publishing Co, New York · Zbl 0611.47018
[17]	Tyrtyshnikov, EE; Zamarashkin, NL, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl., 270, 15-27 (1998) · Zbl 0890.15006 · doi:10.1016/S0024-3795(97)80001-8
[18]	Serra-Capizzano, S., The extension of the concept of the generating function to a class of preconditioned Toeplitz matrices, Linear Algebra Appl., 267, 139-161 (1997) · Zbl 0933.65038 · doi:10.1016/S0024-3795(97)82204-5
[19]	Bogoya, M.; Grudsky, SM; Maximenko, EA, Eigenvalues of Hermitian Toeplitz matrices generated by simple-loop symbols with relaxed smoothness, Oper. Theory Adv. Appl., 259, 179-212 (2017) · Zbl 1468.15007
[20]	Stoer, J.; Bulirsch, R., Introduction to Numerical Analysis (2010), Berlin: Springer, Berlin · Zbl 0423.65002
[21]	Davis, PJ, Interpolation and approximation (1975), New York: Dover, New York · Zbl 0329.41010
[22]	Kac, M.; Murdock, WL; Szegő, G., On the eigenvalues of certain Hermitian forms, J. Rational Mech. Anal., 2, 767-800 (1953) · Zbl 0051.30302
[23]	Trench, WF, Asymptotic distribution of the spectra of a class of generalized kac-Murdock-Szegő matrices, Linear Algebra Appl., 294, 181-192 (1999) · Zbl 0942.15006 · doi:10.1016/S0024-3795(99)00080-4
[24]	Trench, W.F.: Spectral decomposition of Kac-Murdock-Szegő matrices. The selected works of William F. Trench. http://works.bepress.com/william_trench/133(2010)
[25]	Barrera, M.; Grudsky, SM, Asymptotics of eigenvalues for pentadiagonal symmetric Toeplitz matrices, Oper. Theory Adv. Appl., 259, 51-77 (2017) · Zbl 1365.15040
[26]	Serra-Capizzano, S., An ergodic theorem for classes of preconditioned matrices, Linear Algebra Appl., 282, 1-3, 161-183 (1998) · Zbl 0935.65026 · doi:10.1016/S0024-3795(98)80002-5