AngouriMath
PolynomialGcd
Description
Summary
The greatest common divisor of two polynomials in several variables over the
rationals, and the cancellation of a quotient that it makes possible:
(x^2 + 2xy + y^2) / (x^2 - y^2) is (x + y) / (x - y) (#55).
rationals, and the cancellation of a quotient that it makes possible:
Remarks
are polynomials in the rest, so the algorithm is the univariate one applied down a
recursion on the variable count. What it cannot be is the plain Euclidean algorithm
over that coefficient ring: pseudo-division multiplies through by the leading
coefficient every step, and the coefficients of the remainder sequence then grow
exponentially in the degree. The classic example is Knuth's, where two degree-8
polynomials over the integers produce a remainder with a coefficient near 10^35.
splits as the gcd of the contents times the gcd of the primitive parts, because the
content carries everything free of the main variable and the primitive parts carry
nothing of it; so the content is taken out first, recursively, in one variable
fewer. And within the remainder sequence the subresultant coefficients are divided
out at each step — that division is exact, since what is left is a subresultant, and
it is what turns exponential growth into linear. Knuth, TAOCP vol. 2,
§4.6.1, algorithms C and E; Geddes, Czapor and Labahn, Algorithms for Computer
Algebra, §7.3.
divided out of both sides and multiplied back, and the quotient is only used when
both come out equal to what they started as. A divisor that is merely common and
not greatest costs an incomplete cancellation; one that is not a divisor at all
would be a wrong answer, and is the thing the check is there to stop.
Members
MaxComplexity
FieldMaxSteps
FieldTryCancel(AngouriMath.Entity,AngouriMath.Entity,AngouriMath.Entity@)
Method
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 1953 pages online