Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



How to prove that a preconditioner cannot be superlinear

Authors: S. Serra Capizzano and E. Tyrtyshnikov
Journal: Math. Comp. 72 (2003), 1305-1316
MSC (2000): Primary 15A12, 15A18, 65F10, 47B25
Published electronically: February 3, 2003
MathSciNet review: 1972737
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. O. Axelsson and G. Lindskög, The rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 52 (1986), pp. 499-523. MR 88a:65037b
  • 2. D. Bini and M. Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52/53 (1983), pp. 99-126. MR 85k:15008
  • 3. D. Bini and P. Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 500-507. MR 94h:65026
  • 4. R. Chan and M. Ng, Conjugate gradient methods for Toeplitz matrices, SIAM Revue, 38 (1996), pp. 427-482. MR 97i:65048
  • 5. R. Chan, Q. Chang, and H. Sun, Multigrid methods for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comp., 19-2 (1998), pp. 516-529. MR 99b:65030
  • 6. P. Davis, Circulant Matrices. John Wiley and Sons, New York, 1979. MR 81a:15003
  • 7. F. Di Benedetto and S. Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning, Numer. Math., 82-1 (1999), pp. 57-90. MR 2000b:65084
  • 8. F. Di Benedetto and S. Serra Capizzano, Optimal multilevel matrix algebra operators, Linear Multilin. Algebra., 48 (2000), pp. 35-66. MR 2001k:47048
  • 9. G. Fiorentino and S. Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comp., 17-5 (1996), pp. 1068-1081. MR 97h:65039
  • 10. W. Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl., 52/53 (1983), pp. 293-300. MR 84i:65043
  • 11. U. Grenander and G. Szegö, Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. MR 88b:42031
  • 12. G. Heinig and K. Rost, Representation of Toeplitz-plus-Hankel matrices using trigonometric transformations with applications to fast matrix-vector multiplication, Linear Algebra Appl., 275/276 (1998), pp. 225-248. MR 99d:65091
  • 13. 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.
  • 14. T. Kailath and A Sayed, Displacement structure: theory and applications, SIAM Revue, 37 (1995), pp. 297-386. MR 96h:15015
  • 15. J. Kamm and J. Nagy, Optimal Kronecker product approximation of block Toeplitz matrices, SIAM J. Matrix Anal. Appl., 22-1 (2000), pp. 155-172. MR 2001m:65061
  • 16. 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.
  • 17. S. Serra, Preconditioning strategie for asymptotically ill-conditioned block Toeplitz systems, BIT, 34 (1994), pp. 579-594. MR 98a:65052
  • 18. S. Serra Capizzano, Toeplitz preconditioners constructed from linear approximation processes, SIAM J. Matrix Anal. Appl., 20-2 (1998), pp. 446-465. MR 99j:65051
  • 19. S. Serra Capizzano, Korovkin theorems and linear positive Gram matrix algebras approximation of Toeplitz matrices, Linear Algebra Appl., 284 (1998), pp. 307-334. MR 99h:65088
  • 20. S. Serra, A Korovkin-type theory for finite Toeplitz operators via matrix algebras, Numer. Math., 82-1 (1999), pp. 117-142. MR 2000b:65091
  • 21. S. Serra Capizzano and E. Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21-2 (1999), pp. 431-439. MR 2000i:65049
  • 22. S. Serra Capizzano, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343/344 (2002), pp. 303-319.
  • 23. A. van der Sluis and H.A. van der Vorst, The rate of convergence of conjugate gradients, Numer. Math. 48 (1986), pp. 543-560. MR 87h:65061
  • 24. E. Tyrtyshnikov, Circulant preconditioners with unbounded inverses, Linear Algebra Appl., 216 (1995), pp. 1-23. MR 95m:15019
  • 25. E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232 (1996), pp. 1-43. MR 96m:15018
  • 26. E. Tyrtyshnikov and N. Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl. 270 (1998), pp. 15-27. MR 98i:65030
  • 27. E. Tyrtyshnikov, A Brief Introduction to Numerical Analysis, Birkhauser, Boston, 1997. MR 97m:65005
  • 28. E. Tyrtyshnikov, Distributions and clusters. In: Matrix Methods and Algorithms, Institute of Numerical Mathematics of the Russian Academy of Sciences, 1993, pp. 124-166. MR 98m:65061

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 15A12, 15A18, 65F10, 47B25

Retrieve articles in all journals with MSC (2000): 15A12, 15A18, 65F10, 47B25

Additional Information

S. Serra Capizzano
Affiliation: Dipartimento di Chimica, Fisica e Matematica, Università dell’Insubria - Sede di Como, Via Valleggio 11, 22100 Como, Italy

E. Tyrtyshnikov
Affiliation: Institute of Numerical Mathematics, Russian Academy of Sciences, Gubkina 8, Moscow 117333, Russia

Received by editor(s): May 5, 1998
Received by editor(s) in revised form: March 7, 2001
Published electronically: February 3, 2003
Additional Notes: The work of the second author was supported by the Russian Fund for Basic Research (under grant No. 97-01-00155) and Volkswagen-Stiftung.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society