HOME

TheInfoList



OR:

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two
polynomial In mathematics, a polynomial is an expression (mathematics), expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addition, subtrac ...
s is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of two integers. In the important case of
univariate In mathematics, a univariate object is an expression, equation, function or polynomial involving only one variable. Objects involving more than one variable are multivariate. In some cases the distinction between the univariate and multivariate ...
polynomials over a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
the polynomial GCD may be computed, like for the integer GCD, by the
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
using
long division In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals (Positional notation) that is simple enough to perform by hand. It breaks down a division problem into a series of easier ste ...
. The polynomial GCD is defined only
up to Two mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respect to ''R'' a ...
the multiplication by an invertible constant. The similarity between the integer GCD and the polynomial GCD allows extending to univariate polynomials all the properties that may be deduced from the Euclidean algorithm and
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
s of the GCD of two polynomials are the common roots of the two polynomials, and this provides information on the roots without computing them. For example, the
multiple root In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial has a root at a given point is the multiplicity of that root. The notion of multipl ...
s of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow computing the square-free factorization of the polynomial, which provides polynomials whose roots are the roots of a given multiplicity of the original polynomial. The greatest common divisor may be defined and exists, more generally, for
multivariate polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...
s over a field or the ring of integers, and also over a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. 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 Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
on the number of variables to reduce the problem to a variant of the Euclidean algorithm. They are a fundamental tool in computer algebra, because computer algebra systems use them systematically to simplify fractions. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need for efficiency of computer algebra systems.


General definition

Let and be polynomials with
coefficients In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
in an
integral domain In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
, typically a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
or the integers. A greatest common divisor of and is a polynomial that divides and , and such that every common divisor of and also divides . Every pair of polynomials (not both zero) has a GCD if and only if is a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. If is a field and and are not both zero, a polynomial is a greatest common divisor if and only if it divides both and , and it has the greatest degree among the polynomials having this property. If , the GCD is 0. However, some authors consider that it is not defined in this case. The greatest common divisor of and is usually denoted "". The greatest common divisor is not unique: if is a GCD of and , then the polynomial is another GCD if and only if there is an invertible element of such that :f=u d and :d=u^ f. 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. However, since there is no natural
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexi ...
for polynomials over an integral domain, one cannot proceed in the same way here. For
univariate In mathematics, a univariate object is an expression, equation, function or polynomial involving only one variable. Objects involving more than one variable are multivariate. In some cases the distinction between the univariate and multivariate ...
polynomials over a field, one can additionally require the GCD to be monic (that is to have 1 as its coefficient of the highest degree), but in more general cases there is no general convention. Therefore, equalities like or are common abuses of notation which should be read " is a GCD of and " and " and have the same set of GCDs as and ". In particular, means that the invertible constants are the only common divisors. In this case, by analogy with the integer case, one says that and are .


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 In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. *If is any common divisor of and , then divides their GCD. *\gcd(p,q)= \gcd(q,p). *\gcd(p, q)= \gcd(q,p+rq) for any polynomial . This property is at the basis of the proof of Euclidean algorithm. *For any invertible element of the ring of the coefficients, \gcd(p,q)=\gcd(p,kq). *Hence \gcd(p,q)=\gcd(a_1p+b_1q,a_2p+b_2q) 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 and over a field, there exist polynomials and , such that \gcd(p,q)=ap+bq and \gcd(p,q) divides every such linear combination of and ( 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)).


GCD by hand computation

There are several ways to find the greatest common divisor of two polynomials. Two of them are: #''
Factorization of polynomials In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
'', 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. #The ''
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
'', 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 and . : : Thus, their GCD is .


Euclidean algorithm

Factoring polynomials can be difficult, especially if the polynomials have a large degree. The
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
is a method that works for any pair of polynomials. It makes repeated use of
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
. 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 and , one can suppose (otherwise, the GCD is ), and :\deg(b(x)) \le \deg(a(x)) \,. The Euclidean division provides two polynomials , the ''quotient'' and , the ''remainder'' such that :a(x) = q_0(x)b(x) + r_0(x)\qquad\text\qquad \deg(r_0(x)) < \deg(b(x)) A polynomial divides both and if and only if it divides both and . 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 and so on. At each stage we have :\deg(a_)+\deg(b_) < \deg(a_)+\deg(b_), so the sequence will eventually reach a point at which :b_N(x) = 0 and one has got the GCD: :\gcd(a,b)=\gcd(a_1,b_1)=\cdots=\gcd(a_N, 0)=a_N . Example: finding the GCD of and : : : Since is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is . 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 In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common ...
, 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
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
s,
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ratio ...
s, elements of a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, or must belong to some
finitely generated field extension In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ' ...
of one of the preceding fields. If the coefficients are floating-point numbers that represent
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s 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 In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorit ...
result; in this cases other techniques may be used, usually based on
singular value decomposition In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is related ...
.


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 In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. ...
. A third reason is that the theory and the algorithms for the multivariate case and for coefficients in a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
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 In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
for computing GCDs, is very similar to
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
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 "deg(...)" 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 domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. ...
s. Like for the integers, the Euclidean division of the polynomials may be computed by the
long division In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals (Positional notation) that is simple enough to perform by hand. It breaks down a division problem into a series of easier ste ...
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 ), 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 and 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 In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
for computing GCDs. Starting from two polynomials ''a'' and ''b'', Euclid's algorithm consists of recursively replacing the pair by (where "" 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: In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder: The sequence of the degrees of the is strictly decreasing. Thus after, at most, steps, one get a null remainder, say . As and have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs have the same set of common divisors. The common divisors of and are thus the common divisors of and 0. Thus is a GCD of and . 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 mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are princi ...
. 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 and , 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 we have :r_i=as_i+bt_i :s_it_-t_is_=s_it_-t_is_, the latter equality implying :s_it_-t_is_=(-1)^i. The assertion on the degrees follows from the fact that, at every iteration, the degrees of and increase at most as the degree of 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 an algebraic extension of a field , generated by an element whose minimal polynomial has degree . The elements of are usually represented by univariate polynomials over of degree less than . The addition in is simply the addition of polynomials: :a+_Lb=a+_b. The multiplication in is the multiplication of polynomials followed by the division by : :a\cdot_Lb=\operatorname(a._b,f). The inverse of a non zero element of is the coefficient in Bézout's identity , which may be computed by extended GCD algorithm. (the GCD is 1 because the minimal polynomial is irreducible). The degrees inequality in the specification of extended GCD algorithm shows that a further division by is not needed to get deg() < deg().


Subresultants

In the case of univariate polynomials, there is a strong relationship between the greatest common divisors and
resultant In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root (possibly in a field extension), or, equivalently, a common factor (over ...
s. 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 ''i''-th ''subresultant polynomial'' ''Si''(''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'' ''si''(''P'' ,''Q'') is the coefficient of degree ''i'' of ''Si''(''P'', ''Q''). They have the property that the GCD of ''P'' and ''Q'' has a degree ''d'' if and only if :s_0(P,Q)=\cdots=s_(P,Q) =0 \ , s_d(P,Q)\neq 0. In this case, ''Sd''(''P'' ,''Q'') is a GCD of ''P'' and ''Q'' and :S_0(P,Q)=\cdots=S_(P,Q) =0. Every coefficient of the subresultant polynomials is defined as the determinant of a submatrix of the
Sylvester matrix In mathematics, a Sylvester matrix is a matrix associated to two univariate polynomials with coefficients in a field or a commutative ring. The entries of the Sylvester matrix of two polynomials are coefficients of the polynomials. The determinant ...
of ''P'' and ''Q''. This implies 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 :\deg(P)=\deg(\varphi(P)) and :\deg(Q)=\deg(\varphi(Q)), 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 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 In mathematics, Hadamard's inequality (also known as Hadamard's theorem on determinants) is a result first published by Jacques Hadamard in 1893.Maz'ya & Shaposhnikova It is a bound on the determinant of a matrix whose entries are complex numbe ...
, 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 In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
(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_i the ''K'' vector space of dimension ''i'' of polynomials of degree less than ''i''. For non-negative integer ''i'' such that ''i'' ≤ ''m'' and ''i'' ≤ ''n'', let :\varphi_i:\mathcal_ \times \mathcal_ \rightarrow \mathcal_ be the linear map such that :\varphi_i(A,B)=AP+BQ. The
resultant In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root (possibly in a field extension), or, equivalently, a common factor (over ...
of ''P'' and ''Q'' is the determinant of the
Sylvester matrix In mathematics, a Sylvester matrix is a matrix associated to two univariate polynomials with coefficients in a field or a commutative ring. The entries of the Sylvester matrix of two polynomials are coefficients of the polynomials. The determinant ...
, which is the (square) matrix of \varphi_0 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 \varphi_i. Let us describe these matrices more precisely; Let ''p''''i'' = 0 for ''i'' < 0 or ''i'' > ''m'', and ''q''''i'' = 0 for ''i'' < 0 or ''i'' > ''n''. The
Sylvester matrix In mathematics, a Sylvester matrix is a matrix associated to two univariate polynomials with coefficients in a field or a commutative ring. The entries of the Sylvester matrix of two polynomials are coefficients of the polynomials. The determinant ...
is the (''m'' + ''n'') × (''m'' + ''n'')-matrix such that the coefficient of the ''i''-th row and the ''j''-th column is ''p''''m''+''j''−''i'' for ''j'' ≤ ''n'' and ''q''''j''−''i'' for ''j'' > ''n'': :S=\begin p_m & 0 & \cdots & 0 & q_n & 0 & \cdots & 0 \\ p_ & p_m & \cdots & 0 & q_ & q_n & \cdots & 0 \\ p_ & p_ & \ddots & 0 & q_ & q_ & \ddots & 0 \\ \vdots &\vdots & \ddots & p_m & \vdots &\vdots & \ddots & q_n \\ \vdots &\vdots & \cdots & p_ & \vdots &\vdots & \cdots & q_\\ 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. The matrix ''Ti'' of \varphi_i 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'' ''si'' is the determinant of the ''m'' + ''n'' − 2''i'' first rows of ''Ti''. Let ''Vi'' 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 In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
. Then we border the bottom of the resulting matrix by a row consisting in (''m'' + ''n'' − ''i'' − 1) zeros followed by ''Xi'', ''X''''i''−1, ..., ''X'', 1: :V_i=\begin 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^& \cdots & 1 \end. With this notation, the ''i''-th ''subresultant polynomial'' is the determinant of the matrix product ''ViTi''. Its coefficient of degree ''j'' is the determinant of the square submatrix of ''Ti'' 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. 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 ''Ti'' are the vectors of the coefficients of some polynomials belonging to the image of \varphi_i. The definition of the ''i''-th subresultant polynomial ''Si'' shows that the vector of its coefficients is a linear combination of these column vectors, and thus that ''Si'' belongs to the image of \varphi_i. 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 \varphi_i has a degree larger than ''i''. This implies that ''Si''=0. If, on the other hand, the degree of the GCD is ''i'', then Bézout's identity again allows proving that the multiples of the GCD that have a degree lower than ''m'' + ''n'' − ''i'' are in the image of \varphi_i. 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 ''Ti'' is the identity matrix and thus that ''si'' is not 0. Thus ''Si'' 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 algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbe ...
s behave badly with polynomials that have
multiple root In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial has a root at a given point is the multiplicity of that root. The notion of multipl ...
s. 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 In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
. 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_^ f_i^i where, for each ''i'', the polynomial ''f''''i'' 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 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 In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
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_:=\operatorname(r_,r_) of Euclid's algorithm by :r_:=-\operatorname(r_,r_). 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 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 In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
''R'', typically the ring of the integers, and over its
field of fractions In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the field ...
''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 ''p'' ∈ ''R'' 'X'' denoted "cont(''p'')", is the GCD of its coefficients. A polynomial ''q'' ∈ ''F'' 'X''may be written :q = \frac 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: :\operatorname (q) =\frac. In both cases, the content is defined up to the multiplication by a
unit Unit may refer to: Arts and entertainment * UNIT, a fictional military organization in the science fiction television series ''Doctor Who'' * Unit of action, a discrete piece of action (or beat) in a theatrical presentation Music * ''Unit'' (a ...
of ''R''. The ''primitive part'' of a polynomial in ''R'' 'X''or ''F'' 'X''is defined by :\operatorname (p) =\frac. 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 :p =\operatorname (p)\,\operatorname (p), 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 :\operatorname (pq)=\operatorname (p) \operatorname(q) and :\operatorname (pq)=\operatorname (p) \operatorname(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 ''R'' 'X''and in ''F'' 'X'' To avoid ambiguities, the notation "''gcd''" will be indexed, in the following, by the ring in which the GCD is computed. If ''q''1 and ''q''2 belong to ''F'' 'X'' then :\operatorname(\gcd_(q_1,q_2))=\gcd_(\operatorname(q_1),\operatorname(q_2)). If ''p''1 and ''p''2 belong to ''R'' 'X'' then :\gcd_(p_1,p_2)=\gcd_R(\operatorname(p_1),\operatorname(p_2)) \gcd_(\operatorname(p_1),\operatorname(p_2)), and :\gcd_(\operatorname(p_1),\operatorname(p_2))=\operatorname(\gcd_(p_1,p_2)). 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 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 ''R'' 'X''may be deduced from GCDs in ''R'' and in ''F'' 'X'' A closer look on the proof shows that this allows us to prove the existence of GCDs in ''R'' 'X'' if they exist in ''R'' and in ''F'' 'X'' In particular, if GCDs exist in ''R'', and if ''X'' is reduced to one variable, this proves that GCDs exist in ''R'' 'X''(Euclid's algorithm proves the existence of GCDs 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 GCDs exist and may be computed in ''R'', then they exist and may be computed in every multivariate polynomial ring over ''R''. In particular, if ''R'' is either the ring of the integers or a field, then GCDs exist in ''R'' 'x''1,..., ''xn'' 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 In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
''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 the following polynomials :X^8+X^6-3 X^4-3 X^3+8 X^2+2 X-5 and :3 X^6+5 X^4-4 X^2-9 X+21, the successive remainders of Euclid's algorithm are :\begin&-\tfracX^4+\tfracX^2-\tfrac,\\ &-\tfracX^2-9X+\tfrac,\\ &\tfracX-\tfrac,\\ &-\tfrac.\end 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 \deg(A)=a and \deg(B)=b and ''a'' ≥ ''b'', the pseudo-remainder of the pseudo-division of ''A'' by ''B'', denoted by prem(''A'',''B'') is :\operatorname(A,B)=\operatorname(\operatorname(B)^A,B), where is the leading coefficient of ''B'' (the coefficient of ''X''''b''). 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''''i'' obtained by replacing the instruction :r_:=\operatorname(r_,r_) of Euclid's algorithm by :r_:=\frac, 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 nonzero term in a pseudo-remainder sequence is a GCD (in ''Q'' 'X'' of the input polynomials. Therefore, pseudo-remainder sequences allows computing GCD's in ''Q'' 'X''without introducing fractions in ''Q''. 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
resultant In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root (possibly in a field extension), or, equivalently, a common factor (over ...
s and
subresultant In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common di ...
s, or for using
Sturm's theorem In mathematics, the Sturm sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of loc ...
. This control can be done either by replacing by its absolute value in the definition of the pseudo-remainder, or by controlling the sign of (if divides all coefficients of a remainder, the same is true for ).


Trivial pseudo-remainder sequence

The simplest (to define) remainder sequence consists in taking always . 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 ''α'' the content of the numerator. Thus all the ''r''''i'' 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 :-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 ''α'' in such a way that every ''r''''i'' 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 sequence are rarely much larger than those of the primitive pseudo-remainder sequence. As GCD computations in ''Z'' 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 is a pair of polynomials in ''Z'' The are the successive pseudo remainders in ''Z'' the variables ''i'' and 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'' Finally the divisions denoted / are always exact and have their result either in ''Z'' or in ''Z''. 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 ), but also all the subresultant polynomials: The remainder is the -th subresultant polynomial. If , the -th subresultant polynomial is . 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 ''a'' ≥ ''b'', the modified pseudo-remainder prem2(''A'', ''B'') of the pseudo-division of ''A'' by ''B'' is :\operatorname(A,B)=-\operatorname(, \operatorname(B), ^A,B), where , lc(''B''), is the absolute value of the leading coefficient of ''B'' (the coefficient of ''X''''b''). 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(A,B) instead of \operatorname(A,B).


Modular GCD algorithm

If ''f'' and ''g'' are polynomials in ''F'' 'x''for some finitely generated field ''F'', the Euclidean Algorithm is the most natural way to compute their GCD. However, modern computer algebra systems only use it if ''F'' is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if ''F'' is not
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb Traditionally, a finite verb (from la, fīnītus, past particip ...
then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in ''F'' tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by ''b'' leads to a rational number whose denominator is bounded by ''b''2, so in the worst case, the bit size could nearly double with just one operation. To expedite the computation, take a ring ''D'' for which ''f'' and ''g'' are in ''D'' 'x'' and take an ideal ''I'' such that ''D''/''I'' is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
,
rational reconstruction Rational reconstruction is a philosophical term with several distinct meanings. It is found in the work of Jürgen Habermas and Imre Lakatos. Habermas For Habermas, rational reconstruction is a philosophical and linguistic method that systemat ...
, etc.) one can recover the GCD of ''f'' and ''g'' from its image modulo a number of ideals ''I''. One can prove that this works provided that one discards modular images with non-minimal degrees, and avoids ideals ''I'' modulo which a leading coefficient vanishes. Suppose F = \mathbb(\sqrt), D = \mathbb
sqrt In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . E ...
/math>, f = \sqrtx^3 - 5 x^2 + 4x + 9 and g = x^4 + 4 x^2 + 3\sqrtx - 6. If we take I=(2) then D/I is a
finite ring In mathematics, more specifically abstract algebra, a finite ring is a ring that has a finite number of elements. Every finite field is an example of a finite ring, and the additive part of every finite ring is an example of an abelian finite gro ...
(not a field since I is not maximal in D). The Euclidean algorithm applied to the images of f,g in (D/I) /math> succeeds and returns 1. This implies that the GCD of f,g in F /math> 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 Multivariate may refer to: In mathematics * Multivariable calculus * Multivariate function * Multivariate polynomial In computing * Multivariate cryptography * Multivariate division algorithm * Multivariate interpolation * Multivariate optical ...


References

* * * * * * * {{Polynomials Polynomials Computer algebra