Subspace Methods for Eigenvalue Problems

Abstract

This thesis treats a number of aspects of subspace methods for various eigenvalue problems. Vibrations and their corresponding eigenvalues (or frequencies) arise in science, engineering, and daily life. Matrix eigenvalue problems come from a large number of areas, such as chemistry, mechanics, dynamical systems, Markov chains, magneto-hydrodynamics, oceanography, and economics.

Eigenvalues and eigenvectors give valuable information about the behavior and properties of a matrix; therefore it may not be surprising that eigenvalue problems have been the subject of study for over one and a half century.

Many applications, for instance in chemistry, give rise to eigenvalue problems where the size of the matrix easily exceeds one million. These problems often come from discretized partial differential equations; typically only a small portion of the eigenvalues is needed. Moreover, the matrices are often sparse, this means that the matrix contains relatively many entries which are zero. This implies that one can compute a matrix-vector product economically, that is, quickly, also for large matrices. Therefore, iterative methods, and in particular the important subclass of subspace methods, are often the ones of choice for large sparse matrices. In a subspace method, the matrix is projected onto a low-dimensional subspace; the projected matrix is then solved by direct methods. In this way, we get approximate eigenpairs from a low-dimensional subspace.

We study various eigenvalue problems, namely the (standard) eigenvalue problem, the generalized eigenvalue problem, the singular value problem, the polynomial eigenvalue problem, and the multiparameter eigenvalue problem.

The standard and generalized eigenproblem are the most common ones, originating from numerous applications. The singular value problem plays an important role in applications such as signal and image processing, control theory, pattern recognition, statistics, and search engines for the internet. But it also has a central position in the numerical linear algebra itself: least squares problem, numerical rank of a matrix, angles between subspaces, sensitivity of the solution of linear systems, pseudospectra, and norm of a matrix.

The polynomial eigenvalue problem arises in the study of the vibrations of a mechanical system caused by an external force, in the simulation of electronic circuits, and in fluid mechanics.

An example of the origin of the multiparameter eigenvalue problem is the mathematical physics when the method of separation of variables is used to solve boundary value problems.

Part of this thesis is formed by four chapters that consider Jacobi-Davidson type methods for various eigenvalues problems: for the (nonnormal) standard, complex symmetric, generalized, and polynomial eigenvalue problem in Chapter 2; for the singular value problem in Chapters 3 and 4; and for the multiparameter eigenvalue problem in Chapters 5 en 6. In Chapter 7, we examine numerical important aspects of the multiparameter problem: backward error and condition of eigenvalues and eigenvectors, and pseudospectra. For the quadratic and polynomial eigenvalue problem, we consider approximations to an eigenvalue that can be obtained from a given search space in Chapter 8. In Chapter 9, we develop probabilistic bounds for the extreme eigenvalues of a Hermitian matrix with the Lanczos method.