An approach to solving nonlinear algebraic systems. 2

New methods of solving nonlinear algebraic systems in two variables are suggested, which make it possible to find all zero-dimensional roots without knowing initial approximations. The first method reduces the solution of nonlinear algebraic systems to eigenvalue problems for a polynomial matrix pencil. The second method is based on the rank factorization of a two-parameter polynomial matrix, allowing, us to compute the GCD of a set of polynomials and all zero-dimensional roots of the GCD. Bibliography: 10 titles. Translated by V. N. Kublanovskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 71–96     

Error analysis of signal zeros from a related companion matrix eigenvalue problem

An error analysis of the so-called signal zeros of polynomials linked to exponentially damped signals is performed and error bounds are derived. The analysis uses the link between polynomials and companion matrices and allows us to show that the related companion matrix eigenvalue problem is governed by the condition number of a rectangular Vandermonde matrix which has the zeros of interest as nodes. Conditions under which the zeros are well conditioned are discussed.     

Extending the notions of companion and infinite companion to matrix polynomials

The notion of infinite companion matrix is extended to the case of matrix polynomials (including polynomials with singular leading coefficient). For row reduced polynomials a finite companion is introduced as the compression of the shift matrix. The methods are based on ideas of dilation theory. Connections with systems theory are indicated. Applications to the problem of linearization of matrix polynomials, solution of systems of difference and differential equations and new factorization formulae for infinite block Hankel matrices having finite rank are shown. As a consequence, any system of linear difference or differential equations with constant coefficients can be transformed into a first order system of dimension n = deg det D.     

Computing the Invariant Polynomials of a Polynomial Matrix. II

The paper considers the problem of computing the invariant polynomials of a general (regular or singular) one-parameter polynomial matrix. Two new direct methods for computing invariant polynomials, based on the W and V rank-factorization methods, are suggested. Each of the methods may be regarded as a method for successively exhausting roots of invariant polynomials from the matrix spectrum. Application of the methods to computing adjoint matrices for regular polynomial matrices, to finding the canonical decomposition into a product of regular matrices such that the characteristic polynomial of each of them coincides with the corresponding invariant polynomial, and to computing matrix eigenvectors associated with roots of its invariant polynomials are considered. Bibliography: 5 titles.     

Fiedler companion linearizations for rectangular matrix polynomials

The development of new classes of linearizations of square matrix polynomials that generalize the classical first and second Frobenius companion forms has attracted much attention in the last decade. Research in this area has two main goals: finding linearizations that retain whatever structure the original polynomial might possess, and improving properties that are essential for accurate numerical computation, such as eigenvalue condition numbers and backward errors. However, all recent progress on linearizations has been restricted to square matrix polynomials. Since rectangular polynomials arise in many applications, it is natural to investigate if the new classes of linearizations can be extended to rectangular polynomials. In this paper, the family of Fiedler linearizations is extended from square to rectangular matrix polynomials, and it is shown that minimal indices and bases of polynomials can be recovered from those of any linearization in this class via the same simple procedures developed previously for square polynomials. Fiedler linearizations are one of the most important classes of linearizations introduced in recent years, but their generalization to rectangular polynomials is nontrivial, and requires a completely different approach to the one used in the square case. To the best of our knowledge, this is the first class of new linearizations that has been generalized to rectangular polynomials.     

Stability of rootfinding for barycentric Lagrange interpolants

Computing the roots of a univariate polynomial can be reduced to computing the eigenvalues of an associated companion matrix. For the monomial basis, these computations have been shown to be numerically stable under certain conditions. However, for certain applications, polynomials are more naturally expressed in other bases, such as the Lagrange basis or orthogonal polynomial bases. For the Lagrange basis, the equivalent stability results have not been published. We show that computing the roots of a polynomial expressed in barycentric form via the eigenvalues of an associated companion matrix pair is numerically stable, and give a bound for the backward error. Numerical experiments show that the error bound is approximately an order of magnitude larger than the backward error. We also discuss the matter of scaling and balancing the companion matrix to bring it closer to a normal pair. With balancing, we are able to produce roots with small backward error.     

Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification

The spectral properties of Hermitian matrix polynomials with real eigenvalues have been extensively studied, through classes such as the definite or definitizable pencils, definite, hyperbolic, or quasihyperbolic matrix polynomials, and overdamped or gyroscopically stabilized quadratics. We give a unified treatment of these and related classes that uses the eigenvalue type (or sign characteristic) as a common thread. Equivalent conditions are given for each class in a consistent format. We show that these classes form a hierarchy, all of which are contained in the new class of quasidefinite matrix polynomials. As well as collecting and unifying existing results, we make several new contributions. We propose a new characterization of hyperbolicity in terms of the distribution of the eigenvalue types on the real line. By analyzing their effect on eigenvalue type, we show that homogeneous rotations allow results for matrix polynomials with nonsingular or definite leading coefficient to be translated into results with no such requirement on the leading coefficient, which is important for treating definite and quasidefinite polynomials. We also give a sufficient and necessary condition for a quasihyperbolic matrix polynomial to be strictly isospectral to a real diagonal quasihyperbolic matrix polynomial of the same degree, and show that this condition is always satisfied in the quadratic case and for any hyperbolic matrix polynomial, thereby identifying an important new class of diagonalizable matrix polynomials.     

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.     

Sensitivity of convergent matrices and polynomials

A matrix A is said to be convergent if and only if all its characteristic roots have modulus less than unity. When A is real an explicit expression is given for real matrices B such that A + B is also convergent, this expression depending upon the solution of a quadratic matrix equation of Riccati type. If A and A + B are taken to be in companion form, then the result becomes one of convergent polynomials (i.e., polynomials whose roots have modulus less then unity), and is much easier to apply. A generalization is given for the case when A and A + B are complex and have the same number of roots inside and outside a general circle.     

Majorization and multiplier sequences

We present applications of matrix methods to the analytic theory of polynomials. We first show how matrix analysis can be used to give new proofs of a number of classical results on roots of polynomials. Then we use matrix methods to establish a new log-majorization result on roots of polynomials. The theory of multiplier sequences gives the common link between the applications.     

A new differential equation method for finding the Perron root of a positive matrix

A basic problem in linear algebra is the determination of the largest eigenvalue (Perron root) of a positive matrix. In the present paper a new differential equation method for finding the Perron root is given. The method utilizes the initial value differential system developed in a companion paper for individually tracking the eigenvalue and corresponding right eigenvector of a parametrized matrix.     

Bounds and a majorization for the real parts of the zeros of polynomials

We apply some eigenvalue inequalities to the real parts of the Frobenius companion matrices of monic polynomials to establish new bounds and a majorization for the real parts of the zeros of these polynomials.

     

A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

Bezoutians and projections

With each polynomial p of degree n whose roots lie inside the unit disc we may associate the n-dimensional space of all solutions of the recurrence relation whose coefficients are those of p (considered as a subspace of 1²). The main result consists in establishing a close relation between the Bezoutian of two such polynomials (of the same degree) and the projection operator onto one of the corresponding spaces along the complement of the other. The note forms a loose continuation of the author's investigations of the infinite companion matrix—the generating function of the infinite companion matrix of a polynomial p appears thus as a particular case; the corresponding Bezoutian is that of the pair p and zⁿ.     

Polynomial zerofinders based on Szegő polynomials

The computation of zeros of polynomials is a classical computational problem. This paper presents two new zerofinders that are based on the observation that, after a suitable change of variable, any polynomial can be considered a member of a family of Szegő polynomials. Numerical experiments indicate that these methods generally give higher accuracy than computing the eigenvalues of the companion matrix associated with the polynomial.     

Properties of a generalized Sylvester matrix

We consider problems close to that of the minimal stabilization of a linear vector (i.e., MISO or SIMO) dynamic system; more specifically, the problem of determining the number of common roots of a family of polynomials, and investigating the properties of the so-called generalized Sylvester matrix. The classical definition of the Sylvester matrix is valid for two polynomials, and there are different methods for defining the generalized (extended) Sylvester matrix for a family of polynomials. In this work, we consider a definition of the generalized Sylvester matrix and its properties in the context of their potential future application for solving the minimal stabilization problem.     

A bisection method for measuring the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle

The computation of the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle is investigated. The emphasis is placed on backward stable methods that transform the computation of the distance to a palindromic eigenvalue problem for which structure-preserving eigensolvers can be utilized in conjunction with a bisection algorithm. Reliability of the suggested methods is guaranteed by a novel error analysis.     

Permanental compounds and permanents of (0, 1)-circulants

It was shown by the author in a recent paper that a recurrence relation for permanents of (0, 1)-circulants can be generated from the product of the characteristic polynomials of permanental compounds of the companion matrix of a polynomial associated with (0, 1)-circulants of the given type. In the present paper general properties of permanental compounds of companion matrices are studied, and in particular of convertible companion matrices, i.e., matrices whose permanental compounds are equal to the determinantal compounds after changing the signs of some of their entries. These results are used to obtain formulas for the limit of the nth root of the permanent of the n × n (0, 1)-circulant of a given type, as n tends to infinity. The root-squaring method is then used to evaluate this limit for a wide range of circulant types whose associated polynomials have convertible companion matrices.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

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.