Four short stories about Toeplitz matrix calculations. (English) Zbl 0999.65026
The stories told in this paper are dealing with the solution of finite, infinite, and bi-infinite Toeplitz type systems of equations. It is shown that a crucial role in the solution of such systems plays the off-diagonal decay behaviour of Toeplitz matrices and their inverses. Estimates for the approximate solution of (bi-)infinite Toeplitz systems by the finite section method are derived, showing that the approximation rate depends only on the decay of the entries of the Toeplitz matrix and its condition number.
Error estimates are given for the solution of doubly infinite convolution systems by finite circulant systems. Finally, some quantitative results on the construction of preconditioners via circulant embedding are derived, which allows to provide a theoretical explanation for some numerical observations in connection with deconvolution problems.
Error estimates are given for the solution of doubly infinite convolution systems by finite circulant systems. Finally, some quantitative results on the construction of preconditioners via circulant embedding are derived, which allows to provide a theoretical explanation for some numerical observations in connection with deconvolution problems.
Reviewer: Petko Hr.Petkov (Sofia)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 47B35 | Toeplitz operators, Hankel operators, Wiener-Hopf operators |
| 42A10 | Trigonometric approximation |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
infinite Toeplitz systems; Toeplitz matrices; finite section method; condition number; convolution systems; preconditionersReferences:
| [1] | A. Beurling, Sur les intégrales de Fourier absolument convergentes et leur application à une transformation fonctionelle, in: Ninth Scandinavian Mathematical Congress, Helsingfors, 1938, pp. 345-366; A. Beurling, Sur les intégrales de Fourier absolument convergentes et leur application à une transformation fonctionelle, in: Ninth Scandinavian Mathematical Congress, Helsingfors, 1938, pp. 345-366 · JFM 65.0483.02 |
| [2] | A. Böttcher and B. Silbermann, Analysis of Toeplitz Operators, Springer-Verlag, Berlin, 1990; A. Böttcher and B. Silbermann, Analysis of Toeplitz Operators, Springer-Verlag, Berlin, 1990 · Zbl 0732.47029 |
| [3] | Chan, R., Circulant preconditioners for hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl., 10, 542-550 (1989) · Zbl 0684.65035 |
| [4] | Chan, R.; Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013 |
| [5] | Chan, R.; Strang, G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput., 10, 104-119 (1989) · Zbl 0666.65030 |
| [6] | Chan, R. H.; Ng, M., Toeplitz preconditioners for Hermitian Toeplitz systems, Linear Algebra Appl., 190, 181-208 (1993) · Zbl 0783.65042 |
| [7] | Davis, P., Circulant Matrices (1979), Wiley: Wiley New York · Zbl 0418.15017 |
| [8] | Demko, S.; Moss, W.; Smith, P., Decay rates for inverses of band matrices, Math. Comput., 43, 491-499 (1984) · Zbl 0568.15003 |
| [9] | Domar, Y., Harmonic analysis based on certain commutative Banach algebras, Acta Math., 96, 1-66 (1956) · Zbl 0071.11302 |
| [10] | I. Gelfand, D. Raikov, G. Shilov, Commutative Normed Rings, Chelsea, New York, 1964 (translated from the Russian); I. Gelfand, D. Raikov, G. Shilov, Commutative Normed Rings, Chelsea, New York, 1964 (translated from the Russian) |
| [11] | I. Gohberg, I. Fel’dman, Convolution Equations and Projection Methods for their Solution, vol. 41, American Mathematical Society, Providence, R.I., 1974 (translated from the Russian by F.M. Goldware, Translations of Mathematical Monographs); I. Gohberg, I. Fel’dman, Convolution Equations and Projection Methods for their Solution, vol. 41, American Mathematical Society, Providence, R.I., 1974 (translated from the Russian by F.M. Goldware, Translations of Mathematical Monographs) · Zbl 0278.45008 |
| [12] | Gohberg, I.; Goldberg, S.; Kaashoek, M. A., Classes of Linear Operators, Operator Theory: Advances and Applications, vol. 63 (1993), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 0789.47001 |
| [13] | Gohberg, I.; Hanke, M.; Koltracht, I., Fast preconditioned conjugate gradient algorithms for Wiener- Hopf integral equations, SIAM J. Numer. Anal., 31, 429-443 (1994) · Zbl 0820.65092 |
| [14] | Hanke, M.; Nagy, J. G., Toeplitz approximate inverse preconditioner for banded Toeplitz matrices, Numer. Algorithms, 7, 183-199 (1994) · Zbl 0810.65029 |
| [15] | Horn, R.; Johnson, C., Topics in Matrix Analysis (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0801.15001 |
| [16] | Jaffard, S., Propriétés des matrices “bien localisées” près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire, 7, 461-476 (1990) · Zbl 0722.15004 |
| [17] | Kailath, T.; Sayed, A. H., Displacement structure: theory and applications, SIAM Rev., 37, 297-386 (1995) · Zbl 0839.65028 |
| [18] | S. Levin, Asymptotic properties of Toeplitz matrices, Ph.D. thesis, The Weizmann Institute, Rehovot, Israel, 1980; S. Levin, Asymptotic properties of Toeplitz matrices, Ph.D. thesis, The Weizmann Institute, Rehovot, Israel, 1980 |
| [19] | Nagy, J.; Plemmons, R.; Torgersen, T., Iterative image restoration using approximate inverse preconditioning, IEEE Trans. Image Process., 15, 1151-1162 (1996) |
| [20] | Ng, M. K.; Chan, R. H.; Tang, W.-C., A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21, 851-866 (1999), electronic · Zbl 0951.65038 |
| [21] | J.G. Proakis, Digital Communications, 3rd ed., McGraw-Hill, New York, 1995; J.G. Proakis, Digital Communications, 3rd ed., McGraw-Hill, New York, 1995 · Zbl 0292.94002 |
| [22] | Reiter, H., Classical Harmonic Analysis and Locally Compact Abelian Groups (1968), Oxford University Press: Oxford University Press Oxford · Zbl 0165.15601 |
| [23] | Richtmyer, R.; Morton, K., Difference Methods for Initial-Value Problems (1994), Krieger Publishing Company: Krieger Publishing Company Malabar, FL · Zbl 0824.65084 |
| [24] | G. Steidl, Personal communication, 2000; G. Steidl, Personal communication, 2000 |
| [25] | Strohmer, T., Rates of convergence for the approximation of dual shift-invariant systems in \(ℓ^2(Z)\), J. Fourier Anal. Appl., 5, 599-615 (2000) · Zbl 0981.42020 |
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.
