Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems

Serra, Stefano

doi:10.1090/S0025-5718-97-00833-8

Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems
HTML articles powered by AMS MathViewer

by Stefano Serra PDF

Math. Comp. 66 (1997), 651-665 Request permission

Abstract:

In this paper we are concerned with the solution of $n\times n$ Hermitian Toeplitz systems with nonnegative generating functions $f$. The preconditioned conjugate gradient (PCG) method with the well–known circulant preconditioners fails in the case where $f$ has zeros. In this paper we consider as preconditioners band–Toeplitz matrices generated by trigonometric polynomials $g$ of fixed degree $l$. We use different strategies of approximation of $f$ to devise a polynomial $g$ which has some analytical properties of $f$, is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent of $n$. For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates of $l$ for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.

References

N. Ahmed, T. Natarajan, and K. R. Rao, Discrete cosine transform, IEEE Trans. Comput. C-23 (1974), 90–93. MR 356555, DOI 10.1109/t-c.1974.223784
O. Axelsson and V. A. Barker, Finite element solution of boundary value problems, Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. Theory and computation. MR 758437
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
D. Bini, Matrix structures in parallel matrix computations, Calcolo 25 (1988), no. 1-2, 37–51 (1989) (English, with Italian summary). MR 1053746, DOI 10.1007/BF02575746
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
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
Raymond H. Chan, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal. 11 (1991), no. 3, 333–345. MR 1118960, DOI 10.1093/imanum/11.3.333
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.
R.H. Chan, Q. Chang, H. Sun, “Multigrid method for ill-conditioned symmetric Toeplitz systems”, personal communication.
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
R.H. Chan, P. Tang, “Constrained minimax approximation and optimal preconditioners for Toeplitz matrices”, Numer. Alg., 5 (1993), 353–364.
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
Philip J. Davis, Circulant matrices, A Wiley-Interscience Publication, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 543191
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
G. Fiorentino and S. Serra, Multigrid methods for Toeplitz matrices, Calcolo 28 (1991), no. 3-4, 283–305 (1992). MR 1219617, DOI 10.1007/BF02575816
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
Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
I. S. Iohvidov, Hankel and Toeplitz matrices and forms, Birkhäuser, Boston, Mass., 1982. Algebraic theory; Translated from the Russian by G. Philip A. Thijsse; With an introduction by I. Gohberg. MR 677503
D. Jackson, The Theory of Approximation. American Mathematical Society, New York, 1930.
Günter Meinardus, Approximation of functions: Theory and numerical methods, Expanded translation of the German edition, Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. Translated by Larry L. Schumaker. MR 0217482, DOI 10.1007/978-3-642-85643-3
A. Oppenheim, Applications of Digital Signal Processing. Prentice–Hall, Englewood Cliffs, 1978.
M. J. D. Powell, On the maximum errors of polynomial approximations defined by interpolation and by least squares criteria, Comput. J. 9 (1967), 404–407. MR 208807, DOI 10.1093/comjnl/9.4.404
E.J. Remes, “Sur le calcul effectif des polynomes d’approximation de Tchebichef” Compt. Rend. Acad. Sci. Paris, 199 (1934), 337–340.
S. Serra, “Preconditioning strategies for asymptotically ill–conditioned block Toeplitz systems”, BIT, 34 (1994), pp. 579–594.
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.
S. Serra, “Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions”, SIAM J. Matr. Anal. Appl., 17 (1996), pp. 1007–1019.
S. Serra, “On the extreme eigenvalues of Hermitian (block) Toeplitz matrices”, Linear Algebra Appl., to appear.
S. Serra, “On the extreme spectral properties of Toeplitz matrices generated by $L^1$ functions with several minima (maxima)”, BIT, 36 (1996), 135–142.
S. Serra, “Asymptotic results on the spectra of preconditioned Toeplitz matrices and some applications”, TR nr. 9 University of Calabria, (1995).
Ping Tak Peter Tang, A fast algorithm for linear complex Chebyshev approximations, Math. Comp. 51 (1988), no. 184, 721–739. MR 935074, DOI 10.1090/S0025-5718-1988-0935074-5
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
Stephen J. Wright, Parallel algorithms for banded linear systems, SIAM J. Sci. Statist. Comput. 12 (1991), no. 4, 824–842. MR 1102410, DOI 10.1137/0912044