Chan R.H.-F., Jin X.-Q. An Introduction to Iterative Toeplitz Solvers

Society for Industrial and Applied Mathematics, 2009, -124 pp.In this book, we introduce current developments and applications in using iterative methods for solving Toeplitz systems. Toeplitz systems arise in a variety of applications in mathematics, scientific computing, and engineering, for instance, numerical partial and ordinary differential equations; numerical solution of convolution-type integral equations; stationary autoregressive time series in statistics; minimal realization problems in control theory; system identification problems in signal processing and image restoration problems in image processing; see [24, 36, 45, 55, 66].
In 1986, Strang [74] and Olkin [67] proposed independently the use of the preconditioned conjugate gradient (PCG) method with circulant matrices as preconditioners to solve Toeplitz systems. One of the main results of this iterative solver is that the complexity of solving a large class of n-by-n Toeplitz systems T_nu=b is only O(nlog n) operations. Since then, iterative Toeplitz solvers have garnered much attention and evolved rapidly over the last two decades.
This book is intended to be a short and quick guide to the development of iterative Toeplitz solvers based on the PCG method. Within limited space and time, we are forced to deal with only important aspects of iterative Toeplitz solvers and give special attention to the construction of efficient circulant preconditioners. Applications of iterative Toeplitz solvers to some practical problems will be briefly discussed. We wish that after reading the book, the readers can use our methods and algorithms to solve their own problems easily.Circulant preconditioners
Unified treatment from kernels
Ill-conditioned Toeplitz systems
Block Toeplitz systems
M-files used in the book