Exponentially convergent parallel algorithm for nonlinear eigenvalue problems

A. V. Klimenko, V. L. Makarov ^{A new algorithm for nonlinear eigenvalue problems is proposed.The numerical technique is based on a perturbation of the coefficientsof differential equation combined with the Adomian decompositionmethod for the nonlinear part. The approach provides an exponentialconvergence rate with a base which is inversely proportionalto the index of the eigenvalue under consideration. The eigenpairscan be computed in parallel. Numerical examples are presentedto support the theory. They are in good agreement with the spectralasymptotics obtained by other authors.}     

Arnoldi versus nonsymmetric Lanczos algorithms for solving matrix eigenvalue problems

We present theoretical and numerical comparisons between Arnoldi and nonsymmetric Lanczos procedures for computing eigenvalues of nonsymmetric matrices. In exact arithmetic we prove that any type of eigenvalue convergence behavior obtained using a nonsymmetric Lanczos procedure may also be obtained using an Arnoldi procedure but on a different matrix and with a different starting vector. In exact arithmetic we derive relationships between these types of procedures and normal matrices which suggest some interesting questions regarding the roles of nonnormality and of the choice of starting vectors in any characterizations of the convergence behavior of these procedures. Then, through a set of numerical experiments on a complex Arnoldi and on a complex nonsymmetric Lanczos procedure, we consider the more practical question of the behavior of these procedures when they are applied to the same matrices.This work was supported by NSF grant GER-9450081 while the author was visiting the University of Maryland.     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

Subspace methods for three‐parameter eigenvalue problems

We propose subspace methods for three‐parameter eigenvalue problems. Such problems arise when separation of variables is applied to separable boundary value problems; a particular example is the Helmholtz equation in ellipsoidal and paraboloidal coordinates. While several subspace methods for two‐parameter eigenvalue problems exist, their extensions to a three‐parameter setting seem challenging. An inherent difficulty is that, while for two‐parameter eigenvalue problems, we can exploit a relation to Sylvester equations to obtain a fast Arnoldi‐type method, such a relation does not seem to exist when there are three or more parameters. Instead, we introduce a subspace iteration method with projections onto generalized Krylov subspaces that are constructed from scratch at every iteration using certain Ritz vectors as the initial vectors. Another possibility is a Jacobi–Davidson‐type method for three or more parameters, which we generalize from its two‐parameter counterpart. For both approaches, we introduce a selection criterion for deflation that is based on the angles between left and right eigenvectors. The Jacobi–Davidson approach is devised to locate eigenvalues close to a prescribed target; yet, it often also performs well when eigenvalues are sought based on the proximity of one of the components to a prescribed target. The subspace iteration method is devised specifically for the latter task. The proposed approaches are suitable especially for problems where the computation of several eigenvalues is required with high accuracy. MATLAB implementations of both methods have been made available in the package MultiParEig (see http://www.mathworks.com/matlabcentral/fileexchange/47844-multipareig ).     

A compact rational Krylov method for large‐scale rational eigenvalue problems

In this work, we propose a new method, termed as R‐CORK, for the numerical solution of large‐scale rational eigenvalue problems, which is based on a linearization and on a compact decomposition of the rational Krylov subspaces corresponding to this linearization. R‐CORK is an extension of the compact rational Krylov method (CORK) introduced very recently in the literature to solve a family of nonlinear eigenvalue problems that can be expressed and linearized in certain particular ways and which include arbitrary polynomial eigenvalue problems, but not arbitrary rational eigenvalue problems. The R‐CORK method exploits the structure of the linearized problem by representing the Krylov vectors in a compact form in order to reduce the cost of storage, resulting in a method with two levels of orthogonalization. The first level of orthogonalization works with vectors of the same size as the original problem, and the second level works with vectors of size much smaller than the original problem. Since vectors of the size of the linearization are never stored or orthogonalized, R‐CORK is more efficient from the point of view of memory and orthogonalization than the classical rational Krylov method applied directly to the linearization. Taking into account that the R‐CORK method is based on a classical rational Krylov method, to implement implicit restarting is also possible, and we show how to do it in a memory‐efficient way. Finally, some numerical examples are included in order to show that the R‐CORK method performs satisfactorily in practice.     

Two‐step Newton‐type methods for solving inverse eigenvalue problems

In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

A structure-preserving doubling algorithm for quadratic eigenvalue problems arising from time-delay systems

We propose a structure-preserving doubling algorithm for a quadratic eigenvalue problem arising from the stability analysis of time-delay systems. We are particularly interested in the eigenvalues on the unit circle, which are difficult to estimate. The convergence and backward error of the algorithm are analyzed and three numerical examples are presented. Our experience shows that our algorithm is efficient in comparison to the few existing approaches for small to medium size problems.     

A Power–Arnoldi algorithm for computing PageRank

The PageRank algorithm plays an important role in modern search engine technology. It involves using the classical power method to compute the principle eigenvector of the Google matrix representing the web link graph. However, when the largest eigenvalue is not well separated from the second one, the power method may perform poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. The approach presented here, called Power–Arnoldi, is based on a periodic combination of the power method with the thick restarted Arnoldi algorithm. The justification for this new approach is presented. Numerical tests illustrate the efficiency and convergence behaviour of the new algorithm. Copyright © 2007 John Wiley & Sons, Ltd.     

Iterative method for a class of nonlinear eigenvalue problems

Let H Be a complex and separable Hilbert space and consider in H the nonlinear eigenvalue problem where A, B, and C belong to the class of unbounded nonsymmetric operators, which are K- positive K-symmetric. Sufficient conditions insuring the existence of the eigenvalues of (i) are investigated. An iterative method for approximating the eigenvalues of (i) is developed and its convergence proved. Some numerical examples are given to illustrate the theory.     

On the existence and multiplicity of positive solutions for some indefinite nonlinear eigenvalue problem

This paper is concerned with the existence, uniqueness and/or multiplicity, and stability of positive solutions of an indefinite weight elliptic problem with concave or convex nonlinearity. We use mainly bifurcation methods to obtain our results.

     

Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems

In many physical situations, a few specific eigenvalues of a large sparse generalized eigenvalue problem are needed. If exact linear solves with are available, implicitly restarted Arnoldi with purification is a common approach for problems where is positive semidefinite. In this paper, a new approach based on implicitly restarted Arnoldi will be presented that avoids most of the problems due to the singularity of . Secondly, if exact solves are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. Results are illustrated by numerical experiments.

     

A Ulm-like method for inverse eigenvalue problems

We propose a Ulm-like method for solving inverse eigenvalue problems, which avoids solving approximate Jacobian equations comparing with other known methods. A convergence analysis of this method is provided and the R-quadratic convergence property is proved under the assumption of the distinction of given eigenvalues. Numerical experiments as well as the comparison with the inexact Newton-like method are given in the last section.     

Multiple nontrivial solutions for nonlinear eigenvalue problems

In this paper we study a nonlinear eigenvalue problem driven by the -Laplacian. Assuming for the right-hand side nonlinearity only unilateral and sign conditions near zero, we prove the existence of three nontrivial solutions, two of which have constant sign (one is strictly positive and the other is strictly negative), while the third one belongs to the order interval formed by the two opposite constant sign solutions. The approach relies on a combination of variational and minimization methods coupled with the construction of upper-lower solutions. The framework of the paper incorporates problems with concave-convex nonlinearities.

     

A remark on Ricceri's conjecture for a class of nonlinear eigenvalue problems

Consider the eigenvalue problem : −Δu=λf(x,u) in Ω, u=0 on ∂Ω, where Ω is a bounded smooth domain in RN. Denote by the set of all Carathéodory functions f:Ω×R→R such that for a.e. x∈Ω, f(x,⋅) is Lipschitzian with Lipschitz constant L, f(x,0)=0 and , and denote by (resp. ) the set of λ>0 such that has at least one nonzero classical (resp. weak) solution. Let λ₁ be the first eigenvalue for the Laplacian-Dirichlet problem. We prove that and . Our result is a positive answer to Ricceri's conjecture if use f(x,u) instead of f(u) in the conjecture.     

Numerical methods for palindromic eigenvalue problems: Computing the anti‐triangular Schur form

We present structure‐preserving numerical methods for the eigenvalue problem of complex palindromic pencils. Such problems arise in control theory, as well as from palindromic linearizations of higher degree palindromic matrix polynomials. A key ingredient of these methods is the development of an appropriate condensed form—the anti‐triangular Schur form. Ill‐conditioned problems with eigenvalues near the unit circle, in particular near ±1, are discussed. We show how a combination of unstructured methods followed by a structured refinement can be used to solve such problems accurately. Copyright © 2008 John Wiley & Sons, Ltd.     

An Arnoldi Method for Nonlinear Eigenvalue Problems

For the nonlinear eigenvalue problem T()x=0 we propose an iterative projection method for computing a few eigenvalues close to a given parameter. The current search space is expanded by a generalization of the shift-and-invert Arnoldi method. The resulting projected eigenproblems of small dimension are solved by inverse iteration. The method is applied to a rational eigenvalue problem governing damped vibrations of a structure.     

Inertia‐based spectrum slicing for symmetric quadratic eigenvalue problems

In the quadratic eigenvalue problem (QEP) with all coefficient matrices symmetric, there can be complex eigenvalues. However, some applications need to compute real eigenvalues only. We propose a Lanczos‐based method for computing all real eigenvalues contained in a given interval of large‐scale symmetric QEPs. The method uses matrix inertias of the quadratic polynomial evaluated at different shift values. In this way, for hyperbolic problems, it is possible to make sure that all eigenvalues in the interval have been computed. We also discuss the general nonhyperbolic case. Our implementation is memory‐efficient by representing the computed pseudo‐Lanczos basis in a compact tensor product representation. We show results of computational experiments with a parallel implementation in the SLEPc library.     

A nonlinearly preconditioned conjugate gradient algorithm for rank‐R canonical tensor approximation

Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank‐R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank‐R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay‐offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand‐alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non‐preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd.