×
Ahmad, Fayyaz; Al-Aidarous, Eman Salem; Alrehaili, Dina Abdullah; Ekström, Sven-Erik; Furci, Isabella; Serra-Capizzano, Stefano

Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form? (English) Zbl 1398.65055

Numer. Algorithms 78, No. 3, 867-893 (2018).
Summary: In [J. Math. Anal. Appl. 422, No. 2, 1308–1334 (2015; Zbl 1302.65086)], J. M. Bogoya et al. recently obtained the precise asymptotic expansion for the eigenvalues of a sequence of Toeplitz matrices \(\{T_n(f)\}\), under suitable assumptions on the associated generating function \(f\). In this paper, we provide numerical evidence that some of these assumptions can be relaxed and extended to the case of a sequence of preconditioned Toeplitz matrices \(\{T_n^{-1}(g)T_n(f)\}\), for \(f\) trigonometric polynomial, \(g\) nonnegative, not identically zero trigonometric polynomial, \(r = f/g\), and where the ratio \(r\) plays the same role as \(f\) in the nonpreconditioned case. Moreover, based on the eigenvalue asymptotics, we devise an extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices with a high level of accuracy, with a relatively low computational cost, and with potential application to the computation of the spectrum of differential operators.

Cited in 8 Documents

MSC:

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

Keywords:

Toeplitz matrix; mass and stiffness matrix; eigenvalues; polynomial interpolation; extrapolation

Citations:

Zbl 1302.65086
Cite Review PDF
Full Text: DOI
Creative Commons CC license icon Creative Commons BY license icon

References:

[1] Barrera, M; Grudsky, SM, Asymptotics of eigenvalues for pentadiagonal symmetric Toeplitz matrices, Oper. Theory Adv. Appl., 259, 51-77, (2017) · Zbl 1365.15040 · doi:10.1007/978-3-319-49182-0_7
[2] Bhatia, R.: Matrix Analysis Graduate Texts in Mathematics, vol. 169. Springer, New York (1997)
[3] 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
[4] 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
[5] 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
[6] 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
[7] Böttcher, A., Silbermann, B.: Introduction to Large Truncated Toeplitz Matrices. Springer (1999) · Zbl 1067.65046
[8] Brezinski, C., Redivo Zaglia, M.: Extrapolation Methods: Theory and Practice. Elsevier Science Publishers B.V, North-Holland (1991) · Zbl 0744.65004
[9] Chan, RH; Ng, M, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38-3, 427-482, (1996) · Zbl 0863.65013 · doi:10.1137/S0036144594276474
[10] Chan, RH; Tang, P, Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comput., 15, 164-171, (1994) · Zbl 0797.65022 · doi:10.1137/0915011
[11] Di Benedetto, F; Fiorentino, G; Serra, S, C.G. preconditioning for Toeplitz matrices, Comput. Math. Appl., 25-6, 33-45, (1993) · Zbl 0782.65063
[12] Ekström, S.-E., Serra-Capizzano, S.: Eigenvalues and Eigenvectors of Banded Toeplitz Matrices and the Related Symbols. Technical report, 2017-010, Department of Information Technology Uppsala University (2017) · Zbl 0782.65063
[13] 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 (2017). https://doi.org/10.1080/10586458.2017.1320241 · Zbl 0797.65022
[14] Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications, vol. I. Springer (2017) · Zbl 1376.15002
[15] Huckle, T; Serra-Capizzano, S; Tablino-Possio, C, Preconditioning strategies for non-Hermitian Toeplitz linear systems, Numer. Linear Algebra Appl., 12-2/3, 211-220, (2005) · Zbl 1164.65394 · doi:10.1002/nla.396
[16] Huckle, T; Serra-Capizzano, S; Tablino-Possio, C, Preconditioning strategies for Hermitian indefinite Toeplitz linear systems, SIAM. J. Sci. Comput., 25-5, 1633-1654, (2004) · Zbl 1067.65046 · doi:10.1137/S1064827502416332
[17] Serra-Capizzano, S, New PCG based algorithms for the solution of Hermitian Toeplitz systems, Calcolo, 32, 53-176, (1995) · Zbl 0882.65019
[18] Serra-Capizzano, S, Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp., 66-218, 651-665, (1997) · Zbl 0864.65019 · doi:10.1090/S0025-5718-97-00833-8
[19] 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
[20] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, 3rd edn. Springer (2002) · Zbl 1004.65001
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.