Nonlinear eigenproblem explained

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(λ)x=0,

where

x ≠ 0

is a vector, and M

is a matrix-valued function of the number

. The number

is known as the (nonlinear) eigenvalue, the vector

as the (nonlinear) eigenvector, and

(λ,x)

as the eigenpair. The matrix

M(λ)

is singular at an eigenvalue

Definition

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

Let

\Omega\subseteq\Complex

, and let

M:\Omega → \Complex^{n x}

be a function that maps scalars to matrices. A scalar

λ\in\Complex

is called an eigenvalue, and a nonzero vector

x\in\Complexⁿ

is called a right eigevector if

M(λ)x=0

. Moreover, a nonzero vector

y\in\Complexⁿ

is called a left eigevector if

y^HM(λ)=0^H

, where the superscript

denotes the Hermitian transpose. The definition of the eigenvalue is equivalent to

\det(M(λ))=0

, where

\det

denotes the determinant.

The function

is usually required to be a holomorphic function of
λ

(in some domain
\Omega

).

In general,

M(λ)

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)) ≠ 0

. Otherwise it is said to be singular.

Definition: An eigenvalue

is said to have algebraic multiplicity

is the smallest integer such that the

th derivative of

\det(M(z))

with respect to

, in

is nonzero. In formulas that

\left.	d^k\det(M(z))
	dz^k

\right|_z=λ ≠ 0

but

\left.	d^\ell\det(M(z))
	dz^\ell

\right|_z=λ=0

for

\ell=0,1,2,...,k-1

Definition: The geometric multiplicity of an eigenvalue

is the dimension of the nullspace of

M(λ)

Special cases

The following examples are special cases of the nonlinear eigenproblem.

The (ordinary) eigenvalue problem:

M(λ)=A-λI.

The generalized eigenvalue problem:

M(λ)=A-λB.

The quadratic eigenvalue problem:

M(λ)=A₀+λA₁+λ²A_2.

The polynomial eigenvalue problem:

M(λ)=

	m
\sum
	i=0

λⁱA_i.

The rational eigenvalue problem:

M(λ)=

	m₁
\sum
	i=0

A_iλⁱ+

	m₂
\sum
	i=1

B_ir_i(λ),

where

r_i(λ)

are rational functions.

The delay eigenvalue problem:

M(λ)=-Iλ+A₀

	m
+\sum
	i=1

A_i

	-\tau_iλ
e

where

\tau_1,\tau_2,...,\tau_m

are given scalars, known as delays.

Jordan chains

Definition: Let

(λ_0,x₀₎

be an eigenpair. A tuple of vectors

(x_0,x_1,...,x_r-1)\in\Complex^{n x \Complex}^{n x ... x \Complex}ⁿ

is called a Jordan chain if

\sum_^ M^ (\lambda_0) x_ = 0,

for

\ell=0,1,...,r-1

, where

M^(k)(λ₀₎

denotes the

th derivative of

with respect to

and evaluated in

λ=λ₀

. The vectors

x_0,x_1,...,x_r-1

are called generalized eigenvectors,

is called the length of the Jordan chain, and the maximal length a Jordan chain starting with

x₀

is called the rank of

x₀

Theorem: A tuple of vectors

(x_0,x_1,...,x_r-1)\in\Complex^{n x \Complex}^{n x ... x \Complex}ⁿ

is a Jordan chain if and only if the function

M(λ)\chi_\ell(λ)

has a root in

λ=λ₀

and the root is of multiplicity at least

\ell

for

\ell=0,1,...,r-1

, where the vector valued function

\chi_\ell(λ)

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.^[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^[13] 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

maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices.^[14] ^[15]

References

Güttel. Stefan. Tisseur. Françoise. Françoise Tisseur. 2017. The nonlinear eigenvalue problem. Acta Numerica. en. 26. 1–94. 10.1017/S0962492917000034. 46749298. 0962-4929.
Ruhe. Axel. 1973. Algorithms for the Nonlinear Eigenvalue Problem. SIAM Journal on Numerical Analysis. 10. 4. 674–689. 10.1137/0710059. 0036-1429. 2156278. 1973SJNA...10..674R .
Mehrmann. Volker. Volker Mehrmann. Voss. Heinrich. 2004. Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods. GAMM-Mitteilungen. en. 27. 2. 121–152. 10.1002/gamm.201490007. 14493456 . 1522-2608.
Book: Voss, Heinrich. Handbook of Linear Algebra. Chapman and Hall/CRC. 2014. 9781466507289. Hogben. Leslie. Leslie Hogben. 2. Boca Raton, FL. Nonlinear eigenvalue problems. https://www.mat.tuhh.de/forschung/rep/rep174.pdf.
Hernandez . Vicente . Roman . Jose E. . Vidal . Vicente . SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems . ACM Transactions on Mathematical Software . September 2005 . 31 . 3 . 351–362 . 10.1145/1089014.1089019. 14305707 .
Betcke . Timo . Higham . Nicholas J. . Mehrmann . Volker . Schröder . Christian . Tisseur . Françoise . NLEVP: A Collection of Nonlinear Eigenvalue Problems . ACM Transactions on Mathematical Software . February 2013 . 39 . 2 . 1–28 . 10.1145/2427023.2427024. 4271705 .
Polizzi . Eric . 2002.04807 . FEAST Eigenvalue Solver v4.0 User Guide. 2020 . cs.MS .
Güttel . Stefan . Van Beeumen . Roel . Meerbergen . Karl . Michiels . Wim . NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems . SIAM Journal on Scientific Computing . 1 January 2014 . 36 . 6 . A2842–A2864 . 10.1137/130935045. 2014SJSC...36A2842G .
Van Beeumen . Roel . Meerbergen . Karl . Michiels . Wim . Compact rational Krylov methods for nonlinear eigenvalue problems . SIAM Journal on Matrix Analysis and Applications . 2015 . 36 . 2 . 820–838 . 10.1137/140976698. 18893623 .
Lietaert . Pieter . Meerbergen . Karl . Pérez . Javier . Vandereycken . Bart . Automatic rational approximation and linearization of nonlinear eigenvalue problems . IMA Journal of Numerical Analysis . 13 April 2022 . 42 . 2 . 1087–1115 . 10.1093/imanum/draa098. 1801.08622 .
Web site: Berljafa . Mario . Steven . Elsworth . Güttel . Stefan . An overview of the example collection . index.m . 31 May 2022 . 15 July 2020.
Jarlebring . Elias . Bennedich . Max . Mele . Giampaolo . Ringh . Emil . Upadhyaya . Parikshit . NEP-PACK: A Julia package for nonlinear eigenproblems . 23 November 2018. math.NA . 1811.09592 .
Güttel. Stefan. Tisseur. Françoise. Françoise Tisseur. 2017. The nonlinear eigenvalue problem. Acta Numerica. en. 26. 1–94. 10.1017/S0962492917000034. 46749298. 0962-4929.
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. 10.1137/130910014. 1064-8275. 1212.0417. 2014SJSC...36A1978J . 16959079.
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. 10.3934/naco.2020018. 2155-3297. free. 1809.02183.

Nonlinear eigenproblem explained

Definition

Special cases

Jordan chains

Mathematical software

Eigenvector nonlinearity

References

Further reading