Nonlinear eigenproblem

Last updated October 05, 2024

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

where $x\neq 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.^[1]^[2]^[3]^[4]

Let $\Omega \subseteq \mathbb {C}$ , and let $M:\Omega \rightarrow \mathbb {C} ^{n\times n}$ be a function that maps scalars to matrices. A scalar $\lambda \in \mathbb {C}$ is called an eigenvalue, and a nonzero vector $x\in \mathbb {C} ^{n}$ is called a right eigevector if $M(\lambda )x=0$ . Moreover, a nonzero vector $y\in \mathbb {C} ^{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.^[1]

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

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))}{dz^{k}}}\right|_{z=\lambda }\neq 0$ but $\left.{\frac {d^{\ell }\det(M(z))}{dz^{\ell }}}\right|_{z=\lambda }=0$ for $\ell =0,1,2,\dots ,k-1$ .^[1]^[4]

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

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 \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{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}$ .^[1]^[4]

Theorem:^[1] A tuple of vectors $(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 $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.^[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 $M$ maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices.^[13]^[14]

Related Research Articles

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In mathematics, a symmetric matrix $with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the row vector transpose of More generally, a Hermitian matrix is positive-definite if the real number is positive for every nonzero complex column vector where denotes the conjugate transpose of$

In mathematics, a Hermitian matrix is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the $i$ -th row and $j$ -th column is equal to the complex conjugate of the element in the $j$ -th row and $i$ -th column, for all indices $i$ and $j$ :

In mathematics, specifically functional analysis, a trace-class operator is a linear operator for which a trace may be defined, such that the trace is a finite number independent of the choice of basis used to compute the trace. This trace of trace-class operators generalizes the trace of matrices studied in linear algebra. All trace-class operators are compact operators.

In mathematics, particularly in functional analysis, the spectrum of a bounded linear operator is a generalisation of the set of eigenvalues of a matrix. Specifically, a complex number $is said to be in the spectrum of a bounded linear operator if$

In linear algebra, a Jordan normal form, also known as a Jordan canonical form, is an upper triangular matrix of a particular form called a Jordan matrix representing a linear operator on a finite-dimensional vector space with respect to some basis. Such a matrix has each non-zero off-diagonal entry equal to 1, immediately above the main diagonal, and with identical diagonal entries to the left and below them.

In numerical analysis, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.

In linear algebra, the Frobenius companion matrix of the monic polynomial $is the square matrix defined as$

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of general matrices by constructing an orthonormal basis of the Krylov subspace, which makes it particularly useful when dealing with large sparse matrices.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

In linear algebra, an eigenvector or characteristic vector is a vector that has its direction unchanged by a given linear transformation. More precisely, an eigenvector, $, of a linear transformation,, is scaled by a constant factor,, when the linear transformation is applied to it: . It is often important to know these vectors in linear algebra. The corresponding eigenvalue, characteristic value, or characteristic root is the multiplying factor .$

The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the $"most useful" eigenvalues and eigenvectors of an Hermitian matrix, where is often but not necessarily much smaller than . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability.$

In mathematics, delay differential equations (DDEs) are a type of differential equation in which the derivative of the unknown function at a certain time is given in terms of the values of the function at previous times. DDEs are also called time-delay systems, systems with aftereffect or dead-time, hereditary systems, equations with deviating argument, or differential-difference equations. They belong to the class of systems with the functional state, i.e. partial differential equations (PDEs) which are infinite dimensional, as opposed to ordinary differential equations (ODEs) having a finite dimensional state vector. Four points may give a possible explanation of the popularity of DDEs:

Aftereffect is an applied problem: it is well known that, together with the increasing expectations of dynamic performances, engineers need their models to behave more like the real process. Many processes include aftereffect phenomena in their inner dynamics. In addition, actuators, sensors, and communication networks that are now involved in feedback control loops introduce such delays. Finally, besides actual delays, time lags are frequently used to simplify very high order models. Then, the interest for DDEs keeps on growing in all scientific areas and, especially, in control engineering.
Delay systems are still resistant to many classical controllers: one could think that the simplest approach would consist in replacing them by some finite-dimensional approximations. Unfortunately, ignoring effects which are adequately represented by DDEs is not a general alternative: in the best situation, it leads to the same degree of complexity in the control design. In worst cases, it is potentially disastrous in terms of stability and oscillations.
Voluntary introduction of delays can benefit the control system.
In spite of their complexity, DDEs often appear as simple infinite-dimensional models in the very complex area of partial differential equations (PDEs).

In the mathematical discipline of matrix theory, a Jordan matrix, named after Camille Jordan, is a block diagonal matrix over a ring $R$ , where each block along the diagonal, called a Jordan block, has the following form:

<span class="mw-page-title-main">Vertex model</span>

A vertex model is a type of statistical mechanics model in which the Boltzmann weights are associated with a vertex in the model. This contrasts with a nearest-neighbour model, such as the Ising model, in which the energy, and thus the Boltzmann weight of a statistical microstate is attributed to the bonds connecting two neighbouring particles. The energy associated with a vertex in the lattice of particles is thus dependent on the state of the bonds which connect it to adjacent vertices. It turns out that every solution of the Yang–Baxter equation with spectral parameters in a tensor product of vector spaces $yields an exactly-solvable vertex model.$

In linear algebra, if $are complex matrices for some nonnegative integer, and, then the matrix pencil of degree is the matrix-valued function defined on the complex numbers$

In mathematics, an eigenvalue perturbation problem is that of finding the eigenvectors and eigenvalues of a system $that is perturbed from one with known eigenvectors and eigenvalues . This is useful for studying how sensitive the original system's eigenvectors and eigenvalues are to changes in the system. This type of analysis was popularized by Lord Rayleigh, in his investigation of harmonic vibrations of a string perturbed by small inhomogeneities.$

In mathematics, the quadratic eigenvalue problem (QEP), is to find scalar eigenvalues $, left eigenvectors and right eigenvectors such that$

In mathematics, Welch bounds are a family of inequalities pertinent to the problem of evenly spreading a set of unit vectors in a vector space. The bounds are important tools in the design and analysis of certain methods in telecommunication engineering, particularly in coding theory. The bounds were originally published in a 1974 paper by L. R. Welch.

In mathematics, the method of steepest descent or saddle-point method is an extension of Laplace's method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point, in roughly the direction of steepest descent or stationary phase. The saddle-point approximation is used with integrals in the complex plane, whereas Laplace’s method is used with real integrals.

References

1 2 3 4 5 6 7 8 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.
↑ 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.
↑ 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.
1 2 3 4 5 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.
↑ 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.
↑ 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.
↑ Polizzi, Eric (2020). "FEAST Eigenvalue Solver v4.0 User Guide". arXiv: 2002.04807 [cs.MS].
↑ 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.
↑ 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.
↑ 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.
↑ Berljafa, Mario; Steven, Elsworth; Güttel, Stefan (15 July 2020). "An overview of the example collection". index.m. Retrieved 31 May 2022.
↑ 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].
↑ 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.
↑ 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.