×

Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate. (English) Zbl 1059.65041

In the past two decades many papers from the literature deal with the solution of multilevel Toeplitz systems because of several applications: signal prosessing, image restoration, partial differential equations, time series. Futhermore, multilevel Toeplitz matrices are interesting from the viewpoint of complexity theory. A good idea for solving such linear systems is by using iterative solvers in which the involved matrices preserve a Toeplitz structure (for example gradient methods, Chebyshev iterations, Jacobi or Richardson methods).
In this paper the authors show that the multilevel Toeplitz case is dramatically different from the scalar Toeplitz case in terms of preconditioning using fast transform algebras, that is, in multilevel case it is impossible to find superlinear and/or spectrally equivalent matrix algebra preconditioners. The optimality is proved in the case of multilevel band Toeplitz preconditioning.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
15A12 Conditioning of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Bertaccini, G. Golub, S. Serra Capizzano, C. Tablino Possio, Preconditioned HSS method for the solution of non Hermitian positive definite linear systems, Tech. Report SCCM-02-10, Stanford University, 2002.; D. Bertaccini, G. Golub, S. Serra Capizzano, C. Tablino Possio, Preconditioned HSS method for the solution of non Hermitian positive definite linear systems, Tech. Report SCCM-02-10, Stanford University, 2002.
[2] Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52/53, 99-126 (1983) · Zbl 0549.15005
[3] D. Bini, V. Pan, Matrix and Polynomial Computations, vol. 1: Fundamental Algorithms, Birkäuser, Boston, MA, 1994.; D. Bini, V. Pan, Matrix and Polynomial Computations, vol. 1: Fundamental Algorithms, Birkäuser, Boston, MA, 1994. · Zbl 0809.65012
[4] Böttcher, A.; Silbermann, B., Introduction to Large Truncated Toeplitz Operators (1999), Springer: Springer New York, NY · Zbl 0916.15012
[5] Chan, R. H., Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal., 11, 333-345 (1991) · Zbl 0737.65022
[6] Chan, R. H.; Ng, M., Conjugate gradient method for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[7] Di Benedetto, F., Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comput., 16, 682-697 (1995) · Zbl 0830.65032
[8] Di Benedetto, F.; Fiorentino, G.; Serra Capizzano, S., C.G. Preconditioning for Toeplitz matrices, Comput. Math. Appl., 25, 35-45 (1993) · Zbl 0782.65063
[9] Fiorentino, G.; Serra Capizzano, S., Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17, 4, 1068-1081 (1996) · Zbl 0858.65039
[10] Golub, G.; Van Loan, C., Matrix Computations (1983), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MR · Zbl 0559.65011
[11] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics. A Foundation for Computer Science (1989), Addison-Wesley Publ. Company: Addison-Wesley Publ. Company Reading, MA · Zbl 0668.00003
[12] Ng, M., Band preconditioners for block-Toeplitz-Toeplitz-block systems, Linear Algebra Appl., 259, 307-327 (1997) · Zbl 0877.65016
[13] Noutsos, D.; Serra Capizzano, S.; Vassalos, P., Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systemsa negative result, Contemp. Math., 323, 313-322 (2003), (V. Olshevsky Ed.) · Zbl 1039.65029
[14] Noutsos, D.; Vassalos, P., New band Toeplitz preconditioners for ill-conditioned symmetric positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl., 23, 3, 728-743 (2002) · Zbl 1011.65014
[15] Potts, D.; Steidl, G., Preconditioners for ill-conditioned Toeplitz systems constructed from positive kernels, SIAM J. Sci. Comput., 22, 5, 1741-1761 (2001) · Zbl 0985.65034
[16] Potts, D.; Steidl, G., Preconditioning of Hermitian block-Toeplitz-Toeplitz-block matrices by level 1 preconditioners, Contemp. Math., 281, 193-212 (2001), (V. Olshevsky Ed.) · Zbl 0993.65055
[17] Rao, K.; Yip, P., Discrete Cosine Transforms: Algorithms, Advantages, Applications (1990), Academic Press: Academic Press New York, NY · Zbl 0726.65162
[18] Serra Capizzano, S., Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT, 34, 579-594 (1994) · Zbl 0823.65030
[19] Serra Capizzano, S., Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comput., 66, 651-665 (1997) · Zbl 0864.65019
[20] Serra Capizzano, S., The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems, Numer. Math., 81, 3, 461-495 (1999) · Zbl 0918.65059
[21] 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
[22] Serra Capizzano, S., Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343-344, 303-319 (2002) · Zbl 1001.65041
[23] Serra Capizzano, S., Convergence analysis of two grid methods for elliptic Toeplitz and PDEs matrix sequences, Numer. Math., 92, 3, 433-465 (2002) · Zbl 1013.65026
[24] Serra Capizzano, S., Generalized locally Toeplitz sequencesspectral analysis and applications to discretized partial differential equations, Linear Algebra Appl., 366, 1, 371-402 (2003) · Zbl 1028.65109
[25] Serra Capizzano, S.; Tilli, P., Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices, J. Comput. Appl. Math., 108, 1/2, 113-130 (1999) · Zbl 0937.15013
[26] Serra Capizzano, S.; Tyrtyshnikov, E., Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 22, 1, 431-439 (1999) · Zbl 0952.65037
[27] Serra Capizzano, S.; Tyrtyshnikov, E., How to prove that a preconditioner cannot be superlinear, Math. Comput., 72, 1305-1316 (2003) · Zbl 1021.15005
[28] Sun, H.; Jin, X.; Chang, Q., Convergence of the multigrid method for ill-conditioned block Toeplitz systems, BIT, 41, 179-190 (2001) · Zbl 0991.65033
[29] H. Widom, Toeplitz matrices, in: I. Hirshman Jr. (Ed.), Studies in Real and Complex Analysis, Math. Ass. Amer., Washington, DC, 1965.; H. Widom, Toeplitz matrices, in: I. Hirshman Jr. (Ed.), Studies in Real and Complex Analysis, Math. Ass. Amer., Washington, DC, 1965. · Zbl 0173.42501
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.