A Factorized Banded Inverse Preconditioner For Toeplitz Matrices

Toeplitz systems arise in a variety of applications in mathematics, scientific computing and engineering, for instance, numerical partial and ordinary differ-ential equations; numerical solution of convolution-type integral equations; op-timization problems in control theory; signal processing and image restoration problems, see [7,13,18]. The preconditioned conjugate gradient method (PCG) for Toeplitz systems has been arising a big concern of many mathematicians for more than two decades.In 1986, Strang and Olkin independently proposed the circulant precondi-tioners to solve Toeplitz system, see [1,7]. Then, some other good circulant preconditioners are proposed to solve such problems, for examples, the circu-lant preconditioners proposed by T. Chan and by R. Chan, see [6,10,12]. The great advantage of circulant preconditioners is that circulant matrices can be diagonalized by the Fourier matrix. Compared to direct methods for Toeplitz systems, the PCG method using circulant preconditioners can greatly reduce the computational complexity since the total cost is only O(n logn) opera-tions, where n is the order of the linear system. Other useful preconditioners for Toeplitz systems include fast trigonometric transform based preconditioners, Hartley transform based preconditioners and so on, see [2,5,11,19].Since each Toeplitz matrix matches a generating function, a Toeplitz ma-trix is determined by its generating function. Therefore we can construct a good preconditioner based on its generating function, for example, by using the con-volution technique or by using trigonometric polynomial approximation, see [7]. When the generating function is positive definite and even, the corresponding Toeplitz matrix is well-conditioned, and symmetric and positive definite. When the generating function has zeros with even orders, the corresponding system is ill-conditioned. In this situation, band preconditioned matrix is a good choice. R. Chan proposed band matrix preconditioner generated by the trigonometric polynomial g, where g contents the zeros of the original generating function, see [4]. Later R. Chan and Tang extended the method to improve the conver-gence rate of the PCG method, see [9]. Recently, D. Noutsos and P. Vassalos proposed band plus circulate method to construct the preconditioning matrix, see [19].Another approach to construct preconditioners is to construct approximate sparse inverse of the original matrix, see for instance Kolotilina and Yeremin [16] and Tang [21]. Since both the construction of approximate sparse in-verse preconditioner and the preconditioning steps have natural parallelism, this method can be well applied in modern large scale parallel machines. In 2005, Lin, Ng, and Ching applied the approximate sparse inverse technique to obtain a factorized banded inverse preconditioner (FBIP), see [17]. It has been shown that when the Toeplitz matrices have some kind of off-diagonal decay and the corresponding generating function is positive, the FBIP is a very ef-ficient one. In this thesis, we extend the results of FBIP to Toeplitz matrices with non-negative continuous generating function. We will mainly analysis the convergence of the PCG method with our proposed preconditioner, and then use Matlab to implement the method and compare it with some well-known methods.