CIRCULANT AND SKEW-CIRCULANT PRECONDITIONERS FOR SKEW-HERMITIAN-TYPE TOEPLITZ-SYSTEMS

We study the solutions of Toeplitz systems A(n)x = b by the preconditioned conjugate gradient method. The n x n matrix A(n) is of the form a0I + H(n) where a0 is a real number, I is the identity matrix and H(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 matrix C(n) and the skew-circulant matrix S(n) where A(n) = 1/2(C(n) + S(n)). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C(n)-1 A(n) and S(n)-1 A(n). For Toeplitz matrices A(n) with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of C(n) and S(n) and prove that the singular values of C(n)-1 A(n) and S(n)-1 A(n) are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.