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
operations for fast direct Toeplitz solvers to
. 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).