Nonlinear Eigenvalue Problems

Nonlinear eigenvalue problems occur in numerous applications. Up to now, no black box solver for general nonlinear eigenvalue problems exists.

The nonlinear eigenvalue problem (NEP) is to find a scalar c such that the linear system T(c)*x=0 has a nontrivial solution x. Hereby, T( . ) describes a family of matrices depending on a complex parameter c. This definition generalizes the linear eigenvalue problems A*x = c*x, where T(c) = A – c*I, and Ax = c*Bx with T(c) = A – c*B. In contrast to the standard eigenvalue problem, a NEP can have none, finitely or even infinitely many eigenvalues. There are two classes of NEPs appearing in a wide range of applications:

• A nonlinear eigenvalue problem is called “polynomial”, if T(c) has the form

T(c) = c^k A_k + c^{k-1} + A_{k-1} + … + c^1 A_1 + A_0

for certain m-x-n matrix coefficients A_0, … , A_k. Such problems are in general solved by linearization. For the dynamic analysis of mechanical systems in acoustics and linear stability of flows in fluid mechanic, the quadratic eigenvalue problem T(c) = c^2 M + c C + K is of particular interest. In various applications, the matrix coefficients of T(c) are structured (symmetric, positive definite, skew-symmetric etc.) due to physical constraints. This often leads to structural pairings among the eigenvalues of T( . ). Algorithms for the solution of polynomial eigenvalue problems should take present structure into account to be efficient and reliable.

• A nonlinear eigenvalue problem is called “rational”, if T(c) has the form

T(c) = t_k(c) A_k + t_{k-1}(c) A_{k-1} + … + t_1(c) A_1 + t_0(c) A_0

where t_0(c), … ,t_k(c) are rational functions of c, i.e., t_j(c) = p(c)/q(c) with polynomials p(c), q(c). Such rational expressions arise, for instance, from the transfer functions of linear dynamical systems and are important concepts in model order reduction. In this context, the analysis of rational eigenvalue problems automatically includes the analysis of poles which play a crucial role for the behavior of the systems. In addition to that, polynomial and rational eigenvalue problems can have infinity among their eigenvalues. In consequence of their pole-structure and their infinite spectral structure such nonlinear eigenvalue problems have to be treated thoroughly and carefully in the design of numerical algorithms.

Beside polynomial and rational eigenvalue problems, nonlinear eigenvalue problems may also depend on genuine nonlinear functions (such as the exponential or trigonometric functions) arising for instance from the discretization of differential equations and in the stability analysis of vibrating systems under state feedback control. Although all these problems have classical origins, they form a fast-moving field inside numerical linear algebra. Algorithms for their solution include Newton’s method, rational (Padé) approximation and interpolation, linearization, contour integration or projection methods.