Backward error of polynomial eigenvalue problems solved by linearization

It is commonplace in many application domains to utilize polynomial eigenvalue problems to model the behaviour of physical systems. Many techniques exist to compute solutions of these polynomial eigenvalue problems. One of the most frequently used techniques is linearization, in which the polynomial eigenvalue problem is turned into an equivalent linear eigenvalue problem with the same eigenvalues, and with easily recoverable eigenvectors. The eigenvalues and eigenvectors of the linearization are usually computed using a backward stable solver such as the QZ algorithm. Such backward stable algorithms ensure that the computed eigenvalues and eigenvectors of the linearization are exactly those of a nearby linear pencil, where the perturbations are bounded in terms of the machine precision and the norms of the matrices defining the linearization. Although we have solved a nearby linear eigenvalue problem, we are not certain that our computed solution is in fact the exact solution of a nearby polynomial eigenvalue problem. Here, we perform a backward error analysis for the solution of a specific linearization for polynomials expressed in the monomial basis. We use a suitable one-sided factorization of the linearization that allows us to map generic perturbations of the linearization onto structured perturbations of the polynomial coefficients. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A feasible method for optimization with orthogonality constraints

Minimization with orthogonality constraints (e.g., $X^\top X = I$ ) and/or spherical constraints (e.g., $\Vert x\Vert _2 = 1$ ) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we apply the Cayley transform—a Crank-Nicolson-like update scheme—to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For the quadratic assignment problem, a gap 0.842 % to the best known solution on the largest problem “tai256c” in QAPLIB can be reached in 5 min on a typical laptop.     

Solution of the partial eigenvalue problem for a regular matrix pencil

Algorithms are proposed for the solution of the partial eigenvalue problem for regular polynomial matrix pencils. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 159, pp. 33–39, 1987.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

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.     

On KKT points of Celis-Dennis-Tapia subproblem

The Celis-Dennis-Tapia(CDT) problem is a subproblem of the trust region algorithms for the constrained optimization. CDT subproblem is studied in this paper. It is shown that there exists the KKT point such that the Hessian matrix of the Lagrangian is positive semidefinite, if the multipliers at the global solution are not unique. Next the second order optimality conditions are also given, when the Hessian matrix of Lagrange at the solution has one negative eigenvalue. And furthermore, it is proved that all feasible KKT points satisfying that the corresponding Hessian matrices of Lagrange have one negative eigenvalue are the local optimal solutions of the CDT subproblem.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

Algorithms for solving matrix polynomial equations of special form

In this paper we consider a series of algorithms for calculating radicals of matrix polynomial equations. A particular aspect of this problem arise in author’s work, concerning parameter identification of linear dynamic stochastic system. Special attention is given to searching the solution of an equation in a neighbourhood of some initial approximation. The offered approaches and algorithms allow us to receive fast and quite exact solution. We give some recommendations for application of given algorithms.     

ARNOLDI TYPE ALGORITHMS FOR LARGE UNSYMMETRIC MULTIPLE EIGENVALUE PROBLEMS

1.IntroductionTheLanczosalgorithm[Zo]isaverypowerfultoolforextractingafewextremeeigenvaluesandassociatedeigenvectorsoflargesymmetricmatrices[4'5'22].Sincethe1980's,considerableattentionhasbeenpaidtogeneralizingittolargeunsymmetricproblems.Oneofitsgen...     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

Improving the solution of the symmetric eigenvalue problem and an extension

Based on a multipoint approximation of polynomial values, we accelerate the bisection and divide-and-conquer algorithms for the symmetric eigenvalue problem. We also propose a new extension of the bisection algorithm to the unsymmetric eigenvalue problem.     

Reid-Zhi符号数值混合消元方法的一个应用

将Reid和Zhi提出的符号数值混合消元方法应用于求解多项式优化问题,将多项式优化问题转化为矩阵最小特征值求解问题,并在Maple软件中实现了算法.     

Inexact restoration method for minimization problems arising in electronic structure calculations

An inexact restoration (IR) approach is presented to solve a matricial optimization problem arising in electronic structure calculations. The solution of the problem is the closed-shell density matrix and the constraints are represented by a Grassmann manifold. One of the mathematical and computational challenges in this area is to develop methods for solving the problem not using eigenvalue calculations and having the possibility of preserving sparsity of iterates and gradients. The inexact restoration approach enjoys local quadratic convergence and global convergence to stationary points and does not use spectral matrix decompositions, so that, in principle, large-scale implementations may preserve sparsity. Numerical experiments show that IR algorithms are competitive with current algorithms for solving closed-shell Hartree-Fock equations and similar mathematical problems, thus being a promising alternative for problems where eigenvalue calculations are a limiting factor.     

A NOTE ON THE BACKWARD ERRORS FOR INVERSE EIGENVALUE PROBLEMS

In this note,we consider the backward errors for more general inverse eigenvalus prob-lems by extending Sun‘‘‘‘s approach.The optimal backward errors defined for diagonal-ization matrix inverse eigenvalue problem with respect to an approximate solution,and the upper and lower bounds are derived for the optimal backward errors.The results may be useful for testing the stability of practical algorithms.     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

Zero cancellation for general rational matrix functions

The problem of cancelling a specified part of the zeros of a completely general rational matrix function by multiplication with an appropriate invertible rational matrix function is investigated from different standpoints. Firstly, the class of all factors that dislocate the zeros and feature minimal McMillan degree are derived. Further, necessary and sufficient existence conditions together with the construction of solutions are given when the factor fulfills additional assumptions like being J-unitary, or J-inner, either with respect to the imaginary axis or to the unit circle. The main technical tool are centered realizations that deliver a sufficiently general conceptual support to cope with rational matrix functions which may be polynomial, proper or improper, rank deficient, with arbitrary poles and zeros including at infinity. A particular attention is paid to the numerically-sound construction of solutions by employing at each stage unitary transformations, reliable numerical algorithms for eigenvalue assignment and efficient Lyapunov equation solvers.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

用3个向量对构造梁振动系统的刚度矩阵

针对梁的离散化模型的刚度矩阵是五对角矩阵,梁振动反问题的实质是实对称五对角矩阵的特征值反问题.该文利用向量对、Moore-Penrose广义逆给出了实对称五对角矩阵向量对反问题存在唯一解的条件,并结合矩阵分块讨论了双对称五对角矩阵向量对反问题解存在唯一的条件,进而计算了次对角线位置元素为负,其它位置元素均为正的实对称五对角矩阵特征值反问题.由于构造梁的离散模型需要的数据可由测试得到,故而其结果适合于模态分析、系统结构的分析与设计等方面应用.最后给出了数值算例,通过数值讨论说明方法的有效性.