Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Toeplitz approximate inverse preconditioner for banded Toeplitz matrices

  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

In this paper we introduce a new preconditioner for banded Toeplitz matrices, whose inverse is itself a Toeplitz matrix. Given a banded Hermitian positive definite Toeplitz matrixT, we construct a Toepliz matrixM such that the spectrum ofMT is clustered around one; specifically, if the bandwidth ofT is β, all but β eigenvalues ofMT are exactly one. Thus the preconditioned conjugate gradient method converges in β+1 steps which is about half the iterations as required by other preconditioners for Toepliz systems that have been suggested in the literature. This idea has a natural extension to non-banded and non-Hermitian Toeplitz matrices, and to block Toeplitz matrices with Toeplitz blocks which arise in many two dimensional applications in signal processing. Convergence results are given for each scheme, as well as numerical experiments illustrating the good convergence properties of the new preconditioner.

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.S. Ammar and W.B. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988) 61–76.

    Google Scholar 

  2. O. Axelsson and V.A. Barker,Finite Element Solution of Boundary Value Problems, Theory and Computation (Academic Press, New York, 1984).

    Google Scholar 

  3. E.H. Bareiss, Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices, Numer. Math. 13 (1969) 404–424.

    Google Scholar 

  4. A. Björck, Least squares method, in:Handbook of Numerical Analysis vol. 1, eds. P.G. Ciarlet and J.L. Lions (Elsevier/North-Holland, 1990).

  5. A.W. Bojanczyk, R.P. Brent and F.R. de Hoog, QR factorization of Toeplitz matrices, Numer. Math. 49 (1986) 81–94.

    Google Scholar 

  6. J.R. Bunch, Stability of methods for solving Toeplitz systems of equations. SIAM J. Sci. Statist. Comp. 6 (1985) 349–364.

    Google Scholar 

  7. R.H. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10 (1989) 542–550.

    Google Scholar 

  8. R.H. Chan and X.-Q. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comp. 13 (1992) 1218–1235.

    Google Scholar 

  9. R.H. Chan, J.G. Nagy and R.J. Plemmons, Circulant preconditioned Toeplitz least squares iterations, SIAM J. Matrix Anal. Appl. 15 (1994), to appear.

  10. R.H. Chan and K.-P. Ng, Toeplitz preconditioners for Hermitian Toeplitz systems, Lin. Alg. Appl. 190 (1993) 181–208.

    Google Scholar 

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

    Google Scholar 

  12. R.H. Chan and M.-C. Yeung, Circulant preconditioners for complex Toeplitz matrices, SIAM J. Numer. Anal. 30 (1993) 1193–1207.

    Google Scholar 

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

    Google Scholar 

  14. T. Chan and J. Olkin, Preconditioners for Toeplitz-block matrices, Numer. Algor. 6 (1994) 89–101.

    Google Scholar 

  15. P.J. Davis,Circulant Matrices (Wiley, New York, 1979).

    Google Scholar 

  16. R.W. Freund, G.H. Golub and N.M. Nachtigal, Iterative, solution of linear systems, Acta Numer. 1 (1991) 1–44.

    Google Scholar 

  17. G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, MD, 2nd ed., 1989).

    Google Scholar 

  18. M. Hanke, J.G. Nagy and R.J. Plemmons, Preconditioned iterative regularization for ill-posed problems, in:Numerical Linear Algebra and Scientific Computing, eds., L. Reichel, A. Ruttan and R.S. Varga (de Gruyter, Berlin, 1993) pp. 141–163.

    Google Scholar 

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

    Google Scholar 

  20. T. Huckle, Some aspects of circulant preconditioners, SIAM J. Sci. Statist. Comp. 14 (1993) 531–541.

    Google Scholar 

  21. A.K. Jain, Fast inversion of banded Toeplitz matrices by circular decompositions, IEEE Trans. Acoust. Speech Signal Process. 26 (1978) 121–126.

    Google Scholar 

  22. A.K. Jain,Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1989).

    Google Scholar 

  23. S.L. Johnsson, Solving narrow banded systems on ensemble architectures, ACM Trans. Math. Software 11 (1985) 271–288.

    Google Scholar 

  24. T.-K. Ku and C.-C. Kuo, Design and analysis of Toeplitz preconditioners, IEEE Trans. Acoust. Speech Signal Process. 40 (1992) 129–140.

    Google Scholar 

  25. T.-K. Ku and C.-C. Kuo, Spectral properties of preconditioned rational Toeplitz matrices: the nonsymmetric case, SIAM J. Matrix Anal. Appl. 14 (1993) 521–544.

    Google Scholar 

  26. T.-K. Ku and C.-C. Kuo, On the spectrum of a family of preconditioned block Toeplitz matrices, SIAM J. Sci. Statist. Comp. 13 (1992) 948–966.

    Google Scholar 

  27. E. Linzer, On the stability of solution methods for band Toeplitz systems, Lin. Alg. Appl. 170 (1992) 1–32.

    Google Scholar 

  28. A.V. Oppenheim and R.W. Schafer,Discrete-Time Signal Processing, (Prentice-Hall, Englewood Cliffs, NJ, 1989).

    Google Scholar 

  29. G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986) 171–176.

    Google Scholar 

  30. M. Tismenetsky, A decomposition of Toeplitz matrices and optimal circulant preconditioning, Lin. Alg. Appl. 154–156 (1991) 105–121.

    Google Scholar 

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

    Google Scholar 

  32. C. Van Loan,Computational Frameworks for the Fast Fourier Transform (SIAM, Philadelphia, PA, 1992).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Praktische Mathematik, Universität Karlsruhe, D-76128, Karlsruhe, Germany

    Martin Hanke

  2. Department of Mathematics, Southern Methodist University, 75275-0156, Dallas, TX, USA

    James G. Nagy

Authors
  1. Martin Hanke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James G. Nagy
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by M.H. Gutknecht

Partly supported by a travel fund from the Deutsche Forschungsgemeinschaft.

Research supported in part by Oak Ridge Associated Universities grant no. 009707.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hanke, M., Nagy, J.G. Toeplitz approximate inverse preconditioner for banded Toeplitz matrices. Numer Algor 7, 183–199 (1994). https://doi.org/10.1007/BF02140682

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Subject classification

Search

Navigation