Topics in the numerical linear algebra of Toeplitz and Hankel matrices. (English) Zbl 1093.47028
This survey paper treats several classical aspects related to the linear algebra of structured matrices, more specifically Toeplitz, Hankel, and Toeplitz-plus-Hankel matrices. The initial approach is operator theoretical. All the results are there: inversion formulas, Bezoutians, spectra and pseudo-spectra, condition numbers, fast algorithms, matrix factorizations.
The main results are stated but no proofs are provided. The reader is referred to the literature for details.
The main results are stated but no proofs are provided. The reader is referred to the literature for details.
Reviewer: Adhemar Bultheel (Leuven)
MSC:
| 47B35 | Toeplitz operators, Hankel operators, Wiener-Hopf operators |
| 15A09 | Theory of matrix inversion and generalized inverses |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 47-02 | Research exposition (monographs, survey articles) pertaining to operator theory |
References:
| [1] | 12 534 1991 |
| [2] | Bozzo, Algebras of higher dimension for displacement decompositions and computations with Toeplitz-plus-Hankel matrices, Linear Algebra Appl. 188/189 pp 3– (1993) · Zbl 0839.15007 |
| [3] | Böttcher, Pseudospectra and singular values of large convolution operators, J. Integral Equations Appl. 6 pp 267– (1994) · Zbl 0819.45002 · doi:10.1216/jiea/1181075815 |
| [4] | Böttcher, C*-algebras in numerical analysis, Irish Math. Soc. Bull. 45 pp 57– (2000) |
| [5] | Böttcher, Piecewise continuous Toeplitz matrices and opera- tors: slow approach to infinity, SIAM J. Matrix Analysis Appl. 24 pp 484– (2002) · Zbl 1022.47018 · doi:10.1137/S0895479800376971 |
| [6] | Böttcher, Asymptotic spectra of dense Toeplitz matrices are unstable, Numerical Algorithms 33 pp 105– (2003) · Zbl 1038.65030 · doi:10.1023/A:1025547501771 |
| [7] | A. Böttcher S. Grudsky Toeplitz matrices with slowly growing pseudospectra, in: Factorization, Singular Integral Operators, and Related Topics, edited by S. Samko, A. Lebre, and A. F. dos Santos (Kluwer, Dordrecht, 2003), pp. 43-54. · Zbl 1037.47017 · doi:10.1007/978-94-017-0227-0 |
| [8] | A. Böttcher S. Grudsky Structured condition numbers of large Toeplitz matrices are rarely better than usual condition numbers, Numer. Linear Algebra Appl., to appear. · Zbl 1164.15309 |
| [9] | A. Böttcher S. Grudsky E. Ramírez de Arellano On the asymptotic behavior of the eigenvectors of large banded Toeplitz matrices, Math. Nachr., to appear. |
| [10] | A. Böttcher B. Silbermann Introduction to Large Truncated Toeplitz Matrices (Springer, New York, 1999). |
| [11] | Delsarte, The split Levinson algorithm, IEEE Trans. Acoust. Speech Signal Process. 34 pp 470– (1986) · Zbl 0675.62067 · doi:10.1109/TASSP.1986.1164830 |
| [12] | Delsarte, On the splitting of classical algorithms in linear prediction theory, IEEE Trans. Acoust. Speech Signal Process. 35 pp 645– (1987) · doi:10.1109/TASSP.1987.1165193 |
| [13] | Demeure, Bowtie factors of Toeplitz matrices by means of split algorithms, IEEE Trans. Acoust. Speech Signal Process. 37 pp 1601– (1989) · doi:10.1109/29.35401 |
| [14] | Gohberg, On an application of the theory of normed rings to singular integral equations, Uspekhi Mat. Nauk 7 pp 149– (1952) |
| [15] | Gohberg, On the number of solutions of homogeneous singular integral equations with continuous coefficients, Dokl. Akad. Nauk SSSR 122 pp 327– (1958) |
| [16] | I. Gohberg I. A. Feldman Convolution Equations and Projection Methods for Their Solution (Amer. Math. Soc., Providence, R.I., 1974). |
| [17] | Gohberg, The inversion of finite Toeplitz matrices and their continual analogues, Matem. Issled. 7 pp 201– (1972) |
| [18] | R. Hagen S. Roch B. Silbermann C* -Algebras and Numerical Analysis (Marcel Dekker, New York, 2001). · Zbl 0964.65055 |
| [19] | Heinig, Inversion of Toeplitz and Hankel matrices with singular sections, Wiss. Zeitschrift der TH Karl-Marx-Stadt 25 pp 326– (1983) · Zbl 0567.65013 |
| [20] | Heinig, Chebyshev-Hankel matrices and the splitting approach for centrosymmetric Toeplitzplus-Hankel matrices, Linear Algebra Appl. 327 pp 181-196– (2001) · Zbl 1012.65026 · doi:10.1016/S0024-3795(00)00300-1 |
| [21] | G. Heinig Inversion of Toeplitz-plus-Hankel matrices with any rank profile, in: Fast Algorithms for Structured Matrices, edited by V. Olshevsky (AMS series Contemp. Math., vol. 323, 2003), pp. 75-90. · Zbl 1039.65026 |
| [22] | G. Heinig K. Rost Algebraic Methods for Toeplitz-Like Matrices and Operators (Birkhäuser, Basel, 1984). |
| [23] | Heinig, On the inverses of Toeplitz-plus-Hankel matrices, Linear Algebra Appl. 106 pp 39– (1988) · Zbl 0646.15015 · doi:10.1016/0024-3795(88)90021-3 |
| [24] | Heinig, DFT representations of Toeplitz-plus-Hankel Bezoutians with application to fast matrix-vector multiplication, Linear Algebra Appl. 284 pp 157– (1998) · Zbl 0938.65073 · doi:10.1016/S0024-3795(98)10076-9 |
| [25] | Heinig, Hartley transform representations of inverses of real Toeplitz-plus-Hankel matrices, Numerical Functional Analysis and Optimization 21 pp 175– (2000) · Zbl 0958.15006 |
| [26] | G. Heinig K. Rost Efficient inversion formulas for Toeplitz-plus-Hankel matrices using trigonometric transformations, in: Structured Matrices in Mathematics, Computer Science, and Engineering, edited by V. Olshevsky (AMS series Contemp. Math., vol. 281, 2001), pp. 247-264. · Zbl 1007.65016 |
| [27] | Heinig, Centro-symmetric and centro-skewsymmetric Toeplitz matrices and Bezoutians, Linear Algebra Appl. 343/344 pp 195– (2002) · Zbl 0995.15022 · doi:10.1016/S0024-3795(01)00342-1 |
| [28] | G. Heinig K. Rost Fast algorithms for skewsymmetric Toeplitz matrices, in: Toeplitz Matrices and Singular Integral Equations, edited by A. Böttcher, I. Gohberg, P. Junghanns (Birkhäuser, Basel, OT series, vol. 135, 2002), pp. 193-208. · Zbl 1022.65028 |
| [29] | Heinig, Centrosymmetric and centro-skewsymmetric Toeplitz-plus-Hankel matrices and Bezoutians, Linear Algebra Appl. 366 pp 257– (2003) · Zbl 1031.15025 · doi:10.1016/S0024-3795(02)00506-2 |
| [30] | Heinig, Fast algorithms for centro-symmetric and centro-skewsymmetric Toeplitzplus-Hankel matrices, Numerical Algorithms 33 pp 305– (2003) · Zbl 1030.65017 · doi:10.1023/A:1025584509948 |
| [31] | Heinig, New fast algorithms for Toeplitz-plus-Hankel matrices, SIAM J. Matrix Analysis Appl. 25 pp 842– (2004) · Zbl 1062.65032 · doi:10.1137/S0895479802410074 |
| [32] | Heinig, Split algorithms for skewsymmetric Toeplitz matrices with arbitrary rank profile, Theoretical Computer Science 315 pp 453– (2004) · Zbl 1060.65033 · doi:10.1016/j.tcs.2004.01.003 |
| [33] | G. Heinig K. Rost Split algorithms for symmetric Toeplitz matrices with arbitrary rank profile, Numerical Linear Algebra with Applications, to appear. · Zbl 1164.65383 |
| [34] | G. Heinig K. Rost Schur-type algorithms for the solution of Hermitian Toeplitz systems via factorization, in: Operator Theory: Advances and Applications, to appear. |
| [35] | G. Heinig K. Rost Split algorithms for hermitian Toeplitz matrices with arbitrary rank profile, Linear Algebra Appl., to appear. · Zbl 1063.65025 |
| [36] | G. Heinig K. Rost Split algorithms for centrosymmetric Toeplitz-plus-Hankel matrices with arbitrary rank profile, in preparation. · Zbl 1113.65304 |
| [37] | N. J. Higham Accuracy and Stability of Numerical Algorithms (SIAM, Philadelphia, 1996). |
| [38] | Konyagin, Lower bounds for the absolute value of random polynomials on a neighborhood of the unit circle, Trans. Amer. Math. Soc. 351 pp 4963– (1999) · Zbl 0949.42006 · doi:10.1090/S0002-9947-99-02241-2 |
| [39] | Krein, Integral equations on the half-line with a kernel depending on the difference of the arguments, Uspekhi Mat. Nauk 13 pp 3– (1958) · Zbl 0119.09601 |
| [40] | Krein, The method of symmetric and Hermitian forms in the theory of the separation of the roots of algebraic equations, Linear and Multilinear Algebra 56 pp 69– (1974) |
| [41] | Krishna, Computationally efficient reduced polynomial based algorithms for hermitian Toeplitz matrices, SIAM J. Appl. Math. 49 pp 1275– (1989) · Zbl 0679.65030 · doi:10.1137/0149076 |
| [42] | Landau, On Szegö’s eigenvalue distribution theorem and non-Hermitian kernels, J. Analyse Math. 28 pp 335– (1975) · Zbl 0321.45005 · doi:10.1007/BF02786820 |
| [43] | Lander, The Bezoutian and the inversion of Hankel and Toeplitz matrices, Matem. Issled. 9 pp 69– (1974) |
| [44] | Melman, A two-step even-odd split Levinson algorithm for Toeplitz systems, Linear Algebra Appl. 338 pp 219– (2001) · Zbl 0991.65031 · doi:10.1016/S0024-3795(01)00386-X |
| [45] | V.Y. Pan Structured Matrices and Polynomials (Birkhäuser, Boston and Springer, New York, 2001). |
| [46] | Reichel, Eigenvalues and pseudo-eigenvalues of Toeplitz matrices, Linear Algebra Appl. 162/164 pp 153– (1992) · Zbl 0748.15010 · doi:10.1016/0024-3795(92)90374-J |
| [47] | Rump, Structured perturbations, Part I: Normwise distances, SIAM J. Matrix Anal. Appl. 25 pp 1– (2003) · Zbl 1061.15004 · doi:10.1137/S0895479802405732 |
| [48] | Schmidt, The Toeplitz matrices of an arbitrary Laurent polynomial, Math. Scand. 8 pp 15– (1960) · Zbl 0101.09203 · doi:10.7146/math.scand.a-10588 |
| [49] | L. N. Trefethen M. Embree Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators (Princeton University Press, to appear). · Zbl 1085.15009 |
| [50] | Widom, Asymptotic behavior of block Toeplitz matrices and determinants II, Advances in Math. 21 pp 1– (1976) · Zbl 0344.47016 · doi:10.1016/0001-8708(76)90113-4 |
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.
