| The circulant matrices and skew-circulant matrices are two special classes of Toeplitz matrices and play important roles in computation of Toeplitz matrices.In this paper,we focus on the real eigen-structures of the real circulant and skew-circulant matrices,and some of their applications.First,based on the fact that any circulant and skew-circulant matrices can be diagonalized by Fourier matrices,we investigate the real eigen-structures of the real circulant and skew-circulant matrices,and then derive their real Schur forms,which are closely related to the discrete cosine transforms(DCT-I,DCT-II,DCT-V,DCT-VI)and discrete sine transforms(DST-I,DST-II,DST-V,DST-VI).There are two common ways to calculate Toeplitz matrix-vector multiplication:decomposition approach and extension approach.If FFTs are employed,then all op-erations are involved into complex arithmetics.This motivate us to use the real Schur forms to compute real Toeplitz matrix-vector multiplication for both decomposition approach and extension approach,respectively.Based on the DCTs and DSTs,we develop some fast algorithms for computing the real circulant/skew-circulant/Toeplitz matrix-real vector multiplications,in which only real arithmetics are involved,half storage and computational complexity are required.Numerical examples are presented to show that the DCT-DST version saves half of the elapsed CPU time,as compared with the FFT version.Finally,we reformulate the circulant and skew circulant splitting(CSCS)iteration for real positive definite Toeplitz systems,and get the DCT-DST version of the CSCS iteration.Numerical experiments are presented that our method can save half storages and reduce half of the number of float point operations,as compared with the FFT version.Furthermore,our methods can greatly reduce the number of iterations and the elapsed CPU time,in comparison with the Hermitian and skew-Hermitian splitting(HSS)iterative methods.This thesis consists of five chapters:In Chapter 1,we give a brief introduction for research backgrounds,status and contents of Toeplitz 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 investigate the real eigen-structures of real(skew)circulant matrices,and then develop their corresponding real Schur forms.In Chapter 4,we develop some fast algorithms for computing real(skew)circulant and Toeplitz matrix-vector multiplications,based on the DCTs and DSTs.In Chapter 5,a DCT-DST version of CSCS iterative method for solving real positive definite Toeplitz systems is developed. |
