Chan, Raymond H.; Ng, Michael K. Conjugate gradient methods for Toeplitz systems. (English) Zbl 0863.65013 SIAM Rev. 38, No. 3, 427-482 (1996). 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) Cited in 335 Documents MSC: 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 Keywords:fast Fourier transform; fast sine transform; preconditioned conjugate gradient methods; Toeplitz matrices; complexity; circulant matrices; queuing problems; signal and image restoration; integral equations; time series analysis; filtering PDFBibTeX XMLCite \textit{R. H. Chan} and \textit{M. K. Ng}, SIAM Rev. 38, No. 3, 427--482 (1996; Zbl 0863.65013) Full Text: DOI