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.     

Enhanced algebraic substructuring for symmetric generalized eigenvalue problems

This article proposes a new substructuring algorithm to approximate the algebraically smallest eigenvalues and corresponding eigenvectors of a symmetric positive-definite matrix pencil $(A,M)$. The proposed approach partitions the graph associated with $(A,M)$ into a number of algebraic substructures and builds a Rayleigh–Ritz projection subspace by combining spectral information associated with the interior and interface variables of the algebraic domain. The subspace associated with interior variables is built by computing substructural eigenvectors and truncated Neumann series expansions of resolvent matrices. The subspace associated with interface variables is built by computing eigenvectors and associated leading derivatives of linearized spectral Schur complements. The proposed algorithm can take advantage of multilevel partitionings when the size of the pencil. Experiments performed on problems stemming from discretizations of model problems showcase the efficiency of the proposed algorithm and verify that adding eigenvector derivatives can enhance the overall accuracy of the approximate eigenpairs, especially those associated with eigenvalues located near the origin.     

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.     

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.     

The FEAST algorithm for large eigenvalue problems

We consider the eigensolver named FEAST that was introduced by Polizzi in 2009 [1]. This solver, tailored to the (partial) solution of large sparse (generalized) eigenproblems offers good potential for parallelism and showed good robustness in our experiments. We briefly introduce the algorithm, point out some problems and give two examples. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Calculating the minimal/maximal eigenvalue of symmetric parameterized matrices using projection

In applications of linear algebra including nuclear physics and structural dynamics, there is a need to deal with uncertainty in the matrices. We focus on matrices that depend on a set of parameters ω and we are interested in the minimal eigenvalue of a matrix pencil ( A , B ) with A , B symmetric and B positive definite. If ω can be interpreted as the realization of random variables, one may be interested in statistical moments of the minimal eigenvalue. In order to obtain statistical moments, we need a fast evaluation of the eigenvalue as a function of ω . Because this is costly for large matrices, we are looking for a small parameterized eigenvalue problem whose minimal eigenvalue makes a small error with the minimal eigenvalue of the large eigenvalue problem. The advantage, in comparison with a global polynomial approximation (on which, e.g., the polynomial chaos approximation relies), is that we do not suffer from the possible nonsmoothness of the minimal eigenvalue. The small‐scale eigenvalue problem is obtained by projection of the large‐scale problem. Our main contribution is that, for constructing the subspace, we use multiple eigenvectors and derivatives of eigenvectors. We provide theoretical results and document numerical experiments regarding the beneficial effect of adding multiple eigenvectors and derivatives.     

A NEW GENERALIZED GRADIENT PROJECTION TYPEALGORITHM FOR LINEARLY CONSTRAINED PROBLEMS

In this paper, we provide a new generalized gradient projection algorithm for nonlinear programming problems with linear constraints. This algorithm has simple structure and is very practical and stable. Under the weaker assumptions, we have proved the global convergence of our algorithm.     

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 projection based multiscale optimization method for eigenvalue problems

We present a projection based multiscale optimization method for eigenvalue problems. In multiscale optimization, optimization steps using approximations at a coarse scale alternate with corrections by occasional calculations at a finer scale. We study an example in the context of electronic structure optimization. Theoretical analysis and numerical experiments provide estimates of the expected efficiency and guidelines for parameter selection.     

Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion

We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem Ax = λBx, with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations Ax,Bx and B^?1x and avoid forming square roots of B (or operations of the form, B^1/2x or B^?1/2x). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B^?1A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen–Loève expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd.     

The projection Kantorovich method for eigenvalue problems

A modified projection method for eigenvalues and eigenvectors of a compact operator T on a Banach space is defined and analyzed. The method is derived from the Kantorovich regularization for second-kind equations involving the operator T. It is shown that when T is a positive self-adjoint operator on a Hilbert space and the projections are orthogonal, the modified method always gives eigenvalue approximations which are at least as accurate as those obtained from the projection method. For self-adjoint operators, the required computation is essentially the same for both methods. Numerical computations for two integral operators are presented. One has T positive self-adjoint, while in the other T is not self-adjoint. In both cases the eigenvalue approximations from the modified method are more accurate than those from the projection method.     

A note on the Hoffman-Wielandt theorem for generalized eigenvalue problems

Let {A, B} and {C, D} be diagonalizable pairs of order n, i.e., there exist invertible matrices P, Q and X, Ysuchthat A = P∧Q, B = PΩQ, C =XГY, D= X△Y, where
∧ = diag（α1, α2, …, αn）, Ω= diag（βl, β2, …βn）,
Г=diag（γ1,γ2,…,γn）, △=diag（δl,δ2,…,δn）.
Let ρ（（α,β）, （γ,δ））=｜αδ-βγ｜/√｜α｜^2＋｜β｜^2√｜γ｜^2＋｜δ｜^2.In this paper, it will be proved that there is a permutation τ of {1,2,... ,n} such that
n∑i=1[ρ（（αi,βi）,（γτ（i）,δτ（i）））]^2≤n[1-1/κ^2（Y）κ^2（Q）（1-d2F（Z,W）/n）],
where κ（Y） = ｜｜Y｜｜2｜｜Y^-1｜｜2,Z= （A,B）,W= （C, D） and dF（Z,W） = 1/√2｜｜Pz＊ -Pw＊｜｜F.     

On the need for special purpose algorithms for minimax eigenvalue problems

It has been recently reported that minimax eigenvalue problems can be formulated as nonlinear optimization problems involving smooth objective and constraint functions. This result seems very appealing since minimax eigenvalue problems are known to be typically nondifferentiable. In this paper, we show, however, that general purpose nonlinear optimization algorithms usually fail to find a solution to these smooth problems even in the simple case of minimization of the maximum eigenvalue of an affine family of symmetric matrices, a convex problem for which efficient algorithms are available.This work was supported in part by NSF Engineering Research Centers Program No. NSFD-CDR-88-03012 and NSF Grant DMC-84-20740. The author wishes to thank Drs. M. K. H. Fan and A. L. Tits for their many useful suggestions.     

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.     

Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this article an iterative algorithm is studied in connection with an implicit complementarity problem. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by isotone projection cones, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

On minimax eigenvalue problems via constrained optimization

In this paper, we consider the problem of minimizing the maximum eigenvalues of a matrix. The aim is to show that this optimization problem can be transformed into a standard nonlinearly constrained optimization problem, and hence is solvable by existing software packages. For illustration, two examples are solved by using the proposed method.     

A new superconvergent collocation method for eigenvalue problems

Here we propose a new method based on projections for the approximate solution of eigenvalue problems. For an integral operator with a smooth kernel, using an interpolatory projection at Gauss points onto the space of (discontinuous) piecewise polynomials of degree , we show that the proposed method exhibits an error of the order of for eigenvalue approximation and of the order of for spectral subspace approximation. In the case of a simple eigenvalue, we show that by using an iteration technique, an eigenvector approximation of the order can be obtained. This improves upon the order for eigenvalue approximation in the collocation/iterated collocation method and the orders and for spectral subspace approximation in the collocation method and the iterated collocation method, respectively. We illustrate this improvement in the order of convergence by numerical examples.

     

Linear convergence of gradient projection algorithm for split equality problems

ABSTRACT

In this paper, we consider the varying stepsize gradient projection algorithm (GPA) for solving the split equality problem (SEP) in Hilbert spaces, and study its linear convergence. In particular, we introduce a notion of bounded linear regularity property for the SEP, and use it to establish the linear convergence property for the varying stepsize GPA. We provide some mild sufficient conditions to ensure the bounded linear regularity property, and then conclude the linear convergence rate of the varying stepsize GPA. To the best of our knowledge, this is the first work to study the linear convergence for the SEP.     

A degenerate kernel method for eigenvalue problems of compact integral operators

We consider the approximation of eigenfunctions of a compact integral operator with a smooth kernel by a degenerate kernel method. By interpolating the kernel of the integral operator in both the variables, we prove that the error bounds for eigenvalues and for the distance between the spectral subspaces are of the orders h ^2r and h ^r respectively. By iterating the eigenfunctions we show that the error bounds for eigenfunctions are of the orders h ^2r . We give the numerical results.      

A regularized projection method for complementarity problems with non-Lipschitzian functions

We consider complementarity problems involving functions which are not Lipschitz continuous at the origin. Such problems arise from the numerical solution for differential equations with non-Lipschitzian continuity, e.g. reaction and diffusion problems. We propose a regularized projection method to find an approximate solution with an estimation of the error for the non-Lipschitzian complementarity problems. We prove that the projection method globally and linearly converges to a solution of a regularized problem with any regularization parameter. Moreover, we give error bounds for a computed solution of the non-Lipschitzian problem. Numerical examples are presented to demonstrate the efficiency of the method and error bounds.