AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

SquareFreeDecomposition

← Back to list of classes

Description

Summary

Splits a polynomial into square-free parts: f = a_1 * a_2^2 * a_3^3 * ... with
each a_i square-free and any two of them coprime.

Remarks

The first step of every factorisation, and useful on its own. A repeated factor is
exactly a factor shared with the derivative — (x - r)^k contributes
(x - r)^(k-1) to f' — so gcd(f, f') collects every repetition and
dividing by it leaves each distinct factor standing once. That is why factoring only
ever has to deal with square-free input, and why a square-free routine is worth having
before the factoriser that consumes it.
 Yun's algorithm rather than the older Tobey-Horowitz one: both start from
gcd(f, f'), but Yun's carries the derivative quotient forward so that each
round's greatest common divisor is taken between polynomials whose degrees have
already fallen, instead of re-dividing the original every time. The cost is one extra
subtraction a round and the saving is an order of magnitude on high multiplicities.
Yun, On square-free decomposition algorithms, SYMSAC '76; Geddes, Czapor and
Labahn, Algorithms for Computer Algebra, §8.1.
 Characteristic zero only. Over F_p the derivative of x^p vanishes and
the argument above breaks, which is why the finite-field side handles its own
square-free step rather than calling this.

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online