Fast algorithms for Toeplitz equations

We study efficient methods for solving large scale positive definite Toeplitz systems equations, both direct and iterative. Our main emphasis and contributions are for the iterative Preconditioned Conjugate Gradient Algorithm in conjunction with fast (O(nlog(n))) transforms. We develop a general scheme of constructing preconditioners from classes of matrices diagonalizable by a fast transform. Our method is demonstrated in detail for one of the Fast Sine Transforms. In particular we show: (i) how to construct such a preconditioner efficiently, (ii) asymptotic clustering of the spectra of preconditioned matrices, (iii) uniform boundedness of condition numbers of preconditioners corresponding to a projection method, (iv) positive definiteness of the preconditioner. A fast method is developed for Toeplitz matrix-vector multiplication using a Fast Sine Transform and real arithmetic. Traditionally the Fast Fourier Transform is used but this method requires complex arithmetic even when the Toeplitz matrix is real.

Other fast transforms and types of preconditioners are studied although in less detail.

The results of extensive numerical experimentation are presented.