Dissertation

Preconditioned iterative methods for linear systems, eigenvalue and singular value problems

Vecharynski, Eugene

2011

Overview

In the present dissertation we consider three crucial problems of numerical linear algebra: solution of a linear system, an eigenvalue, and a singular value problem. We focus on the solution methods which are iterative by their nature, matrix-free, preconditioned and require a fixed amount of computational work per iteration. In particular, this manuscript aims to contribute to the areas of research related to the convergence theory of the restarted Krylov subspace minimal residual methods, preconditioning for symmetric indefinite linear systems, approximation of interior eigenpairs of symmetric operators, and preconditioned singular value computations. We first consider solving non-Hermitian linear systems with the restarted generalized minimal residual method (GMRES). We prove that the cycle-convergence of the method applied to a system of linear equations with a normal (preconditioned) coefficient matrix is sublinear. In the general case, however, it is shown that any admissible cycle-convergence behavior is possible for the restarted GMRES at a number of initial cycles, moreover the spectrum of the coefficient matrix alone does not determine this cycle-convergence. Next we shift our attention to iterative methods for solving symmetric indefinite systems of linear equations with symmetric positive definite preconditioners. We describe a hierarchy of such methods, from a stationary iteration to the optimal Krylov subspace preconditioned minimal residual method, and suggest a preconditioning strategy based on an approximation of the inverse of the absolute value of the coefficient matrix (absolute value preconditioners). We present an example of a simple (geometric) multigrid absolute value preconditioner for the symmetric model problem of the discretized real Helmholtz (shifted Laplacian) equation in two spatial dimensions with a relatively low wavenumber. We extend the ideas underlying the methods for solving symmetric indefinite linear systems to the problem of computing an interior eigenpair of a symmetric operator. We present a method that we call the Preconditioned Locally Minimal Residual method (PLMR), which represents a technique for finding an eigenpair corresponding to the smallest, in the absolute value, eigenvalue of a (generalized) symmetric matrix pencil. The method is based on the idea of the refined extraction procedure, performed in the preconditioner-based inner product over four-dimensional trial subspaces, and relies on the choice of the (symmetric positive definite) absolute value preconditioner. Finally, we consider the problem of finding a singular triplet of a matrix. We suggest a preconditioned iterative method called PLMR-SVD for computing a singular triplet corresponding to the smallest singular value, and introduce preconditioning for the problem. At each iteration, the method extracts approximations for the right and left singular vectors from two separate four-dimensional trial subspaces by solving small quadratically constrained quadratic programs. We illustrate the performance of the method on the example of the model problem of finding the singular triplet corresponding to the smallest singular value of a gradient operator discretized over a two-dimensional domain. We construct a simple multigrid preconditioner for this problem.

• Publisher: ProQuest Dissertations & Theses
• Subject: Applied Mathematics / Computer science
• ISBN: 1124652825, 9781124652825