Conditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods

Let {An(f)} be a sequence of nested n × n Toeplitz matrices generated by a Lebesgue integrable real-function f defined on [-π, π]. In this paper we, firstly, present some results about the spectral properties of An(f) (density, range, behaviour of the extreme eigenvalues etc.), then we apply these results to the preconditioning problem. We analyze in detail the preconditioned conjugate gradient (PCG) method, where the proposed preconditioners An(g) are positive definite Toeplitz matrices generated by essentially nonnegative functions g. In order to estimate the convergence speed of these algorithms we study the spectral behaviour of the preconditioned matrices An-1(g)An(f): we obtain new results about the range, the density and the extremal properties of their spectra. In particular we deal with the critical case where the matrices An(f) are asymptotically ill-conditioned, i.e., zero belongs to the convex hull of the essential range of f. We consider positive definite Toeplitz linear systems (f ≥ 0), nondefinite Toeplitz linear systems (f with nondefinite sign), with zeros of generic orders. Moreover, these analyses and techniques are partially extended to the block case too.