On The Study Of New Preconditioners For Toeplitz And Related Matrices

In this paper we first consider the solution to the Hermitian positive definite Toeplitz system Ax = b by the preconditioned conjugate gradient method?PCG?.Based on the fact that an Hermitian Toeplitz matrix A can be reduced into a real Toeplitz-plus-Hankel matrix?i.e.,UAU*= T +H?by a unitary similarity transformation(This unitary matrix is U =1/(2^1/2)?I-iJ?),we first reduce the Ax = b to a real linear systems?T + H?[x1,x2]=[b1,b2].Then we propose a new preconditioner for solving those two systems.In particular,our solver only involves real arithmetics when the discrete sine transform?DST?and discrete cosine transform?DCT?are used.The spectral properties of the preconditioned matrix are analyzed,and the computational complexity is discussed.The numerical experiments show that our preconditioner performs well for the Hermitian Toeplitz systems.Then,we consider the solutions to general real symmetric positive definite Toeplitz-plus-Hankel systems by PCG.Based on the trigonometric transformations in[30]for Toeplitz-plus-Hankel systems,we propose a new preconditioner for real Toeplitz-plus-Hankel systems.Different from the preconditioner in[25]for general Toeplitz-plus-Hankel systems in which all operations counts concern complex operations when the DFTs are employed,even if the Toeplitz-plus-Hankel systems are real,our preconditioners only involve real arithmetics when the DSTs and DCTs are used.It is shown that the eigenvalues of the preconditioned matrix are clustered around a constant except a few outliers.The numerical experiments show that our preconditioner performs more efficiently than that of[25]for the real symmetric Toeplitz-plus-Hankel systems.This thesis consists of four chapters:In Chapter 1,we give a brief introduction for research backgrounds,status and contents of Toeplitz and its related matrices,as well as the innovation of this thesis.In Chapter 2,we review some basic definitions and theorems frequently used in the sequel.In Chapter 3,we propose a new preconditioner for solving Hermitian Toeplitz systems.In Chapter 4,we propose a new preconditioner for solving general real symmetric Toeplitz-plus-Hankel systems.