A well known method to solve the Polynomial Eigenvalue Problem (PEP) is via linearization. That is, transforming the PEP into a generalized linear eigenvalue problem with the same spectral ...information and solving such linear problem with some of the eigenvalue algorithms available in the literature. Linearizations of matrix polynomials are usually defined using unimodular transformations. In this paper we establish a connection between the standard definition of linearization for matrix polynomials introduced by Gohberg, Lancaster and Rodman and the notion of polynomial system matrix introduced by Rosenbrock. This connection gives new techniques to show that a matrix pencil is a linearization of the corresponding matrix polynomial arising in a PEP.
In this paper, we consider the linearly structured partial polynomial inverse eigenvalue problem (LPPIEP) of constructing the matrices Ai∈Rn×n for i=0,1,2,…,(k−1) of specified linear structure such ...that the matrix polynomial P(λ)=λkIn+∑i=0k−1λiAi has the m (1⩽m⩽kn) prescribed eigenpairs as its eigenvalues and eigenvectors. Many practical applications give rise to linearly structured matrix polynomials. Typical linearly structured matrices are symmetric, skew-symmetric, tridiagonal, diagonal, pentagonal, Hankel, Toeplitz, etc. Therefore, construction of the matrix polynomial with the aforementioned structures is an important but challenging aspect of the polynomial inverse eigenvalue problem (PIEP). In this paper, a necessary and sufficient condition for the existence of solution to this problem is derived. Additionally, we characterize the class of all solutions to this problem by giving the explicit expressions of the solutions. It should be emphasized that the results presented in this paper resolve some important open problems in the area of PIEP namely, the inverse eigenvalue problems for structured matrix polynomials such as symmetric, skew-symmetric, alternating matrix polynomials as pointed out by De Terán et al. (2015). Further, we study sensitivity of solution to the perturbation of the eigendata. An attractive feature of our solution approach is that it does not impose any restriction on the number of eigendata for computing the solution of LPPIEP. Towards the end, the proposed method is validated with various numerical examples on a spring mass problem.
The contour integral-based eigensolvers have attracted much attention in recent years. In this paper, we consider solving a polynomial eigenvalue problem (PEP) by a contour integral-based eigensolver ...named the Sakurai–Sugiura method with Rayleigh–Ritz projection (SS–RR method). We derive a backward error bound of PEP solved by the SS–RR method. This bound can be used to show the accuracy of the computed approximate eigenpairs of PEP. The accuracy of the derived bounds is demonstrated by several examples.
We present algorithmic, complexity, and implementation results on the problem of sampling points from a spectrahedron, that is, the feasible region of a semidefinite program.
Our main tool is ...geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spectrahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spectrahedra that experimentally show faster mixing times than methods currently employed either in theoretical studies or in applications, including the popular family of Hit-and-Run walks. The different random walks offer a variety of advantages, thus allowing us to efficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applications of independent interest: (i) approximate the volume of a spectrahedron, and (ii) compute the expectation of functions coming from robust optimal control.
We exploit efficient linear algebra algorithms and implementations to address the aforementioned computations in very high dimension. In particular, we provide a C++ open source implementation of our methods that scales efficiently, for the first time, up to dimension 200. We illustrate its efficiency on various data sets.
We present a collection of 52 nonlinear eigenvalue problems in the form of a MATLAB toolbox. The collection contains problems from models of real-life applications as well as ones constructed ...specifically to have particular properties. A classification is given of polynomial eigenvalue problems according to their structural properties. Identifiers based on these and other properties can be used to extract particular types of problems from the collection. A brief description of each problem is given. NLEVP serves both to illustrate the tremendous variety of applications of nonlinear eigenvalue problems and to provide representative problems for testing, tuning, and benchmarking of algorithms and codes.
•The Cauchy integral from the FEAST algorithm can be modified to solve nonlinear eigenvalue problems.•FEAST for nonlinear eigenvalue problems iteratively converges to a solution using a constant ...number of matrix factorizations and a constant subspace dimension.•The Cauchy integral in nonlinear FEAST is a multi-shift generalization of residual inverse iterations.
The linear FEAST algorithm is a method for solving linear eigenvalue problems. It uses complex contour integration to calculate the eigenvectors associated with eigenvalues that are located inside some user-defined region in the complex plane. This makes it possible to parallelize the process of solving eigenvalue problems by simply dividing the complex plane into a collection of disjoint regions and calculating the eigenpairs in each region independently of the eigenpairs in the other regions. In this paper we present a generalization of the linear FEAST algorithm that can be used to solve nonlinear eigenvalue problems. Like its linear progenitor, the nonlinear FEAST algorithm can be used to solve nonlinear eigenvalue problems for the eigenpairs corresponding to eigenvalues that lie in a user-defined region in the complex plane, thereby allowing for the calculation of large numbers of eigenpairs in parallel. We describe the nonlinear FEAST algorithm, and use several physically motivated examples to demonstrate its properties.
PDF
