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.     

Minimization principles and computation for the generalized linear response eigenvalue problem

The minimization principle and Cauchy-like interlacing inequalities for the generalized linear response eigenvalue problem are presented. Based on these theoretical results, the best approximations through structure-preserving subspace projection and a locally optimal block conjugate gradient-like algorithm for simultaneously computing the first few smallest eigenvalues with the positive sign are proposed. Numerical results are presented to illustrate essential convergence behaviors of the proposed algorithm.     

平板几何迁移算子的特征值问题

研究L^p(1相似文献   

A sequential subspace projection method for extreme Z‐eigenvalues of supersymmetric tensors

Z‐eigenvalues of tensors, especially extreme ones, are quite useful and are related to many problems, such as automatic control, quantum physics, and independent component analysis. For supersymmetric tensors, calculating the smallest/largest Z‐eigenvalue is equivalent to solving a global minimization/maximization problem of a homogenous polynomial over the unit sphere. In this paper, we utilize the sequential subspace projection method (SSPM) to find extreme Z‐eigenvalues and the corresponding Z‐eigenvectors. The main idea of SSPM is to form a 2‐dimensional subspace at the current point and then solve the original optimization problem in the subspace. SSPM benefits from the fact that the 2‐dimensional subproblem can be solved by a direct method. Global convergence and linear convergence are established for supersymmetric tensors under certain assumptions. Preliminary numerical results over several testing problems show that SSPM is very promising. Besides, the globalization strategy of random phase can be easily incorporated into SSPM, which promotes the ability to find extreme Z‐eigenvalues. Copyright © 2014 John Wiley & Sons, Ltd.     

Computing the generalized eigenvalues of weakly symmetric tensors

Tensor is a hot topic in the past decade and eigenvalue problems of higher order tensors become more and more important in the numerical multilinear algebra. Several methods for finding the Z-eigenvalues and generalized eigenvalues of symmetric tensors have been given. However, the convergence of these methods when the tensor is not symmetric but weakly symmetric is not assured. In this paper, we give two convergent gradient projection methods for computing some generalized eigenvalues of weakly symmetric tensors. The gradient projection method with Armijo step-size rule (AGP) can be viewed as a modification of the GEAP method. The spectral gradient projection method which is born from the combination of the BB method with the gradient projection method is superior to the GEAP, AG and AGP methods. We also make comparisons among the four methods. Some competitive numerical results are reported at the end of this paper.     

Convergence estimates of nonrestarted and restarted block‐Lanczos methods

The block‐Lanczos method serves to compute a moderate number of eigenvalues and the corresponding invariant subspace of a symmetric matrix. In this paper, the convergence behavior of nonrestarted and restarted versions of the block‐Lanczos method is analyzed. For the nonrestarted version, we improve an estimate by Saad by means of a change of the auxiliary vector so that the new estimate is much more accurate in the case of clustered or multiple eigenvalues. For the restarted version, an estimate by Knyazev is generalized by extending our previous results on block steepest descent iterations and single‐vector restarted Krylov subspace iterations. The new estimates can also be reformulated and applied to invert‐block‐Lanczos methods for solving generalized matrix eigenvalue problems.     

Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem

After reviewing the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, we discuss several extraction processes for subspace methods for the polynomial eigenvalue problem. We generalize the harmonic and refined Rayleigh–Ritz approaches which lead to new approaches to extract promising approximate eigenpairs from a search space. We give theoretical as well as numerical results of the methods. In addition, we study the convergence of the Jacobi–Davidson method for polynomial eigenvalue problems with exact and inexact linear solves and discuss several algorithmic details. Copyright © 2008 John Wiley & Sons, Ltd.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

A FEAST algorithm with oblique projection for generalized eigenvalue problems

The contour integral‐based eigensolvers are the recent efforts for computing the eigenvalues inside a given region in the complex plane. The best‐known members are the Sakurai–Sugiura method, its stable version CIRR, and the FEAST algorithm. An attractive computational advantage of these methods is that they are easily parallelizable. The FEAST algorithm was developed for the generalized Hermitian eigenvalue problems. It is stable and accurate. However, it may fail when applied to non‐Hermitian problems. Recently, a dual subspace FEAST algorithm was proposed to extend the FEAST algorithm to non‐Hermitian problems. In this paper, we instead use the oblique projection technique to extend FEAST to the non‐Hermitian problems. Our approach can be summarized as follows: (a) construct a particular contour integral to form a search subspace containing the desired eigenspace and (b) use the oblique projection technique to extract desired eigenpairs with appropriately chosen test subspace. The related mathematical framework is established. Comparing to the dual subspace FEAST algorithm, we can save the computational cost roughly by a half if only the eigenvalues or the eigenvalues together with their right eigenvectors are needed. We also address some implementation issues such as how to choose a suitable starting matrix and design‐efficient stopping criteria. Numerical experiments are provided to illustrate that our method is stable and efficient.     

Approximation of sign-indefinite spectral problems

A variational sign-indefinite eigenvalue problem in an infinite-dimensional Hilbert space is approximated by a problem in a finite-dimensional subspace. We analyze the convergence and accuracy of approximate eigenvalues and eigenelements. The general results are illustrated by a sample scheme of the finite-element method with numerical integration for a one-dimensional sign-indefinite second-order differential eigenvalue problem.     

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 ).     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

Newton's Method for a Generalized Inverse Eigenvalue Problem

A kind of generalized inverse eigenvalue problem is proposed which includes the additive, multiplicative and classical inverse eigenvalue problems as special cases. Newton's method is applied, and a local convergence analysis is given for both the distinct and the multiple eigenvalue cases. When the multiple eigenvalues are present we show how to state the problem so that it is not over-determined, and discuss a Newton-method for the modified problem. We also prove that the modified method retains quadratic convergence, and present some numerical experiments to illustrate our results. © 1997 by John Wiley & Sons, Ltd.     

On the convergence of Ritz pairs and refined Ritz vectors for quadratic eigenvalue problems

For a given subspace, the Rayleigh-Ritz method projects the large quadratic eigenvalue problem (QEP) onto it and produces a small sized dense QEP. Similar to the Rayleigh-Ritz method for the linear eigenvalue problem, the Rayleigh-Ritz method defines the Ritz values and the Ritz vectors of the QEP with respect to the projection subspace. We analyze the convergence of the method when the angle between the subspace and the desired eigenvector converges to zero. We prove that there is a Ritz value that converges to the desired eigenvalue unconditionally but the Ritz vector converges conditionally and may fail to converge. To remedy the drawback of possible non-convergence of the Ritz vector, we propose a refined Ritz vector that is mathematically different from the Ritz vector and is proved to converge unconditionally. We construct examples to illustrate our theory.     

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.     

Linear system solution by null‐space approximation and projection (SNAP)

Solutions of large sparse linear systems of equations are usually obtained iteratively by constructing a smaller dimensional subspace such as a Krylov subspace. The convergence of these methods is sometimes hampered by the presence of small eigenvalues, in which case, some form of deflation can help improve convergence. The method presented in this paper enables the solution to be approximated by focusing the attention directly on the ‘small’ eigenspace (‘singular vector’ space). It is based on embedding the solution of the linear system within the eigenvalue problem (singular value problem) in order to facilitate the direct use of methods such as implicitly restarted Arnoldi or Jacobi–Davidson for the linear system solution. The proposed method, called ‘solution by null‐space approximation and projection’ (SNAP), differs from other similar approaches in that it converts the non‐homogeneous system into a homogeneous one by constructing an annihilator of the right‐hand side. The solution then lies in the null space of the resulting matrix. We examine the construction of a sequence of approximate null spaces using a Jacobi–Davidson style singular value decomposition method, called restarted SNAP‐JD, from which an approximate solution can be obtained. Relevant theory is discussed and the method is illustrated by numerical examples where SNAP is compared with both GMRES and GMRES‐IR. Copyright © 2006 John Wiley & Sons, Ltd.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

Two-sided bounds of eigenvalues of second-and fourth-order elliptic operators

This article presents an idea in the finite element methods (FEMs) for obtaining two-sided bounds of exact eigenvalues. This approach is based on the combination of nonconforming methods giving lower bounds of the eigenvalues and a postprocessing technique using conforming finite elements. Our results hold for the second and fourth-order problems defined on two-dimensional domains. First, we list analytic and experimental results concerning triangular and rectangular nonconforming elements which give at least asymptotically lower bounds of the exact eigenvalues. We present some new numerical experiments for the plate bending problem on a rectangular domain. The main result is that if we know an estimate from below by nonconforming FEM, then by using a postprocessing procedure we can obtain two-sided bounds of the first (essential) eigenvalue. For the other eigenvalues λ_l, l = 2, 3, …, we prove and give conditions when this method is applicable. Finally, the numerical results presented and discussed in the paper illustrate the efficiency of our method.     

Deflated block Krylov subspace methods for large scale eigenvalue problems

We discuss a class of deflated block Krylov subspace methods for solving large scale matrix eigenvalue problems. The efficiency of an Arnoldi-type method is examined in computing partial or closely clustered eigenvalues of large matrices. As an improvement, we also propose a refined variant of the Arnoldi-type method. Comparisons show that the refined variant can further improve the Arnoldi-type method and both methods exhibit very regular convergence behavior.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997