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.     

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.     

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.     

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.     

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.     

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.     

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.     

The Extended Euclidian Algorithm on Polynomials, and the Computational Efficiency of Hyperelliptic Cryptosystems

After generalising two reduction algorithms tocharacteristic 2, we analyse the average complexity of thearithmetic in hyperelliptic Jacobians over any finite field.To this purpose we determine the exact average number offield operations for computing the greatest common divisor ofpolynomials over a finite field by the extended Euclidianalgorithm.     

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.     

Bi-unitary perfect polynomials overGF(g)

Summary This paper continues the author's excursions into the arithmetic of polynomials over finite fields. For monic polynomials A, B GF[q, x] where p is a prime, q=p^dand d 1: The divisor B of A is a bi-unitary divisor of A provided 1 is the greatest common unitary divisor of the polynomials B and A/B, and we say that A is bi-unitary perfect (b.u.p.) over GF(q) provided A equals the sum ^**(A) of the distinct bi-unitary divisors of A in GF[q, x]. A diversity of b.u.p. polynomials over GF(q) is found, some of which are neither perfect nor unitary perfect. For p > 2 we can only conjecture a characterisation of the b.u.p. polynomials which split in GF[p, x], so several open questions remain. Examples of non-splitting b.u.p. polynomials over GF(p) are given for p=2, 3, 5 which, in turn, allow the construction of such examples over GF(p^d) for these p.     

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.     

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.     

The parity of the number of irreducible factors for some pentanomials

It is well known that the Stickelberger–Swan theorem is very important for determining the reducibility of polynomials over a binary field. Using this theorem the parity of the number of irreducible factors for some kinds of polynomials over a binary field, for instance, trinomials, tetranomials, self-reciprocal polynomials and so on was determined. We discuss this problem for Type II pentanomials, namely x^m+xⁿ⁺²+xⁿ⁺¹+xⁿ+1F₂[x] for even m. Such pentanomials can be used for the efficient implementation of multiplication in finite fields of characteristic two. Based on the computation of the discriminant of these pentanomials with integer coefficients, we will characterize the parity of the number of irreducible factors over F₂ and establish necessary conditions for the existence of this kind of irreducible pentanomials.Our results have been obtained in an experimental way by computing a significant number of values with Mathematica and extracting the relevant properties.     

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.     

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.     

Maximal minors of a matrix with linear form entries

Let P be a matrix whose entries are homogeneous polynomials in n variables of degree one over an algebraically closed field. We show that the maximal minors, say m-minors, of P generate the linear space of homogeneous polynomials of degree m if P has the maximal rank m at every point of the affine n-space except the origin.     

A classification of algorithms for multiplying polynomials of small degree over finite fields

It is shown that any optimal algorithm for computing the product of two degree-n polynomials over the q-element field, where n ≤ q, is based on the Chinese Remainder Theorem, with linear and quadratic polynomials presented as the moduli.     

The ERES method for computing the approximate GCD of several polynomials

The computation of the greatest common divisor (GCD) of a set of polynomials has interested the mathematicians for a long time and has attracted a lot of attention in recent years. A challenging problem that arises from several applications, such as control or image and signal processing, is to develop a numerical GCD method that inherently has the potential to work efficiently with sets of several polynomials with inexactly known coefficients. The presented work focuses on: (i) the use of the basic principles of the ERES methodology for calculating the GCD of a set of several polynomials and defining approximate solutions by developing the hybrid implementation of this methodology. (ii) the use of the developed framework for defining the approximate notions for the GCD as a distance problem in a projective space to develop an optimization algorithm for evaluating the strength of different ad-hoc approximations derived from different algorithms. The presented new implementation of ERES is based on the effective combination of symbolic–numeric arithmetic (hybrid arithmetic) and shows interesting computational properties for the approximate GCD problem. Additionally, an efficient implementation of the strength of an approximate GCD is given by exploiting some of the special aspects of the respective distance problem. Finally, the overall performance of the ERES algorithm for computing approximate solutions is discussed.