Circulant and Skewcirculant Matrices for Solving Toeplitz Matrix Problems

In recent papers, numerous authors studied the solutions of symmetric positive definite Toeplitz systems $Tx = b$ by the conjugate gradient method for different families of circulant preconditioners C. In this paper new circulant / skewcirculant approximations are introduced to T and their properties are studied. The main interest is directed to the skewcirculant case. Furthermore, algorithms for computing the eigenvalues of T are formulated, based on the Lanczos algorithm and Rayleigh quotient iteration. For some numerical examples the spectra of C- 1 T are compared and the behaviour of the introduced eigenvalue algorithms is displayed.