Graduation Semester and Year
2018
Language
English
Document Type
Dissertation
Degree Name
Doctor of Philosophy in Mathematics
Department
Mathematics
First Advisor
Ren-Cang Li
Abstract
The linear system and the linear least squares problem are two fundamental numerical linear algebra problems. Krylov subspace methods are the most practical and common techniques to build solvers. In this thesis, we focus on optimizing Krylov subspace methods for nonsymmetric linear systems and least squares problems. For nonsymmetric linear systems Ax=b one of Krylov subspace methods is GMRES, which seeks approximate solutions over the Krylov subspace K_k (A,b) (with the initial guess x_0=0). Constructing different search spaces and applying restart strategy are two techniques used to deal with possible slow convergence and to reduce computational cost in GMRES and variants of GMRES, such as restarted GMRES and flexible GMRES. In this thesis, we present a numerical method called the heavy ball flexible GMRES method for nonsymmetric linear systems, which is designed to salvage the lost convergence speed of restarted flexible GMRES while keeping the benefit of the restarted flexible GMRES in limiting memory usage and controlling orthogonalization cost. The search space is extended in every iteration by applying the heavy ball idea in optimization. Comparison of the restarted flexible GMRES and the heavy ball flexible GMRES are shown in numerical experiments to illustrate the efficiency of our method. The linear least squares problem, min_x ‖Ax-b‖_2, widely occurs in statistics, geodetics, photogrammetry, signal processing, and control. Based on the Golub-Kahan process, LSMR seeks approximate solutions x_k over the Krylov subspace K_k (A^T A,A^T b). We are aiming to optimize LSMR in two ways. Firstly, we propose the heavy ball minimal residual method by utilizing the restarted technique to combine LSMR with the heavy ball idea. The restarted Golub-Kahan bidiagonalization process is applied to control the memory usage and reorthogonalization cost. We add a new direction to include previous iterations' information in extending the searching subspace, which also speeds up the convergence. Secondly, we present a flexible preconditioned iterative method for least squares problems. Because of lacking effective preconditioners, LSMR sometimes stagnates as iterations go on. Applying a good preconditioner in LSMR is critical to speed up convergence. Usually, it's impossible to tell whether a given preconditioner is suitable for the problem beforehand. So, one may attempt many possible preconditioners together and switch periodically among them. We want to design an algorithm that can switch among preconditioners in the outer iterations instead of restarting LSMR. Our flexible preconditioned LSMR method takes an outer-inner iteration to construct changeable preconditioners and applies the factorization-free preconditioning technique to the Golub-Kahan process to reduce computational cost. Numerical examples demonstrate the efficiency of our method compared to LSMR.
Keywords
Linear system, Least squares problem, Krylov subspace, GMRES, Heavy ball method, FGMRES, Preconditioner, Golub-Kahan bidiagonalization process, LSMR
Disciplines
Mathematics | Physical Sciences and Mathematics
License
This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.
Recommended Citation
Yang, Mei, "Optimizing Krylov Subspace Methods for Linear Systems and Least Squares Problems" (2018). Mathematics Dissertations. 199.
https://mavmatrix.uta.edu/math_dissertations/199
Comments
Degree granted by The University of Texas at Arlington