Study Of Fast Algorithm Of Hermitian Toeplitz Equation

The theory and algorithms for structured matrices have intrigued researchers for years. This thesis focus on how to develop fast direct methods for solving hermitian Toeplitz system. A large literature shows that an hermitian Toeplitz matrix can be mapped into an hermitian Cauchy matrix by exploiting the hermitian Toeplitz structure and DFT, or real Cauchy matrices by exploiting shift structure and permutation. In this thesis we first exploit the reducible properties of centrohermitian matrix to reduce an hermitian Toeplitz matrix into a real symmetric Toeplitz+ Hankel matrix via a simple unitary similarity transformation, and then use the DFT to transform this real symmetric Toeplitz+Hankel matrix into a real symmetric Cauchy matrix.There exist some fast algorithms for solving the Toeplitz+Hankel system. However, those algorithms are lack of numerical stability. Therefore we further study the fast algorithm for the solution of the hermitian Toeplitz system which are mainly based on the fast factorization of real symmetric Cauchy matrices. It is shown that our algorithm is more stable than the existed algorithms.This thesis consists of five chapters which are organized as follows:The first chapter is an introduction. We mainly introduce the backgrou-nd, The main contents and the motivation of thesis.In the second chapter, we briefly review some basic definitions and notations which will be used in the thesis.In the third chapter, we first survey some various transformations which are mapping the hermitian Toeplitz matrices into hermitian Cauchy matrices or real Cauchy matrices. Then we consider another way, that is first to reduce an hermitian Toeplitz matrix into a real symmetric Toeplitz +Hankel matrix via a simple unitary similarity transformation, and then to transform this real symmetric Toeplitz+Hankel matrix into a real symmet-ric Cauchy matrix via DFT.In the fourth chapter, we develop stable direct algorithms for solving the hermitian Toeplitz system, which are based on fast and stable factorization of real symmetric Cauchy matrices.In the fifth chapter, we review some new progress of preconditioning techniques for Toeplitz systems, which can be roughly divided into two classes:circulant preconditioner and non-circulant preconditioner.