On functions of quasi-Toeplitz matrices

D. A. Bini   ; S. Massei   ; B. Meini

Sbornik. Mathematics, Tome 208 (2017) no. 11, pp. 1628-1645

Résumé

Let $a(z)=\sum_{i\in\mathbb Z}a_iz^i$ be a complex-valued function, defined for $|z|=1$, such that $\sum_{i=-\infty}^{+\infty} |ia_i|<\infty$. Consider the semi-infinite Toeplitz matrix $T(a)=(t_{i,j})_{i,j\in\mathbb Z^+}$ associated with the symbol $a(z)$ such that $t_{i,j}=a_{j-i}$. A quasi-Toeplitz matrix associated with the symbol $a(z)$ is a matrix of the form $A=T(a)+E$ where $E=(e_{i,j})$, $\sum_{i,j\in\mathbb Z^+}|e_{i,j}|<\infty$, and is called a $\mathrm{QT}$-matrix. Given a function $f(x)$ and a $\mathrm{QT}$-matrix $M$, we provide conditions under which $f(M)$ is well defined and is a $\mathrm{QT}$-matrix. Moreover, we introduce a parametrization of $\mathrm{QT}$-matrices and algorithms for the computation of $f(M)$. We treat the case where $f(x)$ is given in terms of power series and the case where $f(x)$ is defined in terms of a Cauchy integral. This analysis is also applied to finite matrices which can be written as the sum of a Toeplitz matrix and a low rank correction. Bibliography: 27 titles.

Détail

Keywords: matrix functions, Toeplitz matrices
Mots-clés : infinite matrices.

Bibliographie

[1] B. Beckermann, A. Townsend, On the singular values of matrices with displacement structure, 2016, arXiv: 1609.09494

[2] M. Benzi, P. Boito, “Decay properties for functions of matrices over $C^*$-algebras”, Linear Algebra Appl., 456 (2014), 174–198 | DOI | MR | Zbl

[3] M. Benzi, V. Simoncini, “Decay bounds for functions of Hermitian matrices with banded or Kronecker structure”, SIAM J. Matrix Anal. Appl., 36:3 (2015), 1263–1282 | DOI | MR | Zbl

[4] D. Bertaccini, F. Di Benedetto, “Spectral analysis of nonsymmetric quasi-Toeplitz matrices with applications to preconditioned multistep formulas”, SIAM J. Numer. Anal., 45:6 (2007), 2345–2367 | DOI | MR | Zbl

[5] Large truncated Toeplitz matrices, Toeplitz operators, and related topics, Oper. Theory Adv. Appl., 259, eds. D. A. Bini, T. Ehrhardt, A. Yu. Karlovich, I. Spitkovsky, Birkhäuser/Springer, Cham, 2017, xxvi+740 pp. | DOI | MR | Zbl

[6] D. A. Bini, S. Dendievel, G. Latouche, B. Meini, “Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues”, Linear Algebra Appl., 502 (2016), 387–419 | DOI | MR | Zbl

[7] D. A. Bini, S. Massei, B. Meini, Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes, 2016, arXiv: 1611.06337

[8] D. A. Bini, B. Meini, On the exponential of semi-infinite quasi-Toeplitz matrices, 2016, arXiv: 1611.06380

[9] A. Böttcher, S. M. Grudsky, Toeplitz matrices, asymptotic linear algebra, and functional analysis, Birkhäuser Verlag, Basel, 2000, x+116 pp. | DOI | MR | Zbl

[10] A. Böttcher, S. M. Grudsky, Spectral properties of banded Toeplitz matrices, SIAM, Philadelphia, PA, 2005, x+411 pp. | DOI | MR | Zbl

[11] A. Böttcher, B. Silbermann, Introduction to large truncated Toeplitz matrices, Springer Science Business Media, New York, 2012, 259 pp. | DOI | MR | Zbl

[12] R. Hon-Fu Chan, Xiao-Qing Jin, An introduction to iterative Toeplitz solvers, Fundam. Algorithms, 5, SIAM, Philadelphia, PA, 2007, xii+111 pp. | DOI | MR | Zbl

[13] L. A. Coburn, “Weyl's theorem for nonnormal operators”, Michigan Math. J., 13:3 (1966), 285–288 | DOI | MR | Zbl

[14] Four short courses on harmonic analysis. Wavelets, frames, time-frequency methods, and applications to signal and image analysis, Appl. Numer. Harmon. Anal., eds. B. Forster, P. Massopust, Birkhäuser Boston, Inc., Boston, MA, 2010, xviii+247 pp. | DOI | MR | Zbl

[15] M. I. Gil', “Estimates for entries of matrix valued functions of infinite matrices”, Math. Phys. Anal. Geom., 11:2 (2008), 175–186 | DOI | MR | Zbl

[16] U. Grenander, G. Szegö, Toeplitz forms and their applications, AMS Chelsea Publishing Series, 321, reprint, Univ. of California Press, Berkeley–Los Angeles, 2001, 245 pp. | MR | MR | Zbl | Zbl

[17] P. Henrici, Applied and computational complex analysis, v. 1, Pure and Applied Mathematics, Power series–integration–conformal mapping–location of zeros, Wiley-Interscience [John Wiley Sons], New York–London–Sydney, 1974, xv+682 pp. | MR | Zbl

[18] N. J. Higham, Functions of matrices. Theory and computation, SIAM, Philadelphia, PA, 2008, xx+425 pp. | DOI | MR | Zbl

[19] Fast reliable algorithms for matrices with structure, eds. T. Kailath, A. H. Sayed, SIAM, Philadelphia, PA, 1999, xvi+342 pp. | DOI | MR | Zbl

[20] D. Kressner, R. Luce, Fast computation of the matrix exponential for a Toeplitz matrix, 2016, arXiv: 1607.01733

[21] A. McIntosh, Operator theory – spectra and functional calculi, Lecture notes taken by Lashi Bandara, 2010, 74 pp. maths-people.anu.edu.au/~alan/lectures/optheory.pdf

[22] S. Pozza, V. Simoncini, Decay bounds for non-Hermitian matrix functions, 2016, arXiv: 1605.01595v3

[23] S. Serra Capizzano, “Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations”, Linear Algebra Appl., 366 (2003), 371–402 | DOI | MR | Zbl

[24] S. Serra Capizzano, E. Tyrtyshnikov, “How to prove that a preconditioner cannot be superlinear”, Math. Comp., 72:243 (2003), 1305–1316 | DOI | MR | Zbl

[25] Meiyue Shao, “On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices”, Linear Algebra Appl., 451 (2014), 65–96 | DOI | MR | Zbl

[26] E. E. Tyrtyshnikov, “A unifying approach to some old and new theorems on distribution and clustering”, Linear Algebra Appl., 232 (1996), 1–43 | DOI | MR | Zbl

[27] H. Widom, “On the singular values of Toeplitz matrices”, Z. Anal. Anwendungen, 8:3 (1989), 221–229 | DOI | MR | Zbl