On some factorizations of two-parameter polynomial matrices

This paper is a logical continuation of the author's discussion about the solution of spectral problems for two-parameter polynomial matrices of general type. Various rank factorization algorithms are suggested, among them the so-called minimal factorization of a singular two-parameter polynomial matrix of degenerate rank into a product of some matrices whose ranks are equal to the rank of the original matrix. Spectral properties of these matrices are studied. The notion of minimal factorization is also extended to one-parameter polynomial and constant matrices. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 94–116 Translated by V. N. Kublanovskaya.     

To solving problems of algebra for two-parameter matrices. VII

The paper discusses the method of rank factorization for solving spectral problems for two-parameter polynomial matrices. New forms of rank factorization, which are computed using unimodular matrices only, are suggested. Applications of these factorizations to solving spectral problems for two-parameter polynomial matrices of both general and special forms are presented. In particular, matrices free of the singular spectrum are considered. Conditions sufficient for a matrix to be free of the singular spectrum and also conditions sufficient for a basis matrix of the null-space to have neither the finite regular nor the finite singular spectrum are provided. Bibliography: 3 titles.     

To solving problems of algebra for two-parameter matrices. III

The paper continues the series of papers devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices of general form. It considers linearization methods, which allow one to reduce the problem of solving an equation F(λ, μ)x = 0 with a polynomial two-parameter matrix F(λ, μ) to solving an equation of the form D(λ, μ)y = 0, where D(λ, μ) = A(μ)-λB(μ) is a pencil of polynomial matrices. Consistent pencils and their application to solving spectral problems for the matrix F(λ, μ) are discussed. The notion of reducing subspace is generalized to the case of a pencil of polynomial matrices. An algorithm for transforming a general pencil of polynomial matrices to a quasitriangular pencil is suggested. For a pencil with multiple eigenvalues, algorithms for computing the Jordan chains of vectors are developed. Bibliography: 8 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 166–207.     

Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

To the Solution of Partial Eigenproblems for Polynomial Matrices

Methods for computing scalar and vector spectral characteristics of a polynomial matrix are proposed. These methods are based on determining the so-called generating vectors (eigenvectors and principal vectors) by using the method of rank factorization of polynomial matrices. The possibility of extending the methods to the case of two-parameter polynomial matrices is indicated. Bibliography: 4 titles.     

Generalized Leibniz functional matrices and factorizations of some well-known matrices

In this paper, we introduce the generalized Leibniz functional matrices and study some algebraic properties of such matrices. To demonstrate applications of these properties, we derive several novel factorization forms of some well-known matrices, such as the complete symmetric polynomial matrix and the elementary symmetric polynomial matrix. In addition, by applying factorizations of the generalized Leibniz functional matrices, we redevelop the known results of factorizations of Stirling matrices of the first and second kind and the generalized Pascal matrix.     

Methods and algorithms of solving spectral problems for polynomial and rational matrices

In the present paper, methods and algorithms for numerical solution of spectral problems and some problems in algebra related to them for one- and two-parameter polynomial and rational matrices are considered. A survey of known methods of solving spectral problems for polynomial matrices that are based on the rank factorization of constant matrices, i.e., that apply the singular value decomposition (SVD) and the normalized decomposition (the QR factorization), is given. The approach to the construction of methods that makes use of rank factorization is extended to one- and two-parameter polynomial and rational matrices. Methods and algorithms for solving some parametric problems in algebra based on ideas of rank factorization are presented. Bibliography: 326titles.Dedicated to the memory of my son AlexanderTranslated fromZapiski Nauchnykh Seminarov POMI, Vol. 238, 1997, pp. 7–328.Translated by V. N. Kublanovskaya.     

多变量多项式矩阵素分解的结果和问题

多变量矩阵素分解问题是多维系统和信号处理学科中的基本问题,从提出以来,已经经过众多学者的研究.近年来随着符号代数计算的快速发展,情况有了根本的改变.概述近几年来该领域的研究进展情况和一些相关未解决的问题,从中可以看出该领域的研究密切依赖于机械化数学的研究进展.作为多变多项式矩阵分解理论的应用,给出两个变量多项式矩阵分解存在性定理的新证明.从中可以看出,2个变量多项式矩阵和3个以上变量矩阵的本质区别.     

Simultaneous diagonalization of three real symmetric matrices

We formulate and prove necessary and sufficient conditions of simultaneous diagonalization of three real symmetric matrices of regular pencil. The conditions are algebraic and consist, in particular, of two spectral requirements and one matrix equality. For the degenerate matrix pencil we suggest an approach that allows reducing of the analysis to a regular pencil. With the use of obtained theorems we investigate a decomposition of linear gyroscopic system into subsystems of an order not higher than two and the stability of trivial solution to a system.     

Bezoutian矩阵的一致逼近形式

借助闭区间上的连续函数可以用Bernstein 多项式一致逼近这一事实,将多项式对所生成的经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵推广到C [0,1]上函数对所对应的情形,给出了 Bezoutian 矩阵一致逼近形式的定义,并且得到如下结论：给出了经典 Bezoutian 矩阵的 Barnett 型分解公式和三角分解公式的一致逼近形式;提供了经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵的一致逼近形式的两类算法;得到了上述两种矩阵的一致逼近形式中元素间的两个恒等关系式。最后,利用数值实例对恒等关系式进行验证,结果表明两类算法是有效的。     

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.     

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     

On irreducible factorizations of rational matrices and their applications

This paper is an extension of our studies of the computational aspects of spectral problems for rational matrices pursued in previous papers. Methods of solution of spectral problems for both one-parameter and two-parameter matrices are considered. Ways of constructing irreducible factorizations (including minimal factorizations with respect to the degree and size of multipliers) are suggested. These methods allow us to reduce the spectral problems for rational matrices to the same problems for polynomial matrices. A relation is established between the irreducible factorization of a one-parameter rational matrix and its irreducible realization used in system theory. These results are extended to the case of two-parameter rational matrices. Bibliography: 15 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 117–156. This work was carried out during our visit to Sweden under the financial support of the Chalmer University of Technology in Góterborg and the Institute of Information Processing of the University of Umeă. Translated by V. N. Kublanovskaya.     

Analysis of singular matrix pencils

One considers the spectral problem for a singular pencil D(λ)=A + λB of matrices A and B (A and B are rectangular matrices or det D(λ)≡0). One represents an algorithm which allows us to find the reducing subspaces for D(λ) and with their aid to reduce the dimension of the initial pencil, by isolating from it the zero block, the blocks corresponding to the right and left polynomial solutions of the equations (A+λB)x(λ)=0 and y(λ)(A+λB)=0, respectively, as well as the block corresponding to the regular kernel of the pencil D(λ). The algorithm is based on the application of the normalized process which uses the numerically stable elementary orthogonal transformations (the matrices of plane rotations or reflections).     

包含切比雪夫多项式的循环矩阵行列式的计算

行首加r尾r右循环矩阵和行尾加r首r左循环矩阵是两种特殊类型的矩阵,这篇论文中就是利用多项式因式分解的逆变换这一重要的技巧以及这类循环矩阵漂亮的结构和切比雪夫多项式的特殊的结构,分别讨论了第一类、第二类切比雪夫多项式的关于行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式,从而给出了行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式显式表达式.这些显式表达式与切比雪夫多项式以及参数r有关.这一问题的应用背景主要在循环编码,图像处理等信息理论方面.     

Systèmes hyperboliques d'équations aux dérivées partielles linéaires : régularité L2loc et matrices diagonalisables

The well-posedness of a Cauchy problem issue from an hyperbolic linear system is linked to the spectral properties of a real matrix pencil. It is known that such a problem is well posed in L² if and only if the imaginary exponential of the pencil is bounded. We give a condition to have a bounded exponential when the eigenvalues don't have the same multiplicities. For pencils spanned by two 3×3 matrices, we prove that the exponential is bounded if and only if the pencil is analytically diagonable.     

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     

To Solving Multiparameter Problems of Algebra. 5. The ∇V-q Factorization Algorithm and its Applications

The algorithm of ∇V-factorization, suggested earlier for decomposing one- and two-parameter polynomial matrices of full row rank into a product of two matrices (a regular one, whose spectrum coincides with the finite regular spectrum of the original matrix, and a matrix of full row rank, whose singular spectrum coincides with the singular spectrum of the original matrix, whereas the regular spectrum is empty), is extended to the case of q-parameter (q ≥ 1) polynomial matrices. The algorithm of ∇V-q factorization is described, and its justification and properties for matrices with arbitrary number of parameters are presented. Applications of the algorithm to computing irreducible factorizations of q-parameter matrices, to determining a free basis of the null-space of polynomial solutions of a matrix, and to finding matrix divisors corresponding to divisors of its characteristic polynomial are considered. Bibliogrhaphy: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 144–153.     

Problems of control and information theory (Hungary)

The bezoutian matrix, which provides information concerning co-primeness and greatest common divisor of polynomials, has recently been generalized by Heinig to the case of square polynomial matrices. Some of the properties of the bezoutian for the scalar case then carry over directly. In particular, the central result of the paper is an extension of a factorization due to Barnett, which enables the bezoutian to be expressed in terms of a Kronecker matrix polynomial in an appropriate block companion matrix. The most important consequence of this result is a determination of the structure of the kernel of the bezoutian. Thus, the bezoutian is nonsingular if and only if the two polynomial matrices have no common eigenvalues (i.e., their determinants are relatively prime); otherwise, the dimension of the kernel is given in terms of the multiplicities of the common eigenvalues of the polynomial matrices. Finally, an explicit basis is developed for the kernel of the bezoutian, using the concept of Jordan chains.     

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)