Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices. (English) Zbl 1405.65051

Ekström, Sven-Erik; Furci, Isabella; Serra-Capizzano, Stefano

BIT 58, No. 4, 937-968 (2018).

Authors’ abstract: Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix \(T_n(f)\), as the matrix size \(n\) tends to infinity, have recently been obtained, under suitable assumptions on the associated generating function \(f\). A restriction is that \(f\) has to be polynomial, monotone, and scalar-valued. In this paper we focus on the case where \(\mathbf f\) is an \(s \times s\) matrix-valued trigonometric polynomial with \(s \geq 1\), and \(T-N(\mathbf f)\) is the block Toeplitz matrix generated by \(\mathbf f\), whose size is \(N(n,s)=sn\). The case \(s=1\) corresponds to that already treated in the literature. We numerically derive conditions which ensure the existence of an asymptotic expansion for the eigenvalues. Such conditions generalize those known for the scalar-valued setting. Furthermore, following a proposal in the scalar-valued case by the first author, Garoni, and the third author, we devise an extrapolation algorithm for computing the eigenvalues of banded symmetric block Toeplitz matrices with a high level of accuracy and a low computational cost. The resulting algorithm is an eigensolver that does not need to store the original matrix, does not need to perform matrix-vector products, and for this reason is called matrix-less. We use the asymptotic expansion for the efficient computation of the spectrum of special block Toeplitz structures and we provide exact formulae for the eigenvalues of the matrices coming from the \(\mathbb Q_p\) Lagrangian finite element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.

Reviewer: Giovanni Barbarino (Pisa)

MSC:

65F15	Numerical computation of eigenvalues and eigenvectors of matrices
15B05	Toeplitz, Cauchy, and related matrices
65B05	Extrapolation to the limit, deferred corrections

Keywords:

eigenvalues; Toeplitz matrix; polynomial interpolation; extrapolation; block matrices; asymptotic eigenvalue expansion

References:

[1]	Ahmad, F.; Al-Aidarous, ES; Abdullah Alrehaili, D.; Ekström, S-E; Furci, I.; Serra-Capizzano, S., Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?, Numer. Algorithms, 78, 867-893, (2018) · Zbl 1398.65055 · doi:10.1007/s11075-017-0404-z
[2]	Barrera, M.; Böttcher, A.; Grudsky, SM; Maximenko, EA, Eigenvalues of even very nice Toeplitz matrices can be unexpectedly erratic, Operator Theory Adv. Appl., 268, 51-77, (2018) · doi:10.1007/978-3-319-75996-8_2
[3]	Bhatia, R.: Matrix Analysis. Springer, New York (1997) · doi:10.1007/978-1-4612-0653-8
[4]	Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52-53, 99-126, (1983) · Zbl 0549.15005 · doi:10.1016/0024-3795(83)80009-3
[5]	Bogoya, JM; 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
[6]	Bogoya, JM; 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 · doi:10.1007/978-3-319-49182-0_11
[7]	Bozzo, E.; Fiore, C., On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition SIAM, J. Matrix Anal. Appl., 16, 312-326, (1995) · Zbl 0819.65017 · doi:10.1137/S0895479893245103
[8]	Brezinski, C., Redivo, Zaglia M.: Extrapolation Methods: Theory and Practice. Elsevier Science Publishers B.V, Amsterdam (1991) · Zbl 0744.65004
[9]	Böttcher, A.; Grudsky, SM; Maximenko, EA, Inside the eigenvalues of certain Hermitian Toeplitz band matrices, J. Comput. Appl. Math., 233, 2245-2264, (2010) · Zbl 1195.15009 · doi:10.1016/j.cam.2009.10.010
[10]	Benedetto, F.; Fiorentino, G.; Serra, S., C.G. Preconditioning for Toeplitz matrices, Comput. Math. Appl., 25, 33-45, (1993) · Zbl 0782.65063 · doi:10.1016/0898-1221(93)90297-9
[11]	Donatelli, M.; Neytcheva, M.; Serra-Capizzano, S., Canonical eigenvalue distribution of multilevel block Toeplitz sequences with non-Hermitian symbols, Oper. Theory Adv. Appl., 221, 269-291, (2012) · Zbl 1261.15011
[12]	Ekström S.-E.: Matrix-less Methods for Computing Eigenvalues of Large Structured Matrices. Ph.D. Thesis, Uppsala University, (2018)
[13]	Ekström, Sven-Erik; Furci, Isabella; Garoni, Carlo; Manni, Carla; Serra-Capizzano, Stefano; Speleers, Hendrik, Are the eigenvalues of the B-spline isogeometric analysis approximation of − Δ u = λ u known in almost closed form?, Numerical Linear Algebra with Applications, 25, e2198, (2018) · Zbl 1513.65454 · doi:10.1002/nla.2198
[14]	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. Algorithms. https://doi.org/10.1007/s11075-018-0508-0. · Zbl 1455.65051
[15]	Ekström, S.-E., Garoni, C., Serra-Capizzano, S.: Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form? Exp. Math. (in press). https://doi.org/10.1080/10586458.2017.1320241 · Zbl 1405.15037
[16]	Ekström, S.-E.; Serra-Capizzano, S., Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols, Numerical Linear Algebra with Applications, 25, e2137, (2018) · Zbl 1513.65095 · doi:10.1002/nla.2137
[17]	Garoni, C., Serra-Capizzano, S.: The Theory of Generalized Locally Toeplitz Sequences: Theory and Applications, Vol. I. Springer—Springer Monographs in Mathematics, Berlin (2017) · Zbl 1376.15002 · doi:10.1007/978-3-319-53679-8
[18]	Garoni, C.; Serra-Capizzano, S.; Sesana, D., Spectral analysis and spectral symbol of \(d\)-variate \(\mathbb{Q}_{\varvec {p}}\) Lagrangian FEM stiffness matrices, SIAM J. Matrix Anal. Appl., 36, 1100-1128, (2015) · Zbl 1321.65173 · doi:10.1137/140976480
[19]	Serra-Capizzano, S., Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl., 20-1, 31-44, (1999) · Zbl 0932.65037
[20]	Serra-Capizzano, S., Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT, 39-1, 152-175, (1999) · Zbl 0917.65031 · doi:10.1023/A:1022329526925
[21]	Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, 3rd edn. Springer, New York (2002) · Zbl 1004.65001 · doi:10.1007/978-0-387-21738-3
[22]	Tilli, P., A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra, 45, 147-159, (1998) · Zbl 0951.65033 · doi:10.1080/03081089808818584
[23]	Tilli, P., Some results on complex Toeplitz eigenvalues, J. Math. Anal. Appl., 239, 390-401, (1999) · Zbl 0935.15002 · doi:10.1006/jmaa.1999.6572