An introduction to iterative Toeplitz solvers.

*(English)*Zbl 1146.65028
Fundamentals of Algorithms 5. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-36-8/pbk; 978-0-89871-885-0/ebook). xii, 111 p. (2007).

In the book iterative solvers for Toeplitz systems are presented and analysed.

In the first Chapter, Toeplitz systems are introduced and some basics from the matrix analysis are provided. Chapter 2 is devoted to the study of circulant preconditioners for the preconditioned conjugate gradient method (pcg). Preconditioners which are known from the literature are introduced and a convergence analysis of the pcg method with these preconditioners is given. These preconditioners are efficient for some well-conditioned Hermitian Toeplitz systems.

In Chapter 3, the authors develop a general approach for the construction of circulant preconditioners. The main idea is to get the preconditioners from convoluting the generating function of the given Toeplitz matrix with some famous kernels. Based on the approach presented in Chapter 3 efficient circulant preconditioners for ill-conditioned Hermitian Toeplitz systems are constructed in Chapter 4. The convergence properties of the resulting pcg method are analysed. In Chapter 5, block circulant preconditioners for block Toeplitz systems, where the blocks are Toeplitz matrices, are presented and the convergence of the pcg method is investigated.

Some numerical examples illustrate the effectiveness of the proposed methods. The appendix of the book contains Matlab routines which were used for getting the numerical results.

In the first Chapter, Toeplitz systems are introduced and some basics from the matrix analysis are provided. Chapter 2 is devoted to the study of circulant preconditioners for the preconditioned conjugate gradient method (pcg). Preconditioners which are known from the literature are introduced and a convergence analysis of the pcg method with these preconditioners is given. These preconditioners are efficient for some well-conditioned Hermitian Toeplitz systems.

In Chapter 3, the authors develop a general approach for the construction of circulant preconditioners. The main idea is to get the preconditioners from convoluting the generating function of the given Toeplitz matrix with some famous kernels. Based on the approach presented in Chapter 3 efficient circulant preconditioners for ill-conditioned Hermitian Toeplitz systems are constructed in Chapter 4. The convergence properties of the resulting pcg method are analysed. In Chapter 5, block circulant preconditioners for block Toeplitz systems, where the blocks are Toeplitz matrices, are presented and the convergence of the pcg method is investigated.

Some numerical examples illustrate the effectiveness of the proposed methods. The appendix of the book contains Matlab routines which were used for getting the numerical results.

Reviewer: Michael Jung (Dresden)

##### MSC:

65F10 | Iterative numerical methods for linear systems |

65-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis |

65F35 | Numerical computation of matrix norms, conditioning, scaling |

65Y15 | Packaged methods for numerical algorithms |