1 Introduction
In large sparse matrix eigenvalue problems, a common task is to compute a few eigenvalues closest to a given target, largest in magnitude, or rightmost in the complex plane. If we have already (approximately) computed a number of eigenpairs, and would like to compute a new pair, it is of importance to avoid convergence to one of the previously computed pairs.
Let \(A \in {\mathbb {C}}^{n \times n}\). For the standard eigenvalue problemavoidance of previous vectors can be conveniently achieved by computing Schur vectors instead of eigenvectors. This technique is based on the Schur decomposition \(AQ = QR\) for a matrix A, where Q is unitary and R is upper triangular. If \((\lambda _1, q_1)\), ..., \((\lambda _d, q_d)\) are Schur pairs computed earlier in the process and \(Q_d = [q_1 \ldots q_d]\), then \((I-Q_dQ_d^*) \, A \, (I-Q_dQ_d^*)\) has the same Schur pairs as A, except for \(\lambda _1\), ..., \(\lambda _d\) which are replaced by zero eigenvalues. In a subspace method, the search space may then be kept orthogonal to \(q_1\), ..., \(q_d\) so that the subspace method does not notice these zero eigenvalues. For the generalized eigenvalue problem (GEP) \(Ax= \lambda Bx,\) where \(B \in {\mathbb {C}}^{n \times n}\), the generalized Schur decomposition for matrix pencils may be exploited in a similar way.
$$\begin{aligned} A x= \lambda x, \end{aligned}$$
(1)
Anzeige
The Jacobi–Davidson QR (JDQR [27]) method for (1) and Jacobi–Davidson QZ (JDQZ [27]) method for GEP are both examples of methods that are based on the described strategies. Modified deflation techniques are available for other types of linear eigenvalue problems such as the (generalized) singular value problem [8, 9].
In this paper we discuss a new approach to find several eigenvalues for the regular nonlinear eigenvalue problem (NEP)where \(F(\lambda )\) is an \(n\times n\) matrix, whose elements are analytic functions of the complex parameter \(\lambda\). The regularity means that \(\det (F(\lambda ))\) does not vanish identically. As a special case, we will consider the polynomial eigenvalue problem (PEP)where all matrices are \(n \times n\). In some applications, the leading matrix \(A_m\) may be singular, and eigenvalues may be infinite. For this reason, it may be beneficial to consider homogeneous coordinates, which we will do in Sect. 3. Moreover, because of the practical importance, as well as for convenience of presentation, we will focus in particular on the quadratic eigenvalue problem (QEP)Already for the QEP no deflation procedure comparable to those for the standard and generalized eigenvalue problems is known, which is natural in view of the existence of 2n eigenpairs. This implies that if we compute eigenvalues with, for instance, the Jacobi–Davidson method [27], we may find the same eigenvalue again without preventive measures. It is possible to linearize the QEP or PEP to a GEP, for which a deflation procedure is possible. However, a clear drawback of this is that linearization increases the dimension of the problem by a factor \(m-1\) (see also the comments in Sect. 5). Also, the mathematical properties of linearizations are interesting but not straightforward; see, e.g., [10]. For the NEP, linearizations are even more involved. It is therefore relevant to study techniques that can be directly applied to the problem at hand.
$$\begin{aligned} F(\lambda ) \, x= 0, \end{aligned}$$
(2)
$$\begin{aligned} P(\lambda ) \, x=(\lambda ^m A_m + \cdots + \lambda A_1 + A_0) \, x= 0, \end{aligned}$$
(3)
$$\begin{aligned} Q(\lambda ) \, x=(\lambda ^2 A + \lambda B + C) \, x= 0. \end{aligned}$$
(4)
Several strategies have been mentioned to compute several eigenvalues of nonlinear eigenproblems. One option to find more than one eigenvalue is locking, which was studied for the QEP by Meerbergen [20]. The essence of this approach is to carry out no further computations on sufficiently converged Schur vectors, and retain them in the search space. While this method may be effective, a disadvantage is that the size of the search space grows steadily. In [5, 6, 18], a technique called nonequivalence deflation has been proposed, which replaces the original problem by another. Kressner [19] has developed a block method, while Effenberger [4] proposes a deflation strategy for nonlinear eigenproblems. Several methods have been discussed and compared in [4] and by Güttel and Tisseur [7]. Some further comparisons can be found in Sect. 5.
In this paper, we propose an alternative simple and elegant strategy: computing several eigenvalues by selection. In each iteration we pick an approximate eigenpair from (Ritz) pairs that meet a certain selection criterion. This new strategy is particularly simple to comprehend and implement. We present several selection methods to compute more than one eigenpair of linear and nonlinear, and one-parameter and multiparameter eigenvalue problems (MEPs). We present various variants for the QEP and PEP, and for linear and nonlinear multiparameter eigenvalue problems. The selection criteria can be used for all types of eigenvalue problems, provided that expressions for the divided difference and derivative of the problem are available; see (7).
Anzeige
This work contains contributions in three directions. Although we have already successfully used some of these selection techniques in our work on linear multi-parameter eigenvalue problems ([11, 15], followed by nonlinear two-parameter eigenproblems [13, 24] and linear three-parameter eigenvalue problems [12] very recently), we will present an improvement on these criteria for these problems. Secondly, to the best of our knowledge, the use of selection techniques to compute several eigenvalues in the form as described in this paper is new for one-parameter nonlinear eigenproblems: the QEP (4), PEP (3), and general NEP (2). Thirdly, these problems may have infinite eigenvalues when the leading coefficient matrix is singular. Therefore, methods exploiting homogeneous coordinates may be attractive for these problems (cf., e.g., [3, 14]). We therefore introduce divided differences in homogeneous coordinates, which is nontrivial, and new to the best of our knowledge.
Finally, this paper is also meant to serve as an overview paper on selection techniques. We hope that it will inform about, popularize, and facilitate the use of these effective and easy-to-implement methods for eigenvalue problems.
There are various subspace expansion methods for eigenvalue problems. In this paper we will focus on the Jacobi–Davidson method. However, we want to stress that there are several other options to perform a subspace expansion, such as nonlinear Arnoldi [30] for NEPs, and Krylov type methods for MEPs [21]. The selection techniques operate independently of the expansion of the subspace.
The rest of this paper has been organized as follows. In Sect. 2 we introduce a new selection criterion for nonlinear one-parameter eigenvalue problems. Eigenvalue problems involving matrices which are not full rank may have infinite eigenvalues. To deal with these in a consistent framework, homogeneous coordinates are the proper viewpoint; this is studied in Sect. 3. Section 4 focuses on the use of selection criteria for linear and nonlinear MEPs, our original motivation to study these techniques. We end with some numerical experiments and conclusions in Sects. 6 and 7.
2 Selection for nonlinear one-parameter eigenvalue problems
We first introduce some basic notation and facts. The pair \((\lambda , x)\) is an eigenpair if \(F(\lambda )x= 0\) for a nonzero vector \(x\). If \(y^*F(\lambda )= 0\) for a nonzero \(y\), then \(y\) is a left eigenvector for the eigenvalue \(\lambda\). We assume that both \(x\) and \(y\) have unit norm. We say that \(\lambda _0\) is a simple eigenvalue when \(f(\lambda ) := \det (F(\lambda ))\) has a simple zero at \(\lambda = \lambda _0\). Neumaier [23] proves the following proposition about the left and the right eigenvectors of a simple eigenvalue. The same result with an alternative proof is presented in [26].
Proposition 1
For the nonlinear eigenvalue problem
\(F(\lambda ) \, x=0\)
the following are equivalent:
1.
\(f(\lambda ) = \det (F(\lambda ))\)has a simple zero at\(\lambda =\lambda _0\);
2.
\(F(\lambda _0)\)has corank 1, and for right and left eigenvectors\(x\)and\(y\)corresponding to\(\lambda _0\), we have\(y^*F'(\lambda _0) \, x\ne 0\).
The divided difference for F is defined aswhich is continuous in both variables \(\lambda\) and \(\mu\). An alternative way to denote this without distinction of cases is \(F[\lambda ,\mu ] = \displaystyle \lim _{\mu _1 \rightarrow \mu } \frac{F(\lambda )-F(\mu _1)}{\lambda -\mu _1}\). We will use similar expressions for convenience and brevity in Sect. 4. This divided difference enjoys the following two key properties that can be used in the selection process. First, it is easy to see thatwhen \(x_j\) is the right eigenvector for \(\lambda _j\), and \(y_i\) is the left eigenvector for a different eigenvalue \(\lambda _i \ne \lambda _j\). Secondly, when \(\lambda _i\) is a simple eigenvalue, then it follows from Proposition 1 that \(y_i^* \, F[\lambda _i,\lambda _i] \, x_i \ne 0\).
$$\begin{aligned} F[\lambda ,\mu ]:=\left\{ \begin{array}{ll} \displaystyle \frac{F(\lambda )-F(\mu )}{\lambda -\mu } &\quad \mathrm{if}\ \lambda \ne \mu , \\ \\ F'(\lambda ) &\quad \mathrm{if}\ \lambda =\mu , \end{array}\right. \end{aligned}$$
(5)
$$\begin{aligned} y_i^* \, F[\lambda _i,\lambda _j] \, x_j = 0, \end{aligned}$$
(6)
Based on these two observations, we develop a new selection criterion for NEPs using this \(F[\cdot ,\cdot ]\)-orthogonality of right and left eigenvectors. Suppose that we have already computed eigentriplets \((\lambda _1, x_1, y_1)\), ..., \((\lambda _d, x_d, y_d)\) for (2). We assume that all computed eigenvalues \(\lambda _1,\ldots ,\lambda _d\) are simple; the problem is allowed to have multiple eigenvalues, as long as the computed ones are simple. Our selection criteria are not suitable for multiple eigenvalues.
Suppose that \((\theta , v)\) is a candidate approximation for the next eigenpair, where also \(v\) has unit norm. To steer convergence to a pair different from the previously detected eigenpairs, and in view of (6), we only consider approximate eigenpairs for which \(|y_i^* \, F[\lambda _i, \theta ] \, v|\) is sufficiently small for \(i=1,\ldots ,d\). To be precise, in the selection of the candidate approximate eigenpairs we require thatwhere \(0< \eta < 1\) is a fixed constant, which controls the strictness of the selection. Note that the denominator \(|y_i^*\, F'(\lambda _i) \, x_i|\) is a well-known quantity that arises, e.g., in the eigenvalue condition number (cf. [7, Th. 2.20]).
$$\begin{aligned} \max _{i=1,\ldots ,d} \frac{|y_i^*\, F[\lambda _i,\theta ]\, v|}{|y_i^*\, F'(\lambda _i) \, x_i|} < \eta , \end{aligned}$$
(7)
The next proposition explains the behavior of the criterion close to an eigenpair. Suppose that we have already computed the eigenpair \((\lambda _1, x_1)\), and now approximate a pair \((\lambda _2, x_2)\). Let us assume that \((\lambda _2+\varepsilon \phi , x_2+\varepsilon w)\), for small \(\varepsilon\) and vectors of unit norm, is an approximation for \((\lambda _2, x_2)\). This is a realistic assumption in this situation; see [17] for options to extract an approximate eigenvalue from an approximate eigenvector for the QEP and PEP.
Proposition 2
Let\(y_1\ne 0\)be a left eigenvector for a simple eigenvalue\(\lambda _1\)of the nonlinear eigenvalue problem\(F(\lambda )x=0\). Let\(x_2\ne 0\)be a right eigenvector for a simple eigenvalue\(\lambda _2\ne \lambda _1\)and let\((\theta ,v)\), where\(\theta =\lambda _2+\varepsilon \phi\)and\(v=x_2+\varepsilon w\), be a candidate for the next eigenpair. Thenwhere
$$\begin{aligned} {y_1^*F[\lambda _1,\theta ]v\over y_1^*F'(\lambda _1)x_1}=C\varepsilon +{\mathcal {O}}(\varepsilon ^2), \end{aligned}$$
(8)
$$\begin{aligned} C={y_1^*F(\lambda _2)w + \phi \, y_1^*F'(\lambda _2)x_2 \over (\lambda _2-\lambda _1)(y_1^*F'(\lambda _1)x_1)}. \end{aligned}$$
(9)
Proof
The proposition follows from the Taylor series expansionwhere we take into account that \(y_1^*F(\lambda _1)=0\) and \(F(\lambda _2)x_2=0\). \(\square\)
$$\begin{aligned} y_1^*(F(\lambda _1)-F(\theta ))v= - ( y_1^*F(\lambda _2)w + \phi \, y_1^* F'(\lambda _2) x_2 )\varepsilon + {\mathcal {O}}(\varepsilon ^2), \end{aligned}$$
Proposition 2 indicates that selection based on divided differences may be difficult for eigenvalues which are very close. This is in line with the earlier remark that the selection methods are not suited for multiple eigenvalues. We will again see the expression for C in Sect. 3.
Under the assumptions of Proposition 2, \(\frac{|y_1^*F[\lambda _1,\theta ]\, v|}{|y_1^*\, F'(\lambda _1) \, x_1|}\) converges to 0 when \((\theta , v) \rightarrow (\lambda _2, x_2)\) and converges to 1 when \((\theta , v) \rightarrow (\lambda _1, x_1)\). Although this shows that the selection criteria (7) may work for any value \(\eta\) in the interval (0, 1), we generally recommend to use \(\eta \approx 0.1\), to avoid the already computed eigenvalues while simultaneously avoiding the selection process to be unnecessarily strict. We will use this value in the experiments in Sect. 6.
The divided difference for the PEP (3) has the following simple explicit expression.
Proposition 3
For the polynomial eigenvalue problem (3) we haveIn particular, the divided difference for the QEP (4) is
$$\begin{aligned} P[\lambda ,\theta ] =\sum _{i=0}^{m-1}\lambda ^i\theta ^{m-1-i}A_m +\sum _{i=0}^{m-2}\lambda ^i\theta ^{m-2-i}A_{m-1} +\cdots +(\lambda +\theta )A_2+A_1. \end{aligned}$$
$$\begin{aligned} Q[\lambda ,\theta ] = (\lambda +\theta )A+B. \end{aligned}$$
(10)
Proof
This follows from an easy calculation. \(\square\)
The selection criterion for a candidate eigenpair \((\theta , v)\) for the QEP using divided differences then becomesWe note that an important key to the success and simplicity of the selection criteria is the fact that divided differences can be elegantly generalized for many types of eigenproblems. More specifically, we will describe a homogeneous variant of divided differences and a selection criteria in Sect. 3, and a multiparameter variant in Sect. 4.
$$\begin{aligned} \max _{i=1,\ldots ,d} \frac{|y_i^*((\lambda _i+\theta )A+B)v|}{|y_i^*(2\lambda _iA+B) \, x_i|} < \eta . \end{aligned}$$
(11)
We now proceed to discuss some practical matters of the proposed techniques. A main disadvantage of our selection criterion is that one needs the left eigenvectors corresponding to converged eigenvalues during the process. For symmetric and Hermitian eigenvalue problems and right-definite multiparameter eigenvalue problems (see Sect. 4), these left eigenvectors come without extra computations. In other cases, we generally need extra work to compute them. For large-scale problems, this may comprise several additional matrix-vector products to solve \(y\) from \(F(\lambda )^*y= 0\). Pseudocode for this task is given in Algorithm 1.
We note that in some situations we may have a reasonable approximation to the left eigenvector \(y\) in the process. Moreover, and more importantly, any available preconditioner will usually be of great help. For instance, for eigencomputations, often a preconditioner \(M \approx F(\tau )\), where \(\tau \in {\mathbb {C}}\) is the target of interest, is at our disposal.
For problems that are not truly large-scale, we can solve the system in step 2 in Algorithm 1 with a direct instead of an iterative method. In particular, this holds for applications of the selection techniques for multiparameter eigenvalue problems, where the problem size is often relatively small: here, p vectors of length n are sought while the total problem size is of size \(n^p\), where p is the number of parameters.
In either case, the extra work to compute the left eigenvectors will often be relatively small compared with the overall effort of computing the eigenpairs. In addition, the left eigenvectors are very useful information to determine the condition numbers of the eigenvalues, an important quantity to assess the reliability of the eigenvalue. For instance, for the QEP an absolute eigenvalue condition number is given by Tisseur [29]:where we assume that x and y are of unit norm. For general PEPs there is a straightforward analogous expression [29]. We will study the extra costs of the selection in more detail later in this section.
$$\begin{aligned} \kappa (\lambda ) = \frac{|\lambda |^2 \, \Vert A\Vert + |\lambda | \, \Vert B\Vert +\Vert C\Vert }{|y^*Q'(\lambda ) \, x|}, \end{aligned}$$
As already mentioned in the introduction, the selection criteria presented in this paper can be combined with appropriate subspace methods, which expand given subspaces, and extract potential eigenpairs from the subspaces. As an example, we now give a pseudocode for a Jacobi–Davidson method to compute several eigenpairs for the polynomial eigenvalue problem in Algorithm 2 (cf. also [16]).
Let us comment on Algorithm 2. The key steps for the selection process are indicated in boldface. In step 3, rgs denotes repeated Gram–Schmidt orthogonalization or any other method to compute an orthonormal basis in a stable way. There are several strategies available for the extraction of an approximate eigenpair from the search space \({\mathcal {V}}_k\) in step 5. For the extraction of approximate eigenvectors, standard and harmonic Rayleigh–Ritz are default options [16], while [17] discusses choices for an approximate eigenvalue. We can use the selection criterion independently of these extraction choices. The key selection approach described in this paper is used in steps 5 and 9.
In step 5, it might happen that none of the Ritz vectors satisfies the selection criterion. In such a case we pick the best Ritz pair given the target regardless of the selection criteria and skip step 8 so that the method does not find the same eigenpair twice. The idea is that as the subspace expands, Ritz approximations for other eigenvalues should appear in the extraction.
We now give some more details about the costs of Algorithm 2 with selection, compared to the original version without it. Consider the criterion for the polynomial eigenvalue problem of degree m. We look at (3) and (11) to understand the costs. The selection criterion does not require any extra matrix-vector products (MVs), except for the \(m+1\) MVs \(y^*A_j\) per detected left eigenvector \(y\), and any MVs necessary to compute this left eigenvector. The costs of computing \(y\) depends on the problem. For problems with certain structure, for instance symmetry, the left vector may come for free. For nearly symmetric problems, \(x\) may be a good approximation to \(y\). For general problems, several steps with an iterative solver may be necessary to solve for \(y\). A preconditioner that we already have for the eigenvalue problem will generally be of great help. As an alternative for not-too-large problems, an exact solve with \(P(\theta )\) is often an efficient method to find a very good approximation to \(y\).
Next, we study the costs of the divided differences. Per Ritz vector that we choose to test, we need a product of a “primitive Ritz vector” c with the \(n \times k\) matrix \(V_k\) (cost 2nk), some vector additions (cost 2 nm) and one inner product for each of the d already detected eigenpairs (cost 2 nd). This is summarized in the following table.
Computation | Approx. costs | Note |
|---|---|---|
\(y\) | (Variable) | Only when eigentriplet found |
\(y^*A_j\) | \({\mathcal {O}}(nm)\) | Only when eigentriplet found |
\(v_j = V_kc_j\), \(y^*P[\lambda _i,\theta _j]v_j\) | \({\mathcal {O}}(n(k+d+m))\) | Every step, per pair to test (7) |
The dominant costs of lines 2 and 3 in this table will usually be \(\approx 2nk\) per Ritz pair that does not satisfy the criterion (7), so that we have to take the next candidate pair. We have to compute and store the detected left eigenvectors \(y_i\), but in contrast to locking, no orthogonalization costs with respect to converged vectors is required as they do not form part of the search space. Note that the extra costs of the selection procedure may be considered low compared to the complexity \({\mathcal {O}}(nk^2)\) necessary for orthonormalizing the basis. Also, note that we get valuable extra information about the left eigenvalues and the condition numbers of the eigenvalues.
Example 1
To avoid convergence to the same eigenpairs, one may wonder if the proposed selection criterion based on divided differences (5) is really needed: could it be an alternative to simply compare the angles of a current approximate eigenvector \(v\) with the already detected eigenvectors \(x_1, \ldots , x_d\) instead, and make sure that \(v\) is sufficiently different? This simple example for the standard eigenvalue problem shows that this is generally not a stable approach; the one based on the divided differences is preferable.
Consider the \(2 \times 2\) matrixfor small \(\delta\) and \(\varepsilon\), and suppose that the eigenpair \((0, e_1)\) has already been found, where \(e_1\) is the first standard basis vector. The (nonnnormalized) corresponding left eigenvector is \(y= [\delta , \ \, -\varepsilon ]^T\). Since \(\delta \approx 0\), \(\lambda = 0\) is close to being a multiple eigenvalue, and therefore the second eigenvector is numerically ill defined: all vectors \(v\) with unit norm and associated Rayleigh quotient \(\theta = v^*Av\) have a small residual \(r= Av- \theta v\). Comparing the angle of \(v\) with \(e_1\) only rules out \(v\) that are close to \(e_1\). With the divided difference requirement \(y^*v\approx 0\) the vector \(v\) is forced to be close to the true (non-normalized) second eigenvector \([\varepsilon , \ \, \delta ]^T\).
$$\begin{aligned} A = \left[ \begin{array}{cc} 0 &{}\quad \ \varepsilon \\ 0 &{}\quad \ \delta \end{array}\right] , \end{aligned}$$
×
![]()
×
![]()
3 Selection for polynomial eigenproblems in homogeneous coordinates
The context of this section is restricted to polynomial eigenvalue problems (3) rather than the general nonlinear eigenvalue problem. The PEP (3) may have infinite eigenvalues when the leading matrix \(A_m\) is singular. We therefore study these problems in homogeneous coordinates, and propose a new notion for divided differences in this setting. We consider the QEP (4) for the ease of the presentation, but the techniques carry over to the general polynomial eigenvalue problem (3).
Already at this place, we would like to stress the fact that a homogeneous approach may be very valuable in itself, apart from the use for infinite eigenvalues that may be present. As we will see in this section, homogeneous coordinates lead to a different selection criterion (see Experiment 1 for a numerical example), that may be seen as a mediator between the selection criterion for the standard QEP and the reverse QEP. Homogeneous techniques are mathematically elegant and pleasing, and account for the fact that eigenvalue problems may be scaled and transformed in various ways.
Finite and infinite eigenvalues can be elegantly treated together in one consistent framework by the use of homogeneous coordinatesHere, we have the usual conventions: \(\lambda = \alpha / \beta\); \(\lambda = \infty\) corresponds to \((\alpha , \beta ) = (1,0)\); and \((\alpha , \beta )\) and \((\gamma \alpha , \gamma \beta )\) represent the same projective number when \(\gamma \in {\mathbb {C}}\) is nonzero.
$$\begin{aligned} Q(\alpha , \beta ) = \alpha ^2 A + \alpha \beta B + \beta ^2 C \end{aligned}$$
(12)
In the context of divided differences, we have two pairs \((\alpha _1, \beta _1)\) and \((\alpha _2, \beta _2)\): a detected eigenvalue \(\lambda = \alpha _1/\beta _1\), and a new approximation to an eigenvalue \(\theta = \alpha _2 / \beta _2\). It is common to normalize (or scale) \(|\alpha _1|^2 + |\beta _1|^2 = |\alpha _2|^2 + |\beta _2|^2 = 1\), which can be done without loss of generality. Moreover, we might also assume that the \(\beta\)’s are real, nonnegative, and in the interval [0, 1]; however, this turns out to be sometimes undesirable in our context of divided differences, for the following reason. When \((\alpha _2, \beta _2) \rightarrow (\alpha _1, \beta _1)\) as projective coordinates, we want the componentwise convergence \(\alpha _1 \rightarrow \alpha _2\) and \(\beta _1 \rightarrow \beta _2\) in what is to follow. This is not satisfied for, e.g., the pairs \((i,\varepsilon )\) and (1, 0), for \(\varepsilon \rightarrow 0\). The first pair converges to the second pair, the infinite eigenvalue 1/0, but there is no component-wise convergence.
Therefore, instead, we scale the pair \((\alpha _1, \beta _1)\) such that the coordinate with the maximal absolute value is in [0, 1]. For convenience of notation, we assume that this maximum coordinate is \(\beta _1\), but this is not a restriction. As a result, we know that \(\beta _1 \ge \frac{1}{2} \sqrt{2}\). The other pair is then scaled accordingly to the first pair: \(\beta _2 \in [0,1]\), so that (say) \(\beta _2 > 0.7\) when \((\alpha _2, \beta _2)\) is close enough to \((\alpha _1, \beta _1)\). This scaling ensures that convergence also implies componentwise convergence.
Let \(D_{\alpha }\) denote the derivative operator with respect to \(\alpha\). A homogeneous quantity \(DQ(\alpha , \beta )\) for the homogeneous problem (12), that has a similar role as \(Q'(\lambda )\) for problem (4), is (see, e.g., [3, Thm. 3.3])The following key property of (13) will be exploited in the present section. It is part of [3, Thm. 3.3]; cf. Proposition 1.
$$\begin{aligned} DQ(\alpha , \beta ) := \overline{\beta } \, D_{\alpha } Q(\alpha , \beta ) -\overline{\alpha } \, D_{\beta } Q(\alpha , \beta ). \end{aligned}$$
(13)
Proposition 4
If eigenvalue\((\alpha , \beta )\)is simple with associated right and left eigenvectors\(x\)and\(y\)then\(y^* DQ(\alpha , \beta ) \, x\ne 0\).
We note that a vector of the form \(DQ(\alpha , \beta ) \, x\) has also been exploited in the context of homogeneous Jacobi–Davidson [14].
Divided differences make a distinction between eigenvectors belonging to the same, and belonging to different eigenvalues. We will use these differences to find out whether approximate eigenpairs are likely to converge to already detected eigenpairs which need to be avoided, or to new pairs. Similar to the nonhomogeneous divided difference \(Q[\lambda , \mu ]\), we now would like to derive an expression for a divided difference \(Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)]\) for the homogeneous problem (12), which may be used in the selection process. This is done in the following definition, which is new to the best of our knowledge.
Definition 1
Let \((\alpha _1,\beta _1)\) and \((\alpha _2,\beta _2)\) be normalized homogeneous coordinates. We define divided differences in homogeneous coordinates as
$$\begin{aligned} Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)] :=\left\{ \begin{array}{ll} \displaystyle {Q(\alpha _1, \beta _1)-Q(\alpha _2, \beta _2) \over \alpha _1 \beta _2 -\alpha _2 \beta _1}&{}\quad \mathrm{if}\ (\alpha _1,\beta _1) \ne (\alpha _2,\beta _2), \\ DQ(\alpha _1, \beta _1) &{}\quad \mathrm{otherwise}. \end{array}\right. \end{aligned}$$
Note that this expression is both elegant and related to the chordal distance. We recall that the chordal distance of two homogeneous numbers \((\alpha _1, \beta _1)\) and \((\alpha _2, \beta _2)\) is (see, e.g., [28, p. 139])Note that this is the sine of the angle between the two projective numbers interpreted as vectors; cf. [3, p. 75]. With the standard scaling \(|\alpha |^2+|\beta |^2=1\) of projective numbers, this implies that the absolute value of the denominator in the first case of Definition 1 is equal to the chordal distance (14).
$$\begin{aligned} \chi ((\alpha _1, \beta _1), (\alpha _2, \beta _2)) = \frac{|\alpha _1 \, \beta _2 - \alpha _2 \, \beta _1|}{\sqrt{|\alpha _1|^2 + |\beta _1|^2} \, \sqrt{|\alpha _2|^2 + |\beta _2|^2}}. \end{aligned}$$
(14)
The next result is a justification of Definition 1: \(Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)]\) is a continuous function of its two variables.
Proposition 5
If\((\alpha _2, \beta _2) \rightarrow (\alpha _1, \beta _1)\)then\(Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)] \rightarrow DQ(\alpha _1, \beta _1)\).
Proof
Denote \(d\alpha = \alpha _2 - \alpha _1\) and \(d\beta = \beta _2 - \beta _1\). In view of the restriction that the numbers are on the complex unit circle, the following orthogonality condition holds (cf., e.g., [3, Eq. (3)])For the numerator of the divided differences we havewhere \(R_1(\alpha _1, \alpha _2, \beta ) = (\alpha _1+\alpha _2)A + \beta B\) and \(R_2(\alpha , \beta _1, \beta _2) = \alpha B + (\beta _1+\beta _2)C\). Note that \(\displaystyle \lim _{\alpha _2 \rightarrow \alpha _1} R_1(\alpha _1, \alpha _2, \beta ) = D_{\alpha }Q(\alpha _1, \beta )\), \(\displaystyle \lim _{\beta _2 \rightarrow \beta _1} R_2(\alpha , \beta _1, \beta _2) = D_{\beta }Q(\alpha , \beta _1)\), and that such a procedure also extends to general polynomial eigenvalue problems (3).
$$\begin{aligned} \overline{\alpha }_1 \, d\alpha + \overline{\beta }_1 \, d\beta = 0. \end{aligned}$$
(15)
$$\begin{aligned} Q(\alpha _1, \beta _1) - Q(\alpha _2, \beta _2)&= Q(\alpha _1, \beta _1) - Q(\alpha _2, \beta _1) + Q(\alpha _2, \beta _1) - Q(\alpha _2, \beta _2) \\&= (\alpha _1-\alpha _2) \, R_1(\alpha _1, \alpha _2, \beta _1) + (\beta _1-\beta _2) \, R_2(\alpha _2, \beta _1, \beta _2), \end{aligned}$$
Assuming \(\alpha _1 \ne 0\), we now have, using (15) and the definitions of \(d\alpha\) and \(d\beta\),and, similarly,In the case that \(\alpha _1 = 0\), it is easy to check that the first expression equals \(\beta _1^{-1}\) which is equal to \(\overline{\beta }_1\) in this case, and the second expression equals \(d\beta \, d\alpha ^{-1} \, \beta _1^{-1} = 0\) and therefore is equal to \(-\overline{\alpha }_1\), since \(d\beta\) should vanish in view of (15). \(\square\)
$$\begin{aligned} \frac{\alpha _1-\alpha _2}{\alpha _1 \beta _2 - \alpha _2 \beta _1}&= \frac{-d\alpha }{\alpha _1 \, d\beta -d\alpha \, \beta _1} = \frac{d\beta \, \overline{\beta }_1}{\overline{\alpha }_1 \, (\alpha _1 \, d\beta +d\beta \, \beta _1 \, \overline{\beta }_1 \, \overline{\alpha }_1^{-1})} = \frac{d\beta \, \overline{\beta }_1}{d\beta } = \overline{\beta }_1 \end{aligned}$$
$$\begin{aligned} \frac{\beta _1-\beta _2}{\alpha _1 \beta _2 - \alpha _2 \beta _1} = \frac{-d\beta }{\alpha _1 \, d\beta -d\alpha \, \beta _1} = \frac{-d\beta }{\alpha _1 \, d\beta +d\beta \, \beta _1 \, \overline{\beta }_1 \, \overline{\alpha }_1^{-1}} =\frac{-d\beta \, \overline{\alpha }_1}{d\beta } = -\overline{\alpha }_1. \end{aligned}$$
Suppose \((\alpha _1, \beta _1)\) is an eigenvalue with right eigenvector \(x\) and \((\alpha _2, \beta _2)\) is an eigenvalue with left eigenvector \(y\). Proposition 5 shows that the following two desirable properties are satisfied:These two properties will help us in the selection process to avoid convergence towards an already detected eigenvalue: we would like to only select candidate approximate eigenpairs (in homogeneous form) \(((\theta , \eta ), v)\) for which the divided differences \(y_i^* Q[(\alpha _i,\beta _i), (\theta ,\eta )] \, v\) are small enough for all previously detected eigenvalues \((\alpha _i,\beta _i)\) with corresponding left eigenvectors \(y_i\). For this reason, and in line with (7), during the selection process we require thatwhere, for instance, \(\eta = 0.1\). Elegantly, the denominator in this criterion also appears in the denominator of the condition number [3, Thm. 4.2].
- \(y^* Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)] \, x\ne 0\) when \(x\) and \(y\) belong to the same simple eigenvalue \((\alpha _1,\beta _1) = (\alpha _2,\beta _2)\);
- \(y^* Q[(\alpha _1,\beta _1), (\alpha _2,\beta _2)] \, x= 0\) when \(x\) and \(y\) correspond to different eigenvalues \((\alpha _1,\beta _1) \ne (\alpha _2,\beta _2)\).
$$\begin{aligned} \max _{i=1,\ldots ,d} \frac{|y_i^*Q[(\alpha _i, \beta _i), (\theta , \eta )] \, v|}{|y_i^*DQ(\alpha _i, \beta _i) \, x_i|} < \eta , \end{aligned}$$
(16)
The above selection criteria may be exploited for polynomial eigenvalue problems (3), especially if they are expected to have infinite eigenvalues.
We can show that for a PEP the relation between the standard selection criteria and its homogeneous counterpart depends only on the magnitude of the eigenvalues. As a result we see that, if the magnitudes of the new candidate for the eigenvalue and the computed eigenvalue do not differ much, then (7) and (16) return very close values and both criteria should give the same decision.
Lemma 1
Letxbe the eigenvector for a simple eigenvalue\(\lambda\)of the polynomial eigenvalue problem (3) of degreem. If\(P(\alpha ,\beta )\)is the homogeneous variant of (3), i.e., \(P(\alpha ,\beta )=\beta ^m P(\alpha /\beta )\)for\(\beta \ne 0\), thenwhere\(\alpha = \lambda \, (1+|\lambda |^2)^{-1/2}\)and\(\beta =(1+|\lambda |^2)^{-1/2}\).
$$\begin{aligned} P'(\lambda )x=(1+|\lambda |^2)^{(m-2)/2} DP(\alpha ,\beta )x, \end{aligned}$$
Proof
From the partial derivativesit follows from (13) that\(\square\)
$$\begin{aligned} D_{\alpha }P(\alpha ,\beta )&=\beta ^{m-1}P'(\alpha /\beta ),\\ D_{\beta }P(\alpha ,\beta )&=m\,\beta ^{m-1}P(\alpha /\beta ) -\beta ^{m-2}\alpha \, P'(\alpha /\beta ), \end{aligned}$$
$$\begin{aligned} DP(\alpha ,\beta )x=\beta ^{m-2}\,(|\beta |^2+|\alpha |^2)\, P'(\alpha /\beta ) \,x =(1+|\lambda |^2)^{-{(m-2)/2}}\,P'(\lambda )\,x. \end{aligned}$$
In the next result, we assume for convenience of presentation that the eigenvalues and approximation are real, as this greatly simplifies the expressions.
Proposition 6
Let\(y_1\)be the left eigenvector of a simple real eigenvalue\(\lambda _1\)of the polynomial eigenvalue problem (3) of degreemand let\(P(\alpha ,\beta )\)be the homogeneous variant of (3). Let\(x_2\)be the right eigenvector for a simple real eigenvalue\(\lambda _2\ne \lambda _1\)and let\((\theta ,v) =(\lambda _2+\varepsilon \phi , \, x_2+\varepsilon w)\)be a candidate for the next eigenpair, where\(\theta \in \mathbb R\). ThenwhereCis given by (9), \(\alpha _i=\lambda _i\,(1+\lambda _i^2)^{-1/2}\), \(\beta _i=(1+\lambda _i^2)^{-1/2}\)for\(i=1,2\), \(\widetilde{\alpha }_2=\theta \,(1+\theta ^2)^{-1/2}\), and\(\widetilde{\beta }_2= (1+\theta ^2)^{-1/2}\).
$$\begin{aligned} {y_1^*\,P[(\alpha _1,\beta _1),(\widetilde{\alpha }_2,\widetilde{\beta }_2)]\,v \over y_1^*DP(\alpha _1,\beta _1)x_1}=\left( {1+\lambda _1^2\over 1 +\lambda _2^2}\right) ^{(m-1)/2}C\varepsilon + {\mathcal {O}}(\varepsilon ^2), \end{aligned}$$
(17)
Proof
It follows from an expansion that up to \({\mathcal {O}}(\varepsilon ^2)\)-termsFor the numerator of (17) a multivariate Taylor series expansion gives, omitting the \({\mathcal {O}}(\varepsilon ^2)\)-terms,where we have applied Lemma 1. If we also use Lemma 1 for the denominator of (17) and combine the results, we obtain (17). \(\square\)
$$\begin{aligned} \delta \alpha _2&:= \widetilde{\alpha }_2 - \alpha _2 ={\phi \over (1+\lambda _2^2)^{3/2}} \,\varepsilon = {\phi \over 1+\lambda _2^2}\,\beta _2\,\varepsilon ,\\ \delta \beta _2&:= \widetilde{\beta }_2 - \beta _2 = -{\lambda _2 \, \phi \over (1+\lambda _2^2)^{3/2}} \,\varepsilon = -{\phi \over 1+\lambda _2^2} \,\alpha _2\,\varepsilon . \end{aligned}$$
$$\begin{aligned}&y_1^*P[(\alpha _1,\beta _1),(\widetilde{\alpha }_2,\widetilde{\beta }_2)]\,v\\&\quad = -\frac{y_1^*P(\alpha _2,\beta _2)w \, \varepsilon + y_1^* (\delta \alpha _2 \, D_\alpha P(\alpha _2,\beta _2) + \delta \beta _2 \, D_\beta P(\alpha _2,\beta _2))\,x_2}{\alpha _1\widetilde{\beta }_2 - \widetilde{\alpha }_2 \beta _1} \\&\quad ={(1+\lambda _1^2)^{1/2} \, (1+\lambda _2^2)^{1/2}\over \lambda _2-\lambda _1} \ y_1^*\left( P(\alpha _2,\beta _2)w +{\phi \over 1+\lambda _2^2} \, DP(\alpha _2,\beta _2) \,x_2\right) \,\varepsilon \\&\quad ={(1+\lambda _1^2)^{1/2}\over (\lambda _2-\lambda _1)(1+\lambda _2^2)^{(m-1)/2}} \left( y_1^*P(\lambda _2)w + \phi \, y_1^*P'(\lambda _2)\,x_2\right) \varepsilon , \end{aligned}$$
Finally, we give a result that elegantly connects the homogeneous divided differences with divided difference of the standard QEP and of the reverse QEP defined by \(\lambda ^2 Q(\lambda ^{-1}) = A +\lambda B + \lambda ^2 C\). Let \(\lambda\) and \(\theta\) be given in homogeneous coordinates by \((\alpha _1, \beta _1)\) and \((\alpha _2, \beta _2)\), respectively. By Proposition 3, the divided difference expression for the QEP is \((\lambda +\theta )A+B\), which in homogeneous coordinates corresponds toA divided difference expression for the reverse QEP is \(B+(\lambda ^{-1} + \theta ^{-1}) C\), orin homogeneous coordinates. The numerator of the homogeneous divided differences as defined in Definition 1 isIt may be checked thatTherefore, the homogeneous approach may be viewed as a mediator between the divided differences of the QEP and reversed QEP. (We note that in homogeneous Jacobi–Davidson [14], the homogeneous vector used in the subspace expansion has also been shown to be a mediator between those arising in the standard and reverse QEP.) In fact, it may be shown that a similar expression also holds for the PEP (3). This result illustrates a mathematically pleasant property of homogeneous coordinates.
$$\begin{aligned} D_1 = (\alpha _1 \beta _2 + \alpha _2 \beta _1) A + \beta _1 \beta _2 B. \end{aligned}$$
$$\begin{aligned} D_2 = \alpha _1 \alpha _2 B + (\alpha _1 \beta _2 + \alpha _2 \beta _1) C \end{aligned}$$
$$\begin{aligned} D = (\alpha _1^2-\alpha _2^2)A + (\alpha _1 \beta _1-\alpha _2 \beta _2) B + (\beta _1^2-\beta _2^2)C. \end{aligned}$$
$$\begin{aligned} D = \frac{\alpha _1^2-\alpha _2^2}{\alpha _1 \beta _2 + \alpha _2 \beta _1} \, D_1 + \frac{\beta _1^2-\beta _2^2}{\alpha _1 \beta _2 + \alpha _2 \beta _1} \, D_2. \end{aligned}$$
4 Multiparameter eigenvalue problems
As discussed in the introduction, linear two-parameter eigenvalue problems have been the origin of our interest in selection criteria [11, 15]. We briefly review various previous results, whereby we also improve on our previously proposed criteria. We will keep the discussion as concise as possible, referring to the given references for more information.
Consider the linear two-parameter eigenvalue problemwhere the task is to find one or more eigenvalues \((\lambda , \mu )\) together with their eigenvectors of the form \(x_1 \otimes x_2\). We first briefly follow [11]. Let \(\Delta _0 = B_1 \otimes C_2 - C_1 \otimes B_2\), which we assume to be nonsingular. A left eigenvector \(y_1 \otimes y_2\) and right eigenvector \(\widetilde{x}_1 \otimes \widetilde{x}_2\) corresponding to different simple eigenvalues \((\lambda _1, \mu _1)\) and \((\lambda _2, \mu _2)\), respectively, are \(\Delta _0\)-orthogonal:For a selection criterion, we would like an approximate eigenvector \(v_1 \otimes v_2\) to be sufficiently \(\Delta _0\)-orthogonal to already detected left eigenvectors \(y_1^{(i)} \otimes y_2^{(i)}\), \(i = 1, \ldots , d\). In our previous criterion, as was proposed in [11], we required potential \(v_1 \otimes v_2\) to satisfyWhile criterion (18) has turned out to perform satisfactorily in the numerical tests in [11, 15], it may be unnecessarily strict: if one eigenvalue has been detected with right and left eigenvector \(x_1 \otimes x_2\) and \(y_1 \otimes y_2\) for which the right-hand side of (18) is small, the selection procedure may reject many or all candidate Ritz pairs.
$$\begin{aligned} (A_1 - \lambda B_1 -\mu C_1) \, x_1&= 0, \\ (A_2 - \lambda B_2 -\mu C_2) \, x_2&= 0, \end{aligned}$$
$$\begin{aligned} (y_1 \otimes y_2)^* \Delta _0 (\widetilde{x}_1 \otimes \widetilde{x}_2) = (y_1^* B_1 \widetilde{x}_1)(y_2^* C_2 \widetilde{x}_2) - (y_1^* C_1 \widetilde{x}_1)(y_2^* B_2 \widetilde{x}_2) = 0. \end{aligned}$$
$$\begin{aligned} \max _{i=1,\ldots ,d} \ (y_1^{(i)} \otimes y_2^{(i)})^* \Delta _0 (v_1 \otimes v_2) < \tfrac{1}{2} \cdot \min _{i=1,\ldots ,d} \ (y_1^{(i)} \otimes y_2^{(i)})^* \Delta _0 (x_1^{(i)} \otimes x_2^{(i)}). \end{aligned}$$
(18)
Therefore, instead of (18), we propose the new modified criterion (cf. (7))with, e.g., \(\eta = 0.1\). This criterion has been successfully used very recently in [12].
$$\begin{aligned} \max _{i=1,\ldots ,d} \ \frac{(y_1^{(i)} \otimes y_2^{(i)})^* \Delta _0 (v_1 \otimes v_2)}{(y_1^{(i)} \otimes y_2^{(i)})^* \Delta _0 (x_1^{(i)} \otimes x_2^{(i)})} < \eta , \end{aligned}$$
(19)
In [15] the special but important right-definite case has been treated, where all matrices \(A_i\), \(B_i\), and \(C_i\) are Hermitian, and \(\Delta _0\) is positive definite. In this situation, the right and left eigenvectors coincide, and therefore eigenvectors \(x_1 \otimes x_2\) and \(\widetilde{x}_1 \otimes \widetilde{x}_2\) corresponding to different eigenvalues are \(\Delta _0\)-orthogonal: \((x_1 \otimes x_2)^* \Delta _0 (\widetilde{x}_1 \otimes \widetilde{x}_2) = 0\). We note that [15] has been the first paper where a selection criterion to compute several eigenvalues has been proposed and used, in the context of linear two-parameter eigenproblems.
Besides being simple and easy to implement, selection criteria can be elegantly extended to other types of (multiparameter) eigenvalue problems. The \(\Delta _0\)-orthogonality can be nicely extended to nonlinear two-parameter eigenvalue problems as follows.
For the polynomial and general nonlinear two-parameter eigenvalue problemwe have introduced in [13] a generalized divided differencewhere \(\left| \begin{array}{cc} A&{} B\\ C &{} D \end{array} \right| _\otimes\) stands for the operator determinant \(A\otimes D - B \otimes C\); see also [24]. In these papers, it has been shown that this divided difference has the desired property that the quantityis nonzero when \((\theta , \eta )\) converges to \((\lambda _i, \mu _i)\), while it is 0 when the pair converges to another eigenvalue.
$$\begin{aligned} T_1(\lambda , \mu ) \, x_1&= 0, \\ T_2(\lambda , \mu ) \, x_2&= 0, \end{aligned}$$
$$\begin{aligned} T[(\lambda _1, \mu _1), (\lambda _2, \mu _2)] = \left| \begin{array}{ccc} \displaystyle \lim _{\lambda \rightarrow \lambda _2} \frac{T_1(\lambda , \mu _1) - T_1(\lambda _1, \mu _1)}{\lambda -\lambda _1} &{} \ \displaystyle \lim _{\mu \rightarrow \mu _2} \frac{T_1(\lambda _2, \mu ) -T_1(\lambda _2, \mu _1)}{\mu -\mu _1} \\ \ \displaystyle \lim _{\lambda \rightarrow \lambda _2} \frac{T_2(\lambda , \mu _1) - T_2(\lambda _1, \mu _1)}{\lambda -\lambda _1} &{} \ \displaystyle \lim _{\mu \rightarrow \mu _2} \frac{T_2(\lambda _2, \mu ) -T_2(\lambda _2, \mu _1)}{\mu -\mu _1} \end{array} \right| _\otimes , \end{aligned}$$
$$\begin{aligned} (y_1^{(i)} \otimes y_2^{(i)})^* \, T[(\lambda _i, \mu _i), (\theta , \eta )] \, (v_1 \otimes v_2) \end{aligned}$$
We now illustrate the adaptivity and flexibility of the selection criterion by the following generalization for the differentiable nonlinear three-parameter eigenvalue problemWhile the special case of a linear case of this problem has been treated recently in [12, Lem. 4.2], we now define a divided difference for the nonlinear case (20).
$$\begin{aligned} T_1(\lambda , \mu , \nu ) \, x_1&= 0, \nonumber \\ T_2(\lambda , \mu , \nu ) \, x_2&= 0, \nonumber \\ T_3(\lambda , \mu , \nu ) \, x_3&= 0, \end{aligned}$$
(20)
Definition 2
We define the divided difference \(T[(\lambda _1, \mu _1, \nu _1), (\lambda _2, \mu _2, \nu _2)]\) for problem (20) by
$$\begin{aligned} {\left| \begin{array}{ccc} \displaystyle \lim _{\lambda \rightarrow \lambda _2} \frac{T_1(\lambda ,\mu _1,\nu _1) -T_1(\lambda _1,\mu _1,\nu _1)}{\lambda -\lambda _1} &{} \ \displaystyle \lim _{\mu \rightarrow \mu _2} \frac{T_1(\lambda _2,\mu ,\nu _1) -T_1(\lambda _2,\mu _1,\nu _1)}{\mu -\mu _1} &{} \ \displaystyle \lim _{\nu \rightarrow \nu _2} \frac{T_1(\lambda _2,\mu _2,\nu ) -T_1(\lambda _2,\mu _2,\nu _1)}{\nu -\nu _1} \\ \displaystyle \lim _{\lambda \rightarrow \lambda _2}\frac{T_2(\lambda ,\mu _1,\nu _1) -T_2(\lambda _1,\mu _1,\nu _1)}{\lambda -\lambda _1} &{} \ \displaystyle \lim _{\mu \rightarrow \mu _2} \frac{T_2(\lambda _2,\mu ,\nu _1) -T_2(\lambda _2,\mu _1,\nu _1)}{\mu -\mu _1} &{} \ \displaystyle \lim _{\nu \rightarrow \nu _2} \frac{T_2(\lambda _2,\mu _2,\nu ) -T_2(\lambda _2,\mu _2,\nu _1)}{\nu -\nu _1} \\ \displaystyle \lim _{\lambda \rightarrow \lambda _2}\frac{T_3(\lambda ,\mu _1,\nu _1) -T_3(\lambda _1,\mu _1,\nu _1)}{\lambda -\lambda _1} &{} \ \displaystyle \lim _{\mu \rightarrow \mu _2} \frac{T_3(\lambda _2,\mu ,\nu _1) -T_3(\lambda _2,\mu _1,\nu _1)}{\mu -\mu _1} &{} \ \displaystyle \lim _{\nu \rightarrow \nu _2} \frac{T_3(\lambda _2,\mu _2,\nu ) -T_3(\lambda _2,\mu _2,\nu _1)}{\nu -\nu _1} \end{array} \right| _\otimes .} \end{aligned}$$
The following results justify this definition.
Proposition 7
The quantityis nonzero when\((\lambda _2, \mu _2, \nu _2) = (\lambda _1, \mu _1, \nu _1)\)is a simple eigenvalue with right and left eigenvector\(x_1 \otimes x_2 \otimes x_3\)and\(y_1 \otimes y_2 \otimes y_3\), respectively; it equals 0 when\(x_1 \otimes x_2 \otimes x_3\)and\(y_1 \otimes y_2 \otimes y_3\)belong to different eigenvalues\((\lambda _2, \mu _2, \nu _2) \ne (\lambda _1, \mu _1, \nu _1)\).
$$\begin{aligned} (y_1 \otimes y_2 \otimes y_3)^* \, T[(\lambda _1, \mu _1, \nu _1), (\lambda _2, \mu _2, \nu _2)] \, (x_1 \otimes x_2 \otimes x_3) \end{aligned}$$
Proof
A rather straightforward generalization of [22, Prop. 3.2] shows thatWhen \(\lambda _2 \ne \lambda _1\), \(\mu _2 \ne \mu _1\), and \(\nu _2 \ne \nu _1\),since the sum of the columns is the zero vector. Finally, when some, but not all, of the coordinates of \((\lambda _1,\mu _1,\nu _1)\) are equal to \((\lambda _2,\mu _2,\nu _2)\), the determinant vanishes as well. Indeed, it can be checked that:\(\square\)
$$\begin{aligned}&(y_1 \otimes y_2 \otimes y_3)^* \, T[(\lambda _1, \mu _1, \nu _1), (\lambda _1, \mu _1, \nu _1)] \, (x_1 \otimes x_2 \otimes x_3) \\&\quad = \left| \begin{array}{ccc} y_1^* \frac{\partial T_1}{\partial \lambda } x_1 &{} \quad y_1^* \frac{\partial T_1}{\partial \mu } x_1 &{} \quad y_1^* \frac{\partial T_1}{\partial \nu } x_1 \\ y_2^* \frac{\partial T_2}{\partial \lambda } x_2 &{} \quad y_2^* \frac{\partial T_2}{\partial \mu } x_2 &{} \quad y_2^* \frac{\partial T_2}{\partial \nu } x_2 \\ y_3^* \frac{\partial T_3}{\partial \lambda } x_3 &{} \quad y_3^* \frac{\partial T_3}{\partial \mu } x_3 &{} \quad y_3^* \frac{\partial T_3}{\partial \nu } x_3 \\ \end{array}\right| \ne 0. \end{aligned}$$
$$\begin{aligned}&(y_1 \otimes y_2 \otimes y_3)^* \, T[(\lambda _1, \mu _1, \nu _1), (\lambda _2, \mu _2, \nu _2)] \, (x_1 \otimes x_2 \otimes x_3) \\&\quad = (\lambda _2-\lambda _1)^{-1}(\mu _2-\mu _1)^{-1} (\nu _2-\nu _1)^{-1} \cdot \\&\qquad {\left| \begin{array}{ccc} y_1^*T_1(\lambda _2,\mu _1,\nu _1)x_1 &{} \quad y_1^*(T_1(\lambda _2,\mu _2,\nu _1) - T_1(\lambda _2,\mu _1,\nu _1))x_1 &{} \quad -y_1^*T_1(\lambda _2,\mu _2,\nu _1)x_1 \\ y_2^*T_2(\lambda _2,\mu _1,\nu _1)x_2 &{} \quad y_2^*(T_2(\lambda _2,\mu _2,\nu _1) - T_2(\lambda _2,\mu _1,\nu _1))x_2 &{} \quad -y_2^*T_2(\lambda _2,\mu _2,\nu _1)x_2 \\ y_3^*T_3(\lambda _2,\mu _1,\nu _1)x_3 &{} \quad y_3^*(T_3(\lambda _2,\mu _2,\nu _1) - T_3(\lambda _2,\mu _1,\nu _1))x_3 &{} \quad -y_3^*T_3(\lambda _2,\mu _2,\nu _1)x_3 \\ \end{array} \right| = 0,} \end{aligned}$$
- when \((\lambda _1, \mu _1, \nu _1)\) and \((\lambda _2, \mu _2, \nu _2)\) agree in one of three coordinates then the columns where the coordinates do not agree differ by a factor \(-1\);
- when \((\lambda _1, \mu _1, \nu _1)\) and \((\lambda _2, \mu _2, \nu _2)\) agree in two of three coordinates then the column where the coordinates do not agree is zero.
This result implies that selection criteria in the line of (19) can be exploited.
For multiparameter eigenvalue problems, locking becomes less and less attractive as the number of parameters increases. For instance, when we are prepared to solve projected eigenvalue problems of dimension approximately 100 at the subspace extraction step, the search spaces are limited to dimension 10 for two parameters, and even to dimension 5 for three parameters. As locking keeps the converged vectors in the search space, this technique is generally not an option for MEPs.
Therefore, selection effectively creates more space in the subspaces to contain new information. However, even when using selection criteria to compute several eigenvalues, already detected vectors may sometimes turn up in the search space in practice. Therefore, we will be limited by the size of the search space at some point, and we cannot expect to compute arbitrarily many eigenvalues.
5 Comparison with other approaches
A good comparison of various approaches has already been carried out in [4]. Here we briefly discuss differences of selection criteria compared to other methods for computing several eigenvalues of one-parameter eigenvalue problems.
Besides our selection criteria, there are several alternatives for the computation of several eigenvalues for nonlinear eigenvalue problems and linear and nonlinear multiparameter eigenvalue problems. Nonequivalence deflation [5, 6, 18] has an elegant mathematical foundation, but changes the original problem, and might suffer from instabilities. Block methods may be used to compute several eigenvalues simultaneously [19], but also has some drawbacks as indicated in [4]. Locking, which keeps the eigenvectors in the search space [4, Ch. 6, 20], leaves less space for new vectors; to find new eigenvectors, the search spaces have to grow. Especially for multiparameter eigenvalue problems, where the dimension of the projected problems grows as \(n^p\), with p the number of parameters, locking is not a realistic alternative.
We will now discuss differences with the method by Effenberger [4], which we consider state-of-the-art and of particular importance, in more detail. This method, as our approach, also computes the eigenvalues successively while preventing convergence to the same eigenpairs. However, this method and the one proposed here are still of very different nature. First, the method in [4] is far from trivial to implement. During the computations, it modifies the original problem by adding rows and columns so that the problem size steadily increases. It is unable to deal with infinite eigenvalues, as it does not use homogeneous coordinates. Moreover, it is an open question if the approach can be generalized to multiparameter eigenvalue problems. As a big advantage, Effenberger’s method has been designed with the aim of also computing multiple and clustered eigenvalues in a stable way. Our proposed approach, on the other hand, is (much) simpler, both conceptually and with respect to implementation (just a few lines of codes on top of an existing code). Our method is designed to handle infinite eigenvalues by homogeneous coordinates, and the problem remains unmodified during the iterations. Also, the techniques are elegantly generalizable to various types of eigenproblems. On the other hand, as stated before, the method is not suitable to compute multiple eigenvalues.
We note that standard deflation methods (see Sect. 1) for the generalized eigenvalue problems can be used for polynomial one-parameter and multiparameter eigenvalue problems when one is prepared to linearize the problem into a (much) larger problem. For instance, in [21], a Krylov–Schur type method has been proposed for the linear two-parameter eigenvalue problem, which works on the operators \(\Delta _0^{-1} \Delta _1\) or \(\Delta _0^{-1} \Delta _2\). A main disadvantage of this approach is that it works on vectors of length \(n^2\), instead of n for a direct approach. The action with the \(\Delta _0^{-1} \Delta _i\) operators can be done in \({\mathcal {O}}(n^3)\) effort instead of the expected \({\mathcal {O}}(n^6)\) by solving a Sylvester equation. Therefore, when n is small enough, this method may still be worthwhile for two-parameter problems. For three-parameter problems, the situation looks far less favorable [12].
6 Numerical examples
We present some numerical examples obtained with Matlab. Several successful experiments with several types of multiparameter eigenvalue problems have been carried out and described in [11‐13, 15, 24]. Therefore, we concentrate ourselves mostly on the new use for polynomial eigenvalue problems.
Experiment 1
We consider the QEP utrecht1331 with target \(\tau = -70 - 2000i\) as in [16], and an exact LU preconditioner based on this target. This is a quite challenging interior eigenvalue problem, due to the difficult spectrum, the interior location of the target, and the different scales of the real and imaginary parts; see Fig. 1a. Approximate eigenpairs \((\theta , v)\) are computed to relative tolerance \(10^{-6}\), meaningAt first, we take selection threshold \(\eta = 0.1\) in (11). We use the Jacobi–Davidson method with harmonic extraction [16] and 10 steps of bicgstab to solve the correction equations. The left eigenvectors are solved by an exact solve with \(Q(\theta )^*\) when \(\theta\) has sufficiently converged. For the value extraction we use the one-dimensional Galerkin gal1 approach from [17]. With minimum and maximum subspace sizes of 20 and 40, we find 12 eigentriplets in 200 iterations; the convergence history is displayed in Fig. 1b. The eigenvalues are detected after 10, 12, 14, 16, 78, 96, 105, 118, 133, 147, 165, and 178 iterations. Elegantly, when we sort the eigenvalues with respect to distance to the target, these are eigenvalues number 1 through 12, in this order! The longer “hiccup” after several eigenpairs (here the 5th) may occur in many problems, and is likely due to the fact that new information needs to be inserted in the search space. We note that it seems important that the search spaces are allowed to be sufficiently large; otherwise, at some point, the convergence may stop altogether. For instance, using minimal subspace size 15 and maximal subspace size 25, only 4 eigenvalues are detected in 200 iterations, with indices 5, 7, 6, and 10. Favorably, the process seems to be not very sensitive with respect to the precise threshold value of \(\eta\): the choices of \(\eta = 0.01\), 0.2, and 0.5 result in 9, 13, and 13 found eigenpairs, respectively.
$$\begin{aligned} \Vert r\Vert := \Vert Q(\theta )v\Vert \le 10^{-6} \cdot (\,|\theta |^2 \, \Vert A\Vert _1 + |\theta | \, \Vert B\Vert _1 + \Vert C\Vert _1\,). \end{aligned}$$
Although the problem does not have infinite eigenvalues, we may also use the homogeneous divided differences of Sect. 3. Note that this method is different from the standard divided difference. In this case, we also find 12 eigenpairs in 200 iterations, after 10, 12, 15, 70, 81, 91, 107, 124, 143, 154, 170, and 190 iterations, respectively.
Fig. 1
a Spectrum and target of utrecht1331; b convergence history of 12 converged eigenpairs
×
![]()
Experiment 2
We consider a popular challenge: the problem gyroscopic, a model of a gyroscopic dynamical system, of size \(n = 10{,}000\); cf. [1, p. 654]. Here, A is diagonal with elements uniformly from [0, 1] with additionally \(a_{11} = 0\), B is tridiagonal with \(-1\)s on the subdiagonal and 1s on the superdiagonal, and C is diagonal with elements uniformly from \((-1,0)\). Therefore, A is symmetric positive semidefinite, B is skew-symmetric, and C is symmetric negative definite, which is typical for this type of system. The matrix A is singular and the QEP has infinite eigenvalues. Therefore, it seems appealing to exploit the homogeneous technique of Sect. 3. We take target \(\tau = 80i\), and an exact LU preconditioner based on this target. An eigenpair is considered converged if the residual is below \(10^{-4}\). All other parameters are as in Experiment 1. We find 10 eigenpairs in 800 iterations, after 108, 109, 111, 115, 118, 143, 162, 176, 625, and 777 iterations, respectively. Here, we see again the same pattern of first spending several iterations to obtain a good subspace, then the quick detection of a number of eigenvalues, followed by a new period of enriching the subspace before new eigenpairs are found.
Experiment 3
For the next experiment, we take the largest cubic polynomial eigenvalue problem \((\lambda ^3 A_3 + \lambda ^2 A_2 + \lambda A_1 +A_0)\,x = 0\) of the nlevp toolbox [2]: the problem plasma_drift, with coefficient matrices of size 512; see Fig. 2. We note that this spectrum is quite challenging, with close eigenvalue and eigenvalues of high multiplicity. Our target is \(\tau = 0\), and as in the previous experiment we use an exact LU preconditioner based on this target, so \(LU = A_0\). For the value extraction we use the two-dimensional minimum residual mr2 approach from [17]. The other settings are the same as in Experiment 1. With \(\eta = 0.1\), the Jacobi–Davidson method finds 19 eigenvalues in 200 outer iterations; cf. Fig. 1c. With respect to distance to the target, these are approximations to eigenvalues with index 1 through 12, 511, 512, 514, 14, 16, 515, and 510, respectively. This “alternating” behavior is quite typical for iterative eigensolvers; cf. also [11, 15]. The high indices can be explained by the fact that there are several eigenvalues of high multiplicity close to the origin. This illustrates that the selection method may work fine for problems with multiple eigenvalues, as long as the computed eigenvalues are simple. Other choices for \(\eta\) result in 14 (\(\eta = 0.01\)), 10 (\(\eta = 0.2\)), and 11 (\(\eta = 0.5\)) eigenvalues.
Fig. 2
a, b Spectrum and target of plasma_drift; c convergence history of 19 converged eigenpairs
×
![]()
Experiment 4
We consider the 4-point boundary value problemwhere we seek \((\lambda ,\mu ,\eta )\) such that there exists a nonzero solution y(x). This problem can be decomposed into a 3-parameter eigenvalue problem that consists of three 2-point boundary value problems of the formfor \(i=1,2,3\). A smooth function y(x) that satisfies (21) can be constructed from the functions \(y_1(x_1)\), \(y_2(x_2)\), \(y_3(x_3)\). The 3-parameter eigenvalue problem (22) has the Klein oscillation property, which means that for each triple of nonnegative integers \((m_1,m_2,m_3)\) there exist a triple of values \((\lambda ,\mu ,\eta )\) such that (21) has a solution y(x) that has \(m_1\) zeros on interval (0, 1), \(m_2\) zeros on (1, 2), and \(m_3\) zeros on (2, 3).
$$\begin{aligned} y''(x)+(\lambda + 2\mu \cos (x) +2\eta \cos (2x))\,y(x)=0,\quad y(0)=y(1)=y(2)=y(3)=0, \end{aligned}$$
(21)
$$\begin{aligned} y_i''(x_i)+(\lambda + 2 \mu \cos (x_i) +2 \eta \cos (2x_i))\,y(x_i)=0, \quad y_i(i-1)=y_i(i)=0 \end{aligned}$$
(22)
We discretize (22) using the Chebyshev collocation on 200 points (cf. [12]), which leads to an algebraic 3-parameter eigenvalue problem of the formThe solutions with indices \((j_1,j_2,j_3)\) such that \(j_1+j_2+j_3\) is small correspond to eigenvalues \((\lambda ,\mu ,\eta )\) close to (0, 0, 0). To find eigenvalues close to the origin, we apply the Jacobi–Davidson method, for details see [12]. We restrict the subspace dimensions between 5 and 10 and solve the corresponding correction equations approximately by 10 steps of GMRES, where we use the exact LU preconditioner based on the target, i.e., \(A_j=L_jU_j\) for \(j = 1,2,3\). The Jacobi–Davidson method returns 20 eigenvalues after performing 40 subspace updates. The first nine eigenvalues converged are provided in Table 1 together with their indices, while the corresponding solutions y(x) of (21) are illustrated in Fig. 3. Note that the indices in Table 1 confirm that the eigenvalues converged are indeed the ones closest to the origin.
$$\begin{aligned} (A_i-\lambda B_i-\mu C_i-\eta D_i) \, x_i=0,\quad i=1,2,3. \end{aligned}$$
(23)
Table 1
The first 9 eigenvalues of the 4-point boundary value problem (21) retrieved by the Jacobi–Davidson method with the origin as the target point
\(\lambda\)
|
\(\mu\)
|
\(\eta\)
|
\(j_1\)
|
\(j_2\)
|
\(j_3\)
|
|---|---|---|---|---|---|
9.86960440 | \(-\) 0.00000000 | 0.00000000 | 0 | 0 | 0 |
17.38523159 | 2.12527575 | \(-\) 12.73290564 | 0 | 1 | 0 |
19.68377612 | 8.41730432 | 6.17620916 | 1 | 0 | 0 |
21.44695005 | \(-\) 10.07354787 | 5.66869884 | 0 | 0 | 1 |
27.85962272 | 10.19955145 | \(-\) 6.02172707 | 1 | 1 | 0 |
29.79885232 | \(-\) 8.32972041 | \(-\) 6.38665167 | 0 | 1 | 1 |
31.75591668 | \(-\) 1.66950908 | 11.70626000 | 1 | 0 | 1 |
39.47841760 | 0.00000000 | \(-\) 0.00000000 | 1 | 1 | 1 |
22.26126463 | 7.52057950 | \(-\) 38.93555514 | 0 | 2 | 0 |
7 Conclusions
We have presented several selection criteria for computing several eigenvalues for nonlinear one-parameter, and linear and nonlinear multiparameter eigenvalue problems. Selection means that an approximate eigenpair is picked from candidate pairs that satisfy a certain suitable criterion. The goal of this process is to steer the process away from already previously found pairs. These criteria are easy to understand and implement, and also elegantly extend to various types of eigenproblems. We have also developed a divided difference and selection criterion in homogeneous coordinates. This not only has the potential to handle infinite eigenvalues, but also is a valuable alternative approach in itself.
The methods work directly on the original problem; no linearizations (as for instance discussed in [10]) are necessary. They require the computation of the left eigenvector, which implies some extra costs for nonsymmetric problems. However, these additional costs are often relatively small compared to the total costs. For certain problems with structure, such as symmetric problems, the left eigenvectors come for free. Also, left eigenvectors provide valuable information on the condition number and reliability of the computed eigenvalues.
A main advantage of the selection techniques is that the search spaces effectively may contain more useful vectors for the computations of new eigenvectors. Instead of locking, which keeps the converged vectors in the search space, the search spaces can now be more fully used for new information. Moreover, and also important for practical use, the selection criteria are relatively easy to understand and implement compared with several existing approaches.
For the quadratic and polynomial (one-parameter) eigenvalue problem, the presented methods are new, and a valuable alternative to other methods such as locking or block methods (cf. [4]); a more detailed comparison can be found in Sect. 5. For linear and nonlinear multiparameter eigenvalue problems, we would like to stress the fact that the presented selection techniques seem to be the only realistic option. While for multiparameter eigenvalue problems we already proposed selection criteria in the past, in this paper we propose updated and less strict criteria of the type (19) instead of (18).
The approach can also be applied to general nonlinear eigenproblems \(F(\lambda )x=0\), as long as we can evaluate the derivative \(F'(\lambda )\) and the divided difference \(F[\lambda ,\mu ]\).
We note that for challenging problems, it sometimes is not easy to find more than about 10 eigenpairs with the selection criterion. Reasons for this may be that a larger part of the search space is occupied by already detected eigenvectors, or that the preconditioner is of lower quality for the new eigenvalues. In this case, it may be a good idea to start a new process with a modified target and preconditioner.
Code for the proposed techniques for one-parameter eigenvalue problems is available on request; for multiparameter eigenvalue problems, we refer to [25].
Acknowledgements
We thank Daniel Kressner for helpful discussions and two expert referees for useful comments. MH has been supported by an NWO Vidi research grant (Grants 693.032.223 and 040.11.434). BP has been supported in part by the Slovenian Research Agency (Grant P1-0294) and by an NWO visitor’s grant.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.