|
|
| Line 1: |
Line 1: |
| {{refimprove|date=September 2012}}
| | Andrew Simcox is the title his mothers and fathers gave him and he totally loves this title. Invoicing is my occupation. To climb is some thing she would never give up. Alaska is exactly where he's always been living.<br><br>my website ... real psychics, [http://Conniecolin.com/xe/community/24580 Conniecolin.com], |
| In algebra, the '''greatest common divisor''' (frequently abbreviated as GCD) of two [[polynomial]]s is a polynomial, of the highest possible degree, that is a [[factorization|factor]] of both the two original polynomials. This concept is analogous to the [[greatest common divisor]] of two integers.
| |
| | |
| In the important case of [[univariate]] polynomials over a [[field (mathematics)|field]] the polynomial GCD may be computed, like for the integer GCD, by [[Euclid's algorithm]] using [[polynomial long division|long division]]. The main difference lies in the fact that there is no natural [[total order]] on the polynomials. Therefore, "greatest" is meant for the relation of [[divisibility]]. As this relation is only a [[preorder]], the polynomial GCD is defined only [[up to]] the multiplication by an invertible constant.
| |
| | |
| The similarity between the integer GCD and the polynomial GCD allows us to extend to univariate polynomials all the properties that may be deduced from Euclid's algorithm and [[Euclidean division]]. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the [[root of a function|root]]s of the GCD of two polynomials are the common roots of the two polynomials, and this allows to get information on the roots without computing them. For example the [[multiple root]]s of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow to compute the [[square-free factorization]] of the polynomial, which provides polynomials whose roots are the roots of a given [[multiplicity (mathematics)|multiplicity]].
| |
| | |
| The greatest common divisor may be defined and exists, more generally, for [[multivariate polynomial]]s over a field or the ring of integers, and also over a [[unique factorization domain]]. There exist algorithms to compute them as soon as one has a GCD algorithm in the ring of coefficients. These algorithms proceed by a [[recursion]] on the number of variables to reduce the problem to a variant of Euclid's algorithm. They are a fundamental tool in [[computer algebra]], because [[computer algebra system]]s use them systematically to simplify fractions. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need of efficiency of computer algebra systems.
| |
| | |
| ==General definition==
| |
| Let ''p'' and ''q'' be polynomials with [[coefficients]] in an [[integral domain]] ''F'', typically a [[field (mathematics)|field]] or the integers.
| |
| A '''greatest common divisor''' of ''p'' and ''q'' is a polynomial ''d'' that divides ''p'' and ''q'' and such that every common divisor of ''p'' and ''q'' also divides ''d''. Every pair of polynomials has a GCD if and only if ''F'' is a [[unique factorization domain]].
| |
| | |
| If ''F'' is a field and ''p'' and ''q'' are not both zero, ''d'' is a greatest common divisor if and only if it divides both ''p'' and ''q'' and it has the greatest degree among the polynomials having this property. If ''p'' = ''q'' = 0, the GCD is 0. However, some authors consider that it is not defined in this case.
| |
| | |
| The greatest common divisor of ''p'' and ''q'' is usually denoted "gcd(''p'', ''q'')".
| |
| | |
| The greatest common divisor is not unique: if ''d'' is a GCD of ''p'' and ''q'', then the polynomial ''f'' is another GCD if and only if there is an invertible element ''u'' of ''F'' such that
| |
| :<math>f=u d</math>
| |
| and
| |
| :<math>d=u^{-1} f</math>.
| |
| In other words, the GCD is unique up to the multiplication by an invertible constant.
| |
| | |
| In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive (there is another one, which is its opposite). With this convention, the GCD of two integers is also the greatest (for the usual ordering) common divisor. When one want to settle this indetermination in the polynomial case, one lacks of a natural [[total order]]. Therefore, one chooses once for all a particular GCD that is then called ''the'' greatest common divisor. For [[univariate]] polynomials over a field, this is usually the unique GCD which is [[monic polynomial|monic]] (that is has 1 as coefficient of the highest degree). In more general cases, there is no general convention and above indetermination is usually kept. Therefore equalities like ''d'' = gcd(''p'', ''q'') or gcd(''p'', ''q'') = gcd(''r'', ''s'') are usual abuses of notation which should be read "''d'' is a GCD of ''p'' and ''q''" and "''p'', ''q'' has the same set of GCD as ''r'', ''s''". In particular, gcd(''p'', ''q'') = 1 means that the invertible constants are the only common divisors, and thus that ''p'' and ''q'' are [[coprime]].
| |
| | |
| <!-- This example seems not really useful. In any case, it should be placed in another section
| |
| | |
| These hypotheses for the ring of the coefficients are necessary. For example, suppose we allow ''F'' = '''Z'''/6'''Z''', which is not a field. Then we have
| |
| | |
| : <math>x(x + 3) = x^2 + 3x,\ </math>
| |
| | |
| : <math>x(x + 1) = x^2 + x,\ </math>
| |
| | |
| and
| |
| | |
| : <math>(x + 3)(x + 4) = x^2 + 7x + 12 = x^2 + x,\ </math>
| |
| | |
| after reduction modulo six (see [[modular arithmetic]]). This shows that ''x'' and <math>x+3</math> would both satisfy the definition of
| |
| | |
| : <math>\gcd(x^2 + x, x^2 + 3x).\ </math>
| |
| -->
| |
| | |
| ==Properties==
| |
| | |
| *As stated above, the GCD of two polynomials exists if the coefficients belong either to a field, the ring of the integers or more generally to a [[unique factorization domain]].
| |
| *If ''c'' is any common divisor of ''p'' and ''q'', then ''c'' divides their GCD.
| |
| *<math>\gcd(p,q)= \gcd(q,p).</math>
| |
| *<math>\gcd(p, q)= \gcd(q,p+rq)</math> for any polynomial ''r''. This property is at the basis of the proof of Euclid's algorithm.
| |
| *For any invertible element ''k'' of the ring of the coefficients, <math>\gcd(p,q)=\gcd(p,kq)</math>.
| |
| *Hence <math>\gcd(p,q)=\gcd(a_1p+b_1q,a_2p+b_2q)</math> for any scalars <math>a_1, b_1, a_2, b_2</math> such that <math>a_1 b_2 - a_2 b_1</math> is invertible.
| |
| *If <math>\gcd(p, r)=1</math>, then <math>\gcd(p, q)=\gcd(p, qr)</math>.
| |
| *If <math>\gcd(q, r)=1</math>, then <math>\gcd(p, qr)=\gcd(p, q)\,\gcd(p, r)</math>.
| |
| *For two univariate polynomials ''p'' and ''q'' over a field, there exist polynomials ''a'' and ''b'', such that <math>\gcd(p,q)=ap+bq</math> and <math>\gcd(p,q)</math> divides every such linear combination of ''p'' and ''q'' ([[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:
| |
| ::<math>\gcd(p, q, r) = \gcd(p, \gcd(q, r)),</math>
| |
| : and
| |
| ::<math>\gcd(p_1, p_2, \dots , p_n) = \gcd( p_1, \gcd(p_2, \dots , p_n)).</math>
| |
| | |
| ==GCD by hand writing computation==
| |
| There are several ways to find the greatest common divisor of two polynomials. Two of them are:
| |
| | |
| #''[[Factorization]]'', 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 very simple cases, as, like for the integers, factoring is usually much more difficult than computing the greatest common divisor. Moreover, there are fields of coefficient for which there is no factorization algorithm, while Euclidean algorithm always exists.
| |
| #The ''[[Euclidean algorithm]]'', which can be used to find the GCD of two polynomials in the same manner as for two numbers.
| |
| | |
| ===Factoring===
| |
| To find the GCD of two polynomials using factoring, simply factor the two polynomials completely. Then, take the product of all common factors. At this stage, we do not necessarily have a monic polynomial, so finally multiply this by a constant to make it a monic polynomial. This will be the GCD of the two polynomials as it includes all common divisors and is monic.
| |
| | |
| Example one: Find the GCD of ''x''<sup>2</sup> + 7''x'' + 6 and ''x''<sup>2</sup> − 5''x'' − 6.
| |
| | |
| ''x''<sup>2</sup> + 7''x'' + 6 = (''x'' + 1)(''x'' + 6)
| |
| | |
| ''x''<sup>2</sup> − 5''x'' − 6 = (''x'' + 1)(''x'' − 6)
| |
| | |
| Thus, their GCD is ''x'' + 1.
| |
| | |
| ===Euclidean algorithm===
| |
| Factoring polynomials can be difficult, especially if the polynomials have large degree. The [[Euclidean algorithm]] is a method which works for any pair of polynomials. It makes repeated use of [[polynomial long division]] or [[synthetic 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, assume we wish to find the gcd of two polynomials ''a''(''x'') and ''b''(''x''), where we can suppose
| |
| :<math>\deg(b(x)) \le \deg(a(x)) \,.</math>
| |
| | |
| We can find two polynomials ''q''(''x'') and ''r''(''x'') which satisfy (see [[Polynomial long division]])
| |
| | |
| * <math>a(x) = q_0(x)b(x) + r_0(x)</math>
| |
| * <math>\deg(r_0(x)) < \deg(b(x))</math>
| |
| | |
| The polynomial ''q''<sub>0</sub>(''x'') is called the quotient and ''r''<sub>0</sub>(''x'') is the remainder. Notice that a polynomial ''g''(''x'') divides ''a''(''x'') and ''b''(''x'') if and only if it divides ''b''(''x'') and ''r''<sub>0</sub>(''x''). We deduce
| |
| :<math>\gcd(a(x), b(x)) = \gcd(b(x), r_0(x)) \,.</math>.
| |
| Then set
| |
| :<math>a_1(x) = b(x), b_1(x) = r_0(x)\,.</math>
| |
| Repeat the [[Polynomial long division]] to get new polynomials ''q''<sub>1</sub>(''x''), ''r''<sub>1</sub>(''x''), ''a''<sub>2</sub>(''x''), ''b''<sub>2</sub>(''x'') and so on. At each stage we have
| |
| :<math>\deg(a_{k+1})+\deg(b_{k+1}) < \deg(a_{k})+\deg(b_{k})\ ,</math>
| |
| so the sequence will eventually reach a point at which
| |
| :<math>b_N(x) = 0</math>
| |
| and we will have found our GCD:
| |
| :<math>\gcd(a,b)=\gcd(a_1,b_1)=\cdots=\gcd(a_N, 0)=a_N \,.</math>
| |
| | |
| Example: Find the GCD of <span style="color:#0000ff">''x''<sup>2</sup> + 7''x'' + 6</span> and <span style="color:#990000">''x''<sup>2</sup> − 5''x'' − 6</span>.
| |
| | |
| : <span style="color:#0000ff">''x''<sup>2</sup> + 7''x'' + 6</span> = <span style="color:#990000">(''x''<sup>2</sup> − 5''x'' − 6)</span>(1) + <span style="color:#009900">(''x'' + 1)</span>(12)
| |
| | |
| : <span style="color:#990000">''x''<sup>2</sup> − 5''x'' − 6</span> = <span style="color:#009900">(''x'' + 1)</span>(''x'' − 6) + 0
| |
| | |
| Since <span style="color:#009900">''x'' + 1</span> is the last nonzero remainder, the GCD of these polynomials is ''x'' + 1.
| |
| | |
| This method works only if one may test the equality to zero of the elements of the field of the coefficients. Thus, in practice, it works only for polynomials with coefficients in the field of [[rational number]]s, in a [[finite field]] or a [[number field]] or in the field of [[rational function]]s over one of the previous fields.
| |
| | |
| This induces a new difficulty: For all these fields except the finite ones, the coefficients are fractions. If the fractions are not simplified during the computation, the size of the coefficients grows exponentially during the computation, which makes it impossible except for very small degrees. On the other hand, it is highly time consuming to simplify the fractions immediately. Therefore two different alternative methods have been introduced (see below):
| |
| * Pseudo-remainder sequences, especially subresultant sequences.
| |
| * Modular GCD algorithm using [[modular arithmetic]]
| |
| | |
| ==Univariate polynomials with coefficients in a field==
| |
| | |
| The case of univariate polynomials over a field is specially important for several reasons. Firstly, it is the most elementary case and therefore appear 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 polynomial|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|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
| |
| :<math>a=bq+r</math>
| |
| and
| |
| :<math>\deg(r)<\deg(b),</math>
| |
| where "deg(...)" denotes the degree and the degree of 0 is defined as 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 domain]]s.
| |
| | |
| Like for the integers, the Euclidean division of the polynomials may be computed by the [[polynomial long division|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.
| |
| | |
| {{quotation|
| |
| '''Euclidean division'''
| |
| <br>
| |
| '''''Input:''''' ''a'' and ''b'' ≠ 0 two polynomials in the variable ''x'';
| |
| <br>
| |
| '''''Output:''''' ''q'', the quotient and ''r'', the remainder;
| |
| <br>
| |
| '''''Begin'''''
| |
| <br>
| |
| <math>q:=0; \quad r:=a; \quad d:=\deg(b);</math>
| |
| <br>
| |
| <math>d:=\deg(b); \quad c:=\text{lc}(b);</math>
| |
| <br>
| |
| '''''while''''' <math>\deg(r) \geq d </math> '''''do'''''
| |
| :<math>s:=\frac{\text{lc}(r)}{c}x^{\deg(r)-d};</math>
| |
| :<math>q:=q+s;</math>
| |
| :<math>r:=r-sb;</math>
| |
| '''''end do;'''''
| |
| <br>
| |
| return (''q'', ''r'');
| |
| <br>
| |
| '''''end.'''''
| |
| }}
| |
| | |
| The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have ''a'' = ''bq'' + ''r'' and deg(''r'') is a non-negative integer that decreases at each iteration. Thus the proof of the validity of this algorithm also proves the validity of Euclidean division.
| |
| | |
| ===Euclid's algorithm===
| |
| As for the integers, 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 (''a'', ''b'') by (''b'', rem(''a'', ''b'')) (where "rem(''a'', ''b'')" 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:
| |
| {{quotation|
| |
| <math>\gcd(a,b):= \text{if}\;b=0\; \text{then}\;a\;\text{else}\; \gcd(b, \text{rem}(a,b))</math>.
| |
| }}
| |
| In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder:
| |
| {{quotation|
| |
| <math>r_0:=a;\quad r_1:=b;\quad i:=1;</math>
| |
| <br>
| |
| '''''while''''' <math>r_i \neq 0</math> '''''do'''''
| |
| :<math>r_{i+1}:=\text{rem}(r_{i-1},r_{i});\quad i:=i+1;</math>
| |
| '''''end do;'''''
| |
| <br>
| |
| '''''return'''''
| |
| <math>(r_{i-1}).</math>
| |
| }}
| |
| | |
| The sequence of the degrees of the ''r<sub>i</sub>'' is strictly decreasing. Thus after, at most, deg(''b'') steps, one get a null remainder, say ''r<sub>k</sub>''. As (''a'', ''b'') and (''b'', rem(''a'',''b'')) have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs (''r<sub>i</sub>'', ''r''<sub>''i'' + 1</sub>) have the same set of common divisors. The common divisors of ''a'' and ''b'' are thus the common divisors of ''r''<sub>''k'' − 1</sub> and 0. Thus ''r''<sub>''k'' − 1</sub> is a GCD of ''a'' and ''b''.
| |
| This not only proves that Euclid's algorithm computes GCDs, but also proves that GCDs exist.
| |
| | |
| ===Bézout's identity and extended GCD algorithm===
| |
| | |
| [[Bézout's identity]] 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.
| |
| | |
| {{quotation|
| |
| If ''g'' is the greatest common divisor of two polynomials ''a'' and ''b'', then there are two polynomials ''u'' and ''v'' such that
| |
| :<math>au+bv=g\quad\text{(Bézout's identity)}</math>
| |
| and
| |
| :<math>\deg(u)<\deg(b)-\deg(g), \quad \deg(v)<\deg(a)-\deg(g).</math>
| |
| }}
| |
| | |
| The interest of this result in the case of the polynomials is that there is an efficient algorithm to compute the polynomials ''u'' and ''v'', This algorithm differs from Euclid's algorithm by a few more computation done at each iteration of the loop. It is therefore called '''extended GCD algorithm'''. Another difference with Euclid's algorithm is that it uses the quotient, denoted "quo", of the Euclidean division instead of the remainder. This algorithm works as follows.
| |
| | |
| {{quotation|
| |
| '''Extended GCD''' algorithm
| |
| <br> | |
| '''''Input:''''' ''a'', ''b'',univariate polynomials
| |
| <br> | |
| '''''Output:'''''
| |
| :''g'',the GCD of ''a'' and ''b''
| |
| :''u'', ''v'', such that
| |
| ::<math>au+bv=g,</math>
| |
| ::<math>\deg(u)<\deg(b)-\deg(g)</math>
| |
| ::<math>\deg(v)<\deg(a)-\deg(g)</math>
| |
| :''a''<sub>1</sub>, ''b''<sub>1</sub>, such that
| |
| ::<math>a=ga_1</math>
| |
| ::<math>b=gb_1</math>
| |
| '''''Begin'''''
| |
| :<math>r_0:=a;\quad r_1:=b;</math>
| |
| :<math>s_0:=1;\quad s_1:=0;</math>
| |
| :<math>t_0:=0;\quad t_1:=1;</math>
| |
| :<math>i:=1;</math>
| |
| :'''''while''''' ''r<sub>i</sub>'' ≠ 0 '''''do'''''
| |
| ::<math>q:=\text{quo}(r_{i-1},r_{i});</math>
| |
| ::<math>r_{i+1}:=r_{i-1}-qr_{i};</math>
| |
| ::<math>s_{i+1}:=s_{i-1}-qs_{i};</math>
| |
| ::<math>t_{i+1}:=t_{i-1}-qt_{i};</math>
| |
| ::<math>i:=i+1;</math>
| |
| :'''''end do;'''''
| |
| :<math>g:=r_{i-1};</math>
| |
| :<math>u:=s_{i-1};\quad v:=t_{i-1};</math>
| |
| :<math>a_1:=(-1)^{i-1}t_i;\quad b_1:=(-1)^i s_i;</math>
| |
| '''''end.'''''
| |
| }}
| |
| | |
| The proof that the algorithm satisfies its output specification relies on the fact that, for every ''i'' we have
| |
| :<math>r_i=as_i+bt_i</math>
| |
| :<math>s_it_{i+1}-t_is_{i+1}=s_it_{i-1}-t_is_{i-1},</math>
| |
| the latter equality implying
| |
| :<math>s_it_{i+1}-t_is_{i+1}=(-1)^i.</math>
| |
| The assertion on the degrees follows from the fact that, at every iteration, the degrees of ''s<sub>i</sub>'' and ''t<sub>i</sub>'' increase at most as the degree of ''r<sub>i</sub>'' 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 extended GCD algorithm is that it allows to compute division in [[algebraic extension|algebraic field extension]]s.
| |
| | |
| Let ''L'' an algebraic extension of a field ''K'', generated by an element whose minimal polynomial ''f'' has degree ''n''. The elements of ''L'' are usually represented by univariate polynomials over ''K'' of degree less than ''n''.
| |
| | |
| The addition in ''L'' is simply the addition of polynomials:
| |
| :<math>a+_Lb=a+_{K[X]}b.</math>
| |
| | |
| The multiplication in ''L'' is the multiplication of polynomials followed by the division by ''f'':
| |
| :<math>a\cdot_Lb=\text{rem}(a._{K[X]}b),f).</math>
| |
| | |
| The inverse of a non zero element ''a'' of ''L'' is the coefficient ''u'' in Bézout's identity ''au'' + ''fv'' = 1, which may be computed by extended GCD algorithm. (the GCD is 1 because the minimal polynomial ''f'' is irreducible). The degrees inequality in the specification of extended GCD algorithm shows that a further division by ''f'' is not needed to get deg(''u'') < deg(''f'').
| |
| | |
| ===Subresultants===<!-- [[subresultant]] links here -->
| |
| | |
| In the case of univariate polynomials, there is a strong relationship between greatest common divisors and [[resultant]]s. In fact 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 to characterize generically the GCD of two polynomials, and the resultant is the 0-th subresultant polynomial.<ref>
| |
| {{cite book
| |
| | author = Saugata Basu
| |
| | coauthors = Richard Pollack, Marie-Françoise Roy
| |
| | year = 2006
| |
| | title = Algorithms in real algebraic geometry, chapter 4.2
| |
| | publisher = [[Springer Science+Business Media|Springer-Verlag]]
| |
| | url = http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html
| |
| }}</ref>
| |
| | |
| The ''i''-th ''subresultant polynomial'' ''S<sub>i</sub>''(''P'' ,''Q'') of two polynomials ''P'' and ''Q'' is a polynomial of degree at most ''i'' whose coefficients are polynomial functions of the coefficients of ''P'' and ''Q'', and the ''i''-th ''principal subresultant coefficient'' ''s<sub>i</sub>''(''P'' ,''Q'') is the coefficient of degree ''i'' of ''S<sub>i</sub>''(''P'', ''Q''). They have the property that the GCD of ''P'' and ''Q'' has a degree ''d'' if and only if
| |
| :<math>s_0(P,Q)=\cdots=s_{d-1}(P,Q) =0 \ , s_d(P,Q)\neq 0</math>.
| |
| | |
| In this case, ''S<sub>d</sub>''(''P'' ,''Q'') is a GCD of ''P'' and ''Q'' and
| |
| | |
| :<math>S_0(P,Q)=\cdots=S_{d-1}(P,Q) =0.</math>
| |
| | |
| Every coefficient of the subresultant polynomials is defined as the determinant of a submatrix of the [[Sylvester matrix]] of ''P'' and ''Q''. This implies that that subresultants "specialize" well. More precisely, subresultants are defined for polynomials over any commutative ring ''R'', and have the following property.
| |
| | |
| Let φ be a ring homomorphism of ''R'' into another commutative ring ''S''. It extends to another homomorphism, denoted also φ between the polynomials rings over ''R'' and ''S''. Then, if ''P'' and ''Q'' are univariate polynomials with coefficients in ''R'' such that
| |
| :<math>\deg(P)=\deg(\varphi(P))</math>
| |
| and
| |
| :<math>\deg(Q)=\deg(\varphi(Q)),</math>
| |
| then the subresultant polynomials and the principal subresultant coefficients of φ(''P'') and φ(''Q'') are the image by φ of those of ''P'' and ''Q''.
| |
| | |
| The subresultants have two important properties whch make them fundamental for the computation on computers of the GCD of two polynomials with integer coefficients.
| |
| Firstly, their definition through determinants allows to bound, through [[Hadamard inequality]], the size of the coefficients of the GCD.
| |
| Secondly, this bound and the property of good specialization allow to compute the GCD of two polynomials with integer coefficients through [[modular arithmetic|modular computation]] and [[Chinese remainder theorem]] (see [[#Modular GCD algorithm|below]]).
| |
| | |
| ====Technical definition====
| |
| Let
| |
| :<math>P=p_0+p_1 X+\cdots +p_m X^m,\quad Q=q_0+q_1 X+\cdots +q_n X^n.</math>
| |
| be two univariate polynomials with coefficients in a field ''K''. Let us denote by <math>\mathcal{P}_i</math> the ''K'' vector space of dimension ''i'' the polynomials of degree less than ''i''. For non negative integer ''i'' such that ''i''≤''m'' and ''i''≤''n'', let
| |
| :<math>\varphi_i:\mathcal{P}_{n-i} \times \mathcal{P}_{m-i} \rightarrow \mathcal{P}_{m+n-i}</math>
| |
| be the linear map such that
| |
| :<math>\varphi_i(A,B)=AP+BQ.</math>
| |
| | |
| The [[resultant]] of ''P'' and ''Q'' is the determinant of the [[Sylvester matrix]], which is the (square) matrix of <math>\varphi_0</math> on the bases of the powers of ''X''. Similarly, the ''i''-subresultant polynomial is defined in term of determinants of submatrices of the matrix of <math>\varphi_i.</math>
| |
| | |
| Let us describe these matrices more precisely;
| |
| | |
| Let ''p''<sub>''i''</sub> = 0 for ''i'' < 0 or ''i'' > ''m'', and ''q''<sub>''i''</sub> = 0 for ''i'' < 0 or ''i'' > ''n''. The [[Sylvester matrix]] is the (''m'' + ''n'') × (''m'' + ''n'')-matrix such that the coefficient of the ''i''-th row and the ''j''-th column is ''p''<sub>''m'' + ''j'' - ''i''</sub> for ''j'' ≤ ''n'' and ''q''<sub>''j'' - ''i''</sub> for ''j'' > ''n'':<ref>Many author define the Sylvester matrix as the transpose of ''S''. This breaks the usual convention for writing the matrix of a linear map.</ref>
| |
| | |
| :<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}.</math>
| |
| | |
| The matrix ''T<sub>i</sub>'' of <math>\varphi_i</math> is the (''m'' + ''n'' − ''i'') × (''m'' + ''n'' − 2''i'')-submatrix of ''S'' which is obtained by removing the last ''i'' rows of zeros in the submatrix of the columns 1 to ''n''-''i'' and ''n''+1 to ''m''+''n''-''i'' of ''S'' (that is removing ''i'' columns in each block and the ''i'' last rows of zeros). The ''principal subresultant coefficient'' ''s<sub>i</sub>'' is the determinant of the ''m'' + ''n'' - 2''i'' first rows of ''T<sub>i</sub>''.
| |
| | |
| Let ''V<sub>i</sub>'' be the (''m'' + ''n'' − 2''i'') × (''m'' + ''n'' − ''i'') matrix defined as follows. First we add (''i'' + 1) columns of zeros to the right of the (''m'' + ''n'' - 2''i'' - 1) × (''m'' + ''n'' - 2''i'' - 1) [[identity matrix]]. Then we border the bottom of the resulting matrix by a row consisting in (''m'' + ''n'' - ''i'' - 1) zeros followed by ''X<sup>i</sup>'', ''X''<sup>''i'' − 1</sub>, ..., ''X'', 1:
| |
| :<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}.</math>
| |
| | |
| With this notation, the ''i''-th ''subresultant polynomial'' is the determinant of the matrix product ''V<sub>i</sub>T<sub>i</sub>''. Its coefficient of degree ''j'' is the determinant of the square submatrix of ''T<sub>i</sub>'' consisting in its ''m'' + ''n'' - 2''i'' - 1 first rows and the (''m'' + ''n'' - ''i'' - ''j'')-th row.
| |
| | |
| ====Sketch of the proof====
| |
| It is not obvious that, as defined, the subresultants have the desired properties. In fact 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 ''T<sub>i</sub>'' are the vectors of the coefficients of some polynomials belonging to the image of <math>\varphi_i</math>. The definition of the ''i''-th subresultant polynomial ''S<sub>i</sub>'' shows that the vector of its coefficients is a linear combination of these column vectors, and thus that ''S<sub>i</sub>'' belongs to the image of <math>\varphi_i.</math>
| |
| | |
| If the degree of the GCD is greater than ''i'', then [[Bézout's identity]] shows that every non zero polynomial in the image of <math>\varphi_i</math> has a degree larger than ''i''. This implies that ''S<sub>i</sub>''=0.
| |
| | |
| If, on the other hand, the degree of the GCD is ''i'', then Bézout's identity again allows to prove that the multiples of the GCD that have a degree lower than ''m'' + ''n'' - ''i'' are in the image of <math>\varphi_i</math>. The vector space of these multiples has the dimension ''m'' + ''n'' - 2''i'' and has a base of polynomials of pairwise different degrees, not smaller than ''i''. This implies that the submatrix of the ''m'' + ''n'' - 2''i'' first rows of the column echelon form of ''T<sub>i</sub>'' is the identity matrix and thus that ''s<sub>i</sub>'' is not 0. Thus ''S<sub>i</sub>'' is a polynomial in the image of <math>\varphi_i</math>, 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====
| |
| {{main|Square-free factorization}}
| |
| | |
| Most [[root-finding algorithm]]s behave badly with polynomials that have [[multiple root]]s. It is therefore useful to detect and remove them before calling a root-finding algorithm. A GCD computation allows to detect the existence of multiple roots, because the multiple roots of a polynomial are the roots of the GCD of the polynomial and its [[formal derivative|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
| |
| :<math>f=\prod_{i=1}^{\deg(f)} f_i^i</math>
| |
| where, for each ''i'', the polynomial ''f''<sub>''i''</sub> either is 1 if ''f'' does not have any root of multiplicity ''i'' or is a square-free polynomial (that is a polynomial without multiple root) whose roots are exactly the roots of multiplicity ''i'' of ''f'' (see [[Square-free polynomial#Yun's algorithm|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====
| |
| {{main|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
| |
| :<math>r_{i+1}:=\text{rem}(r_{i-1},r_{i})</math>
| |
| of Euclid's algorithm by
| |
| :<math>r_{i+1}:=-\text{rem}(r_{i-1},r_{i}).</math>
| |
| | |
| Let ''V''(''a'') be the number of changes of signs in the sequence, when evaluated at a point ''a''. Sturm's theorem asserts that ''V''(''a'')-''V''(''b'') is the number of real roots of the polynomial in the interval [''a'',''b'']. Thus the Sturm sequence allows to compute 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 over 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===
| |
| {{see also|Content (algebra)|Gauss's lemma (polynomial)}}
| |
| | |
| The ''content'' of a polynomial ''p'' ∈ ''R''[''X''], denoted "cont(''p'')", is the GCD of its coefficients. A polynomial ''q'' ∈ ''F''[''X''] may be written
| |
| | |
| :<math>q = \frac{p}{c}</math>
| |
| where ''p'' ∈ ''R''[''X''] and ''c'' ∈ ''R'': it suffices to take for ''c'' a multiple of all denominators of the coefficients of ''q'' (for example their product) and ''p'' = ''cq''. The ''content'' of ''q'' is defined as:
| |
| :<math>\text{cont} (q) =\frac{\text{cont} (p)}{c}.</math>
| |
| In both cases, the content is defined up to the multiplication by a [[unit (ring theory)|unit]] of ''R''.
| |
| | |
| The ''primitive part'' of a polynomial in ''R''[''X''] or ''F''[''X''] is defined by
| |
| :<math>\text{primpart} (p) =\frac{p}{\text{cont} (p)}.</math>
| |
| | |
| In both cases, it is a polynomial in ''R''[''X''] that is ''primitive'', which means that 1 is a GCD of its coefficients.
| |
| | |
| Thus every polynomial in ''R''[''X''] or ''F''[''X''] may be factorized as
| |
| :<math>p =\text{cont} (p)\,\text{primpart} (p),</math>
| |
| and this factorization is unique up to the multiplication of the content by a unit of ''R'' 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
| |
| :<math>\text{primpart} (pq)=\text{primpart} (p)\,\text{primpart}(q)</math>
| |
| and
| |
| :<math>\text{cont} (pq)=\text{cont} (p)\,\text{cont}(q).</math>
| |
| | |
| ===Relation between the GCD over ''R'' and over ''F''===
| |
| | |
| The relations of the preceding section implies a strong relation between the GCD's in ''R''[''X''] and in ''F''[''X'']. In order to avoid ambiguities, the notation "''gcd''" will be indexed, in the following, by the ring in which the GCD is computed.
| |
| | |
| If ''q''<sub>1</sub> and ''q''<sub>2</sub> belong to ''F''[''X''], then
| |
| :<math>\text{primpart}(\text{gcd}_{F[X]}(q_1,q_2))=\text{gcd}_{R[X]}(\text{primpart}(q_1),\text{primpart}(q_2)).</math>
| |
| | |
| If ''p''<sub>1</sub> and ''p''<sub>2</sub> belong to ''R''[''X''], then
| |
| :<math>\text{gcd}_{R[X]}(p_1,p_2)=\text{gcd}_{R}(\text{cont}(p_1),\text{cont}(p_2))\,\text{gcd}_{R[X]}(\text{primpart}(p_1),\text{primpart}(p_2)),</math>
| |
| and
| |
| :<math>\text{gcd}_{R[X]}(\text{primpart}(p_1),\text{primpart}(p_2))=\text{primpart}(\text{gcd}_{F[X]}(p_1,p_2)).</math>
| |
| | |
| Thus the computation of polynomial GCD's is essentially the same problem over ''F''[''X''] and over ''R''[''X''].
| |
| | |
| 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 to simplify 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 in replacing Euclidean division, which introduces fractions, by a so-called ''pseudo-division'', and replacing the remainder sequence of Euclid's algorithm by so-called ''pseudo-remainder sequences'' (see [[#Pseudo-remainder sequences|below]]).
| |
| | |
| ===Proof that GCD exist for multivariate polynomials===
| |
| | |
| In the previous section we have seen that the GCD of polynomials in ''R''[''X''] may be deduced from GCD's in ''R'' and in ''F''[''X'']. A closer look on the proof shows that this allows to prove the existence of GCD's in ''R''[''X''], if they exist in ''R'' and in ''F''[''X'']. In particular, if GCD's exist in ''R'', and if ''X'' is reduced to one variable, this proves that GCD's exist in ''R''[''X''] (Euclid's algorithm proves the existence of GCD's in ''F''[''X'']).
| |
| | |
| A polynomial in ''n'' variables may be considered as a univariate polynomial over the ring of polynomials in (''n'' − 1) variables. Thus a recursion on the number of variables shows that if GCD's exists and may be computed in ''R'', then they exist and may be computed in every multivariate polynomial rings over ''R''. In particular, if ''R'' is either the ring of the integers or a field, then GCD's exist in ''R''[''x''<sub>1</sub>,..., ''x<sub>n</sub>''], 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 provides an algorithm, because there is no general algorithm to factorize univariate polynomials over a field (there are examples of fields for which it does not exist any factorization algorithm for the univariate polynomials).
| |
| | |
| ==Pseudo-remainder sequences==
| |
| | |
| In this section, we consider an [[integral domain]] ''Z'' (typically the ring '''Z''' of the integers) and its field of fractions ''Q'' (typically the field '''Q''' of the rational numbers). Given two polynomials ''A'' and ''B'' in the univariate polynomial ring ''Z''[''X''], the Euclidean division (over ''Q'') of ''A'' by ''B'' provides a quotient and a remainder which may not belong to ''Z''[''X''].
| |
| | |
| For, if one applies Euclid's algorithm to
| |
| :<math>X^8+X^6-3 X^4-3 X^3+8 X^2+2 X-5</math>
| |
| and
| |
| :<math>3 X^6+5 X^4-4 X^2-9 X+21,</math>
| |
| the successive remainders of Euclid's algorithm are
| |
| :<math>-\frac{5}{9}X^4+\frac{1}{9}X^2-\frac{1}{3},</math>
| |
| :<math>-\frac{117}{25}X^2-9X+\frac{441}{25},</math>
| |
| :<math>\frac{233150}{19773}X-\frac{102500}{6591},</math>
| |
| :<math>-\frac{1288744821}{543589225}.</math>
| |
| 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 ''Z''[''X''].
| |
| | |
| If <math>\deg(A)=a</math> and <math>\deg(B)=b</math> and ''a''≥''b'', the '''pseudo-remainder''' of the pseudo-division of ''A'' by ''B'', denoted by prem(''A'',''B'') is
| |
| :<math>\text{prem}(A,B)=\text{rem}(\text{lc}(B)^{a-b+1}A,B),</math>
| |
| where lc(''B'') is the leading coefficient of ''B'' (the coefficient of ''X''<sup>''b''</sup>).
| |
| | |
| The pseudo-remainder of the pseudo-division of two polynomials in ''Z''[''X''] belongs always to ''Z''[''X''].
| |
| | |
| A '''pseudo-remainder sequence''' is the sequence of the (pseudo) remainders ''r''<sub>''i''</sub> obtained by replacing the instruction
| |
| :<math>r_{i+1}:=\text{rem}(r_{i-1},r_{i})</math>
| |
| of Euclid's algorithm by
| |
| :<math>r_{i+1}:=\frac{\text{prem}(r_{i-1},r_{i})}{\alpha},</math>
| |
| where ''α'' is an element of ''Z'' that divides exactly every coefficient of the numerator. Different choices of ''α'' 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 ''Q''), the last non zero term in a pseudo-remainder sequence is a GCD (in ''Q''[''X'']) of the input polynomials. Therefore pseudo-remainder sequences allows to compute GCD's in ''Q''[''X''] without introducing fractions in ''Q''.
| |
| | |
| ===Trivial pseudo-remainder sequence===
| |
| | |
| The simplest (to define) remainder sequence consists in taking always ''α''=1. In practice, it is not interesting, as the size of the coefficients grow 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
| |
| :<math>-15\, X^4+3\, X^2-9,</math>
| |
| :<math>15795\, X^2+30375\, X-59535,</math>
| |
| :<math>1254542875143750\, X-1654608338437500,</math>
| |
| :<math>12593338795500743100931141992187500.</math>
| |
| The number of digits of the coefficients of the successive remainders is more than doubled at each iteration of the algorithm. This is a typical behavior of the trivial pseudo-remainder sequences.
| |
| | |
| === Primitive pseudo-remainder sequence===
| |
| | |
| The ''primitive pseudo-remainder sequence'' consists in taking for ''α'' the content of the numerator. Thus all the ''r''<sub>''i''</sub> 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 ''Z'', 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
| |
| :<math>-5\,X^4+X^2-3,</math>
| |
| :<math>13\,X^2+25\,X-49,</math>
| |
| :<math>4663\,X-6150,</math>
| |
| :<math>1.</math>
| |
| 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===
| |
| | |
| The subresultant pseudo-remainder sequence consists in choosing ''α'' is such a way that every ''r''<sub>''i''</sub> is a subresultant polynomial. Surprisingly, the computation of ''α'' 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 pseudo-remainder sequence are rarely much larger than those of the primitive pseudo-remainder sequence. As GCD computations in ''Z'' are not needed, the subresultant pseudo-remainder sequence is the pseudo-remainder sequence which gives the most efficient computation.
| |
| | |
| With the same input as in the preceding sections, the successive remainders are
| |
| :<math>-15\,X^4+3\,X^2-9,</math>
| |
| :<math>65\,X^2+125\,X-245,</math>
| |
| :<math>9326\,X-12300,</math>
| |
| :<math>260708.</math>
| |
| 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 pseudo-remainder sequence is given below. In this algorithm, the input (''a'', ''b'') is a pair of polynomials in ''Z''[X]. The ''r''<sub>''i''</sub> are the successive pseudo remainders in ''Z''[X], the variables ''i'' and ''d''<sub>''i''</sub> are non negative integers, and the Greek letters denote elements in ''Z''. 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 ''Z''[X]. Finally the divisions denoted / are always exact and have their result either in ''Z''[X] or in ''Z''.
| |
| | |
| {{quotation|
| |
| <math>r_0:=a;\quad r_1:=b;\quad i:=1;</math>
| |
| <br>
| |
| <math>d_1:=\deg(r_0)-\deg(r_1);\quad \gamma_1:=\text{lc}(r_1); \quad \beta_1:=(-1)^{d_1+1};\quad \psi_1=-1;</math>
| |
| <br>
| |
| '''''while''''' <math>r_i \neq 0</math> '''''do'''''
| |
| :<math>r_{i+1}:=\text{rem}(\gamma^{d_i +1}r_{i-1},r_{i})/\beta_i;</math>
| |
| :<math> i:=i+1;</math>
| |
| :<math> d_{i}:=\deg(r_{i-1})-\deg(r_{i}); \quad \gamma_{i}:=\text{lc}(r_{i});\quad \psi_{i}:=(-\gamma_i)^{d_{i-1}}/\psi_{i-1}^{d_{i-1}-1}; \quad \beta_i:=-\gamma_{i-1}\psi_i^{d_i}</math>
| |
| '''''end do.'''''
| |
| }}
| |
| | |
| This algorithm computes not only the greatest common divisor (the last non zero {{math|''r''<sub>''i''</sub>}}), but also all the subresultant polynomials: The remainder {{math|''r''<sub>''i''</sub>}} is the {{math|(deg(''r''<sub>''i''-1</sub>)-1)}}-th subresultant polynomial. If {{math|deg(''r''<sub>''i''</sub>)<deg(''r''<sub>''i''-1</sub>)-1}}, the {{math|deg(''r''<sub>''i''</sub>)}}-th subresultant polynomial is {{math|lc(''r''<sub>''i''</sub>)<sup>deg(''r''<sub>''i''-1</sub>)-deg(''r''<sub>''i''</sub>)-1</sup>''r''<sub>''i''</sub>}}. All the other subresultant polynomials are null.
| |
| | |
| ==Modular GCD algorithm==
| |
| {{expand section|date=August 2012}}
| |
| | |
| ==See also==
| |
| * [[List of polynomial topics]]
| |
| * [[Multivariate division algorithm]]
| |
| | |
| ==References==
| |
| {{reflist|1}}
| |
| *{{cite book|first1=James H.|last1=Davenport|author1-link=James H. Davenport|first2=Yvon|last2=Siret|first3=Èvelyne|last3=Tournier|title=Computer algebra: systems and algorithms for algebraic computation|others=Translated from the French by A. Davenport and J.H. Davenport|year=1988|publisher=Academic Press|isbn=978-0-12-204230-0}}
| |
| *{{cite book
| |
| |author=[[Donald E. Knuth|Knuth, Donald E]]
| |
| |title=Seminumerical Algorithms
| |
| |series=The Art of Computer Programming
| |
| |volume=2
| |
| |edition=Third
| |
| |location=Reading, Massachusetts
| |
| |publisher=Addison-Wesley
| |
| |year=1997
| |
| |pages=439–461, 678–691<!-- xiv+762 -->
| |
| |isbn=0-201-89684-2}}
| |
| * {{citation|first1=Rudiger|last1=Loos|chapter=Generalized polynomial remainder sequences|title=Computer Algebra|publisher=Springer Verlag|year=1982|editor1 =B. Buchberger|editor2=R. Loos|editor3=G. Collins}}
| |
| | |
| [[Category:Polynomials]]
| |
| [[Category:Computer algebra]]
| |