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.
Similar content being viewed by others
References
G. Ammar, W. Gragg,Superfast solution of real positive definite Toeplitz systems, SIAM J. Matr. Anal. Appl.9, (1988) 61–76.
O. Axelsson, G. Lindskög,The rate of convergence of the preconditioned conjugate gradient method, Num. Math.52, (1986) 499–523.
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.
D. Bini, M. Capovani,Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl.52/53, (1983) 99–126.
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.
D. Bini, P. Favati,On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl.14, (1993) 500–507.
R.H. Chan,Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal.11, (1991) 333–345.
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, M. Ng,Conjugate gradient methods for Toeplitz systems, SIAM Rev.38, (1996) 427–482.
R.H. Chan, G. Strang,Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Stat. Comp.10, (1989) 104–119.
R.H. Chan, P. Tang,Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comp.15, (1994) 164–171.
T.F. Chan,An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comp.9, (1988) 766–771.
T.F. Chan, P.C. Hansen,A look-ahead Levinson algorithm for indefinite Toeplitz systems, SIAM J. Matr. Anal Appl.13, (1992) 491–506.
R. De Vore, G. Lorentz, Constructive Approximation, Springer-Verlag, Berlin, 1991.
F. Di Benedetto,Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comp.16, (1995) 682–697.
F. Di Benedetto, G. Fiorentino, S. Serra,C.G. Preconditioning for Toeplitz Matrices, Comp. Math. Applic.6, (1993) 35–45.
Z. Dizian, G. Freud,Linear approximation processes with limited oscillation, J. Approx. Th.12, (1974) 23–31.
U. Grenander, G. Szegö, Toeplitz Forms and Their Applications, Second Edition, Chelsea, New York, 1984.
T. Huckle,Circulant and skewcirculant matrices for solving Toeplitz matrix problems, SIAM J. Matr. Anal. Appl.13, (1992) 767–777.
D. Jackson, The Theory of Approximation, American Mathematical Society, New York, 1930.
M. Kac, W. Murdoch, G. Szegö,On the extreme eigenvalues of certain Hermitian forms, J. Rat. Mech. Anal.13, (1953) 767–800.
P.P. Korovkin,Linear Operators and Approximation Theory (English translation), Hindustan Publishing Co., Delhi, 1960.
I.P. Natanson, Constructive Function Theory, I, Frederick Ungar Publishing Co., New York, 1964.
A. Oppenheim, Applications of Digital Signal Processing, Prentice-Hall, Englewood Cliffs, 1978.
S. Serra,Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT34, (1994) 579–594.
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.
S. Serra,Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matr. Anal. Appl.17–4, (1996) 1007–1019.
S. Serra,On the extreme spectral properties of Toeplitz matrices generated by L 1 functions with several minima/maxima, BIT36, (1996) 135–142.
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.
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).
S. Serra,Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp.66, (1997), 651–665.
S. Serra,The extension of the concept of generatingfunction to a class of preconditioned Toeplitz matrices, Linear Algebra Appl., in press.
S. Serra,On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl., in press.
S. Serra,New PCG based algorithms for the solution of Hermitian Toeplitz systems, Calcolo, in press.
S. Serra,Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp., to appear.
S. Serra,How to choose the best iterative strategy for symmetric Toeplitz systems?, submitted (1996).
E. Tyrtyshnikov,Optimal and superoptimal circulant preconditioners, SIAM J. Matr. Anal. Appl.13, (1992) 459–473.
C. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia, 1992.
R. S. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, 1962.
Author information
Authors and Affiliations
Rights 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
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02576001