Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems

Author: Stefano Serra
Journal: Math. Comp. 66 (1997), 651-665
MSC (1991): Primary 65F10, 65F15
MathSciNet review: 1401945
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we are concerned with the solution of $n\times n$ Hermitian Toeplitz systems with nonnegative generating functions $f$. The preconditioned conjugate gradient (PCG) method with the well-known circulant preconditioners fails in the case where $f$ has zeros. In this paper we consider as preconditioners band-Toeplitz matrices generated by trigonometric polynomials $g$ of fixed degree $l$. We use different strategies of approximation of $f$ to devise a polynomial $g$ which has some analytical properties of $f$, is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent of $n$. For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates of $l$ for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.

References [Enhancements On Off] (What's this?)

  • 1. N. Ahmed, T. Natarajan, K. Rao, ``Discrete cosine transforms'', IEEE Trans. Comp., 23 (1974), 90-93. MR 50:9025
  • 2. O. Axelsson, V. Barker, Finite Element Solution of Boundary Value Problems, Theory and Computation, Academic press Inc., New York 1984. MR 85m:65116
  • 3. O. Axelsson, G. Lindskög, ``The rate of convergence of the preconditioned conjugate gradient method'', Num. Math., 52 (1986), 499-523. MR 88a:65037b
  • 4. D. Bini, ``Matrix structure in parallel matrix computation'', Calcolo, 25 (1988), pp. 37-51. MR 91g:65322
  • 5. D. Bini, M. Capovani, ``Spectral and computational properties of band symmetric Toeplitz matrices'', Linear Algebra Appl., 52/53 (1983), 99-126. MR 85k:15008
  • 6. D. Bini, P. Favati, ``On a matrix algebra related to the discrete Hartley transform'', SIAM J. Matrix Anal. Appl., 14 (1993), 500-507. MR 94h:65026
  • 7. R.H. Chan, ``Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions'', IMA J. Numer. Anal., 11 (1991), 333-345. MR 92f:65041
  • 8. R.H. Chan, W. Ching, ``Toeplitz-circulant preconditioners for Toeplitz systems and their applications to queueing network with batch arrivals'', SIAM J. Sci. Comp., 17 (1996), 762-772. CMP 96:11
  • 9. R.H. Chan, Q. Chang, H. Sun, ``Multigrid method for ill-conditioned symmetric Toeplitz systems'', personal communication.
  • 10. R.H. Chan, G. Strang, ``Toeplitz equations by conjugate gradients with circulant preconditioner'', SIAM J. Sci. Stat. Comp., 10 (1989), 104-119. MR 90d:65069
  • 11. R.H. Chan, P. Tang, ``Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems'', SIAM J. Sci. Comp., 15 (1994), 164-171. MR 94j:65043
  • 12. R.H. Chan, P. Tang, ``Constrained minimax approximation and optimal preconditioners for Toeplitz matrices'', Numer. Alg., 5 (1993), 353-364. CMP 94:07
  • 13. T.F. Chan, ``An optimal circulant preconditioner for Toeplitz systems'', SIAM J. Sci. Stat. Comp., 9 (1988), 766-771. MR 89e:65046
  • 14. P. Davis, Circulant Matrices. John Wiley and Sons, New York 1979. MR 81a:15003
  • 15. F. Di Benedetto, ``Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices'', SIAM J. Sci. Comp., 16 (1995), 682-697. MR 95m:65082
  • 16. F. Di Benedetto, G. Fiorentino, S. Serra, ``C.G. Preconditioning for Toeplitz Matrices'', Comp. Math. Applic., 25 (1993), 35-45. MR 93h:65063
  • 17. G. Fiorentino, S. Serra, ``Multigrid methods for Toeplitz matrices'', Calcolo, 28 (1991), pp. 283-305. MR 94c:65039
  • 18. I. Gohberg, I. Feldman, Convolution Equations and Projection Methods for Their Solution, Transaction of Mathematical Monographs, 41, American Mathematical Society, Providence, Rhode Island 1974. MR 50:8149
  • 19. G.H. Golub, C.F. Van Loan, Matrix Computations. The Johns Hopkins University Press, Baltimore 1983. MR 85h:65063
  • 20. U. Grenander, G. Szegö, Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. MR 88b:42031
  • 21. I.S. Iokhvidov, Hankel and Toeplitz Forms: Algebraic Theory. Birkhäuser, Boston, 1982. MR 83k:15021
  • 22. D. Jackson, The Theory of Approximation. American Mathematical Society, New York, 1930.
  • 23. G. Meinardus, Approximation of Functions: Theory and Numerical Methods. Springer-Verlag, Berlin, 1967. MR 36:571
  • 24. A. Oppenheim, Applications of Digital Signal Processing. Prentice-Hall, Englewood Cliffs, 1978.
  • 25. M.J.D. Powell, ``On the maximum errors of polynomial approximation defined by interpolation and least squares criteria'', Comput. J., 9 (1966), 404-407. MR 34:8616
  • 26. E.J. Remes, ``Sur le calcul effectif des polynomes d'approximation de Tchebichef'' Compt. Rend. Acad. Sci. Paris, 199 (1934), 337-340.
  • 27. S. Serra, ``Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems'', BIT, 34 (1994), pp. 579-594.
  • 28. S. Serra, ``Conditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods'', Proc. in Advanced Signal Processing Algorithms, Architectures, and Implementations - SPIE conference, F. Luk Ed., San Diego (CA), july 1995, pp. 326-337.
  • 29. S. Serra, ``Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions'', SIAM J. Matr. Anal. Appl., 17 (1996), pp. 1007-1019.
  • 30. S. Serra, ``On the extreme eigenvalues of Hermitian (block) Toeplitz matrices'', Linear Algebra Appl., to appear.
  • 31. S. Serra, ``On the extreme spectral properties of Toeplitz matrices generated by $L^1$ functions with several minima (maxima)'', BIT, 36 (1996), 135-142.
  • 32. S. Serra, ``Asymptotic results on the spectra of preconditioned Toeplitz matrices and some applications'', TR nr. 9 University of Calabria, (1995).
  • 33. P. Tang, ``A fast algorithm for linear complex Chebyshev approximation'', Math. Comp., 51 (1988), 721-739. MR 89j:30054
  • 34. C. Van Loan, Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia, 1992. MR 93a:65186
  • 35. S. Wright, ``Parallel algorithms for banded linear systems'', SIAM J. Sci. Stat. Comp., 12 (1991), 824-842. MR 92a:65096

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F10, 65F15

Retrieve articles in all journals with MSC (1991): 65F10, 65F15

Additional Information

Stefano Serra
Affiliation: Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56100 Pisa (Italy)

Keywords: Toeplitz matrix, Chebyshev interpolation and approximation, conjugate gradient method, Remez algorithm
Received by editor(s): January 20, 1995
Received by editor(s) in revised form: January 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society