Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations

We derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. We also analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra. Finally, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements and show that structure preserving linearizations which minimize structured condition numbers of eigenvalues also minimize the structured backward errors of approximate eigenelements.     

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.     

A framework for analyzing nonlinear eigenproblems and parametrized linear systems

Associated with an n×n matrix polynomial of degree , are the eigenvalue problem P(λ)x=0 and the linear system problem P(ω)x=b, where in the latter case x is to be computed for many values of the parameter ω. Both problems can be solved by conversion to an equivalent problem L(λ)z=0 or L(ω)z=c that is linear in the parameter λ or ω. This linearization process has received much attention in recent years for the eigenvalue problem, but it is less well understood for the linear system problem. We develop a framework in which more general versions of both problems can be analyzed, based on one-sided factorizations connecting a general nonlinear matrix function N(λ) to a simpler function M(λ), typically a polynomial of degree 1 or 2. Our analysis relates the solutions of the original and lower degree problems and in the linear system case indicates how to choose the right-hand side c and recover the solution x from z. For the eigenvalue problem this framework includes many special cases studied in the literature, including the vector spaces of pencils L₁(P) and L₂(P) recently introduced by Mackey, Mackey, Mehl, and Mehrmann and a class of rational problems. We use the framework to investigate the conditioning and stability of the parametrized linear system P(ω)x=b and thereby study the effect of scaling, both of the original polynomial and of the pencil L. Our results identify situations in which scaling can potentially greatly improve the conditioning and stability and our numerical results show that dramatic improvements can be achieved in practice.     

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.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.     

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)     

The distance from a matrix polynomial to matrix polynomials with a prescribed multiple eigenvalue

For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).     

Local convergence analysis of iterative aggregation-disaggregation methods with polynomial correction

The paper introduces some new results on local convergence analysis of one class of iterative aggregation-disaggregation methods for computing a stationary probability distribution vector of an irreducible stochastic matrix. We focus on methods, where the basic iteration on the fine level corresponds to a multiplication by a polynomial of order one with nonnegative coefficients in the original matrix. We show that this process is locally convergent for matrices with positive diagonals or when the coefficients of the polynomial are positive. On the other hand there are examples for which the process may diverge in a local sense for higher degree polynomials even if it converges for a polynomial of a lower degree for the same matrix.     

Jordan structures of alternating matrix polynomials

Alternating matrix polynomials, that is, polynomials whose coefficients alternate between symmetric and skew-symmetric matrices, generalize the notions of even and odd scalar polynomials. We investigate the Smith forms of alternating matrix polynomials, showing that each invariant factor is an even or odd scalar polynomial. Necessary and sufficient conditions are derived for a given Smith form to be that of an alternating matrix polynomial. These conditions allow a characterization of the possible Jordan structures of alternating matrix polynomials, and also lead to necessary and sufficient conditions for the existence of structure-preserving strong linearizations. Most of the results are applicable to singular as well as regular matrix polynomials.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for computation of the smallest perturbation with a special structure, which makes a given Hamiltonian matrix own a purely imaginary eigenvalue.     

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.     

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.     

First order spectral perturbation theory of square singular matrix polynomials

We develop first order eigenvalue expansions of one-parametric perturbations of square singular matrix polynomials. Although the eigenvalues of a singular matrix polynomial P(λ) are not continuous functions of the entries of the coefficients of the polynomial, we show that for most perturbations they are indeed continuous. Given an eigenvalue λ₀ of P(λ) we prove that, for generic perturbations M(λ) of degree at most the degree of P(λ), the eigenvalues of P(λ)+?M(λ) admit covergent series expansions near λ₀ and we describe the first order term of these expansions in terms of M(λ₀) and certain particular bases of the left and right null spaces of P(λ₀). In the important case of λ₀ being a semisimple eigenvalue of P(λ) any bases of the left and right null spaces of P(λ₀) can be used, and the first order term of the eigenvalue expansions takes a simple form. In this situation we also obtain the limit vector of the associated eigenvector expansions.     

A generalized inverse eigenvalue problem in structural dynamic model updating

This paper is concerned with the problem of the best approximation for a given matrix pencil under a given spectral constraint and a submatrix pencil constraint. Such a problem arises in structural dynamic model updating. By using the Moore–Penrose generalized inverse and the singular value decomposition (SVD) matrices, the solvability condition and the expression for the solution of the problem are presented. A numerical algorithm for solving the problem is developed.     

Instability indices for matrix polynomials

There is a well-established instability index theory for linear and quadratic matrix polynomials for which the coefficient matrices are Hermitian and skew-Hermitian. This theory relates the number of negative directions for the matrix coefficients which are Hermitian to the total number of unstable eigenvalues for the polynomial. Herein we extend the theory to ?-even matrix polynomials of any finite degree. In particular, unlike previously known cases we show that the instability index depends upon the size of the matrices when the degree of the polynomial is greater than two. We also consider Hermitian matrix polynomials, and derive an index which counts the number of eigenvalues with nonpositive imaginary part. The results are refined if we consider the Hermitian matrix polynomial to be a perturbation of a ?-even polynomials; however, this refinement requires additional assumptions on the matrix coefficients.     

Adaptive Lanczos methods for recursive condition estimation

Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.Research supported by the US Air Force under grant no. AFOSR-88-0285.Research supported by the US Army under grant no. DAAL03-90-G-105.Research supported by the US Air Force under grant no. AFOSR-88-0285.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented