Nonlinear eigenproblem

{{short description|Mathematical equation involving a matrix-valued function that is singular at the eigenvalue.}}

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.{{Cite journal|last1=Güttel|first1=Stefan|last2=Tisseur|first2=Françoise|author-link2=Françoise Tisseur|date=2017|title=The nonlinear eigenvalue problem|url=http://eprints.maths.manchester.ac.uk/2538/1/main.pdf|journal=Acta Numerica|language=en|volume=26|pages=1–94|doi=10.1017/S0962492917000034|s2cid=46749298|issn=0962-4929}}{{Cite journal|last=Ruhe|first=Axel|date=1973|title=Algorithms for the Nonlinear Eigenvalue Problem|url=https://epubs.siam.org/doi/10.1137/0710059|journal=SIAM Journal on Numerical Analysis|volume=10|issue=4|pages=674–689|doi=10.1137/0710059|issn=0036-1429|jstor=2156278|bibcode=1973SJNA...10..674R |url-access=subscription}}{{Cite journal|last1=Mehrmann|first1=Volker|author-link=Volker Mehrmann|last2=Voss|first2=Heinrich|date=2004|title=Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/gamm.201490007|journal=GAMM-Mitteilungen|language=en|volume=27|issue=2|pages=121–152|doi=10.1002/gamm.201490007|s2cid=14493456 |issn=1522-2608}}{{Cite book|last=Voss|first=Heinrich|url=https://www.routledge.com/Handbook-of-Linear-Algebra/Hogben/p/book/9781138199897|title=Handbook of Linear Algebra|publisher=Chapman and Hall/CRC|year=2014|isbn=9781466507289|editor-last=Hogben|editor-first=Leslie|editor-link=Leslie Hogben|edition=2|location=Boca Raton, FL|chapter=Nonlinear eigenvalue problems|chapter-url=https://www.mat.tuhh.de/forschung/rep/rep174.pdf}}

Let $\Omega \subseteq \Complex$ , and let $M : \Omega \rightarrow \Complex^{n\times n}$ 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 eigenvector if $M (\lambda) x = 0$ . Moreover, a nonzero vector $y \in \Complex^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)) \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{d^k \det(M (z))}{d z^k} \right|_{z=\lambda} \neq 0$ but $\left.\frac{d^\ell \det(M (z))}{d z^\ell} \right|_{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\Complex^n\times\Complex^n\times\dots\times\Complex^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\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_{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.{{cite journal |last1=Hernandez |first1=Vicente |last2=Roman |first2=Jose E. |last3=Vidal |first3=Vicente |title=SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems |journal=ACM Transactions on Mathematical Software |date=September 2005 |volume=31 |issue=3 |pages=351–362 |doi=10.1145/1089014.1089019|s2cid=14305707 }}
The [https://github.com/ftisseur/nlevp NLEVP collection of nonlinear eigenvalue problems] is a MATLAB package containing many nonlinear eigenvalue problems with various properties. {{cite journal |last1=Betcke |first1=Timo |last2=Higham |first2=Nicholas J. |last3=Mehrmann |first3=Volker |last4=Schröder |first4=Christian |last5=Tisseur |first5=Françoise |title=NLEVP: A Collection of Nonlinear Eigenvalue Problems |journal=ACM Transactions on Mathematical Software |date=February 2013 |volume=39 |issue=2 |pages=1–28 |doi=10.1145/2427023.2427024|s2cid=4271705 }}
The [http://www.feast-solver.org/ 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.{{cite arXiv |last=Polizzi |first=Eric |eprint=2002.04807 |title=FEAST Eigenvalue Solver v4.0 User Guide|year=2020 |class=cs.MS }}
The MATLAB toolbox [https://bitbucket.org/roelvb/nleigs/ NLEIGS] contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant.{{cite journal |last1=Güttel |first1=Stefan |last2=Van Beeumen |first2=Roel |last3=Meerbergen |first3=Karl |last4=Michiels |first4=Wim |title=NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems |journal=SIAM Journal on Scientific Computing |date=1 January 2014 |volume=36 |issue=6 |pages=A2842–A2864 |doi=10.1137/130935045|bibcode=2014SJSC...36A2842G }}
The MATLAB toolbox [https://bitbucket.org/roelvb/cork/ CORK] contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils.{{cite journal |last1=Van Beeumen |first1=Roel |last2=Meerbergen |first2=Karl |last3=Michiels |first3=Wim |title=Compact rational Krylov methods for nonlinear eigenvalue problems |journal=SIAM Journal on Matrix Analysis and Applications |date=2015 |volume=36 |issue=2 |pages=820–838 |doi=10.1137/140976698|s2cid=18893623 |url=https://lirias.kuleuven.be/handle/123456789/490706 |url-access=subscription }}
The MATLAB toolbox [https://people.cs.kuleuven.be/~karl.meerbergen/files/aaa/autoCORK.zip AAA-EIGS] contains an implementation of CORK with rational approximation by set-valued AAA.{{cite journal |last1=Lietaert |first1=Pieter |last2=Meerbergen |first2=Karl |last3=Pérez |first3=Javier |last4=Vandereycken |first4=Bart |title=Automatic rational approximation and linearization of nonlinear eigenvalue problems |journal=IMA Journal of Numerical Analysis |date=13 April 2022 |volume=42 |issue=2 |pages=1087–1115 |doi=10.1093/imanum/draa098|arxiv=1801.08622 }}
The MATLAB toolbox [http://guettel.com/rktoolbox/ RKToolbox] (Rational Krylov Toolbox) contains implementations of the rational Krylov method for nonlinear eigenvalue problems as well as features for rational approximation. {{cite web |last1=Berljafa |first1=Mario |last2=Steven |first2=Elsworth |last3=Güttel |first3=Stefan |title=An overview of the example collection |url=http://guettel.com/rktoolbox/examples/html/index.html#5 |website=index.m |access-date=31 May 2022 |date=15 July 2020}}
The Julia package [https://nep-pack.github.io/NonlinearEigenproblems.jl/ NEP-PACK] contains many implementations of various numerical methods for nonlinear eigenvalue problems, as well as many benchmark problems.{{Cite arXiv|last1=Jarlebring |first1=Elias |last2=Bennedich |first2=Max |last3=Mele |first3=Giampaolo |last4=Ringh |first4=Emil |last5=Upadhyaya |first5=Parikshit |title=NEP-PACK: A Julia package for nonlinear eigenproblems |date=23 November 2018|class=math.NA |eprint=1811.09592 }}
The review paper of Güttel & Tisseur{{Cite journal|last1=Güttel|first1=Stefan|last2=Tisseur|first2=Françoise|author-link2=Françoise Tisseur|date=2017|title=The nonlinear eigenvalue problem|url=http://eprints.maths.manchester.ac.uk/2538/1/main.pdf|journal=Acta Numerica|language=en|volume=26|pages=1–94|doi=10.1017/S0962492917000034|s2cid=46749298|issn=0962-4929}} 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=Jarlebring|first1=Elias|last2=Kvaal|first2=Simen|last3=Michiels|first3=Wim|date=2014-01-01|title=An Inverse Iteration Method for Eigenvalue Problems with Eigenvector Nonlinearities|url=https://epubs.siam.org/doi/10.1137/130910014|journal=SIAM Journal on Scientific Computing|volume=36|issue=4|pages=A1978–A2001|doi=10.1137/130910014|issn=1064-8275|arxiv=1212.0417|bibcode=2014SJSC...36A1978J |s2cid=16959079}}{{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|arxiv=1809.02183}}