The Toeplitz System Solution Method

Toeplitz matrices arise from a variety of scientific and engineering applications, such as signal processing, image processing, queuing networks, numerical solution of ordinary/partial differential equations (ODEs/PDEs) and numerical solution of integral equations. So Toeplitz Solver plays an important role in practice and theory. This dissertation mainly studies the algorithm to find the inverse of a general pentadiagonal matrix and new splitting iteration methods for Toeplitz systems. The thesis mainly includes the following four parts:1. Brief introductions of background,basic concepts and history of Toeplitz solver are given.2. Employing the general Doolittle factorization, an efficient algorithm is developed to find the inverse of a general pentadiagonal matrix which is suitable for implementation using computer algebra systems software such as Matlab and Maple. Particularly, in case of pentadiagonal Toeplitz matrix, the algorithm successfully avoid breakdown occurring in Trench's algorithm. Examples are given to illustrate the efficiency of the algorithm.3. Brief introductions of the concept of displacement rank and its properties are given. Then newly developed displacement approach (Newton's iteration method) is illustrated.4. New splitting iteration methods for Toeplitz systems are proposed by means of matrix splitting based on discrete cosine/sine transform. Theoretical analysis shows that the new splitting iteration methods always converge to the unique solution of complex symmetric Toeplitz systems. Moreover, accelerating techniques such as finding the optimal parameter and SOR accelerating are studied. Numerical examples are given to illustrate the efficiency of the splitting iteration methods.