Research On Fast Algorithms Of Several Circulant Matrices

Circulant matrices is a kind of important structured matrices which arise in many ar-eas of image reconstruction, coding theory, signal processing, molecular vibration and applied mathematics. For recent years the properties and applications of them have been extensively investigated.The thesis is made up of four chapters which mainly discuss about how to compute inver-sions, multiplications, square roots of circulant matrices and their generalizations. Based on the existed methods, we present several new fast algorithms. Details are as follows:In Chapter 1, we give a brief introduction to the importance and the current research situation on circulant matrices, then some definitions and properties of generalized circulant matrices are proposed. Moreover, some theories, lemmas and notations about circulant matrices which will be used in the sequel are introduced.In Chapter 2, several sufficient conditions for determining the nonsingularity of circulant matrices are proposed. Then we introduced fast algorithms for inversions and multiplications of circulant matrices by fast Fourier transform. Using reduced forms of circulant matrices, we presented some fast algorithms compute inversions and multiplications of circulant matrices. Moreover, we analysis the computation time complexity of these algorithms.In Chapter 3, some fast algorithms are presented to compute the inversions and mul-tiplications of generalized circulant mtrices. By fast Fourier transform, we develop two fast algorithms to compute the inversions and multiplications of level 2 (ri,r2)- circulant matrices of type (n1,n2). By a reduced order method, a fast algorithm for computing the inversions and multiplications of (R, r)-block circulant matrices is given. Generalizing the definition of scaled factor circulant matrices, matrices with scaled factor circulant blocks are introduced, and we develop a recursive algorithm for the inversion of them.In Chapter 4, we give a brief introduction to the current research situation, existence and classification of matrix square roots. Then some lemmas about matrix square roots are introduced. In the first part of this chapter, we investigate the reduced forms of circulant matrices and quasi-skew circulant matrices. By using their properties we present two efficient algorithms to compute the square roots of circulant matrices and quasi-skew circulant matrices respectively. Those methods are faster than the standard algorithm which is based on the Schur decomposition. Then we discuss the numbers, forms and classifications of circulant matrices and quasi-skew circulant matrices. We further consider circulant H-matrices with positive diagonal entries and develop two algorithms for computing their principal square roots. Those two algorithms have the common advantage that is they only need matrix-matrix multiplications and don't need to calculate any trigonometric functions in their iterative sequences. Finally, a fast algorithm for computing matrix square roots of scaled factor circulant matrices is given by the interpolation method.