Conjugate gradient methods for Toeplitz systems. (English) Zbl 0863.65013

The use of preconditioned conjugate gradient methods to solve linear systems of equations with Toeplitz matrices is discussed. Using this iterative method, the complexity is reduced from \(O(n\log^2n)\) operations for fast direct Toeplitz solvers to \(O(n \log n)\). The authors review the use of preconditioners based on circulant matrices, embedding, minimization of norms, optimal transform (like the fast Fourier or sine transform) and band Toeplitz matrices. The various techniques are applied for solving partial differential equations, queuing problems, signal and image restoration, integral equations and time series analysis (filtering).
Reviewer: W.Gander (Zürich)


65F10 Iterative numerical methods for linear systems
68U10 Computing methodologies for image processing
65F35 Numerical computation of matrix norms, conditioning, scaling
65R20 Numerical methods for integral equations
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65C99 Probabilistic methods, stochastic differential equations
Full Text: DOI