RT Dissertation/Thesis
T1 Krylov methods for large-scale modern problems in numerical linear algebra
A1 González Pizarro, Javier Andrés
AB Large-scale problems have attracted much attention in the last decades sincethey arise from different applications in several fields. Moreover, the matrices thatare involved in those problems are often sparse, this is, the majority of their entriesare zero. Around 40 years ago, the most common problems related to large-scale andsparse matrices consisted in solving linear systems, finding eigenvalues and/or eigenvectors,solving least square problems or computing singular value decompositions.However, in the last years, large-scale and sparse problems of different natures haveappeared, motivating and challenging numerical linear algebra to develop effectiveand efficient algorithms to solve them.Common difficulties that appear during the development of algorithms for solvingmodern large-scale problems are related to computational costs, storage issues andCPU time, given the large size of the matrices, which indicate that direct methodscan not be used. This suggests that projection methods based on Krylov subspacesare a good option to develop procedures for solving large-scale and sparse modernproblems.In this PhD Thesis we develop novel and original algorithms for solving twolarge-scale modern problems in numerical linear algebra: first, we introduce theR-CORK method for solving rational eigenvalue problems and, second, we presentprojection methods to compute the solution of T-Sylvester matrix equations, bothbased on Krylov subspaces.The R-CORK method is an extension of the compact rational Krylov method(CORK) [104] introduced to solve a family of nonlinear eigenvalue problems that canbe expressed and linearized in certain particular ways and which include arbitrarypolynomial eigenvalue problems, but not arbitrary rational eigenvalue problems.The R-CORK method exploits the structure of the linearized problem by representingthe Krylov vectors in a compact form in order to reduce the cost of storage,resulting in a method with two levels of orthogonalization. The first level of orthogonalizationworks with vectors of the same size as the original problem, and thesecond level works with vectors of size much smaller than the original problem. Sincevectors of the size of the linearization are never stored or orthogonalized, R-CORKis more efficient from the point of view of memory and orthogonalization costs thanthe classical rational Krylov method applied to the linearization. Moreover, sincethe R-CORK method is based on a classical rational Krylov method, the implementationof implicit restarting is possible and we present an efficient way to do it, thatpreserves the compact representation of the Krylov vectors.We also introduce in this dissertation projection methods for solving the TSylvesterequation, which has recently attracted considerable attention as a consequenceof its close relation to palindromic eigenvalue problems and other applications.The theory concerning T-Sylvester equations is rather well understood, and before the work in this thesis, there were stable and efficient numerical algorithmsto solve these matrix equations for small- to medium- sized matrices. However,developing numerical algorithms for solving large-scale T-Sylvester equations was acompletely open problem. In this thesis, we introduce several projection methodsbased on block Krylov subspaces and extended block Krylov subspaces for solvingthe T-Sylvester equation when the right-hand side is a low-rank matrix. We also offeran intuition on the expected convergence of the algorithm based on block Krylovsubspaces and a clear guidance on which algorithm is the most convenient to use ineach situation.All the algorithms presented in this thesis have been extensively tested, and thereported numerical results show that they perform satisfactorily in practice.
YR 2018
FD 2018-07
LK https://hdl.handle.net/10016/27692
UL https://hdl.handle.net/10016/27692
LA eng
NO Adicionalmente se recibió ayuda parcial de los proyectos de investigación: “Structured Numerical Linear Algebra: MatrixPolynomials, Special Matrices, and Conditioning” (Ministerio de Economía y Competitividad de España, Númerode proyecto: MTM2012-32542) y “Structured Numerical Linear Algebra for Constant, Polynomial and Rational Matrices” (Ministerio de Economía y Competitividad de España,Número de proyecto: MTM2015-65798-P), donde el investigador principal de ambos proyectos fue Froilán MartínezDopico.
DS e-Archivo
RD 3 may. 2024