Skip to main content
Springer Nature Link
Log in

A practical algorithm to design fast and optimal band-Toeplitz preconditioners for hermitian toeplitz systems

  • Published:
CALCOLO Aims and scope Submit manuscript

Abstract

In this paper we are concerned with the iterative solution ofn×n Hermitian Toeplitz systems by means of preconditioned conjugate gradient (PCG) methods. In many applications [9] such as signal processing [24], differential equations [39], linear prediction of stationary processes [18], the related Toeplitz systems have the formA n (f)x=b where the symbolf, the generating function, is anL 1 function and the entries ofA n (f) along thek-th diagnonal coincide with thek-th Fourier coefficient off. When the essential range of the generating function has a convex hull containing zero, the matricesA n (f) are asymptotically ill-conditioned [21, 33, 28] and circulant or Hartley preconditioners do not work [15]. For this difficult case the only optimal preconditioners in the sense of [3, 29] are found in the τ algebra [15, 35] and especially in the band Toeplitz matrix class [7, 16]. In particular the band Toeplitz preconditioning strategy has been shown to be the most flexible one since it allows one to treat the nonnegative case [7, 16, 11, 31], the nondefinite one [27, 30, 34, 26]. On the other hand, the main criticism to this approach is surely the assumption that we must know the position and the order of the zeros off: in some applicative fields this is a feasible assumption, in other applications it is merely a theoretical possibility. Therefore, we discuss an economical technique in order to discover the sign off, the position of the possible zeros of the generating function and to evaluate approximately the order of these zeros. Finally, we exhibit some numerical experiments which confirm the effectiveness of the proposed idea.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. G. Ammar, W. Gragg,Superfast solution of real positive definite Toeplitz systems, SIAM J. Matr. Anal. Appl.9, (1988) 61–76.

    Article  MATH  MathSciNet  Google Scholar 

  2. O. Axelsson, G. Lindskög,The rate of convergence of the preconditioned conjugate gradient method, Num. Math.52, (1986) 499–523.

    Article  Google Scholar 

  3. O. Axelsson, M. Neytcheva,The algebraic multilevel iteration methods—theory and applications, Proc. of the 2nd Int. Coll. on Numerical Analysis D. Bainov Ed., Plovdiv (Bulgaria), August 1993, 13–23.

  4. D. Bini, M. Capovani,Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl.52/53, (1983) 99–126.

    MathSciNet  Google Scholar 

  5. D. Bini, F. Di Benedetto,A new preconditioner for the parallel solution of positive definite Toeplitz linear systems, Proc. 2nd SPAA conf. Crete (Greece), July 1990, 220–223.

    Google Scholar 

  6. D. Bini, P. Favati,On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl.14, (1993) 500–507.

    Article  MATH  MathSciNet  Google Scholar 

  7. R.H. Chan,Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal.11, (1991) 333–345.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Article  MATH  MathSciNet  Google Scholar 

  9. R.H. Chan, M. Ng,Conjugate gradient methods for Toeplitz systems, SIAM Rev.38, (1996) 427–482.

    Article  MATH  MathSciNet  Google Scholar 

  10. R.H. Chan, G. Strang,Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Stat. Comp.10, (1989) 104–119.

    Article  MATH  MathSciNet  Google Scholar 

  11. R.H. Chan, P. Tang,Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comp.15, (1994) 164–171.

    Article  MATH  MathSciNet  Google Scholar 

  12. T.F. Chan,An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comp.9, (1988) 766–771.

    Article  MATH  Google Scholar 

  13. T.F. Chan, P.C. Hansen,A look-ahead Levinson algorithm for indefinite Toeplitz systems, SIAM J. Matr. Anal Appl.13, (1992) 491–506.

    MathSciNet  Google Scholar 

  14. R. De Vore, G. Lorentz, Constructive Approximation, Springer-Verlag, Berlin, 1991.

    Google Scholar 

  15. F. Di Benedetto,Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comp.16, (1995) 682–697.

    Article  MATH  Google Scholar 

  16. F. Di Benedetto, G. Fiorentino, S. Serra,C.G. Preconditioning for Toeplitz Matrices, Comp. Math. Applic.6, (1993) 35–45.

    Article  Google Scholar 

  17. Z. Dizian, G. Freud,Linear approximation processes with limited oscillation, J. Approx. Th.12, (1974) 23–31.

    Article  Google Scholar 

  18. U. Grenander, G. Szegö, Toeplitz Forms and Their Applications, Second Edition, Chelsea, New York, 1984.

    MATH  Google Scholar 

  19. T. Huckle,Circulant and skewcirculant matrices for solving Toeplitz matrix problems, SIAM J. Matr. Anal. Appl.13, (1992) 767–777.

    Article  MATH  MathSciNet  Google Scholar 

  20. D. Jackson, The Theory of Approximation, American Mathematical Society, New York, 1930.

    MATH  Google Scholar 

  21. M. Kac, W. Murdoch, G. Szegö,On the extreme eigenvalues of certain Hermitian forms, J. Rat. Mech. Anal.13, (1953) 767–800.

    Google Scholar 

  22. P.P. Korovkin,Linear Operators and Approximation Theory (English translation), Hindustan Publishing Co., Delhi, 1960.

    Google Scholar 

  23. I.P. Natanson, Constructive Function Theory, I, Frederick Ungar Publishing Co., New York, 1964.

    Google Scholar 

  24. A. Oppenheim, Applications of Digital Signal Processing, Prentice-Hall, Englewood Cliffs, 1978.

    Google Scholar 

  25. S. Serra,Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT34, (1994) 579–594.

    Article  MATH  MathSciNet  Google Scholar 

  26. S. Serra,Conditioning and solution, by means of preconditioned conjugate gradient methods, of Hermitian (block) Toeplitz systems, Proc. in Advanced Signal Processing Algorithms, Architectures, and Implementations—SPIE conference F. Luk Ed., San Diego (CA), July 1995, 326–337.

  27. S. Serra,Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matr. Anal. Appl.17–4, (1996) 1007–1019.

    Article  MathSciNet  Google Scholar 

  28. S. Serra,On the extreme spectral properties of Toeplitz matrices generated by L 1 functions with several minima/maxima, BIT36, (1996) 135–142.

    Article  MATH  MathSciNet  Google Scholar 

  29. S. Serra,On the conditioning and solution, by means of multigrid methods, of symmetric (block) Toeplitz systems, Proc. 5th Int. Coll. on Differential Equations D. Bainov Ed., Plovdiv (Bulgaria), August 1995, 249–256.

  30. S. Serra,New PCG based algorithms for the solution of symmetric Toeplitz systems with L 1 generating functions, TR nr. 10, LAN, University of Calabria (1995).

  31. S. Serra,Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp.66, (1997), 651–665.

    Article  MATH  MathSciNet  Google Scholar 

  32. S. Serra,The extension of the concept of generatingfunction to a class of preconditioned Toeplitz matrices, Linear Algebra Appl., in press.

  33. S. Serra,On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl., in press.

  34. S. Serra,New PCG based algorithms for the solution of Hermitian Toeplitz systems, Calcolo, in press.

  35. S. Serra,Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp., to appear.

  36. S. Serra,How to choose the best iterative strategy for symmetric Toeplitz systems?, submitted (1996).

  37. E. Tyrtyshnikov,Optimal and superoptimal circulant preconditioners, SIAM J. Matr. Anal. Appl.13, (1992) 459–473.

    Article  MATH  MathSciNet  Google Scholar 

  38. C. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia, 1992.

    MATH  Google Scholar 

  39. R. S. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, 1962.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Energetica, Via Lombroso 6/17, 50100, Firenze

    Stefano Serra

  2. Dipartimento di Informatica, Corso Italia 40, 56100, Pisa, (Italy)

    Stefano Serra

Authors
  1. Stefano Serra
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Serra, S. A practical algorithm to design fast and optimal band-Toeplitz preconditioners for hermitian toeplitz systems. Calcolo 33, 209–221 (1996). https://doi.org/10.1007/BF02576001

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02576001

Keywords

AMS SC

Search

Navigation