Superlinear PCG methods for symmetric Toeplitz systems
HTML articles powered by AMS MathViewer
- by Stefano Serra PDF
- Math. Comp. 68 (1999), 793-803 Request permission
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
- 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, DOI 10.1137/0609005
- 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, DOI 10.1007/BF01389447
- Dario Bini and Milvio Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl. 52/53 (1983), 99â126. MR 709346, DOI 10.1016/0024-3795(83)80009-3
- 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.
- 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, DOI 10.1137/0614035
- E. Bozzo, Matrix Algebras and Discrete Transforms. PhD. thesis in Comp. Sci., Dept. Comp. Sci., University of Pisa, Italy, 1994.
- R.H. Chan, âToeplitz preconditioners for Toeplitz systems with nonnegative generating functionsâ, IMA J. Numer. Anal., 11, pp. 333â345 (1991).
- 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, DOI 10.1137/S1064827594266581
- Raymond H. Chan and Michael K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38 (1996), no. 3, 427â482. MR 1409592, DOI 10.1137/S0036144594276474
- 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, DOI 10.1137/0910009
- 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, DOI 10.1137/0915011
- 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, DOI 10.1090/S0025-5718-1992-1106960-1
- 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, DOI 10.1016/0021-9045(92)90084-2
- Tony F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), no. 4, 766â771. MR 945937, DOI 10.1137/0909051
- E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
- Philip J. Davis, Circulant matrices, A Wiley-Interscience Publication, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 543191
- Frank de Hoog, A new algorithm for solving Toeplitz systems of equations, Linear Algebra Appl. 88/89 (1987), 123â138. MR 882445, DOI 10.1016/0024-3795(87)90107-8
- Fabio Di Benedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comput. 16 (1995), no. 3, 682â697. MR 1326818, DOI 10.1137/0916041
- Fabio Di Benedetto, Giuseppe Fiorentino, and Stefano Serra, CG preconditioning for Toeplitz matrices, Comput. Math. Appl. 25 (1993), no. 6, 35â45. MR 1201877, DOI 10.1016/0898-1221(93)90297-9
- F. Di Benedetto and S. Serra Capizzano, âA unifying approach to matrix algebra preconditioningâ, Numer. Math., in press.
- I. C. Gohberg and I. A. Felâ˛dman, Convolution equations and projection methods for their solution, Translations of Mathematical Monographs, Vol. 41, American Mathematical Society, Providence, R.I., 1974. Translated from the Russian by F. M. Goldware. MR 0355675
- 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
- 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.
- Ulf Grenander and Murray Rosenblatt, Statistical analysis of stationary time series, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890514
- Ulf Grenander and GĂĄbor SzegĹ, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
- D. Jackson, The Theory of Approximation. Amer. Math. Soc., New York, 1930.
- X.-Q. Jin, Hartley preconditioners for Toeplitz systems generated by positive continuous functions, BIT 34 (1994), no. 3, 367â371. MR 1429937, DOI 10.1007/BF01935646
- Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82â96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
- A. Oppenheim, Applications of Digital Signal Processing. PrenticeâHall, Englewood Cliffs, NJ, 1978.
- Walter Rudin, Principles of mathematical analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-DĂźsseldorf, 1976. MR 0385023
- Stefano Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT 34 (1994), no. 4, 579â594. MR 1430910, DOI 10.1007/BF01934269
- 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.
- 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, DOI 10.1137/S089547989427141X
- S. Serra, âOn the extreme eigenvalues of Hermitian (block) Toeplitz matricesâ, Linear Algebra Appl., 270, pp. 109â129 (1998).
- Stefano Serra, On the extreme spectral properties of Toeplitz matrices generated by $L^1$ functions with several minima/maxima, BIT 36 (1996), no. 1, 135â142. MR 1431579, DOI 10.1007/BF01740550
- S. Serra, âAsymptotic results on the spectra of preconditioned Toeplitz matrices and some applicationsâ, TR nr. 9, LAN - Dept. Math., University of Calabria, (1995).
- 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, DOI 10.1090/S0025-5718-97-00833-8
- E. E. Tyrtyshnikov, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1â23. MR 1319972, DOI 10.1016/0024-3795(93)00092-E
- 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, DOI 10.1137/1.9781611970999
- A. Zygmund, Trigonometric series. 2nd ed. Vols. I, II, Cambridge University Press, New York, 1959. MR 0107776
Additional Information
- Stefano Serra
- Affiliation: Dipartimento di Informatica, Corso Italia 40, 56100 Pisa (ITALY)
- MR Author ID: 332436
- Email: serra@mail.dm.unipi.it
- Received by editor(s): February 7, 1996
- Received by editor(s) in revised form: October 15, 1996, and July 18, 1997
- © Copyright 1999 American Mathematical Society
- 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