Accelerated Circulant and Skew Circulant Splitting Methods for Hermitian Positive Definite Toeplitz Systems

We study the CSCS method for large Hermitian positive definite Toeplitz linear systems, which first appears in Ng's paper published in (Ng, 2003), and CSCS stands for circulant and skew circulant splitting of the coefficient matrix . In this paper, we present a new iteration method for the numerical solution of Hermitian positive definite Toeplitz systems of linear equations. The method is a two-parameter generation of the CSCS method such that when the two parameters involved are equal, it coincides with the CSCS method. We discuss the convergence property and optimal parameters of this method. Finally, we extend our method to BTTB matrices. Numerical experiments are presented to show the effectiveness of our new method. 1. Introduction We consider iterative solution of the large system of linear equations where is Hermitian positive definite Toeplitz matrix and . An -by- matrix is said to be Toeplitz if ; that is, is constant along its diagonals. Toeplitz systems arise in a variety of applications, especially in signal processing and control theory. Many direct methods are proposed for solving Toeplitz linear systems. A straightforward application of Gaussian elimination will lead to an algorithm with complexity. There are a number of fast Toeplitz solvers that decrease the complexity to operations, see for instance [1–3]. Around 1980, superfast direct Toeplitz solvers of complexity , such as the one by Ammar and Gragg [4], were also developed. Recent research on using the preconditioned conjugate gradient method as an iterative method for solving Toeplitz systems has brought much attention. One of the main important results of this methodology is that the PCG method has a computational complexity proportional to for a large class of problem [5] and is therefore competitive with any direct method. In [6], an iterative method based on circulant and skew circulant splitting (CSCS) of the Toeplitz matrix was given. The authors have driven an upper bound of the contraction factor of the CSCS iteration which is dependent solely on the spectra of the circulant and the skew circulant matrices involved. In [7] the authors studied the HSS iteration method for large sparse non-Hermitian positive definite Toeplitz linear systems, which first appears in [8]. They used the HSS iteration method based on a special case of the HSS splitting, where the symmetric part is a centrosymmetric matrix and skew-symmetric part is a skew-centrosymmetric matrix for a given Toeplitz matrix and discussed the computational complexity of the HSS and IHSS methods. In this paper we