Polynomial Factorisation
Root Finding over the Reals and Complex Numbers
Numerical root finding for polynomials with exact coefficients, root isolation over the reals, and the precision required to be reliable.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0571
Complex roots of a defining polynomial give the embeddings of a number field, which are needed for the conjugate vector representation, for regulators and for logarithmic embeddings. The computation is numerical but the input is exact, which changes the requirements.
Two distinct problems
- Root isolation
- Find intervals or regions each containing exactly one root. Exact and combinatorial.
- Root refinement
- Compute a root to required precision within an isolating region. Numerical and fast.
Real root isolation
Sturm sequences give the exact number of real roots in any interval. Bisecting until each interval holds exactly one root isolates them all.
Real root isolation and refinement
- Build the Sturm sequenceFrom the polynomial and its derivative, by a signed remainder sequence.
- Bound the rootsUse a Cauchy-type bound to get an interval containing all real roots.
- Count and bisectEvaluate sign changes at endpoints; bisect any interval holding more than one root.
- RefineApply Newton iteration within each isolating interval.
Complex roots
For complex roots the standard practical methods are Aberth or Durand-Kerner iteration, which refine all roots simultaneously from spread initial estimates. They converge quickly for well-separated roots and slowly for clustered ones.
Precision requirements
| Situation | Precision guidance |
|---|---|
| Well-separated roots, low degree | Machine precision adequate |
| Clustered roots | Precision proportional to the clustering |
| Large coefficient range | Scale first; precision must cover the range |
| Feeding an exact computation | Precision must exceed the exact reconstruction requirement — see dependence detection |
Signature of a number field
The counts of real roots and complex conjugate pairs of the defining polynomial give the signature of the field, which determines the unit rank via the Dirichlet unit theorem and the shape of the conjugate vector representation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.6.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.