How to prove that a preconditioner cannot be superlinear

Serra Capizzano, S.; Tyrtyshnikov, E.

doi:10.1090/S0025-5718-03-01506-0

How to prove that a preconditioner cannot be superlinear
HTML articles powered by AMS MathViewer

by S. Serra Capizzano and E. Tyrtyshnikov;

Math. Comp. 72 (2003), 1305-1316

DOI: https://doi.org/10.1090/S0025-5718-03-01506-0

Published electronically: February 3, 2003

PDF | Request permission

Abstract:

In the general case of multilevel Toeplitz matrices, we recently proved that any multilevel circulant preconditioner is not superlinear (a cluster it may provide cannot be proper). The proof was based on the concept of quasi-equimodular matrices, although this concept does not apply, for example, to the sine-transform matrices. In this paper, with a new concept of partially equimodular matrices, we cover all trigonometric matrix algebras widely used in the literature. We propose a technique for proving the non-superlinearity of certain frequently used preconditioners for some representative sample multilevel matrices. At the same time, we show that these preconditioners are, in a certain sense, the best among the sublinear preconditioners (with only a general cluster) for multilevel Toeplitz matrices.

References

Owe Axelsson and Gunhild Lindskog, On the eigenvalue distribution of a class of preconditioning methods, Numer. Math. 48 (1986), no. 5, 479–498. MR 839613, DOI 10.1007/BF01389447
Dario Bini and Milvio Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl. 52/53 (1983), 99–126. MR 709346, DOI 10.1016/0024-3795(83)80009-3
Dario Bini and Paola Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl. 14 (1993), no. 2, 500–507. MR 1211803, DOI 10.1137/0614035
Raymond H. Chan and Michael K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38 (1996), no. 3, 427–482. MR 1409592, DOI 10.1137/S0036144594276474
Raymond H. Chan, Qian-Shun Chang, and Hai-Wei Sun, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput. 19 (1998), no. 2, 516–529. MR 1618824, DOI 10.1137/S1064827595293831
Philip J. Davis, Circulant matrices, A Wiley-Interscience Publication, John Wiley & Sons, New York-Chichester-Brisbane, 1979. Pure and Applied Mathematics. MR 543191
Fabio Di Benedetto and Stefano Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning, Numer. Math. 82 (1999), no. 1, 57–90. MR 1681307, DOI 10.1007/s002110050411
Fabio Di Benedetto and Stefano Serra Capizzano, Optimal multilevel matrix algebra operators, Linear and Multilinear Algebra 48 (2000), no. 1, 35–66. MR 1814029, DOI 10.1080/03081080008818658
Giuseppe Fiorentino and Stefano Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput. 17 (1996), no. 5, 1068–1081. MR 1404861, DOI 10.1137/S1064827594271512
Walter Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl. 52/53 (1983), 293–300. MR 709357, DOI 10.1016/0024-3795(83)80020-2
Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
Georg Heinig and Karla Rost, Representations of Toeplitz-plus-Hankel matrices using trigonometric transformations with application to fast matrix-vector multiplication, Proceedings of the Sixth Conference of the International Linear Algebra Society (Chemnitz, 1996), 1998, pp. 225–248. MR 1628391, DOI 10.1016/S0024-3795(97)10024-6
T. Kailath and V. Olshevsky, Displacement structure approach to discrete-trigonometric-transform based preconditioners of G. Strang type and T. Chan type, Proc. “Workshop on Toeplitz matrices”, Cortona (Italy), September 1996. Calcolo, 33 (1996), pp. 191–208.
Thomas Kailath and Ali H. Sayed, Displacement structure: theory and applications, SIAM Rev. 37 (1995), no. 3, 297–386. MR 1355506, DOI 10.1137/1037082
Julie Kamm and James G. Nagy, Optimal Kronecker product approximation of block Toeplitz matrices, SIAM J. Matrix Anal. Appl. 22 (2000), no. 1, 155–172. MR 1779722, DOI 10.1137/S0895479898345540
D. Noutsos, S. Serra Capizzano and P. Vassalos, Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result, Contemp. Math., in press.
Stefano Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT 34 (1994), no. 4, 579–594. MR 1430910, DOI 10.1007/BF01934269
Stefano Serra Capizzano, Toeplitz preconditioners constructed from linear approximation processes, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 446–465. MR 1662417, DOI 10.1137/S0895479897316904
Stefano Serra Capizzano, Korovkin theorems and linear positive Gram matrix algebra approximations of Toeplitz matrices, Linear Algebra Appl. 284 (1998), no. 1-3, 307–334. ILAS Symposium on Fast Algorithms for Control, Signals and Image Processing (Winnipeg, MB, 1997). MR 1655142, DOI 10.1016/S0024-3795(98)10072-1
Stefano Serra, A Korovkin-type theory for finite Toeplitz operators via matrix algebras, Numer. Math. 82 (1999), no. 1, 117–142. MR 1681309, DOI 10.1007/s002110050413
S. Serra Capizzano and E. Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 431–439. MR 1718339, DOI 10.1137/S0895479897331941
S. Serra Capizzano, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343/344 (2002), pp. 303–319.
A. van der Sluis and H. A. van der Vorst, The rate of convergence of conjugate gradients, Numer. Math. 48 (1986), no. 5, 543–560. MR 839616, DOI 10.1007/BF01389450
E. E. Tyrtyshnikov, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1–23. MR 1319972, DOI 10.1016/0024-3795(93)00092-E
Evgenij E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. 232 (1996), 1–43. MR 1366576, DOI 10.1016/0024-3795(94)00025-5
E. E. Tyrtyshnikov and N. L. Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl. 270 (1998), 15–27. MR 1484073
Eugene E. Tyrtyshnikov, A brief introduction to numerical analysis, Birkhäuser Boston, Inc., Boston, MA, 1997. MR 1442956, DOI 10.1007/978-0-8176-8136-4
E. E. Tyrtyshnikov, Distributions and clusters, Matrix methods and algorithms (Russian), Ross. Akad. Nauk, Inst. Vychisl. Mat., Moscow, 1993, pp. 124–166 (Russian, with Russian summary). MR 1477969