Polynomial Greatest Common Divisor
The calculator gives the greatest common divisor (GCD) of two input polynomials.
The calculator produces the polynomial greatest common divisor using the 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.
The phenomenon of explosive coefficient growth.
For calculating GCD for the polynomials of higher degrees, the polynomial remainder coefficients grow explosively. Even in this calculator, you may see it with default input data; the remainder sequence contains 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, not counting trivial pseudo division without any coefficient reduction.
Best coefficient reduction gives content reduction method, which divides all the terms by the coefficients GCD. But the computing cost of this method can be unacceptably high for higher degree polynomials with complex coefficients since the Euclidean algorithm is applied in every iteration for every coefficient.
As the tradeoff variant of coefficient growth controlling is 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 Algorithm^{1}.
The calculator produces the pseudo remainders table with polynomial content for every remainder to estimate algorithm effectiveness. The lesser content, the higher algorithm effectiveness.

W.S. Brown, Bell Laboratories. ACM Transactions on Mathematical Software, Vol 4, No 3, September 1978, p.p. 237249 ↩
Comments