@TechReport{ it:2014-024,
author = {Stefano Serra-Capizzano},
title = {{T}oeplitz Matrices: Spectral Properties and
Preconditioning in the {CG} Method},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2014},
number = {2014-024},
month = dec,
abstract = {We consider multilevel Toeplitz matrices $T_n(f)$
generated by Lebes\-gue integrable functions $f$ defined
over $I^d$, $I=[-\pi,\pi)$, $d\ge 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.}
}