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 Tn(f) generated by Lebesgue integrable functions f defined over Id, I=[-pi,pi), dge 1. We are interested in the solution of linear systems with coefficient matrix Tn(f) when the size of Tn(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 Tn(f); the third deals with the spectral behavior of Tn-1(g) Tn(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.