Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Superlinear PCG methods
for symmetric Toeplitz systems

Author: Stefano Serra
Journal: Math. Comp. 68 (1999), 793-803
MSC (1991): Primary 65F10, 65F15
MathSciNet review: 1620251
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we deal with the solution, by means of preconditioned conjugate gradient (PCG) methods, of $n\times n$ symmetric Toeplitz systems $A_n(f) \mathbf{ x}= \mathbf{ b}$ with nonnegative generating function $f$. Here the function $f$ is assumed to be continuous and strictly positive, or is assumed to have isolated zeros of even order. In the first case we use as preconditioner the natural and the optimal $\tau$ approximation of $A_n(f)$ proposed by Bini and Di Benedetto, and we prove that the related PCG method has a superlinear rate of convergence and a total arithmetic cost of $O(n\log n)$ ops. Under the second hypothesis we cannot guarantee that the natural $\tau$ matrix is positive definite, while for the optimal we show that, in the ill-conditioned case, this can be really a bad choice. Consequently, we define a new $\tau$ matrix for preconditioning the given system; then, by applying the Sherman-Morrison-Woodbury inversion formula to the preconditioned system, we introduce a small, constant number of subsidiary systems which can be solved again by means of the previous PCG method. Finally, we perform some numerical experiments that show the effectiveness of the devised technique and the adherence with the theoretical analysis.

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

  • 1. G. Ammar and W. Gragg, ``Superfast solution of real positive definite Toeplitz systems'', SIAM J. Matrix Anal. Appl., 9, pp. 61-76 (1988). MR 89b:65065
  • 2. O. Axelsson and G. Lindskog, ``The rate of convergence of the preconditioned conjugate gradient method'', Numer. Math., 48, pp. 499-523 (1986). MR 88a:65037b
  • 3. D. Bini and M. Capovani, ``Spectral and computational properties of band symmetric Toeplitz matrices'', Linear Algebra Appl., 52/53, pp. 99-126 (1983). MR 85k:15008
  • 4. D. Bini and F. Di Benedetto, ``A new preconditioner for the parallel solution of positive definite Toeplitz systems'', Proc. 2nd ACM SPAA, Crete, Greece, July 1990, pp. 220-223.
  • 5. D. Bini and P. Favati, ``On a matrix algebra related to the discrete Hartley transform'', SIAM J. Matrix Anal. Appl., 14, pp. 500-507 (1993). MR 94h:65026
  • 6. E. Bozzo, Matrix Algebras and Discrete Transforms. PhD. thesis in Comp. Sci., Dept. Comp. Sci., University of Pisa, Italy, 1994.
  • 7. R.H. Chan, ``Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions'', IMA J. Numer. Anal., 11, pp. 333-345 (1991).
  • 8. R.H. Chan and W.-K. Ching, ``Toeplitz-circulant preconditioners for Toeplitz systems and their applications to queueing networks with batch arrivals'', SIAM J. Sci. Comput., 17, pp. 762-772 (1996). MR 97b:65054
  • 9. R.H. Chan and M.K. Ng, ``Conjugate gradient method for Toeplitz systems'', SIAM Rev., 38, pp. 427-482, (1996). MR 97i:65048
  • 10. R.H. Chan and G. Strang, ``Toeplitz equations by conjugate gradients with circulant preconditioner'', SIAM J. Sci. Statist. Comput., 10, pp. 104-119 (1989). MR 90d:65069
  • 11. R.H. Chan and P. Tang, ``Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems'', SIAM J. Sci. Comput., 15, pp. 164-171 (1994). MR 94j:65043
  • 12. R.H. Chan and M.-C. Yeung, ``Circulant preconditioners for Toeplitz matrices with positive continuous generating functions'', Math. Comp., 58, pp. 233-240 (1992). MR 92e:65040
  • 13. R.H. Chan and M.-C. Yeung, ``Jackson's theorem and circulant preconditioned Toeplitz systems'', J. Approx. Theory, 70, pp. 191-205 (1992). MR 93c:65046
  • 14. T.F. Chan, ``An optimal circulant preconditioner for Toeplitz systems'', SIAM J. Sci. Statist. Comput., 9, pp. 766-771 (1988). MR 89e:65046
  • 15. E. Cheney, Introduction to Approximation Theory. McGraw-Hill, New York, 1966. MR 36:5568
  • 16. P. Davis, Circulant Matrices. John Wiley and Sons, New York, 1979. MR 81a:15003
  • 17. F. de Hoog, ``A new algorithm for solving Toeplitz systems of equations'', Linear Algebra Appl., 88/89, pp. 123-138 (1987). MR 88d:65053
  • 18. F. Di Benedetto, ``Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices'', SIAM J. Sci. Comput., 16, pp. 682-697 (1995). MR 95m:65082
  • 19. F. Di Benedetto, G. Fiorentino and S. Serra, ``C.G. preconditioning for Toeplitz matrices'', Comput. Math. Appl., 25, pp. 35-45 (1993). MR 93h:65063
  • 20. F. Di Benedetto and S. Serra Capizzano, ``A unifying approach to matrix algebra preconditioning'', Numer. Math., in press.
  • 21. I. Gohberg and I. Fel'dman, Convolution Equations and Projection Methods for Their Solution, Transl. Math. Monogr., 41, Amer. Math. Soc., Providence, RI, 1974. MR 50:8149
  • 22. G.H. Golub and C.F. Van Loan, Matrix Computations. The Johns Hopkins University Press, Baltimore, MD, 1983. MR 85h:65063
  • 23. B. Grasso, Tecniche di Precondizionamento per la Risoluzione Numerica di Sistemi Lineari Tramite Proiezioni su Particolari Algebre Matriciali. Undergraduate thesis, Dept. Math., University of Genova, Italy, 1995.
  • 24. U. Grenander and M. Rosenblatt, Statistical Analysis of Stationary Time Series. Second edition, Chelsea, New York, 1984. MR 88f:62003
  • 25. U. Grenander and G. Szegö, Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. MR 88b:42031
  • 26. D. Jackson, The Theory of Approximation. Amer. Math. Soc., New York, 1930.
  • 27. X.-Q. Jin, ``Hartley preconditioners for Toeplitz systems generated by positive continuous functions'', BIT, 34, pp. 367-371 (1994). MR 97i:65050
  • 28. M. Kac, W. Murdock, and G. Szegö, ``On the eigenvalues of certain Hermitian forms'', J. Rational Mech. Anal., 2, pp. 767-800 (1953). MR 15:538b
  • 29. A. Oppenheim, Applications of Digital Signal Processing. Prentice-Hall, Englewood Cliffs, NJ, 1978.
  • 30. W. Rudin, Principles of Mathematical Analysis. McGraw-Hill, New York, 1985. MR 52:5893
  • 31. S. Serra, ``Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems'', BIT, 34, pp. 579-594 (1994). MR 98a:65052
  • 32. 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.
  • 33. S. Serra, ``Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions'', SIAM J. Matrix Anal. Appl., 17, pp. 1007-1019 (1996). MR 98a:65042
  • 34. S. Serra, ``On the extreme eigenvalues of Hermitian (block) Toeplitz matrices'', Linear Algebra Appl., 270, pp. 109-129 (1998). CMP 98:05
  • 35. S. Serra, ``On the extreme spectral properties of Toeplitz matrices generated by $L^1$ functions with several minima/maxima'', BIT, 36, pp. 135-142 (1996). MR 98a:65051
  • 36. S. Serra, ``Asymptotic results on the spectra of preconditioned Toeplitz matrices and some applications'', TR nr. 9, LAN - Dept. Math., University of Calabria, (1995).
  • 37. S. Serra, ``Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems'', Math. Comp., 66, pp. 651-665 (1997). MR 97h:65056
  • 38. E.E. Tyrtyshnikov, ``Circulant preconditioners with unbounded inverses'', Linear Algebra Appl., 216, pp. 1-23 (1995). MR 95m:15019
  • 39. C.F. Van Loan, Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia, PA, 1992. MR 93a:65186
  • 40. A. Zygmund, Trigonometric Series. Cambridge University Press, London, 1959. MR 21:6498

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, Corso Italia 40, 56100 Pisa (ITALY)

Keywords: Toeplitz matrix, $\tau$ algebra, conjugate gradient method
Received by editor(s): February 7, 1996
Received by editor(s) in revised form: October 15, 1996, and July 18, 1997
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society