Superlinear PCG methods
for symmetric Toeplitz systems
Author:
Stefano Serra
Journal:
Math. Comp. 68 (1999), 793-803
MSC (1991):
Primary 65F10, 65F15
DOI:
https://doi.org/10.1090/S0025-5718-99-01045-5
MathSciNet review:
1620251
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: In this paper we deal with the solution, by means of preconditioned conjugate gradient (PCG) methods, of symmetric Toeplitz systems
with nonnegative generating function
. Here the function
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
approximation of
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
ops. Under the second hypothesis we cannot guarantee that the natural
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
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.
- 1. Gregory S. Ammar and William B. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988), no. 1, 61–76. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938136, https://doi.org/10.1137/0609005
- 2. Owe Axelsson and Gunhild Lindskog, On the eigenvalue distribution of a class of preconditioning methods, Numer. Math. 48 (1986), no. 5, 479–498. MR 839613, https://doi.org/10.1007/BF01389447
- 3. Dario Bini and Milvio Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl. 52/53 (1983), 99–126. MR 709346, https://doi.org/10.1016/0024-3795(83)80009-3
- 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. Dario Bini and Paola Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl. 14 (1993), no. 2, 500–507. MR 1211803, https://doi.org/10.1137/0614035
- 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. Raymond H. Chan and Wai-Ki Ching, Toeplitz-circulant preconditioners for Toeplitz systems and their applications to queueing networks with batch arrivals, SIAM J. Sci. Comput. 17 (1996), no. 3, 762–772. MR 1384265, https://doi.org/10.1137/S1064827594266581
- 9. Raymond H. Chan and Michael K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38 (1996), no. 3, 427–482. MR 1409592, https://doi.org/10.1137/S0036144594276474
- 10. Raymond H. Chan and Gilbert Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10 (1989), no. 1, 104–119. MR 976165, https://doi.org/10.1137/0910009
- 11. Raymond H. Chan and Ping Tak Peter Tang, Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comput. 15 (1994), no. 1, 164–171. MR 1257161, https://doi.org/10.1137/0915011
- 12. Raymond H. Chan and Man-Chung Yeung, Circulant preconditioners for Toeplitz matrices with positive continuous generating functions, Math. Comp. 58 (1992), no. 197, 233–240. MR 1106960, https://doi.org/10.1090/S0025-5718-1992-1106960-1
- 13. Raymond H. Chan and Man-Chung Yeung, Jackson’s theorem and circulant preconditioned Toeplitz systems, J. Approx. Theory 70 (1992), no. 2, 191–205. MR 1172018, https://doi.org/10.1016/0021-9045(92)90084-2
- 14. Tony F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), no. 4, 766–771. MR 945937, https://doi.org/10.1137/0909051
- 15. E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
- 16. Philip J. Davis, Circulant matrices, John Wiley & Sons, New York-Chichester-Brisbane, 1979. A Wiley-Interscience Publication; Pure and Applied Mathematics. MR 543191
- 17. Frank de Hoog, A new algorithm for solving Toeplitz systems of equations, Linear Algebra Appl. 88/89 (1987), 123–138. MR 882445, https://doi.org/10.1016/0024-3795(87)90107-8
- 18. Fabio Di Benedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comput. 16 (1995), no. 3, 682–697. MR 1326818, https://doi.org/10.1137/0916041
- 19. Fabio Di Benedetto, Giuseppe Fiorentino, and Stefano Serra, CG preconditioning for Toeplitz matrices, Comput. Math. Appl. 25 (1993), no. 6, 35–45. MR 1201877, https://doi.org/10.1016/0898-1221(93)90297-9
- 20. F. Di Benedetto and S. Serra Capizzano, ``A unifying approach to matrix algebra preconditioning'', Numer. Math., in press.
- 21. I. C. Gohberg and I. A. Fel′dman, Convolution equations and projection methods for their solution, American Mathematical Society, Providence, R.I., 1974. Translated from the Russian by F. M. Goldware; Translations of Mathematical Monographs, Vol. 41. MR 0355675
- 22. Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
- 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. Ulf Grenander and Murray Rosenblatt, Statistical analysis of stationary time series, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890514
- 25. Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
- 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 (1994), no. 3, 367–371. MR 1429937, https://doi.org/10.1007/BF01935646
- 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. Walter Rudin, Principles of mathematical analysis, 3rd ed., McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976. International Series in Pure and Applied Mathematics. MR 0385023
- 31. Stefano Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT 34 (1994), no. 4, 579–594. MR 1430910, https://doi.org/10.1007/BF01934269
- 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. Stefano Serra, Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 1007–1019. MR 1410714, https://doi.org/10.1137/S089547989427141X
- 34. S. Serra, ``On the extreme eigenvalues of Hermitian (block) Toeplitz matrices'', Linear Algebra Appl., 270, pp. 109-129 (1998). CMP 98:05
- 35. Stefano Serra, On the extreme spectral properties of Toeplitz matrices generated by 𝐿¹ functions with several minima/maxima, BIT 36 (1996), no. 1, 135–142. MR 1431579, https://doi.org/10.1007/BF01740550
- 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. Stefano Serra, Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp. 66 (1997), no. 218, 651–665. MR 1401945, https://doi.org/10.1090/S0025-5718-97-00833-8
- 38. E. E. Tyrtyshnikov, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1–23. MR 1319972, https://doi.org/10.1016/0024-3795(93)00092-E
- 39. Charles Van Loan, Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1153025
- 40. A. Zygmund, Trigonometric series. 2nd ed. Vols. I, II, Cambridge University Press, New York, 1959. MR 0107776
Retrieve articles in Mathematics of Computation 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)
Email:
serra@mail.dm.unipi.it
DOI:
https://doi.org/10.1090/S0025-5718-99-01045-5
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