A decomposition of Toeplitz matrices and optimal circulant preconditioning (Q811088)

Using a representation of Pustylnikov for a Toeplitz matrix T, the author is able to find that circulant matrix C which minimizes the Frobenius norm of I-CT. To compute it, fast Fourier transformation can be utilized so that the operation count is O(nlog n). Numerical experiments with 15\(\times 15\) and 36\(\times 36\) Toeplitz matrices show that T preconditioned by C has a spectrum clustered around unity (except for the extreme eigenvalues); for the best preconditioning proposed here the computed spectral radii of the corresponding iteration matrices turned out to be less than 0.5.