Back to search

Clemson University

Convergence Estimate of Minimal Residual Methods and Random Sketching of Krylov Subspace Methods

Abstract

dc:description.abstract

This study concerns two main issues in numerical linear algebra: convergence estimate of minimal residual methods based on explicit construction of approximate min-max polynomials for in- definite matrices, and development and analysis of Krylov subspace methods using non-orthonormal basis vectors based on random sketching. For a matrix A with spectrum Λ(A), it is well known that the min-max polynomial problem min max |pk (z)| pk ∈Pk, pk (0)=1, z∈Λ(A) is used to bound the relative error of Krylov subspace minimum residual methods or similar methods. For a symmetric positive definite matrix A, the min-max polynomial for the Conjugate Gradient (CG) algorithm is explicitly known, and in certain cases, provides a sharp bound. We provide an explicit construction for real, symmetric indefinite and nonsymmetric matrices, adding to the limited results found in the literature. It is also well known that minimum residual methods converge slowly when the spectrum of A is large, or the ratio of the largest to smallest eigenvalues (in modulus) is large. As the eigenvalues along the exterior of Λ(A) are resolved, minimum residual methods experience an acceleration in convergence. Subspace recycling takes advantage of this by approximating the subspace spanned by eigenvectors corresponding to the k smallest eigenvalues, and using those k basis vectors to start the Krylov subspace in the next iteration (deflated restart) or linear system (subspace recycling). We consider subspace recycling as it applies to the GCRO algorithm. To reduce the cost associated with full orthogonalization, we use random sketching to form a non-orthonormal basis, allowing us to reduce computation cost while still preventing the basis vectors from getting too ill-conditioned. Then we extend this practice to constructing non-orthonormal basis vectors for Krylov subspace methods for approximating the matrix exponential times a vector and approximating the largest singular triplets. Our methodology is also effective to save considerable orthogonalization cost in these problem settings, without obviously slowing down the convergence of the original algorithms. We discuss insights into the convergence (error analysis) of the sketched variants. The discussions of linear system solvers, matrix exponential times a vector, and dominant singular triplets cover a range of fundamental numerical linear algebra problems for large (and typically sparse) matrices.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
School of Mathematical and Statistical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Westerbaan, Peter
Contributors dc:contributor
  • Fei Xue
  • Qingshan Chen
  • Lea Jenkins
  • Matthew Saltzman

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/3548

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Westerbaan, Peter. Convergence Estimate of Minimal Residual Methods and Random Sketching of Krylov Subspace Methods. Dissertation thesis, https://open.clemson.edu/all_dissertations/3548