New Algorithms for Polynomial J-Spectral Factorization

In this paper new algorithms are developed for J-spectral factorization of polynomial matrices. These algorithms are based on the calculus of two-variable polynomial matrices and associated quadratic differential forms, and share the common feature that the problem is lifted from the original one-variable polynomial context to a two-variable polynomial context. The problem of polynomial J-spectral factorization is thus reduced to a problem of factoring a constant matrix obtained from the coefficient matrices of the polynomial matrix to be factored. In the second part of the paper, we specifically address the problem of computing polynomial J-spectral factors in the context of H _∞ control. For this, we propose an algorithm that uses the notion of a Pick matrix associated with a given two-variable polynomial matrix. Date received: January 1, 1998. Date revised: October 15, 1998.     

Computation of the structured stability radius via matrix sign function

Robustness of perturbed state space models of the form is considered, where B, C are given matrices, A is an asymptotically stable matrix and D is the unknown perturbation matrix. An efficient algorithm to compute the complex structured stability radius, which is based on the properties of the matrix sign function, is presented. A comparison with previous algorithms shows the efficiency of the new algorithm     

Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices

We exhibit fast computational methods for the evaluation of the determinant and the characteristic polynomial of a (2k+1)-diagonal Toeplitz matrix with elements in the complex field, either for sequential or for parallel computations. A fast algorithm, to achieve one step of Newton's method, is shown to be suitable to compute the eigenvalues of such a matrix. Bounds to the eigenvalues and necessary and sufficient conditions for positive definiteness, which are easy to check, are given either for matrices with scalar elements or for matrices with blocks. In the case in which the blocks are themselves band Toeplitz matrices such conditions assume a very simple form. Dedicated to Prof. Aldo Ghizzetti on his 75 th birthday     

Stabilisation of matrix polynomials

A state feedback is proposed to analyse the stability of a matrix polynomial in closed loop. First, it is shown that a matrix polynomial is stable if and only if a state space realisation of a ladder form of certain transfer matrix is stable. Following the ideas of the Routh–Hurwitz stability procedure for scalar polynomials, certain continued-fraction expansions of polynomial matrices are carrying out by unimodular matrices to achieve the Euclid’s division algorithm which leads to an extension of the well-known Routh–Hurwitz stability criteria but this time in terms of matrix coefficients. After that, stability of the closed-loop matrix polynomial is guaranteed based on a Corollary of a Lyapunov Theorem. The sufficient stability conditions are: (i) The matrices of one column of the presented array must be symmetric and positive definite and (ii) the matrices of the cascade realisation must satisfy a commutative condition. These stability conditions are also necessary for matrix polynomial of second order. The results are illustrated through examples.     

A strategy for detecting extreme eigenvalues bounding gaps in the discrete spectrum of self-adjoint operators

For a self-adjoint linear operator with a discrete spectrum or a Hermitian matrix, the “extreme” eigenvalues define the boundaries of clusters in the spectrum of real eigenvalues. The outer extreme ones are the largest and the smallest eigenvalues. If there are extended intervals in the spectrum in which no eigenvalues are present, the eigenvalues bounding these gaps are the inner extreme eigenvalues.We will describe a procedure for detecting the extreme eigenvalues that relies on the relationship between the acceleration rate of polynomial acceleration iteration and the norm of the matrix via the spectral theorem, applicable to normal matrices. The strategy makes use of the fast growth rate of Chebyshev polynomials to distinguish ranges in the spectrum of the matrix which are devoid of eigenvalues.The method is numerically stable with regard to the dimension of the matrix problem and is thus capable of handling matrices of large dimension. The overall computational cost is quadratic in the size of a dense matrix; linear in the size of a sparse matrix. We verify computationally that the algorithm is accurate and efficient, even on large matrices.     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.     

矩阵方程AX-EXF=BY的通解及其应用

给出矩阵方程 AX-EXY=BY的一个完全解析的、具有显式表达式和完全自由度的参数解 (X,Y) .这里假设矩阵束 (E,A,B) 为R-能控的, F为任意的方阵.相比于现有结论,求解算法不要求矩阵A和F具有特殊的形式,且对它们的特征值没有任何的限制.此外,本文给出的通解还具有结构简洁的特点.作为一个应用,给出了广义系统正常Luenberger函数观测器的一种参数化的设计方法.算例证明了方法的有效性.     

h-space structure in matrix displacement formulas

A class of spaces of matrices, calledh-spaces, is considered, extending previous results in [R. Bevilacqua, P. Zellini,Closure, commutativity and minmal complexity of some space of matrices, Linear and Multilinear Algebra,25, (1989) 1–25]. These spaces include several known classes of matrix algebras, such as group matrix algebras and Hessenberg algebras and, in particular, certain symmetric closed 1-spaces, which are structurally related to Toeplitz plus Hankel-like matrices. Following the displacement rank technique, these spaces are involved in general displacement decomposition formulas of an arbitrary matrixA. These decompositions lead to a significant representation formula for the inverse of a centrosymmetric Toeplitz plus Hankel matrix.     

Insensitivity of asymptotically stable matrices to variations in submatrices

For a given asymptotically stable matrix A which has all characteristic roots with negative real parts, changes are found in arbitrary submatrices of A which do not affect the distribution of roots with respect to the imaginary axis. The results give only sufficient, conditions but are relatively straightforward to apply. Application to matrices in companion form enables one or all of the coefficients of a polynomial to be altered without affecting its asymptotic stability. Illustrative numerical examples are given.     

Fast computation of the Smith form of a sparse integer matrix

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix . The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about black box evaluations for word-sized primes p and , plus additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about bit operations, where O(MM(m)) operations are sufficient to multiply two matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error. Received: March 9, 2000.     

Approximate controllability of the n -th order infinite dimensional systems with controls delayed by the control devices

The main aim of this article is to derive general conditions for a few types of controllability at once for an arbitrary order abstract differential equation and arbitrary eigenvalues multiplicities, instead of conditions for fixed order equation and single eigenvalues. Another innovation of this article is taking into account delays caused by electronic control microcontrollers. This was possible thanks to analysis of the n-th order linear system in the Frobenius form, generating Jordan transition matrix of the confluent Vandermonde form. Using the explicit analytical form of the inverse confluent Vandermonde matrix enabled us to receive general conditions of different types of controllability for the infinite dimensional systems. We derived this analytical form of the inverse confluent Vandermonde matrix using new results from the linear algebra, presented in the paper by S. Hou and W. Pang, “Inversion of confluent Vandermonde matrices”, Int. J. Comput. Math. Appl., 43, pp. 1539–1547, 2002.     

Polynomial approximation of functions of matrices and applications

In solving a mathematical problem numerically, we frequently need to operate on a vector by an operator that can be expressed asf(A), whereA is anN ×N matrix [e.g., exp(A), sin(A), A^–-]. Except for very simple matrices, it is impractical to construct the matrixf (A) explicitly. Usually an approximation to it is used. This paper develops an algorithm based upon a polynomial approximation tof (A). First the problem is reduced to a problem of approximatingf (z) by a polynomial in z, where z belongs to a domainD in the complex plane that includes all the eigenvalues ofA. This approximation problem is treated by interpolatingf (z) in a certain set of points that is known to have some maximal properties. The approximation thus achieved is almost best. Implementing the algorithm to some practical problems is described. Since a solution to a linear systemAx=b isx=A ^–1 b, an iterative solution algorithm can be based upon a polynomial approximation tof (A)=A ^–1. We give special attention to this important problem.     

A Contribution to the Feasibility of the Interval Gaussian Algorithm

We apply the interval Gaussian algorithm to an n × n interval matrix [A] whose comparison matrix 〈[A]〉 is generalized diagonally dominant. For such matrices we prove conditions for the feasibility of this method, among them a necessary and sufficient one. Moreover, we prove an equivalence between a well-known sufficient criterion for the algorithm on H matrices and a necessary and sufficient one for interval matrices whose midpoint is the identity matrix. For the more general class of interval matrices which also contain the identity matrix, but not necessarily as midpoint, we derive a criterion of infeasibility. For general matrices [A] we show how the feasibility of reducible interval matrices is connected with that of irreducible ones. Dedicated to Professor Dr. H. J. Stetter, Wien, on the occasion of his 75th birthday     

Computation of eigenvalues of a real matrix

This paper presents a computational procedure for finding eigenvalues of a real matrix based on Alternate Quadrant Interlocking Factorization, a parallel direct method developed by Rao in 1994 for the solution of the general linear system Ax=b. The computational procedure is similar to LR algorithm as studied by Rutishauser in 1958 for finding eigenvalues of a general matrix. After a series of transformations the eigenvalues are obtained from simple 2×2 matrices derived from the main and cross diagonals of the limit matrix. A sufficient condition for the convergence of the computational procedure is proved. Numerical examples are given to demonstrate the method.     

Maximal stability region of a perturbed nonnegative matrix

For a class of positive matrices A+K with a stable positive nominal part A and a structured positive perturbation part K, we address the problem of finding the largest set of admissible perturbations such that the global matrix remains stable. Theoretical bounds are derived and an algorithm for constructing this set is presented. As an example, this algorithm is applied to the regulation of water flow in open channels. Copyright © 2008 John Wiley & Sons, Ltd.     

Generalized Cayley-Hamilton theorem for polynomial matrices with arbitrary degree

We give an alternative, more convenient expression of the well known Cayley-Hamilton theorem when polynomial matrices of arbitrary degree are involved. Based on the results of a recently developed algorithm (Fragulis et al. 1991) for the computation of the inverse of a polynomial matrix, certain relationships among the coefficient matrices of the given polynomial matrix are obtained. We also propose two ways of finding the powers of a polynomial matrix: one in terms of its coefficient matrices and the other making use of the generalized Cayley-Hamilton theorem. These methods are of closed form and are easily implementable in a digital computer.     

Eigen-solving via reduction to DPR1 matrices

Highly effective polynomial root-finders have been recently designed based on eigen-solving for DPR1 (that is diagonal + rank-one) matrices. We extend these algorithms to eigen-solving for the general matrix by reducing the problem to the case of the DPR1 input via intermediate transition to a TPR1 (that is triangular + rank-one) matrix. Our transforms use substantially fewer arithmetic operations than the QR classical algorithms but employ non-unitary similarity transforms of a TPR1 matrix, whose representation tends to be numerically unstable. We, however, operate with TPR1 matrices implicitly, as with the inverses of Hessenberg matrices. In this way our transform of an input matrix into a similar DPR1 matrix partly avoids numerical stability problems and still substantially decreases arithmetic cost versus the QR algorithm.     

Analytic inversion for a general case of certain classes of matrices

The explicit inverse and determinant of a class of matrices are presented. The class under consideration is defined by 4n ? 2 parameters, analytic expressions of which form the elements of the upper Hessenberg type inverse. These analytic expressions enable recursion formulae to be obtained, which reduce the arithmetic operations to O(n ²). The Hadamard product of two specific structures' matrices provides the class presented, special cases of which are already known classes of test matrices.