A PhD thesis @ NALAG

TW 2015_02

Nick Vannieuwenhoven
The numerical solution of multi-parameter eigenvalue problems
February 24, 2015

Advisor(s): Raf Vandebril and Karl Meerbergen

Abstract

The solution of many problems resulting from practical applications (signal processing, vibration analysis) requires computing eigenvalues of a matrix. The performance of solvers is usually of utmost importance. Performance can often be improved significantly by exploiting structure and problem dependent information.

Two parameter eigenvalue problems are eigenvalue problems with two eigenvalue parameters instead of a single one as in the classical eigenvalue problem. The aim of this project is the development of numerical methods for the solution of two­parameter eigenvalue problems.

An important class of applications is the detection of Hopf bifurcations of dynamical systems or critical delays of delay differential equations. Those problems can be written as eigenvalue problems that depend on a parameter. One aims at computing parameter values, for which the eigenvalues have purely imaginary parts. There are only a finite number of parameter values for which there are purely imaginary eigenvalues. The existence of only a finite number of solutions transforms the problem to a discrete, so­called two­parameter eigenvalue problem [1]. The physical parameter together with the eigenvalue form the two eigenvalues of the two­parameter eigenvalue problem.

The two­parameter eigenvalue problem can be written as a generalized eigenvalue problem of squared size, whose matrices are sums of Kronecker products, which we call the Kronecker eigenvalue problem. The squaring of the dimension is the major bottleneck for standard eigenvalue solvers. Taking into consideration that the size of the matrices can be arbitrarily large, as they often arise from the spatial discretization of partial differential equations, it is clear that there is the need for good reliable and fast methods for tackling the 'two­ parameter eigenvalue problem'. Fortunately, there is a large amount of structure in the Kronecker eigenvalue problem. For example, under mild conditions, the eigenvectors have tensor decomposable form, i.e., they are the Kronecker product of two vectors. Moreover there is a one­to­one relation between the Kronecker eigenvalue problem and a Lyapunov eigenvalue problem, for which the eigenvectors are, in fact, low rank matrices. Whereas the solution of Lyapunov equations is well understood (see. e.g. the Bartels and Stewart algorithm), little is known about the theory and solution of 'Lyapunov eigenvalue problems'.

In this project, we aim at developing new and reliable solution techniques for the above described 'two­ parameter' eigenvalue problem. To achieve this goal, we need to investigate the structure and solution methods related to all problems involved: the two­parameter eigenvalue problem, the Kronecker eigenvalue problem and the Lyapunov eigenvalue problem. We need to investigate the intimate relations and the interplay between these problems. We have to search for the maximum available and exploitable structure and provide theoretical settings on which we can build solution approaches, to obtain fast and reliable solvers keeping both memory and computational costs low.