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.     

Greatest common divisor of generalized polynomials and polynomial matrices

The comrade matrix was introduced recently as the analogue of the companion matrix when a polynomial is expressed in terms of a basis set of orthogonal polynomials. It is now shown how previous results on determining the greatest common divisor of two or more polynomials can be extended to the case of generalized polynomials using the comrade form. Furthermore, a block comrade matrix is defined, and this is used to extend to the generalized case another previous result on the regular greatest common divisor of two polynomial matrices.     

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.     

Degree distribution of the greatest common divisor of polynomials over 𝔽q

We study the degree distribution of the greatest common divisor of two or more random polynomials over a finite field ??_q. We provide estimates for several parameters like number of distinct common irreducible factors, number of irreducible factors counting repetitions, and total degree of the gcd of two or more polynomials. We show that the limiting distribution of a random variable counting the total degree of the gcd is geometric and that the distributions of random variables counting the number of common factors (with and without repetitions) are very close to Poisson distributions when q is large. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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.     

Common Divisor Character Degree Graphs of Solvable Groups with Four Vertices

Let G be a finite solvable group. The common divisor graph Γ(G) attached to G is a character degree graph. Its vertices are the degrees of the nonlinear irreducible complex characters of G, and different vertices m, n are adjacent if the greatest common divisor (m, n) > 1. In this article, we classify all graphs with four vertices that may occur as Γ(G) for solvable group G.     

Faber polynomials corresponding to rational exterior mapping functions

Faber polynomials corresponding to rational exterior mapping functions of degree (m, m − 1) are studied. It is shown that these polynomials always satisfy an (m + 1)-term recurrence. For the special case m = 2, it is shown that the Faber polynomials can be expressed in terms of the classical Chebyshev polynomials of the first kind. In this case, explicit formulas for the Faber polynomials are derived.     

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.     

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.     

Regular and determinant forms for representing the cauchy index of a rational function

We consider regular and determinant forms for representing the index of an arbitrary rational function based on a proposed generalization of the Routh method. We propose forms for representing the index relative to the negative real axis, the positive real axis and the entire axis, as well as the greatest common divisor of polynomials both in terms of the elements of the Routh method and in terms of the determinant of the corresponding Hurwitz matrix. Translated fromDinamicheskie Sistemy, Vol. 11, 1992.     

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(λ).     

Realization and GCD-existence theorem for generalized polynomials

It is shown, that in the ring F _ℚ[I] of generalized polynomials with several indeterminates from the set I over the field F and with rational exponents, each two elements have a greatest common divisor. On the other hand, this ring is Bezout only if I = O/ or I is a singleton.     

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.     

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.     

On cubature formulae with a minimal number of knots

Summary In this paper an approach is outlined to the two-dimensional analogon of the Gaussian quadrature problem. The main results are necessary and sufficient conditions for the existence of cubature formulae which are exact for all polynomials of degree m and which have a minimal number of 1/2k(k+1) knots,k=[m/2]+1. Ifm is odd, similar results are due to I.P. Mysovskikh ([5, 6]) which will be derived in a new way as a special case of the general characterization given here. Furthermore, it will be shown how this characterization can be used to construct minimal formulae of even degree.     

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     

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.     

Special isomorphisms of F[x 1,..., x n ] preserving GCD and their use

On the ring R = F[x ₁,..., x _n ] of polynomials in n variables over a field F special isomorphisms A’s of R into R are defined which preserve the greatest common divisor of two polynomials. The ring R is extended to the ring S: = F[[x ₁,..., x _n ]]⁺ and the ring T: = F[[x ₁,..., x _n ]] of generalized polynomials in such a way that the exponents of the variables are non-negative rational numbers and rational numbers, respectively. The isomorphisms A’s are extended to automorphisms B’s of the ring S. Using the property that the isomorphisms A’s preserve GCD it is shown that any pair of generalized polynomials from S has the greatest common divisor and the automorphisms B’s preserve GCD. On the basis of this Theorem it is proved that any pair of generalized polynomials from the ring T = F[[x ₁,..., x _n ]] has a greatest common divisor.     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Common multiples and common divisors of matrix polynomials, II. Vandermonde and resultant matrices

In this paper explicit formulas are given for least common multiples and greatest common divisors of a finite number of matrix polynomials in terms of the coefficients of the given polynomials. An important role is played by block matrix generalizations of the classical Vandermonde and resultant matrices. Special attention is given to the evaluation of the degrees and other characteristics. Applications to matrix polynomial equations and factorization problems are made.