Greatest common divisors from generalized sylvester resultant matrices

Sylvester's classical resultant matrix for determining the degree of the greatest common divisor of two polynomials has recently been generalized to deal with m+1 polynomialsm>1. A slightly stronger version is given in this paper for the case when the polynomials do not all have the same degree. The proof relies .on using an appropriate companion matrix, and thereby provides a link with previous work using this approach. It is then shown how the coefficients in a greatest common divisor can be obtained by reducing this extended resultant matrix to row echelon form, this again being an extension of a previous result for the casem=1. Finally, it is shown how the results can be modified when the polynomials are expressed relative to an arbitrary orthogonal basis.     

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.     

Applications of the generalized Sylvester matrix

Recently a Sylvester matrix for several polynomials has been defined, establishing the relative primeness and the greatest common divisor of polynomials. Using this matrix, we perform qualitative analysis of several polynomials regarding the inners, the bigradients, Trudi's theorem, and the connection of inners and the Schur complement. Also it is shown how the regular greatest common divisor of m+1 (m>1) polynomial matrices can be determined.     

Congenial matrices

For a given polynomial in the usual power form, its associated companion matrix can be applied to investigate qualitative properties, such as the location of the roots of the polynomial relative to regions of the complex plane, or to determine the greatest common divisor of a set of polynomials. If the polynomial is in “generalized” form, i.e. expressed relative to an orthogonal basis, then an analogue to the companion matrix has been termed the comrade form. This followed a special case when the basis is Chebyshev, for which the term colleague matrix had been introduced. When a yet more general basis is used, the corresponding matrix has been named confederate. These constitute the class of congenial matrices, which allow polynomials to be studied relative to an appropriate basis. Block-partitioned forms relate to polynomial matrices.     

矩阵多项式秩的和的恒等式及其应用

证明了矩阵A的两个多项式秩的和等于它们最大公因式与最小公倍式秩的和,这个结果不仅可以概括近期文献的相关工作,而且可以对应用矩阵多项式求逆矩阵的方法作进一步的研究,同时也可使关于矩阵秩恒等式的最新讨论获得一种简单统一的处理方法.     

Division of generalized polynomials using the comrade matrix

Let a(λ) and b(λ) be two polynomials expressed in generalized form, i.e. relative to a given orthogonal basis. It is shown how their greatest common divisor d(λ), the quotient a(λ)/d(λ), and the quotient and remainder on division of a(λ) by b(λ) can be determined simultaneously, without any conversion into standard power form. This is done by applying elementary row operations to the matrix b(A), where A is the comrade matrix associated with a(λ).     

Computation of the GCD of polynomials of several variables on a MPC

The article is devoted to computer calculations with polynomials of several variables, in particular, to the construction of sets of large-block polynomial operations and to the concretization of the generalized algorithm of Euclid for computing the greatest common divisor (GCD) of two polynomials of several variables.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 148–155, 1976.     

Spectral factorization of non-symmetric polynomial matrices

The topic of the paper is spectral factorization of rectangular and possibly non-full-rank polynomial matrices. To each polynomial matrix we associate a matrix pencil by direct assignment of the coefficients. The associated matrix pencil has its finite generalized eigenvalues equal to the zeros of the polynomial matrix. The matrix dimensions of the pencil we obtain by solving an integer linear programming (ILP) minimization problem. Then by extracting a deflating subspace of the pencil we come to the required spectral factorization. We apply the algorithm to most general-case of inner–outer factorization, regardless continuous or discrete time case, and to finding the greatest common divisor of polynomial matrices.     

The Bezoutian and the eigenvalue-separation problem for matrix polynomials

A generalized Bezout matrix for a pair of matrix polynomials is studied and, in particular, the structure of its kernel is described and the relations to the greatest common divisor of the given matrix polynomials are presented. The classical root-separation problems of Hermite, Routh-Hurwitz and Schur-Cohn are solved for matrix polynomials in terms of this Bezout matrix. The eigenvalue-separation results are also expressed in terms of Hankel matrices whose entries are Markov parameters of rational matrix function. Some applications of Jacobi's method to these problems are pointed out.     

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     

Analysis of the distribution of roots of a polynomial using a generalized Routh scheme

We study the problem of determining the numerical characteristics of the distribution of the set of roots of a polynomial. The complete solution of this problem is achieved by applying a generalized Routh scheme, proposed previously for computing the Cauchy indices and the greatest common divisor of polynomials. Translated fromDinamicheskie Sistemy, No. 13, 1994, pp. 107–118.     

Blind image deconvolution using a banded matrix method

In this paper we study the blind image deconvolution problem in the presence of noise and measurement errors. We use a stable banded matrix based approach in order to robustly compute the greatest common divisor of two univariate polynomials and we introduce the notion of approximate greatest common divisor to encapsulate the above approach, for blind image restoration. Our method is analyzed concerning its stability and complexity resulting to useful conclusions. It is proved that our approach has better complexity than the other known greatest common divisor based blind image deconvolution techniques. Examples illustrating our procedures are given.     

On computation of the greatest common divisor of several polynomials over a finite field

We propose a probabilistic algorithm to reduce computing the greatest common divisor of m polynomials over a finite field (which requires computing m−1 pairwise greatest common divisors) to computing the greatest common divisor of two polynomials over the same field.     

A method for finding a common linear divisor of the matrix polynomials over an arbitrary field

Conditions are found which guarantee the existence of a common linear unital divisor with a given characteristic polynomial for the regular matrix polynomials over an arbitrary field. The result obtained is applied when finding a common solution of matrix polynomial equations.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 8, pp. 1181–1183, August, 1993.     

线性时不变系统两种描述的等价性

自从Kalman提出了用状态空间方法描述系统后,Rosenbrock与Wolovich等又提出了用微分算子描述系统的方法。这两种描述方法,利用各自表示方法的特点,在多变量系统理论的研究上,都取得了很大的进展。 本文利用Yokoyama标准形与多项式矩阵之间的关系,把上述两种描述联系起来,给出了它们之间等价的转换形式。这样就可以把在一种描述方法上得到的结果,等价地搬到另一种描述方法的系统上去。     

A heuristic verification of the degree of the approximate GCD of two univariate polynomials

We consider the problem of computing verified real interval perturbations of the coefficients of two univariate polynomials such that there exist corresponding perturbed polynomials which have an exact greatest common divisor (GCD) of a given degree k. Based on the certification of the rank deficiency of a submatrix of the Bezout matrix of two univariate polynomials, we propose an algorithm to compute verified real perturbations. Numerical experiments show the performance of our algorithm.     

Structured Low Rank Approximation of a Bezout Matrix

The task of determining the approximate greatest common divisor (GCD) of more than two univariate polynomials with inexact coefficients can be formulated as computing for a given Bezout matrix a new Bezout matrix of lower rank whose entries are near the corresponding entries of that input matrix. We present an algorithm based on a version of structured nonlinear total least squares (SNTLS) method for computing approximate GCD and demonstrate the practical performance of our algorithm on a diverse set of univariate polynomials. The work is partially supported by a National Key Basic Research Project of China 2004CB318000 and Chinese National Science Foundation under Grant 10401035.     

Further Results on the Qualitative Theory of Generalized Polynomials

This paper continues on from work presented in a previous one,concerning polynomials expressed in terms of an orthogonal polynomialbasis. Firstly, a Routh-type tabular array for determining thegreatest common divisor of two polynomials is expressed in analternative form which does not involve divisions. A positivityproperty of the elements is then shown to extend to the generalizedcase, and the relationship between the standard and generalizedarrays is given. This is followed by an expression for the generalizedHurwitz determinants introduced in the previous paper in termsof the generalized array. Finally, a different type of tabulararray for determining-the g.c.d. is described.     

A new method for computing polynomial greates common divisors and polynomial remainder sequences

Summary A new method is presented for the computation of a greatest common divisor (gcd) of two polynomials, along with their polynomial remainder sequence (prs). This method is based on our generalization of a theorem by Van Vleck [12] and uniformly treats both normal and abnormal prs's, making use of Bareiss's [3] integer-preserving transformation algorithm for Gaussian elimination. Moreover, for the polynomials of the prs's, this method provides the smallest coefficients that can be expected without coefficient ged computations (as in Bareiss [3]) and it clearly demonstrates the divisibility properties; hence, it combines the best of both the reduced and the subresultant prs algorithms.This paper is affectionately dedicated to the memory of my father     

多项式的最大公因式的一种新求法

本文介绍了一种利用数域上矩阵的初等行变换求一组一元ｎ次多项式的最大公因式的方法．