An integral method for solving nonlinear eigenvalue problems

We propose a numerical method for computing all eigenvalues (and the corresponding eigenvectors) of a nonlinear holomorphic eigenvalue problem that lie within a given contour in the complex plane. The method uses complex integrals of the resolvent operator, applied to at least k column vectors, where k is the number of eigenvalues inside the contour. The theorem of Keldysh is employed to show that the original nonlinear eigenvalue problem reduces to a linear eigenvalue problem of dimension k. No initial approximations of eigenvalues and eigenvectors are needed. The method is particularly suitable for moderately large eigenvalue problems where k is much smaller than the matrix dimension. We also give an extension of the method to the case where k is larger than the matrix dimension. The quadrature errors caused by the trapezoid sum are discussed for the case of analytic closed contours. Using well known techniques it is shown that the error decays exponentially with an exponent given by the product of the number of quadrature points and the minimal distance of the eigenvalues to the contour.     

A block Arnoldi-type contour integral spectral projection method for solving generalized eigenvalue problems

For generalized eigenvalue problems, we consider computing all eigenvalues located in a certain region and their corresponding eigenvectors. Recently, contour integral spectral projection methods have been proposed for solving such problems. In this study, from the analysis of the relationship between the contour integral spectral projection and the Krylov subspace, we conclude that the Rayleigh–Ritz-type of the contour integral spectral projection method is mathematically equivalent to the Arnoldi method with the projected vectors obtained from the contour integration. By this Arnoldi-based interpretation, we then propose a block Arnoldi-type contour integral spectral projection method for solving the eigenvalue problem.     

Boundary element approximation for Maxwell's eigenvalue problem

We introduce a new method for computing eigenvalues of the Maxwell operator with boundary finite elements. On bounded domains with piecewise constant material coefficients, the Maxwell solution for fixed wave number can be represented by boundary integrals, which allows to reduce the eigenvalue problem to a nonlinear problem for determining the wave number along with boundary and interface traces. A Galerkin discretization yields a smooth nonlinear matrix eigenvalue problem that is solved by Newton's method or, alternatively, the contour integral method. Several numerical results including an application to the band structure computation of a photonic crystal illustrate the efficiency of this approach. Copyright © 2013 John Wiley & Sons, Ltd.     

A combination difference scheme for the eigenvalue problem of the Laplace operator

The paper constructs and analyzes a combination difference scheme for numerical determination of the eigenvalues of the Laplace operator. The proposed scheme uses the two-sided (from above and from below) properties of variational-difference and ordinary difference schemes for the eigenvalue problem of the Laplace operator in convex domains. The half-sum of the two schemes in convex domains gives an O(h⁴) approximation to the exact eigenvalue. A summation representation formula is constructed as an implementation of the ten-point difference scheme.Kiev University. Nukus University. Turkmen Teachers College. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 75, pp. 55–60, 1991.     

A multilevel correction method for Stokes eigenvalue problems and its applications

In this paper, a new multilevel correction scheme is proposed to solve Stokes eigenvalue problems by the finite element method. This new scheme contains a series of correction steps, and the accuracy of eigenpair approximation can be improved after each step. In each correction step, we only need to solve a Stokes problem on the corresponding fine finite element space and a Stokes eigenvalue problem on the coarsest finite element space. This correction scheme can improve the efficiency of solving Stokes eigenvalue problems by the finite element method. As applications of this multilevel correction method, a multigrid method and an adaptive finite element technique are introduced for Stokes eigenvalue problems. Some numerical results are given to validate our schemes. Copyright © 2013 John Wiley & Sons, Ltd.     

A new type of full multigrid method for the elasticity eigenvalue problem

This paper introduces a new type of full multigrid method for the elasticity eigenvalue problem. The main idea is to avoid solving large scale elasticity eigenvalue problem directly by transforming the solution of the elasticity eigenvalue problem into a series of solutions of linear boundary value problems defined on a multilevel finite element space sequence and some small scale elasticity eigenvalue problems defined on the coarsest correction space. The involved linear boundary value problems will be solved by performing some multigrid iterations. Besides, some efficient techniques such as parallel computing and adaptive mesh refinement can also be absorbed in our algorithm. The efficiency and validity of the multigrid methods are verified by several numerical experiments.     

Finding Eigenvalues of Holomorphic Fredholm Operator Pencils Using Boundary Value Problems and Contour Integrals

Investigating the stability of nonlinear waves often leads to linear or nonlinear eigenvalue problems for differential operators on unbounded domains. In this paper we propose to detect and approximate the point spectra of such operators (and the associated eigenfunctions) via contour integrals of solutions to resolvent equations. The approach is based on Keldysh’ theorem and extends a recent method for matrices depending analytically on the eigenvalue parameter. We show that errors are well-controlled under very general assumptions when the resolvent equations are solved via boundary value problems on finite domains. Two applications are presented: an analytical study of Schrödinger operators on the real line as well as on bounded intervals and a numerical study of the FitzHugh–Nagumo system. We also relate the contour method to the well-known Evans function and show that our approach provides an alternative to evaluating and computing its zeros.     

A block Newton method for nonlinear eigenvalue problems

We consider matrix eigenvalue problems that are nonlinear in the eigenvalue parameter. One of the most fundamental differences from the linear case is that distinct eigenvalues may have linearly dependent eigenvectors or even share the same eigenvector. This has been a severe hindrance in the development of general numerical schemes for computing several eigenvalues of a nonlinear eigenvalue problem, either simultaneously or subsequently. The purpose of this work is to show that the concept of invariant pairs offers a way of representing eigenvalues and eigenvectors that is insensitive to this phenomenon. To demonstrate the use of this concept in the development of numerical methods, we have developed a novel block Newton method for computing such invariant pairs. Algorithmic aspects of this method are considered and a few academic examples demonstrate its viability.     

A boundary element method for the Dirichlet eigenvalue problem of the Laplace operator

The solution of eigenvalue problems for partial differential operators by using boundary integral equation methods usually involves some Newton potentials which may be resolved by using a multiple reciprocity approach. Here we propose an alternative approach which is in some sense equivalent to the above. Instead of a linear eigenvalue problem for the partial differential operator we consider a nonlinear eigenvalue problem for an associated boundary integral operator. This nonlinear eigenvalue problem can be solved by using some appropriate iterative scheme, here we will consider a Newton scheme. We will discuss the convergence and the boundary element discretization of this algorithm, and give some numerical results.     

A linear eigenvalue algorithm for the nonlinear eigenvalue problem

The Arnoldi method for standard eigenvalue problems possesses several attractive properties making it robust, reliable and efficient for many problems. The first result of this paper is a characterization of the solutions to an arbitrary (analytic) nonlinear eigenvalue problem (NEP) as the reciprocal eigenvalues of an infinite dimensional operator denoted ${\mathcal {B}}$ . We consider the Arnoldi method for the operator ${\mathcal {B}}$ and show that with a particular choice of starting function and a particular choice of scalar product, the structure of the operator can be exploited in a very effective way. The structure of the operator is such that when the Arnoldi method is started with a constant function, the iterates will be polynomials. For a large class of NEPs, we show that we can carry out the infinite dimensional Arnoldi algorithm for the operator ${\mathcal {B}}$ in arithmetic based on standard linear algebra operations on vectors and matrices of finite size. This is achieved by representing the polynomials by vector coefficients. The resulting algorithm is by construction such that it is completely equivalent to the standard Arnoldi method and also inherits many of its attractive properties, which are illustrated with examples.     

A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method

The Sakurai-Sugiura projection method, which solves generalized eigenvalue problems to find certain eigenvalues in a given domain, was reformulated by using the resolvent theory. A new interpretation based on filter diagonalization was given, and the corresponding filter function was derived explicitly. A block version of the method was also proposed, which enabled not only resolution of degenerated eigenvalues, but also an improvement in numerical accuracy. Three numerical examples were provided to illustrate the method.     

Perturbed preconditioned inverse iteration for operator eigenvalue problems with applications to adaptive wavelet discretization

In this paper we discuss an abstract iteration scheme for the calculation of the smallest eigenvalue of an elliptic operator eigenvalue problem. A short and geometric proof based on the preconditioned inverse iteration (PINVIT) for matrices (Knyazev and Neymeyr, SIAM J Matrix Anal 31:621–628, 2009) is extended to the case of operators. We show that convergence is retained up to any tolerance if one only uses approximate applications of operators which leads to the perturbed preconditioned inverse iteration (PPINVIT). We then analyze the Besov regularity of the eigenfunctions of the Poisson eigenvalue problem on a polygonal domain, showing the advantage of an adaptive solver to uniform refinement when using a stable wavelet base. A numerical example for PPINVIT, applied to the model problem on the L-shaped domain, is shown to reproduce the predicted behaviour.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.     

Series solution of nonlinear eigenvalue problems by means of the homotopy analysis method

A general analytic approach for nonlinear eigenvalue problems is described. Two physical problems are used as examples to show the validity of this approach for eigenvalue problems with either periodic or non-periodic eigenfunctions. Unlike perturbation techniques, this approach is independent of any small physical parameters. Besides, different from all other analytic techniques, it provides a simple way to ensure the convergence of series of eigenvalues and eigenfunctions so that one can always get accurate enough approximations. Finally, unlike all other analytic techniques, this approach provides great freedom to choose an auxiliary linear operator so as to approximate the eigenfunction more effectively by means of better base functions. This approach provides us a new way to investigate eigenvalue problems with strong nonlinearity.     

Structured eigenvalue problems for rational gauss quadrature

The connection between Gauss quadrature rules and the algebraic eigenvalue problem for a Jacobi matrix was first exploited in the now classical paper by Golub and Welsch (Math. Comput. 23(106), 221–230, 1969). From then on many computational problems arising in the construction of (polynomial) Gauss quadrature formulas have been reduced to solving direct and inverse eigenvalue problems for symmetric tridiagonals. Over the last few years (rational) generalizations of the classical Gauss quadrature formulas have been studied, i.e., formulas integrating exactly in spaces of rational functions. This paper wants to illustrate that stable and efficient procedures based on structured numerical linear algebra techniques can also be devised for the solution of the eigenvalue problems arising in the field of rational Gauss quadrature.     

Numerical methods for analytic continuation and mesh generation

The problem of computing the analytic continuation of a holomorphic function known on a circle is considered. Several fast numerical schemes based on solving an initial-value problem for the Cauchy-Riemann equations are analyzed. To avoid instability problems, some of the schemes consist of two parts: one for integrating the Cauchy-Riemann equations, and one for smoothing the function values so obtained. We show that with appropriate integration and smoothing methods, the stability and accuracy of such schemes is sufficient for many applications. The schemes are well-suited for generating level curves and stream lines of conformal mappings. Computed examples are presented. We also indicate how the schemes can be used to generate near-orthogonal boundary-fitted grids with given mesh sizes along the boundary.     

Quadrature formulas for periodic functions and their application to the boundary element method

Two-dimensional and axisymmetric boundary value problems for the Laplace equation in a domain bounded by a closed smooth contour are considered. The problems are reduced to integral equations with a periodic singular kernel, where the period is equal to the length of the contour. Taking into account the periodicity property, high-order accurate quadrature formulas are applied to the integral operator. As a result, the integral equations are reduced to a system of linear algebraic equations. This substantially simplifies the numerical schemes for solving boundary value problems and considerably improves the accuracy of approximation of the integral operator. The boundaries are specified by analytic functions, and the remainder of the quadrature formulas decreases faster than any power of the integration step size. The examples include the two-dimensional potential inviscid circulation flow past a single blade or a grid of blades; the axisymmetric flow past a torus; and free-surface flow problems, such as wave breakdown, standing waves, and the development of Rayleigh-Taylor instability.     

Solving eigenvalue problems by implicit decomposition

This paper presents three innovative methods for solving eigenvalue problems for differential equations based upon the techniques of implicit decomposition developed by Luo and Friedman. An eigenvalue problem can be written as an approximate algebraic system of the form [K]{X} + λ[M]{X} = 0 by employing finite elements. These methods provide robust techniques to compute the real eigenpair, λ and {X}, where [K] and [M] can be asymmetric, indefinite, and even singular.     

Guaranteed lower eigenvalue bounds for the biharmonic equation

The computation of lower eigenvalue bounds for the biharmonic operator in the buckling of plates is vital for the safety assessment in structural mechanics and highly on demand for the separation of eigenvalues for the plate’s vibrations. This paper shows that the eigenvalue provided by the nonconforming Morley finite element analysis, which is perhaps a lower eigenvalue bound for the biharmonic eigenvalue in the asymptotic sense, is not always a lower bound. A fully-explicit error analysis of the Morley interpolation operator with all the multiplicative constants enables a computable guaranteed lower eigenvalue bound. This paper provides numerical computations of those lower eigenvalue bounds and studies applications for the vibration and the stability of a biharmonic plate with different lower-order terms.     

Inverse spectral problems for Dirac operator with eigenvalue dependent boundary and jump conditions

We deal with the Dirac operator with eigenvalue dependent boundary and jump conditions. Properties of eigenvalues, eigenfunctions and the resolvent operator are studied. Moreover, uniqueness theorems of the inverse problem according to the Weyl functions and the spectral data (the sets of eigenvalues and norming constants; two different eigenvalues sets) are proved.