Nonlinear eigenproblem

In mathematics, a nonlinear eigenproblem, sometimes nonlinear eigenvalue problem, is a generalization of the (ordinary) eigenvalue problem to equations that depend nonlinearly on the eigenvalue. Specifically, it refers to equations of the form

$$M(\lambda )x=0,$$

where $x\ne 0$ is a vector, and $M$ is a matrix-valued function of the number $\lambda$. The number $\lambda$ is known as the (nonlinear) eigenvalue, the vector $x$ as the (nonlinear) eigenvector, and $(\lambda ,x)$ as the eigenpair. The matrix $M(\lambda )$ is singular at an eigenvalue $\lambda$.

Definition

In the discipline of numerical linear algebra the following definition is typically used.

Let $\Omega \subseteq ℂ$, and let $M:\Omega \to {ℂ}^{n\times n}$ be a function that maps scalars to matrices. A scalar $\lambda \in ℂ$ is called an eigenvalue, and a nonzero vector $x\in {ℂ}^n$ is called a right eigenvector if $M(\lambda )x=0$. Moreover, a nonzero vector $y\in {ℂ}^n$ is called a left eigenvector if $y^{H}M(\lambda )=0^H$, where the superscript ${}^H$ denotes the Hermitian transpose. The definition of the eigenvalue is equivalent to $\det (M(\lambda ))=0$, where $\det ()$ denotes the determinant.

The function $M$ is usually required to be a holomorphic function of $\lambda$ (in some domain $\Omega$).

In general, $M(\lambda )$ could be a linear map, but most commonly it is a finite-dimensional, usually square, matrix.

Definition: The problem is said to be regular if there exists a $z\in \Omega$ such that $\det (M(z))\ne 0$. Otherwise it is said to be singular.

Definition: An eigenvalue $\lambda$ is said to have algebraic multiplicity $k$ if $k$ is the smallest integer such that the $k$th derivative of $\det (M(z))$ with respect to $z$, in $\lambda$ is nonzero. In formulas that ${\frac{d^k\det (M(z))}{d{z}^k}|}_{z=\lambda }\ne 0$ but ${\frac{d^{\ell }\det (M(z))}{d{z}^{\ell }}|}_{z=\lambda }=0$ for $\ell =0,1,2,\dots ,k-1$.

Definition: The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of the nullspace of $M(\lambda )$.

Special cases

The following examples are special cases of the nonlinear eigenproblem.

• The (ordinary) eigenvalue problem: $M(\lambda )=A-\lambda I.$
• The generalized eigenvalue problem: $M(\lambda )=A-\lambda B.$
• The quadratic eigenvalue problem: $M(\lambda )=A_0+\lambda A_1+{\lambda }^2{A}_2.$
• The polynomial eigenvalue problem: $M(\lambda )=\sum _{i=0}^m{\lambda }^i{A}_i.$
• The rational eigenvalue problem: $M(\lambda )=\sum _{i=0}^{m_1}{A}_i{\lambda }^i+\sum _{i=1}^{m_2}{B}_i{r}_i(\lambda ),$ where $r_i(\lambda )$ are rational functions.
• The delay eigenvalue problem: $M(\lambda )=-I\lambda +A_0+\sum _{i=1}^m{A}_i{e}^{-{\tau }_i\lambda },$ where ${\tau }_1,{\tau }_2,\dots ,{\tau }_m$ are given scalars, known as delays.

Jordan chains

Definition: Let $({\lambda }_0,x_0)$ be an eigenpair. A tuple of vectors $(x_0,x_1,\dots ,x_{r-1})\in {ℂ}^n\times {ℂ}^n\times \dots \times {ℂ}^n$ is called a Jordan chain if$$\sum _{k=0}^{\ell }{M}^{(k)}({\lambda }_0)x_{\ell -k}=0,$$for $\ell =0,1,\dots ,r-1$, where $M^{(k)}({\lambda }_0)$ denotes the $k$th derivative of $M$ with respect to $\lambda$ and evaluated in $\lambda ={\lambda }_0$. The vectors $x_0,x_1,\dots ,x_{r-1}$ are called generalized eigenvectors, $r$ is called the length of the Jordan chain, and the maximal length a Jordan chain starting with $x_0$ is called the rank of $x_0$.

Theorem: A tuple of vectors $(x_0,x_1,\dots ,x_{r-1})\in {ℂ}^n\times {ℂ}^n\times \dots \times {ℂ}^n$ is a Jordan chain if and only if the function $M(\lambda ){\chi }_{\ell }(\lambda )$ has a root in $\lambda ={\lambda }_0$ and the root is of multiplicity at least $\ell$ for $\ell =0,1,\dots ,r-1$, where the vector valued function ${\chi }_{\ell }(\lambda )$ is defined as$${\chi }_{\ell }(\lambda )=\sum _{k=0}^{\ell }{x}_k(\lambda -{\lambda }_0{)}^k.$$

Mathematical software

• The eigenvalue solver package SLEPc contains C-implementations of many numerical methods for nonlinear eigenvalue problems.
• The NLEVP collection of nonlinear eigenvalue problems is a MATLAB package containing many nonlinear eigenvalue problems with various properties.
• The FEAST eigenvalue solver is a software package for standard eigenvalue problems as well as nonlinear eigenvalue problems, designed from density-matrix representation in quantum mechanics combined with contour integration techniques.
• The MATLAB toolbox NLEIGS contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant.
• The MATLAB toolbox CORK contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils.
• The MATLAB toolbox AAA-EIGS contains an implementation of CORK with rational approximation by set-valued AAA.
• The MATLAB toolbox RKToolbox (Rational Krylov Toolbox) contains implementations of the rational Krylov method for nonlinear eigenvalue problems as well as features for rational approximation.
• The Julia package NEP-PACK contains many implementations of various numerical methods for nonlinear eigenvalue problems, as well as many benchmark problems.
• The review paper of Güttel & Tisseur contains MATLAB code snippets implementing basic Newton-type methods and contour integration methods for nonlinear eigenproblems.

Eigenvector nonlinearity

Eigenvector nonlinearities is a related, but different, form of nonlinearity that is sometimes studied. In this case the function $M$ maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices.

Further reading

• Françoise Tisseur and Karl Meerbergen, "The quadratic eigenvalue problem," SIAM Review 43 (2), 235–286 (2001) (link).
• Gene H. Golub and Henk A. van der Vorst, "Eigenvalue computation in the 20th century," Journal of Computational and Applied Mathematics 123, 35–65 (2000).
• Philippe Guillaume, "Nonlinear eigenproblems," SIAM Journal on Matrix Analysis and Applications 20 (3), 575–595 (1999) (link).
• Cedric Effenberger, "Robust solution methods fornonlinear eigenvalue problems", PhD thesis EPFL (2013) (link)
• Roel Van Beeumen, "Rational Krylov methods fornonlinear eigenvalue problems", PhD thesis KU Leuven (2015) (link)