Uppsala University
Department of Information Technology

### Technical Report 2014-024

# Toeplitz Matrices: Spectral Properties and Preconditioning in the CG Method

### Stefano Serra-Capizzano

December 2014

**Abstract:**
We consider multilevel Toeplitz matrices *T*_{n}(f) generated by Lebesgue integrable functions *f* defined over *I*^{d}, *I=[-pi,pi)*, *dge 1*. We are interested in the solution of linear systems with coefficient matrix *T*_{n}(f) when the size of *T*_{n}(f) is large. Therefore the use of iterative methods is recommended for computational and numerical stability reasons. In this note we focus our attention on the (preconditioned) conjugate gradient (P)CG method and on the case where the symbol *f* is known and univariate (*d=1*): the second section treat spectral properties of Toeplitz matrices *T*_{n}(f); the third deals with the spectral behavior of *T*_{n}^{-1}(g) T_{n}(f) and the fourth with the band Toeplitz preconditioning; in the fifth section we consider the matrix algebra preconditioning through the Korovkin theory. Then in the sixth section we study the multilevel case *d>1* by emphasizing the results that have a plain generalization (those in the Sections 2, 3, and 4) and the results which strongly depend on the number *d* of levels (those in Section 5): in particular the quality of the matrix algebra preconditioners (circulants, trigonometric algebras, Hartley etc.) deteriorates sensibly as *d* increases.

A section of conclusive remarks and two appendices treating the theory of the (P)CG method and spectral distributional results of structured matrix sequences.

Available as
PDF (641 kB, no cover)

Download BibTeX entry.