On the Iterative Solution of Toeplitz Systems
by
Dimitrios Noutsos
Department of Mathematics, University of Ioannina, GR-451 10, Ioannina, Greece

Applications to Toeplitz systems arise from image and signal processing, time series analysis, partial differential equations, integral equations, Pade approximation, control theory and statistics. Fast Direct methods solve Toeplitz linear systems in O(nlog²n) operations but they are, in general, unstable. The most famous methods that solve Toeplitz systems are Preconditioned Conjugate Gradient ones which reduce in many cases the cost in O(nlogn) operations and guarantee the stability.

Three classes of preconditioners proposed for Toeplitz systems are presented and reviewed:

Circulant preconditioners can be used in Toeplitz systems generated by positive functions. These preconditioners are based on the approximation of Toeplitz matrices by circulant ones and solved in O(nlogn) operations by Fast Fourier Transform (FFT).

Band Toeplitz preconditioners can be used in Toeplitz systems generated by nonnegative functions with roots of even multiplicity. They are based on trigonometric polynomials that elliminate the roots and approximate the generating functions by best Chebyshev approximation or by best rational approximation. Some numerical experiments are illustrated to compare the methods.

W-circulant preconditioners can be used in the cases mentioned above as well as in the nondefinite case by applying to the system of normal equations.

Finally, some comments for the multigrid strategy and for the solution of multilevel Toeplitz systems are given.

Date received: March 25, 2001