Fast Transform Based Preconditioners for Toeplitz Equations

We present a new preconditioner for $n \times n$ symmetric, positive definite Toeplitz systems. This preconditioner is an element of the n-dimensional vector space of matrices that are diagonalized by the discrete sine transform. Conditions are given for which the preconditioner is positive definite and for which the preconditioned system has asymptotically clustered eigenvalues. The diagonal form of the preconditioner can be calculated in $O( n \log ( n ) )$ operations if $n = 2^k - 1$. Thus only n additional parameters need be stored. Moreover, complex arithmetic is not needed. To use the preconditioner effectively, we develop a new technique for computing a fast convolution using the discrete sine transform (also requiring only real arithmetic). The results of numerical experimentation with this preconditioner are presented. Our preconditioner is comparable, and in some cases superior, to the standard circulant preconditioner of Tony Chan. Possible generalizations for other fast transforms are also ind...