Author

Mei Yang

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

Comments

Degree granted by The University of Texas at Arlington

Included in

Mathematics Commons

Share

COinS