Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA_nx=b by the preconditioned conjugate gradient method. Then ×n matrixA_n is of the forma₀I+H_n wherea₀ is a real number,I is the identity matrix andH_n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC_n and the skew-circulant matrixS_n whereA_n=1/2(C_n+S_n). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC^–1_n A_n andS^–1_nA_n. For Toeplitz matricesA_n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC_n andS_n and prove that the singular values ofC^–1_nA_n andS^–1_nA_n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.