|
How to prove that a preconditioner cannot be superlinear
Author(s):
S.
Serra
Capizzano;
E.
Tyrtyshnikov.
Journal:
Math. Comp.
72
(2003),
1305-1316.
MSC (2000):
Primary 15A12, 15A18, 65F10, 47B25
Posted:
February 3, 2003
Retrieve article in:
PDF DVI PostScript
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:
-
- 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
Email:
stefano.serrac@uninsubria.it; serra@monge.dm.unipi.it
E.
Tyrtyshnikov
Affiliation:
Institute of Numerical Mathematics, Russian Academy of Sciences, Gubkina 8, Moscow 117333, Russia
Email:
tee@inm.ras.ru
DOI:
10.1090/S0025-5718-03-01506-0
PII:
S 0025-5718(03)01506-0
Received by editor(s):
May 5, 1998
Received by editor(s) in revised form:
March 7, 2001
Posted:
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.
Copyright of article:
Copyright
2003,
American Mathematical Society
|
Comments: webmaster@ams.org