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\neq0$ 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 \Complex$, and let $M : \Omega \rightarrow \Complex^$ be a function that maps scalars to matrices. A scalar $\lambda \in \Complex$ is called an ''eigenvalue'', and a nonzero vector $x \in \Complex^n$is called a ''right eigevector'' if $M (\lambda) x = 0$. Moreover, a nonzero vector $y \in \Complex^n$is called a ''left eigevector'' 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)) \neq 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 $\left.\frac \_ \neq 0$ but $\left.\frac \_ = 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_^m \lambda^i A_i.$
* The rational eigenvalue problem: $M (\lambda) = \sum_^ A_i \lambda^i + \sum_^ B_i r_i(\lambda),$ where $r_i(\lambda)$ are rational functions.
* The delay eigenvalue problem: $M (\lambda) = -I\lambda + A_0 +\sum_^m A_i e^,$ 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_)\in\Complex^n\times\Complex^n\times\dots\times\Complex^n$ is called a ''Jordan chain'' if$\sum_^ M^ (\lambda_0) x_ = 0 ,$for $\ell = 0,1,\dots , r-1$, where $M^(\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_$ 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_)\in\Complex^n\times\Complex^n\times\dots\times\Complex^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_^\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.
* Th
NLEVP collection of nonlinear eigenvalue problems
is a MATLAB package containing many nonlinear eigenvalue problems with various properties.
* Th
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 toolbo
NLEIGS
contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant.
* The MATLAB toolbo
CORK
contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils.
* The MATLAB toolbo
AAA-EIGS
contains an implementation of CORK with rational approximation by set-valued AAA.
* The MATLAB toolbo
RKToolbox
(Rational Krylov Toolbox) contains implementations of the rational Krylov method for nonlinear eigenvalue problems as well as features for rational approximation.
* The Julia packag
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.{{Cite journal, last1=Upadhyaya, first1=Parikshit, last2=Jarlebring, first2=Elias, last3=Rubensson, first3=Emanuel H., date=2021, title=A density matrix approach to the convergence of the self-consistent field iteration, journal=Numerical Algebra, Control & Optimization, volume=11, issue=1, pages=99, doi=10.3934/naco.2020018, issn=2155-3297, doi-access=free

References

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

Linear algebra