Palindromic quadratization and structure-preserving algorithm for palindromic matrix polynomials of even degree

In this paper, we propose a palindromic quadratization approach, transforming a palindromic matrix polynomial of even degree to a palindromic quadratic pencil. Based on the (S+ S^-1){(\mathcal{S}+ \mathcal{S}^{-1})} -transform and Patel’s algorithm, the structure-preserving algorithm can then be applied to solve the corresponding palindromic quadratic eigenvalue problem. Numerical experiments show that the relative residuals for eigenpairs of palindromic polynomial eigenvalue problems computed by palindromic quadratized eigenvalue problems are better than those via palindromic linearized eigenvalue problems or polyeig{{\texttt {polyeig}}} in MATLAB.     

A rank‐exploiting infinite Arnoldi algorithm for nonlinear eigenvalue problems

We consider the nonlinear eigenvalue problem M(λ)x = 0, where M(λ) is a large parameter‐dependent matrix. In several applications, M(λ) has a structure where the higher‐order terms of its Taylor expansion have a particular low‐rank structure. We propose a new Arnoldi‐based algorithm that can exploit this structure. More precisely, the proposed algorithm is equivalent to Arnoldi's method applied to an operator whose reciprocal eigenvalues are solutions to the nonlinear eigenvalue problem. The iterates in the algorithm are functions represented in a particular structured vector‐valued polynomial basis similar to the construction in the infinite Arnoldi method [Jarlebring, Michiels, and Meerbergen, Numer. Math., 122 (2012), pp. 169–195]. In this paper, the low‐rank structure is exploited by applying an additional operator and by using a more compact representation of the functions. This reduces the computational cost associated with orthogonalization, as well as the required memory resources. The structure exploitation also provides a natural way in carrying out implicit restarting and locking without the need to impose structure in every restart. The efficiency and properties of the algorithm are illustrated with two large‐scale problems. Copyright © 2016 John Wiley & Sons, Ltd.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

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

一类特征值反问题(IEP)的基于矩阵方程的Ulm型算法

应用求解算子方程的Ulm方法构造了求解一类矩阵特征值反问题（IEP）的新算法.所给算法避免了文献[Aishima K.,A quadratically convergent algorithm based on matrix equations for inverse eigenvalue problems,Linear Algebra and its Applications,2018,542：310-33]中算法在每次迭代中要求解一个线性方程组的不足,证明了在给定谱数据互不相同的条件下所给算法具有根收敛意义下的二次收敛性.数值实验表明本文所给算法在矩阵阶数较大时计算效果优于上文所给算法.     

Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

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.     

Power iteration and inverse power iteration for eigenvalue complementarity problem

In this paper, an inverse complementarity power iteration method (ICPIM) for solving eigenvalue complementarity problems (EiCPs) is proposed. Previously, the complementarity power iteration method (CPIM) for solving EiCPs was designed based on the projection onto the convex cone K. In the new algorithm, a strongly monotone linear complementarity problem over the convex cone K is needed to be solved at each iteration. It is shown that, for the symmetric EiCPs, the CPIM can be interpreted as the well‐known conditional gradient method, which requires only linear optimization steps over a well‐suited domain. Moreover, the ICPIM is closely related to the successive quadratic programming (SQP) via renormalization of iterates. The global convergence of these two algorithms is established by defining two nonnegative merit functions with zero global minimum on the solution set of the symmetric EiCP. Finally, some numerical simulations are included to evaluate the efficiency of the proposed algorithms.     

Solution of boundary and eigenvalue problems for second‐order elliptic operators in the plane using pseudoanalytic formal powers

We propose a method for solving boundary value and eigenvalue problems for the elliptic operator D = div p grad + qin the plane using pseudoanalytic function theory and in particular pseudoanalytic formal powers. Under certain conditions on the coefficients p and q with the aid of pseudoanalytic function theory a complete system of null solutions of the operator can be constructed following a simple algorithm consisting in recursive integration. This system of solutions is used for solving boundary value and spectral problems for the operator D in bounded simply connected domains. We study theoretical and numerical aspects of the method. Copyright © 2010 John Wiley & Sons, Ltd.     

特征值问题的自适应反迭代有限元算法

1引言设Ω∈R~2为Lipschitz单连通的有界闭区域,X为定义在Ω的Sobolev空间,a(·,·)和b(·,·)为X×X→C的有界双线性或半双线性泛函,考虑变分特征值问题:求(λ,u≠0)∈C×X使得a(u,v)=λb(u,u),(?)u∈X,其中a(·,·)满足X上的"V-强制性"条件或者连续的inf-sup条件,设M_h为Q区域上的正则三角形剖分,X_h∈X为定义在M_h有限元子空间,上述变分问题对应的有限元离散问题为:求(λ_h,u_h)∈R×X,u_h≠0使得     

Numerical solution of eigenvalue problems for Hamiltonian systems

This paper discusses the numerical solution of eigenvalue problems for Hamiltonian systems of ordinary differential equations. Two new codes are presented which incorporate the algorithms described here; to the best of the author’s knowledge, these are the first codes capable of solving numerically such general eigenvalue problems. One of these implements a new new method of solving a differential equation whose solution is a unitary matrix. Both codes are fully documented and are written inPfort-verifiedFortran 77, and will be available in netlib/aicm/sl11f and netlib/aicm/sl12f.     

Extremal Eigenvalues of the Sturm-Liouville Problems with Discontinuous Coefficients

In this paper, an extremal eigenvalue problem to the Sturm-Liouville equations with discontinuous coefficients and volume constraint is investigated. Liouville transformation is applied to change the problem into an equivalent minimization problem. Finite element method is proposed and the convergence for the finite element solution is established. A monotonic decreasing algorithm is presented to solve the extremal eigenvalue problem. A global convergence for the algorithm in the continuous case is proved. A few numerical results are given to depict the efficiency of the method.     

Approximation and eigenvalue extrapolation of Stokes eigenvalue problem by nonconforming finite element methods

In this paper we analyze the stream function-vorticity-pressure method for the Stokes eigenvalue problem. Further, we obtain full order convergence rate of the eigenvalue approximations for the Stokes eigenvalue problem based on asymptotic error expansions for two nonconforming finite elements, Q ₁^rot and EQ ₁^rot. Using the technique of eigenvalue error expansion, the technique of integral identities and the extrapolation method, we can improve the accuracy of the eigenvalue approximations. This project is supported in part by the National Natural Science Foundation of China (10471103) and is subsidized by the National Basic Research Program of China under the grant 2005CB321701.     

Convergence of Inverse Power Method for First Eigenvalue of p-Laplace Operator

In this article, convergence of an iterative scheme to approximate the first eigenfunction and related eigenvalue for p-Laplace operator is shown. Moreover, numerical examples are presented that show the e?ciency and accuracy of the algorithm.     

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.     

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

An implicit method for linear ill‐posed problems with perturbed operators

An implicit iterative method is applied to solving linear ill‐posed problems with perturbed operators. It is proved that the optimal convergence rate can be obtained after choosing suitable number of iterations. A generalized Morozov's discrepancy principle is proposed for the problems, and then the optimal convergence rate can also be obtained by an a posteriori strategy. The convergence results show that the algorithm is a robust regularization method. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

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.