Utente:Grasso Luigi/sandbox4/MCD polinomi

In algebra, il massimo comun divisore (o i suoi acronimi MCD o GCD) di due polinomi è un polinomio, del più alto grado possibile, cioè un fattore comune a entrambi i due polinomi. Questo concetto è analogo a quello di MCD di due numeri interi $a,\ b\in \mathbb {Z}$.

In particolare per polinomi univariati su un campo il polinomio MCD si può calcolare, come nel caso di $\operatorname {MCD} (a,\ b)$, con l'algoritmo di Euclide utilizzando una divisione lunga. Il polinomio MCD è definito a meno del prodotto per una costante invertibile.

La somiglianza tra MCD intero e MCD polinomiale permette di estendere ai polinomi univariati tutte le proprietà dedotte dall'algoritmo euclideo e dalla divisione euclidea. Inoltre, l'MCD polinomiale ha proprietà specifiche che ne fanno una nozione fondamentale in vari ambiti dell'algebra. Tipicamente, le radici del MCD di due polinomi sono le radici comuni dei due polinomi, e quindi non occorre un ulteriore calcolo. Ad esempio, le radici multiple di un polinomio coincidono con le radici del polinomio MCD e dei suoi derivati, e l' MCD permette di calcolare la fattorizzazione senza quadrati del polinomio, che fornisce polinomi le cui radici sono le radici di una data molteplicità del polinomio iniziale.

Generalizzando, il massimo comun divisore può essere definito ed esiste per i polinomi multivariati su un campo o anello di numeri interi, e anche su un UFD. Esistono algoritmi per calcolarli non appena si ha l'algoritmo MCD nell'anello dei coefficienti. Questi algoritmi procedono mediante ricorsione sul numero di variabili e il problema si riduce ad una variante dell'algoritmo euclideo. Sono uno strumento fondamentale in algebra computazionale, perché il CAS li utilizza sistematicamente per la semplificazione delle frazioni. Al contrario, la maggior parte della moderna teoria del MCD polinomiale è stata sviluppata per soddisfare le necessarie esigenze di efficienza dei sistemi di computer algebra.

Definizione

Siano $p,\ q$ polinomi con coefficienti in un dominio d'integrità F, di solito un campo o il gruppo degli interi $\mathbb {Z}$. Il massimo comune divisore di $p,\ q$ è un polinomio $d:d\mid p,\ d\mid q$ cioè un divisore comune ad entrambi, e tale che ogni divisore comune di $p,\ q$ divide anche $d$. Ogni coppia di polinomi (non entrambi nulli) ha un MCD se e solo se F ha struttura UFD.

Se $F$ è un campo e non si verifica il caso $p=q=0$, un polinomio $d$ è il MCD se e solo se divide entrambiv$p,\ q$, ed ha il grado maggiore tra i polinomi che hanno questa proprietà. Nel caso $p=q=0$, allora MCD è il polinomio nullo. Tuttavia, alcuni autori ritengono che in questo caso non sia definito.

La notazione utilizzata per il massimo comune divisore di $p,\ q$ è

$\operatorname {MCD} (p,\ q)$

MCD non è unico: se $\operatorname {MCD} (p,\ q)=d$, allora il polinomio $f$ è pure MCD se e solo se invertible element Template:Math

$\exists u\in F\ :f\ =ud\implies d\ =u^{-1}f.$

In altre parole, il MCD è unico a meno di una moltiplicazione per una costante invertibile.

Nel caso degli interi, questa indeterminazione è stata risolta scegliendo, come MCD, l'unico positivo (ce n'è un altro, che è il suo opposto). Con tale convenzione, MCD di due interi è anche il più grande (per il solito ordinamento) divisore comune. Tuttavia, poiché non esiste un ordine totale naturale per i polinomi su un dominio intero, non si può procedere allo stesso modo. Per i polinomi univariati su un campo, un requisito aggiuntivo è che l'MCD sia un polinomio monico

$d(x)\ =\ x^{n}+d_{n-1}x^{n-1}+\cdots +d_{2}x^{2}+d_{1}x+d_{0},\quad n\geq 0$

(cioè avere 1 come coefficiente di massimo grado), ma in casi più generali non esiste una convenzione generale. Perciò, uguaglianze come

$\operatorname {MCD} (p,\ q)=d,\ \operatorname {MCD} (p,\ q)=\operatorname {MCD} (r,\ s)$

sono abusi comuni di notazione che andrebbero letti $d$ è il MCD di $p,\ q$ e $p,\ q$ hanno lo stesso insieme di soluzioni come $r,\ s$.

In particolare, $\operatorname {MCD} (p,\ q)\ =1$ significa che le costanti invertibili sono gli unici divisori comuni. In questo caso, per analogia con il caso intero, si dice che $p,\ q$ sono polinomi coprimi.

Proprietà

• Come già detto, il MCD di due polinomi esiste se i coefficienti appartengono o ad un campo, o all'anello degli interi, o più in generale ad un UFD.
• Se $P_{c}(x)$ è un divisore comune di $P_{1}(x),\ P_{2}(x)$, allora $P_{c}(x)$ divide il loro MCD.
• $\gcd(p,q)=\gcd(q,p).$
• $\gcd(p,q)=\gcd(q,p+rq)$ for any polynomial Template:Math. This property is at the basis of the proof of Euclidean algorithm.
• For any invertible element Template:Math of the ring of the coefficients, $\gcd(p,q)=\gcd(p,kq)$.
• Hence $\gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ for any scalars $a_{1},b_{1},a_{2},b_{2}$ such that $a_{1}b_{2}-a_{2}b_{1}$ is invertible.
• If $\gcd(p,r)=1$, then $\gcd(p,q)=\gcd(p,qr)$.
• If $\gcd(q,r)=1$, then $\gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)$.
• For two univariate polynomials Template:Math and Template:Math over a field, there exist polynomials Template:Math and Template:Math, such that $\gcd(p,q)=ap+bq$ and $\gcd(p,q)$ divides every such linear combination of Template:Math and Template:Math (Bézout's identity).
• The greatest common divisor of three or more polynomials may be defined similarly as for two polynomials. It may be computed recursively from GCD's of two polynomials by the identities:
  $$\gcd(p,q,r)=\gcd(p,\gcd(q,r)),$$
  and
  $$\gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).$$

MCD metodi di calcolo

There are several ways to find the greatest common divisor of two polynomials. Two of them are:

1. Factorization of polynomials, in which one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors. This method may be useful only in simple cases, as factoring is usually more difficult than computing the greatest common divisor.
2. The Euclidean algorithm, which can be used to find the GCD of two polynomials in the same manner as for two numbers.

Fattorizzazione

Per trovare MCD di due polinomi si usa il metodo di fattorizzarli completamente. Quindi, si considera il prodotto di tutti fattori comuni. In questa fase, non abbiamo necessariamente un polinomio monico, per cui occorre moltiplicarlo per una costante per renderlo monico. Questo sarà il MCD dei due polinomi poiché include tutti i divisori comuni ed è monico.

Esempio

Trovare $\operatorname {MCD} \ (\ p(x)=x^{2}+7x+6\ ,q(x)=x^{2}-5x-6\ )$ abbiamo la seguente fattorizzazione

${\begin{aligned}p(x)=x^{2}+7x+6&=(x+1)(x+6)\\q(x)=x^{2}-5x-6&=(x+1)(x-6)\\\end{aligned}}$

ottenendo $\operatorname {MCD} \left(p(x),\ q(x)\right)=(x\ +1)=d(x)$

Algoritmo di Euclide

Factoring polynomials can be difficult, especially if the polynomials have a large degree. The Euclidean algorithm is a method that works for any pair of polynomials. It makes repeated use of Euclidean division. When using this algorithm on two numbers, the size of the numbers decreases at each stage. With polynomials, the degree of the polynomials decreases at each stage. The last nonzero remainder, made monic if necessary, is the GCD of the two polynomials.

More specifically, for finding the gcd of two polynomials Template:Math and Template:Math, one can suppose Template:Math (otherwise, the GCD is Template:Math), and

$$\deg(b(x))\leq \deg(a(x))\,.$$

The Euclidean division provides two polynomials Template:Math, the quotient and Template:Math, the remainder such that

$$a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{and}}\quad \deg(r_{0}(x))<\deg(b(x))$$

A polynomial Template:Math divides both Template:Math and Template:Math if and only if it divides both Template:Math and Template:Math. Thus

$$\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).$$

Setting

$$a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),$$

one can repeat the Euclidean division to get new polynomials Template:Math and so on. At each stage we have

$$\deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),$$

so the sequence will eventually reach a point at which

$$b_{N}(x)=0$$

ottenendo il polinomio MCD

$\operatorname {MCD} \ (a,\ b)=\operatorname {MCD} \ (a_{1},\ b_{1})=\cdots =\operatorname {MCD} \ (a_{N},\ 0)=a_{N}.$

Esempio

Trovare $\quad \operatorname {MCD} \ (p(x)\ =x^{2}+7x+6,\ q(x)\ =x^{2}-5x-6)$

$x^{2}\ +7x\ +6\ =1\cdot (x^{2}-5x-6)+(12x+12)$

$x^{2}\ -5x\ -6\ =(12x+12)\cdot ({\frac {1}{12}}\ x-{\frac {1}{2}})\ +0$

Poichè Template:Math is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is Template:Math.

In this example, it is not difficult to avoid introducing denominators by factoring out 12 before the second step. This can always be done by using pseudo-remainder sequences, but, without care, this may introduce very large integers during the computation. Therefore, for computer computation, other algorithms are used, that are described below.

This method works only if one can test the equality to zero of the coefficients that occur during the computation. So, in practice, the coefficients must be integers, rational numbers, elements of a finite field, or must belong to some finitely generated field extension of one of the preceding fields. If the coefficients are floating-point numbers that represent real numbers that are known only approximately, then one must know the degree of the GCD for having a well defined computation result (that is a numerically stable result; in this cases other techniques may be used, usually based on singular value decomposition.

Univariate polynomials with coefficients in a field

The case of univariate polynomials over a field is especially important for several reasons. Firstly, it is the most elementary case and therefore appears in most first courses in algebra. Secondly, it is very similar to the case of the integers, and this analogy is the source of the notion of Euclidean domain. A third reason is that the theory and the algorithms for the multivariate case and for coefficients in a unique factorization domain are strongly based on this particular case. Last but not least, polynomial GCD algorithms and derived algorithms allow one to get useful information on the roots of a polynomial, without computing them.

Euclidean division

Euclidean division of polynomials, which is used in Euclid's algorithm for computing GCDs, is very similar to Euclidean division of integers. Its existence is based on the following theorem: Given two univariate polynomials a and b ≠ 0 defined over a field, there exist two polynomials q (the quotient) and r (the remainder) which satisfy

$$a=bq+r$$

and

$$\deg(r)<\deg(b),$$

where "Template:Math" denotes the degree and the degree of the zero polynomial is defined as being negative. Moreover, q and r are uniquely defined by these relations.

The difference from Euclidean division of the integers is that, for the integers, the degree is replaced by the absolute value, and that to have uniqueness one has to suppose that r is non-negative. The rings for which such a theorem exists are called Euclidean domains.

Like for the integers, the Euclidean division of the polynomials may be computed by the long division algorithm. This algorithm is usually presented for paper-and-pencil computation, but it works well on computers when formalized as follows (note that the names of the variables correspond exactly to the regions of the paper sheet in a pencil-and-paper computation of long division). In the following computation "deg" stands for the degree of its argument (with the convention deg(0) < 0), and "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable.

The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have Template:Math and Template:Math is a non-negative integer that decreases at each iteration. Thus the proof of the validity of this algorithm also proves the validity of the Euclidean division.

Euclid's algorithm

As for the integers, the Euclidean division allows us to define Euclid's algorithm for computing GCDs.

Starting from two polynomials a and b, Euclid's algorithm consists of recursively replacing the pair Template:Math by Template:Math (where "Template:Math" denotes the remainder of the Euclidean division, computed by the algorithm of the preceding section), until b = 0. The GCD is the last non zero remainder.

Euclid's algorithm may be formalized in the recursive programming style as:

$$\gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}$$

In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder: Template:Pre

The sequence of the degrees of the Template:Math is strictly decreasing. Thus after, at most, Template:Math steps, one get a null remainder, say Template:Math. As Template:Math and Template:Math have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs Template:Math have the same set of common divisors. The common divisors of Template:Mvar and Template:Mvar are thus the common divisors of Template:Math and 0. Thus Template:Math is a GCD of Template:Mvar and Template:Mvar. This not only proves that Euclid's algorithm computes GCDs but also proves that GCDs exist.

Identità di Bézout e algoritmo esteso di euclide

L'identità di Bézout is a GCD related theorem, initially proved for the integers, which is valid for every principal ideal domain. In the case of the univariate polynomials over a field, it may be stated as follows.

The interest of this result in the case of the polynomials is that there is an efficient algorithm to compute the polynomials Template:Mvar and Template:Mvar, This algorithm differs from Euclid's algorithm by a few more computations done at each iteration of the loop. It is therefore called extended GCD algorithm. Another difference with Euclid's algorithm is that it also uses the quotient, denoted "quo", of the Euclidean division instead of only the remainder. This algorithm works as follows.

The proof that the algorithm satisfies its output specification relies on the fact that, for every Template:Mvar we have

$$r_{i}=as_{i}+bt_{i}$$

$$s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},$$

the latter equality implying

$$s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.$$

The assertion on the degrees follows from the fact that, at every iteration, the degrees of Template:Math and Template:Math increase at most as the degree of Template:Math decreases.

An interesting feature of this algorithm is that, when the coefficients of Bezout's identity are needed, one gets for free the quotient of the input polynomials by their GCD.

Arithmetic of algebraic extensions

An important application of the extended GCD algorithm is that it allows one to compute division in algebraic field extensions.

Let Template:Mvar an algebraic extension of a field Template:Mvar, generated by an element whose minimal polynomial Template:Mvar has degree Template:Mvar. The elements of Template:Mvar are usually represented by univariate polynomials over Template:Mvar of degree less than Template:Mvar.

The addition in Template:Mvar is simply the addition of polynomials:

$$a+_{L}b=a+_{K[X]}b.$$

The multiplication in Template:Mvar is the multiplication of polynomials followed by the division by Template:Mvar:

$$a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).$$

The inverse of a non zero element Template:Mvar of Template:Mvar is the coefficient Template:Mvar in Bézout's identity Template:Math, which may be computed by extended GCD algorithm. (the GCD is 1 because the minimal polynomial Template:Mvar is irreducible). The degrees inequality in the specification of extended GCD algorithm shows that a further division by Template:Mvar is not needed to get deg(Template:Mvar) < deg(Template:Mvar).

Subresultants

In the case of univariate polynomials, there is a strong relationship between the greatest common divisors and resultants. More precisely, the resultant of two polynomials P, Q is a polynomial function of the coefficients of P and Q which has the value zero if and only if the GCD of P and Q is not constant.

The subresultants theory is a generalization of this property that allows characterizing generically the GCD of two polynomials, and the resultant is the 0-th subresultant polynomial.

The Template:Mvar-th subresultant polynomial Template:Math of two polynomials Template:Math and Template:Math is a polynomial of degree at most Template:Mvar whose coefficients are polynomial functions of the coefficients of Template:Math and Template:Math, and the Template:Mvar-th principal subresultant coefficient Template:Math is the coefficient of degree Template:Mvar of Template:Math. They have the property that the GCD of Template:Math and Template:Math has a degree Template:Mvar if and only if

$$s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0.$$

In this case, Template:Math is a GCD of Template:Math and Template:Math and

$$S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.$$

Every coefficient of the subresultant polynomials is defined as the determinant of a submatrix of the Sylvester matrix of Template:Math and Template:Math. This implies that subresultants "specialize" well. More precisely, subresultants are defined for polynomials over any commutative ring R, and have the following property.

Let Template:Math be a ring homomorphism of Template:Math into another commutative ring Template:Math. It extends to another homomorphism, denoted also Template:Math between the polynomials rings over Template:Math and Template:Math. Then, if Template:Math and Template:Math are univariate polynomials with coefficients in Template:Math such that

$$\deg(P)=\deg(\varphi (P))$$

and

$$\deg(Q)=\deg(\varphi (Q)),$$

then the subresultant polynomials and the principal subresultant coefficients of Template:Math and Template:Math are the image by Template:Math of those of Template:Math and Template:Math.

The subresultants have two important properties which make them fundamental for the computation on computers of the GCD of two polynomials with integer coefficients. Firstly, their definition through determinants allows bounding, through Hadamard inequality, the size of the coefficients of the GCD. Secondly, this bound and the property of good specialization allow computing the GCD of two polynomials with integer coefficients through modular computation and Chinese remainder theorem (see below).

Technical definition

Let

$$P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.$$

be two univariate polynomials with coefficients in a field K. Let us denote by ${\mathcal {P}}_{i}$ the Template:Math vector space of dimension Template:Mvar of polynomials of degree less than Template:Mvar. For non-negative integer Template:Mvar such that Template:Math and Template:Math, let

$$\varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}$$

be the linear map such that

$$\varphi _{i}(A,B)=AP+BQ.$$

The resultant of Template:Math and Template:Math is the determinant of the Sylvester matrix, which is the (square) matrix of $\varphi _{0}$ on the bases of the powers of Template:Math. Similarly, the Template:Math-subresultant polynomial is defined in term of determinants of submatrices of the matrix of $\varphi _{i}.$

Let us describe these matrices more precisely;

Let Template:Math for Template:Math or Template:Math, and Template:Math for Template:Math or Template:Math. The Sylvester matrix is the Template:Math-matrix such that the coefficient of the Template:Math-th row and the Template:Math-th column is Template:Math for Template:Math and Template:Math for Template:Math:

$$S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n}&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots \\\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.$$

The matrix Template:Math of $\varphi _{i}$ is the Template:Math-submatrix of Template:Math which is obtained by removing the last Template:Math rows of zeros in the submatrix of the columns 1 to Template:Math and Template:Math to Template:Math of Template:Math (that is removing Template:Math columns in each block and the Template:Math last rows of zeros). The principal subresultant coefficient Template:Math is the determinant of the Template:Math first rows of Template:Math.

Let Template:Math be the Template:Math matrix defined as follows. First we add Template:Math columns of zeros to the right of the Template:Math identity matrix. Then we border the bottom of the resulting matrix by a row consisting in Template:Math zeros followed by Template:Math:

$$V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.$$

With this notation, the Template:Math-th subresultant polynomial is the determinant of the matrix product Template:Math. Its coefficient of degree Template:Math is the determinant of the square submatrix of T_i consisting in its Template:Math first rows and the Template:Math-th row.

Sketch of the proof

It is not obvious that, as defined, the subresultants have the desired properties. Nevertheless, the proof is rather simple if the properties of linear algebra and those of polynomials are put together.

As defined, the columns of the matrix Template:Math are the vectors of the coefficients of some polynomials belonging to the image of $\varphi _{i}$. The definition of the Template:Math-th subresultant polynomial Template:Math shows that the vector of its coefficients is a linear combination of these column vectors, and thus that S_i belongs to the image of $\varphi _{i}.$

If the degree of the GCD is greater than Template:Math, then Bézout's identity shows that every non zero polynomial in the image of $\varphi _{i}$ has a degree larger than Template:Math. This implies that Template:Math.

If, on the other hand, the degree of the GCD is Template:Math, then Bézout's identity again allows proving that the multiples of the GCD that have a degree lower than Template:Math are in the image of $\varphi _{i}$. The vector space of these multiples has the dimension Template:Math and has a base of polynomials of pairwise different degrees, not smaller than Template:Math. This implies that the submatrix of the Template:Math first rows of the column echelon form of Template:Math is the identity matrix and thus that Template:Math is not 0. Thus Template:Math is a polynomial in the image of $\varphi _{i}$, which is a multiple of the GCD and has the same degree. It is thus a greatest common divisor.

GCD and root finding

Square-free factorization

Most root-finding algorithms behave badly with polynomials that have multiple roots. It is therefore useful to detect and remove them before calling a root-finding algorithm. A GCD computation allows detection of the existence of multiple roots, since the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative.

After computing the GCD of the polynomial and its derivative, further GCD computations provide the complete square-free factorization of the polynomial, which is a factorization

$$f=\prod _{i=1}^{\deg(f)}f_{i}^{i}$$

where, for each Template:Math, the polynomial Template:Math either is 1 if Template:Math does not have any root of multiplicity Template:Math or is a square-free polynomial (that is a polynomial without multiple root) whose roots are exactly the roots of multiplicity Template:Math of Template:Math (see Yun's algorithm).

Thus the square-free factorization reduces root-finding of a polynomial with multiple roots to root-finding of several square-free polynomials of lower degree. The square-free factorization is also the first step in most polynomial factorization algorithms.

Sturm sequence

The Sturm sequence of a polynomial with real coefficients is the sequence of the remainders provided by a variant of Euclid's algorithm applied to the polynomial and its derivative. For getting the Sturm sequence, one simply replaces the instruction

$$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$$

of Euclid's algorithm by

$$r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).$$

Let Template:Math be the number of changes of signs in the sequence, when evaluated at a point Template:Math. Sturm's theorem asserts that Template:Math is the number of real roots of the polynomial in the interval Template:Math. Thus the Sturm sequence allows computing the number of real roots in a given interval. By subdividing the interval until every subinterval contains at most one root, this provides an algorithm that locates the real roots in intervals of arbitrary small length.

GCD over a ring and its field of fractions

In this section, we consider polynomials over a unique factorization domain R, typically the ring of the integers, and over its field of fractions F, typically the field of the rational numbers, and we denote R[X] and F[X] the rings of polynomials in a set of variables over these rings.

Primitive part–content factorization

The content of a polynomial Template:Math, denoted "Template:Math", is the GCD of its coefficients. A polynomial Template:Math may be written

$$q={\frac {p}{c}}$$

where Template:Math and Template:Math: it suffices to take for Template:Math a multiple of all denominators of the coefficients of Template:Math (for example their product) and Template:Math. The content of Template:Math is defined as:

$$\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.$$

In both cases, the content is defined up to the multiplication by a unit of Template:Math.

The primitive part of a polynomial in Template:Math or Template:Math is defined by

$$\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.$$

In both cases, it is a polynomial in Template:Math that is primitive, which means that 1 is a GCD of its coefficients.

Thus every polynomial in Template:Math or Template:Math may be factorized as

$$p=\operatorname {cont} (p)\,\operatorname {primpart} (p),$$

and this factorization is unique up to the multiplication of the content by a unit of Template:Math and of the primitive part by the inverse of this unit.

Gauss's lemma implies that the product of two primitive polynomials is primitive. It follows that

$$\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)$$

and

$$\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).$$

Relation between the GCD over R and over F

The relations of the preceding section imply a strong relation between the GCD's in Template:Math and in Template:Math. To avoid ambiguities, the notation "gcd" will be indexed, in the following, by the ring in which the GCD is computed.

If Template:Math and Template:Math belong to Template:Math, then

$$\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).$$

If Template:Math and Template:Math belong to Template:Math, then

$$\gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),$$

and

$$\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).$$

Thus the computation of polynomial GCD's is essentially the same problem over Template:Math and over Template:Math.

For univariate polynomials over the rational numbers, one may think that Euclid's algorithm is a convenient method for computing the GCD. However, it involves simplifying a large number of fractions of integers, and the resulting algorithm is not efficient. For this reason, methods have been designed to modify Euclid's algorithm for working only with polynomials over the integers. They consist of replacing the Euclidean division, which introduces fractions, by a so-called pseudo-division, and replacing the remainder sequence of the Euclid's algorithm by so-called pseudo-remainder sequences (see below).

Proof that GCD exists for multivariate polynomials

In the previous section we have seen that the GCD of polynomials in Template:Math may be deduced from GCDs in Template:Math and in Template:Math. A closer look on the proof shows that this allows us to prove the existence of GCDs in Template:Math, if they exist in Template:Math and in Template:Math. In particular, if GCDs exist in Template:Math, and if Template:Math is reduced to one variable, this proves that GCDs exist in Template:Math (Euclid's algorithm proves the existence of GCDs in Template:Math).

A polynomial in Template:Mvar variables may be considered as a univariate polynomial over the ring of polynomials in (Template:Math) variables. Thus a recursion on the number of variables shows that if GCDs exist and may be computed in Template:Math, then they exist and may be computed in every multivariate polynomial ring over Template:Math. In particular, if Template:Math is either the ring of the integers or a field, then GCDs exist in Template:Math, and what precedes provides an algorithm to compute them.

The proof that a polynomial ring over a unique factorization domain is also a unique factorization domain is similar, but it does not provide an algorithm, because there is no general algorithm to factor univariate polynomials over a field (there are examples of fields for which there does not exist any factorization algorithm for the univariate polynomials).

Pseudo-remainder sequences

In this section, we consider an integral domain Template:Math (typically the ring Template:Math of the integers) and its field of fractions Template:Math (typically the field Template:Math of the rational numbers). Given two polynomials Template:Math and Template:Math in the univariate polynomial ring Template:Math, the Euclidean division (over Template:Math) of Template:Math by Template:Math provides a quotient and a remainder which may not belong to Template:Math.

For, if one applies Euclid's algorithm to the following polynomials

$$X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5$$

and

$$3X^{6}+5X^{4}-4X^{2}-9X+21,$$

the successive remainders of Euclid's algorithm are

$${\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X-{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}$$

One sees that, despite the small degree and the small size of the coefficients of the input polynomials, one has to manipulate and simplify integer fractions of rather large size.

The pseudo-division has been introduced to allow a variant of Euclid's algorithm for which all remainders belong to Template:Math.

If $\deg(A)=a$ and $\deg(B)=b$ and Template:Math, the pseudo-remainder of the pseudo-division of Template:Math by Template:Math, denoted by Template:Math is

$$\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),$$

where Template:Math is the leading coefficient of Template:Math (the coefficient of Template:Math).

The pseudo-remainder of the pseudo-division of two polynomials in Template:Math belongs always to Template:Math.

A pseudo-remainder sequence is the sequence of the (pseudo) remainders Template:Math obtained by replacing the instruction

$$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$$

of Euclid's algorithm by

$$r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},$$

where Template:Math is an element of Template:Math that divides exactly every coefficient of the numerator. Different choices of Template:Math give different pseudo-remainder sequences, which are described in the next subsections.

As the common divisors of two polynomials are not changed if the polynomials are multiplied by invertible constants (in Template:Math), the last nonzero term in a pseudo-remainder sequence is a GCD (in Template:Math) of the input polynomials. Therefore, pseudo-remainder sequences allows computing GCD's in Template:Math without introducing fractions in Template:Math.

In some contexts, it is essential to control the sign of the leading coefficient of the pseudo-remainder. This is typically the case when computing resultants and subresultants, or for using Sturm's theorem. This control can be done either by replacing Template:Math by its absolute value in the definition of the pseudo-remainder, or by controlling the sign of Template:Mvar (if Template:Mvar divides all coefficients of a remainder, the same is true for Template:Math).

Trivial pseudo-remainder sequence

The simplest (to define) remainder sequence consists in taking always Template:Math. In practice, it is not interesting, as the size of the coefficients grows exponentially with the degree of the input polynomials. This appears clearly on the example of the preceding section, for which the successive pseudo-remainders are

$$-15\,X^{4}+3\,X^{2}-9,$$

$$15795\,X^{2}+30375\,X-59535,$$

$$1254542875143750\,X-1654608338437500,$$

$$12593338795500743100931141992187500.$$

The number of digits of the coefficients of the successive remainders is more than doubled at each iteration of the algorithm. This is typical behavior of the trivial pseudo-remainder sequences.

Primitive pseudo-remainder sequence

The primitive pseudo-remainder sequence consists in taking for Template:Mvar the content of the numerator. Thus all the Template:Math are primitive polynomials.

The primitive pseudo-remainder sequence is the pseudo-remainder sequence, which generates the smallest coefficients. However it requires to compute a number of GCD's in Template:Math, and therefore is not sufficiently efficient to be used in practice, especially when Z is itself a polynomial ring.

With the same input as in the preceding sections, the successive remainders, after division by their content are

$$-5\,X^{4}+X^{2}-3,$$

$$13\,X^{2}+25\,X-49,$$

$$4663\,X-6150,$$

$$1.$$

The small size of the coefficients hides the fact that a number of integers GCD and divisions by the GCD have been computed.

Subresultant pseudo-remainder sequence

A subresultant sequence can be also computed with pseudo-remainders. The process consists in choosing Template:Mvar in such a way that every Template:Math is a subresultant polynomial. Surprisingly, the computation of Template:Mvar is very easy (see below). On the other hand, the proof of correctness of the algorithm is difficult, because it should take into account all the possibilities for the difference of degrees of two consecutive remainders.

The coefficients in the subresultant sequence are rarely much larger than those of the primitive pseudo-remainder sequence. As GCD computations in Template:Math are not needed, the subresultant sequence with pseudo-remainders gives the most efficient computation.

With the same input as in the preceding sections, the successive remainders are

$$15\,X^{4}-3\,X^{2}+9,$$

$$65\,X^{2}+125\,X-245,$$

$$9326\,X-12300,$$

$$260708.$$

The coefficients have a reasonable size. They are obtained without any GCD computation, only exact divisions. This makes this algorithm more efficient than that of primitive pseudo-remainder sequences.

The algorithm computing the subresultant sequence with pseudo-remainders is given below. In this algorithm, the input Template:Math is a pair of polynomials in Template:Math. The Template:Math are the successive pseudo remainders in Template:Math, the variables Template:Math and Template:Math are non negative integers, and the Greek letters denote elements in Template:Math. The functions deg() and rem() denote the degree of a polynomial and the remainder of the Euclidean division. In the algorithm, this remainder is always in Template:Math. Finally the divisions denoted / are always exact and have their result either in Template:Math or in Template:Math.

Template:Pre Note: "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable.

This algorithm computes not only the greatest common divisor (the last non zero Template:Math), but also all the subresultant polynomials: The remainder Template:Math is the Template:Math-th subresultant polynomial. If Template:Math, the Template:Math-th subresultant polynomial is Template:Math. All the other subresultant polynomials are zero.

Sturm sequence with pseudo-remainders

One may use pseudo-remainders for constructing sequences having the same properties as Sturm sequences. This requires to control the signs of the successive pseudo-remainders, in order to have the same signs as in the Sturm sequence. This may be done by defining a modified pseudo-remainder as follows.

If $\deg(A)=a$ and $\deg(B)=b$ and Template:Math, the modified pseudo-remainder Template:Math of the pseudo-division of Template:Math by Template:Math is

$$\operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),$$

where Template:Math is the absolute value of the leading coefficient of Template:Math (the coefficient of Template:Math).

For input polynomials with integer coefficients, this allows retrieval of Sturm sequences consisting of polynomials with integer coefficients. The subresultant pseudo-remainder sequence may be modified similarly, in which case the signs of the remainders coincide with those computed over the rationals.

Note that the algorithm for computing the subresultant pseudo-remainder sequence given above will compute wrong subresultant polynomials if one uses $-\mathrm {prem2} (A,B)$ instead of $\operatorname {prem} (A,B)$.

Modular GCD algorithm

If Template:Math and Template:Math are polynomials in Template:Math for some finitely generated field Template:Math, the Euclidean Algorithm is the most natural way to compute their GCD. However, modern computer algebra systems only use it if Template:Math is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if Template:Math is not finite then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in Template:Math tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by Template:Math leads to a rational number whose denominator is bounded by Template:Math, so in the worst case, the bit size could nearly double with just one operation.

To expedite the computation, take a ring Template:Math for which Template:Math and Template:Math are in Template:Math, and take an ideal Template:Math such that Template:Math is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (Chinese remainder theorem, rational reconstruction, etc.) one can recover the GCD of Template:Math and Template:Math from its image modulo a number of ideals Template:Math. One can prove that this works provided that one discards modular images with non-minimal degrees, and avoids ideals Template:Math modulo which a leading coefficient vanishes.

Suppose $F=\mathbb {Q} ({\sqrt {3}})$, $D=\mathbb {Z} [{\sqrt {3}}]$, $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ and $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$. If we take $I=(2)$ then $D/I$ is a finite ring (not a field since $I$ is not maximal in $D$). The Euclidean algorithm applied to the images of $f,g$ in $(D/I)[x]$ succeeds and returns 1. This implies that the GCD of $f,g$ in $F[x]$ must be 1 as well. Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal $I$.

See also

• List of polynomial topics
• Multivariate division algorithm

References

Bibliography

• Algorithms in real algebraic geometry, chapter 4.2, Springer-Verlag, 2006.
• Computer algebra: systems and algorithms for algebraic computation, Translated from the French by A. Davenport and J.H. Davenport, Academic Press, 1988, ISBN 978-0-12-204230-0.
• Algorithms for polynomial GCD computation over algebraic function fields, ISSAC 2004, 2004, pp. 297–304.
• A sparse modular GCD algorithm for polynomials over algebraic function fields, ISSAC 2007, 2007, pp. 187–194.
• Donald E. Knuth, The Art of Computer Programming II, Addison-Wesley, 1969, pp. 370–371.
• Donald E. Knuth, Seminumerical Algorithms, Third, Reading, Massachusetts, Addison-Wesley, 1997, pp. 439–461, 678–691, ISBN 0-201-89684-2.
• Computer Algebra, Springer Verlag, 1982.

Template:Polynomials