Skip to main content

Krylov methods for nonlinear eigenvalue problems and matrix equations

Time: Tue 2020-02-11 10.00

Location: F3, Lindstedtsvägen 26, Sing-Sing, floor 2, KTH Campus, Stockholm (English)

Subject area: Applied and Computational Mathematics, Numerical Analysis

Doctoral student: Giampaolo Mele , Numerisk analys, NA, SeRC - Swedish e-Science Research Centre

Opponent: Professor Raf Vandebril, KU Katholieke Universiteit Leuven, Begien

Supervisor: Associate Professor Elias Jarlebring, Numerisk analys, NA, SeRC - Swedish e-Science Research Centre


Nonlinear eigenvalue problems (NEPs) arise in many fields of science and engineering. Such problems are often defined by large matrices, which have specific structures, such as being sparse, low-rank, etc. Like the linear eigenvalue problem, the eigenvector appears in a linear form, whereas the eigenvalue appears in a nonlinear form. This feature allows for an extension of several methods, which are originally derived for the linear eigenvalue problem, to the nonlinear case. Among these methods, Krylov algorithms have been successfully extended in various ways. These methods are designed to take advantage of the matrix structures mentioned above. In this thesis, we present two Krylov-based methods for solving NEPs: the tensor infinite Arnoldi (TIAR), with its restarting variant, and infinite Lanczos (ILAN). We illustrate the flexibility of TIAR by adapting it for solving a NEP which comes from the study of waves propagating in periodic mediums. Despite the fact that Krylov methods are, in a sense, globally convergent, the convergence to the targeted eigenvalues, in certain cases, may be slow. When an accurate solution is required, the obtained approximations are refined with methods which have higher convergence order, e.g., Newton-like methods, which are also analyzed in this thesis. In the context of eigenvalue computation, the framework used to analyse Newton methods can be combined with the Keldysh theorem in order to better characterize the convergence factor. We also show that several well-established methods, such as residual inverse iteration and Ruhe’s method of successive linear problems, belong to the class of Newton-like methods. In this spirit, we derive a new quasi-Newton method, which is, in terms of convergence properties, equivalent to residual inverse iteration, but does not require the solution of a nonlinear system per iteration. The mentioned methods are implemented in NEP-PACK, which is a registered Julia package for NEPs that we develop. This package consists of: many state-of-the-art, but also well-established, methods for solving NEPs, a vast problem collection, and types and structures to efficiently represent and do computations with NEPs.Many problems in control theory, and many discretized partial differential equations, can be efficiently solved if formulated as matrix equations. Moreover, matrix equations arise in a very large variety of areas as intrinsic problems. In our framework, for certain applications, solving matrix equations is a part of the process of solving a NEP. In this thesis we derive a preconditioning technique which is applicable to linear systems which can be formulate as generalized Sylvester equation. More precisely, we assume that the matrix equation can be formulated as the sum of a Sylvester operator and another term which can be low-rank approximated. Such linear systems arise, e.g., when solving certain NEPs which come from wave propagation problems.We also derive an algorithm, which consists of applying a Krylov method directly to the the matrix equation rather then to the vectorized linear system, that exploits certain structures in the matrix coefficients.