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

$${\displaystyle M(\lambda )x=0,}$$

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

Definition

In the discipline of numerical linear algebra the following definition is typically used. ^{[1] [2] [3] [4]}

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

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

In general, ${\displaystyle 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 ${\displaystyle z\in \Omega }$ such that ${\displaystyle \det(M(z))\neq 0}$. Otherwise it is said to be singular. ^{[1] [4]}

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

Definition: The geometric multiplicity of an eigenvalue ${\displaystyle \lambda }$ is the dimension of the nullspace of ${\displaystyle M(\lambda )}$. ^{[1] [4]}

Special cases

The following examples are special cases of the nonlinear eigenproblem.

• The (ordinary) eigenvalue problem: ${\displaystyle M(\lambda )=A-\lambda I.}$
• The generalized eigenvalue problem: ${\displaystyle M(\lambda )=A-\lambda B.}$
• The quadratic eigenvalue problem: ${\displaystyle M(\lambda )=A_{0}+\lambda A_{1}+\lambda ^{2}A_{2}.}$
• The polynomial eigenvalue problem: ${\displaystyle M(\lambda )=\sum _{i=0}^{m}\lambda ^{i}A_{i}.}$
• The rational eigenvalue problem: ${\displaystyle M(\lambda )=\sum _{i=0}^{m_{1}}A_{i}\lambda ^{i}+\sum _{i=1}^{m_{2}}B_{i}r_{i}(\lambda ),}$ where ${\displaystyle r_{i}(\lambda )}$ are rational functions.
• The delay eigenvalue problem: ${\displaystyle M(\lambda )=-I\lambda +A_{0}+\sum _{i=1}^{m}A_{i}e^{-\tau _{i}\lambda },}$ where ${\displaystyle \tau _{1},\tau _{2},\dots ,\tau _{m}}$ are given scalars, known as delays.

Jordan chains

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

Theorem: ^[1] A tuple of vectors ${\displaystyle (x_{0},x_{1},\dots ,x_{r-1})\in \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{n}}$ is a Jordan chain if and only if the function ${\displaystyle M(\lambda )\chi _{\ell }(\lambda )}$ has a root in ${\displaystyle \lambda =\lambda _{0}}$ and the root is of multiplicity at least ${\displaystyle \ell }$ for ${\displaystyle \ell =0,1,\dots ,r-1}$, where the vector valued function ${\displaystyle \chi _{\ell }(\lambda )}$ is defined as$${\displaystyle \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. ^[5]
• The NLEVP collection of nonlinear eigenvalue problems is a MATLAB package containing many nonlinear eigenvalue problems with various properties. ^[6]
• 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. ^[7]
• The MATLAB toolbox NLEIGS contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant. ^[8]
• The MATLAB toolbox CORK contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils. ^[9]
• The MATLAB toolbox AAA-EIGS contains an implementation of CORK with rational approximation by set-valued AAA. ^[10]
• 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. ^[11]
• The Julia package NEP-PACK contains many implementations of various numerical methods for nonlinear eigenvalue problems, as well as many benchmark problems. ^[12]
• The review paper of Güttel & Tisseur ^[1] 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 ${\displaystyle M}$ maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices. ^{[13] [14]}

References

1. Güttel, Stefan; Tisseur, Françoise (2017). "The nonlinear eigenvalue problem" (PDF). Acta Numerica. 26: 1–94. doi:10.1017/S0962492917000034. ISSN   0962-4929. S2CID   46749298.
2. Ruhe, Axel (1973). "Algorithms for the Nonlinear Eigenvalue Problem" . SIAM Journal on Numerical Analysis. 10 (4): 674–689. Bibcode:1973SJNA...10..674R. doi:10.1137/0710059. ISSN   0036-1429. JSTOR   2156278.
3. Mehrmann, Volker; Voss, Heinrich (2004). "Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods". GAMM-Mitteilungen. 27 (2): 121–152. doi:10.1002/gamm.201490007. ISSN   1522-2608. S2CID   14493456.
4. Voss, Heinrich (2014). "Nonlinear eigenvalue problems" (PDF). In Hogben, Leslie (ed.). Handbook of Linear Algebra (2 ed.). Boca Raton, FL: Chapman and Hall/CRC. ISBN   9781466507289.
5. Hernandez, Vicente; Roman, Jose E.; Vidal, Vicente (September 2005). "SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems". ACM Transactions on Mathematical Software. 31 (3): 351–362. doi:10.1145/1089014.1089019. S2CID   14305707.
6. Betcke, Timo; Higham, Nicholas J.; Mehrmann, Volker; Schröder, Christian; Tisseur, Françoise (February 2013). "NLEVP: A Collection of Nonlinear Eigenvalue Problems". ACM Transactions on Mathematical Software. 39 (2): 1–28. doi:10.1145/2427023.2427024. S2CID   4271705.
7. Polizzi, Eric (2020). "FEAST Eigenvalue Solver v4.0 User Guide". arXiv: 2002.04807 [cs.MS].
8. Güttel, Stefan; Van Beeumen, Roel; Meerbergen, Karl; Michiels, Wim (1 January 2014). "NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems". SIAM Journal on Scientific Computing. 36 (6): A2842 –A2864. Bibcode:2014SJSC...36A2842G. doi:10.1137/130935045.
9. Van Beeumen, Roel; Meerbergen, Karl; Michiels, Wim (2015). "Compact rational Krylov methods for nonlinear eigenvalue problems" . SIAM Journal on Matrix Analysis and Applications. 36 (2): 820–838. doi:10.1137/140976698. S2CID   18893623.
10. Lietaert, Pieter; Meerbergen, Karl; Pérez, Javier; Vandereycken, Bart (13 April 2022). "Automatic rational approximation and linearization of nonlinear eigenvalue problems". IMA Journal of Numerical Analysis. 42 (2): 1087–1115. arXiv: 1801.08622 . doi:10.1093/imanum/draa098.
11. Berljafa, Mario; Steven, Elsworth; Güttel, Stefan (15 July 2020). "An overview of the example collection". index.m. Retrieved 31 May 2022.
12. Jarlebring, Elias; Bennedich, Max; Mele, Giampaolo; Ringh, Emil; Upadhyaya, Parikshit (23 November 2018). "NEP-PACK: A Julia package for nonlinear eigenproblems". arXiv: 1811.09592 [math.NA].
13. Jarlebring, Elias; Kvaal, Simen; Michiels, Wim (2014-01-01). "An Inverse Iteration Method for Eigenvalue Problems with Eigenvector Nonlinearities". SIAM Journal on Scientific Computing. 36 (4): A1978 –A2001. arXiv: 1212.0417 . Bibcode:2014SJSC...36A1978J. doi:10.1137/130910014. ISSN   1064-8275. S2CID   16959079.
14. Upadhyaya, Parikshit; Jarlebring, Elias; Rubensson, Emanuel H. (2021). "A density matrix approach to the convergence of the self-consistent field iteration". Numerical Algebra, Control & Optimization. 11 (1): 99. arXiv: 1809.02183 . doi: 10.3934/naco.2020018 . ISSN   2155-3297.

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)