BTTB Preconditioner For BTTB Least Squares Problems

The least squares problems min‖b-Tx‖₂ have many applications in scienceand engineering. In this thesis, we consider the case where T is a large rect-angular matrix consists of several Toeplitz matrices or BTTB matrices. Suchkind of least squares problems have many applications, e.g., in image restora-tion and series analysis, etc. We consider solving the least squares problems bythe preconditioned conjugate gradient methods with Toeplitz preconditionersand BTTB preconditioners. In the computation, mainly use the 1-D and 2-DFast Fourier Transform to get fast algorithms.This thesis consists of two chapters. The main contents are as follow:In chapter one, we give some introductory materials, including the ground-ing of this thesis and some results of the early works on the least squares prob-lems. We introduce the definition of Toeplitz matrix and BTTB matrix andtheir generating functions, and give some related symbols, basic conceptionsand theorems. We also make a brief review on the preconditioned conjugategradient methods for BTTB Least squares problems.In chapter two, we discuss in detail the preconditioned conjugate gradientmethod for solving Toeplitz least squares problems and BTTB least squaresproblems. The main concern is the construction of Toeplitz preconditioner andBTTB preconditioner, and their properties. We prove that they are e?cientpreconditioners. Numerical results show that our preconditioners are more ef-ficient than circulant preconditioners. Finally, we make a brief summary and aplan of our future research.