Precondition Methods For Solving Generalized Toeplitz Eigenvalue Problems

It is well-known that many problems in sciences and engineering eventually lead to large-scale spase or structured matrix computation problems,such as numerical solution of large-scale linear systems, eigenvalue problems and generalized eigenvalue problems.This thesis mainly addresses solving generalized eigenvalue problems of special structure matrices such as Toeplitz matrices,i.e.seeking eigenpalr(λ,x) such that A_nx =λB_nx with A_n and B_n are n-by-n Toeplitz matrices or block Toeplitz matrices.Iteration methods are commonly used when solving high-order generalized eigenvalue problems with special structure.However,when the matrix order is excessively large or the matrix is ill- conditioned, preconditioning is needed to accelerate the convergence rate of the iteration methods.But if the matrix or matrix pencil has some special structure,special attention is needed on how to utilize the benefit of the structure properties when using precondition methods.In fact,If we are able to take advantage of these special structure and properties properly when we construct the preconditioner,not only computing time can be saved,but also the physical meaning of the eigenpair can be preserved at the mean while.Therefore,it is very important to design a fast algorithm according to the matrix structure and prove the feasibility and convergence of the algorithm.This thesis mainly discusses the precondition methods based on sine transform for solving generalized Toeplitz eigenvalue problem and generalized block Toeplitz eigenvalue problem.By using the special structure of(block) Toeplitz matrix pencil,the preconditioners based on sine transform have been used to deal with the Toeplitz shift matrices A_nx-λB_nx,which speed up the convergence of the precondition methods.In our methods,inversion and matrix factorization can be avoided,and only matrix and vector multiplication that involves Toeplitz matrix and sine transform matrix are needed.Therefore,the fast transform algorithms can be used,and large quantity of calculation are saved comparing to the common choice of incomplete factorization methods.Moreover,our methods are considered to be optimal precondition methods to a certain extent.In this thesis,we presents some properties of the preconditioner,analyzes the feasibility and the convergence behavior of the algorithms.Finally,the contrast between algorithms in this thesis and other generally acknowledged algorithms helps to verify the feasibility and the effectiveness of the preconditioned methods we presented.