AMaSiS 2018 Workshop: Abstracts

Nonlinear eigenvalue problems and contour integration

Marc Van Barel

KU Leuven, Dept. of Computer Science

In this talk, the following eigenvalue problem is considered. Given an integer $m\ge 1$, a domain $\mathrm{\Omega }\subset ℂ$ and a matrix-valued function $T:\mathrm{\Omega }\to {ℂ}^{m\times m}$ analytic in $\mathrm{\Omega }$, we want to compute the values $\lambda \in \mathrm{\Omega }$ (eigenvalues) and $v\in {ℂ}^m$, $v\ne 0$ (eigenvectors) such that

$$T(\lambda )v=0.$$

Note that this formulation reduces to the linear eigenvalue problem in case $T(z)=A-zB$, and to the polynomial eigenvalue problem when $T(z)$ is a polynomial matrix. If the problem size $m$ is equal to $1$, then the problem reduces to that of computing all the zeros $\lambda$ of the analytic scalar function $T$ inside the domain $\mathrm{\Omega }$.

The number of eigenvalues could be large, e.g., when $m$ is large, or in case of a polynomial eigenvalue problem when the degree of the polynomial matrix is large. In several applications, one is not interested in all eigenvalues but only in those lying in a certain region(s) of the complex plane. Therefore, we can reduce the original problem of finding all eigenvalues into one where we are only interested in those eigenvalues (and corresponding eigenvectors) lying within (or in the neighborhood) of a given closed contour $\mathrm{\Gamma }\subset \mathrm{\Omega }$.

The approach discussed in this talk is based on (numerical approximations of) contour integrals of the resolvent operator $T{(z)}^{-1}$ applied to a rectangular matrix $\widehat{V}$:

$$\frac{1}{2\pi i}{\int }_{\mathrm{\Gamma }}f(z)T{(z)}^{-1}\widehat{V}dz\mathit{\hspace{1em}}\in {ℂ}^{m\times q}$$

where $f:\mathrm{\Omega }\to ℂ$ is analytic in $\mathrm{\Omega }$ and $\widehat{V}\in {ℂ}^{m\times q}$ is a matrix chosen randomly or in another specified way, with $q\le m$.

The contour integral is approximated by a quadrature rule with nodes $t_j$ and corresponding weights $u_j$, i.e.,

$${\int }_{\mathrm{\Gamma }}f(z)𝑑z\approx \sum _{j=1}^N{u}_{j}f(t_j).$$

As was explained in [1], from Keldysh’ theorem, we know that the resolvent function $T{(z)}^{-1}$ can be written (for simple eigenvalues $\lambda$) as

$$T{(z)}^{-1}=\sum _k{v}_k{w}_k^H\frac{1}{z-{\lambda }_k}+R(z)$$

with $R(z)$ an analytic function where $T(z)$ is analytic. Note that if $T^{-1}$ is a matrix-valued strictly proper rational function, the analytic function $R$ is equal to zero. This is the case, for example, if $T(z)=A-zB$ with $B$ nonsingular or if $T(z)$ is a matrix polynomial in $z$ with nonsingular highest degree coefficient.

Hence, applying the quadrature rule on the moments of the resolvent function $z^{l}T{(z)}^{-1}$ gives us

${\displaystyle {\int }_{\mathrm{\Gamma }}}{z}^{l}T{(z)}^{-1}𝑑z$ $\approx$ ${\displaystyle \sum _{j=1}^N}{u}_j{t}_j^{l}T{(t_j)}^{-1}={\displaystyle \sum _k}{v}_k{w}_k^H{\displaystyle \sum _{j=1}^N}{\displaystyle \frac{u_j{t}_j^l}{t_j-{\lambda }_k}}+{\displaystyle \sum _{j=1}^N}{u}_j{t}_j^{l}R(t_j).$

The filter functions $b_l(z)$ are defined as the rational functions of degree $\delta$ corresponding to the quadrature rule as follows

$$b_l(z)=\sum _{j=1}^N\frac{u_j{t}_j^l}{t_j-z}.$$

In [3], we argued that it is important to have robust and cheap ways to design good filter functions. This design consists in finding the weights $u_j$ and the nodes $t_j$ such that the following conditions are satisfied [2]:

1. $b_l(z)=b_0(z)z^l$;

2. $|b_l(z)|$ is large inside $\mathrm{\Gamma }$ and small outside $\mathrm{\Gamma }$;

3. $|{\sum }_{j=1}^N{u}_j{t}_j^{l}R(t_j)|$ is small.

We call the function $b_0(z)$ “the filter function” and denote it as $b(z)$. It is easy to see that as long as with $\nu$ the degree of the numerator of the filter function $b(z)$, the first condition is satisfied. To satisfy the second and third condition, we will solve an optimization problem looking for the variables $u_j$ and $t_j$ such that $|b_l(z)|$ is large inside $\mathrm{\Gamma }$ and small outside $\mathrm{\Gamma }$. The validity of the approach will be illustrated by some numerical experiments.