Solution of Toeplitz normal equations by sine transform based preconditioning

The normal equations constructed by a Toeplitz matrix are studied, in order to find a suitable preconditioner related to the discrete sine transform. New results are given about the structure of the product of two Toeplitz matrices, which allow the CGN method to achieve a superlinear rate of convergence. This preconditioner outperforms the circulant one for the iterative solution of Toeplitz least-squares problems; such strategy can also be applied to nonsymmetric linear systems. A block generalization is discussed. Keyword list: Toeplitz matrix, least squares, normal equations, preconditioning, sine transform. AMS classification: 65F10, 65F15. 1 Introduction Let C m;n 2 R m\Thetan be a Toeplitz matrix , that is its (i; j) element is a function c i\Gammaj of the difference of indices. When the elements fc k g on each diagonal come from the formal Laurent expansion of a function r(z) = +1 X k=\Gamma1 c k z k on the unit circle, we use the notation C m;n = T m;n (r) (or Tn (r..