homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightlinear algebra

Polynomial Greatest Common Divisor

The calculator gives the greatest common divisor (GCD) of two input polynomials.

This page exists due to the efforts of the following people:

Anton
Anton

The calculator produce the polynomial greatest common divisor using Euclid method and polynomial division. The polynomial coefficients are integers, fractions or complex numbers with integer or fractional real and imaginary parts. The result is polynomial, which divides two input polynomials without remainder or 1 if there is no such polynomial.

PLANETCALC, Polynomial greatest common divisor.

Polynomial greatest common divisor.

Pseudoremainders correction algorithm.

Coefficients GCD will be calculated on each step.

Result
 
Remainders

The phenomenon of explosive coefficient growth.

Calculating GCD for the polynomials of higher degrees, the polynomial remainder coefficients grow explosively. You may see it even in this calculator results with default input data the remainder sequence contain big fractions. To eliminate the fractions and reduce integer coefficients one can use pseudo division with a remainder coefficient reduction algorithm. 3 pseudo remainder calculation algorithms are available in this calculator, non counting trivial pseudo division without any coefficient reduction.

Best coefficient reduction gives content reduction method, which simply divides all the terms by the coefficients GCD. But the computing cost of this method can be unacceptable high for higher degree polynomials with complex coefficients since Euclidean algorithm is applied in every iteration for every coefficient.

As tradeoff variant of coefficient growth controlling are algorithms based on subresultant PRS. The calculator employs two of them (Algorithm 1 and Algorithm 3), described by W.S. Brown in the article: The Subresultant PRS Algorithm1.
To estimate algorithm effectiveness the calculator produces the pseudo remainders table with with polynomial content for every remainder. The lesser content the higher algorithm effectiveness.


  1. W.S. Brown, Bell Laboratories. ACM Transactions on Mathematical Software, Vol 4, No 3, September 1978, p.p. 237-249 

Comments