The Iterative Algorithm For Block Toeplitz Systems

Block Toeplitz matrices have a wide range of engineering applicationssuch as in signal processing and so on. The theory and structured algorithmsabout block Toeplitz matrices have been widely researched for decades. Themethods for solving Toeplitz systems can be reduced into the direct methodsand iterative methods. The block Gauss-Seidel iterations and block SORiterations for solving block Toeplitz systems and BTTB systems areconsidered in this thesis. We first discuss some properties of blocktriangular Toeplitz matrices, and then present some fast algorithms forcomputing the inverse of such a class of matrices and the inverse of BTTBmatrices respectively. Furthermore, we obtain fast block Gauss-Seideliterative algorithms and fast block SOR iterative algorithms for thosesystems. Finally, we show that our methods are convergent when thecoefficient matrices are symmetric positive definite or H-matrices. Somenumerical examples demonstrate the convergence of our schemes. At theend of the thesis, we give a comparison of our algorithm for inversion withothers.This thesis is organized as the following five chapters.The first chapter is an introduction, in which the research backgrounds,the motivation of the theme’s choice, contents and the innovation of thepaper are described respectively.The second chapter is the preliminaries, including of some notation,definitions, and basic properties frequently used in this paper.In the third chapter we consider the iterative algorithms for blockToeplitz systems. We first give a core algorithm of this paper, which is afast algorithm for solving the inverse of block triangular Toeplitz matrices.We also analyze the complexity of this algorithm. Then we give two iterative algorithms for solving block Toeplitz systems.The fourth chapter is about iterative algorithms for BTTB systems. Asimilar core algorithm is given, which is fast algorithm for computing theinverse of triangular BTTB matrices. The corresponding complexity is alsoanalyzed.In the fifth chapter we first discuss convergence of the correspondingalgorithms for block Toeplitz systems and BTTB systems respectively, andthen give some numerical experiments. Finally, we give a comparisonamong the different algorithms for solving the inverse of these matrices.