Numerical output, exact obligations
Complex roots are needed to compute embeddings of a number field, hence traces, norms, regulators and the analytic quantities used to verify class numbers. The task is numerical, but the obligations are those of exact mathematics: a root computed to inadequate precision produces a wrong regulator that looks entirely reasonable. Conditioning must therefore be assessed, and precision must be budgeted rather than hoped for.
Learning objectives
- Assess the conditioning of a polynomial's roots.
- Compare simultaneous iteration methods with deflation-based approaches.
- Budget working precision for a required accuracy in the roots.
- Explain why root finding is a prerequisite for exact number field computation.
Section 01Conditioning
Roots can be extraordinarily sensitive to coefficient perturbations. The standard illustration is the polynomial with roots at 1, 2, …, 20: a change in the eighteenth decimal place of one coefficient moves several roots visibly and can make real roots collide and become complex.
The condition number is governed by 1/|f′(α)|. Roots that are close together make the derivative small and the problem ill-conditioned; repeated roots make it singular. A polynomial with tightly clustered roots simply cannot have those roots computed to high relative accuracy from its coefficients, no matter which algorithm is used.
No algorithm can recover accuracy that the representation does not contain. Where high precision is required for clustered roots, the working precision must be increased — or the polynomial must be handled through a better-conditioned representation, such as its factorisation.
Section 02Methods
| Method | Character | Strengths | Weaknesses |
|---|---|---|---|
| Newton with deflation | Sequential | Simple; quadratic convergence near a simple root | Deflation accumulates error; later roots progressively less accurate |
| Durand–Kerner | Simultaneous | Finds all roots at once; no deflation error | Convergence can be slow; sensitive to the starting configuration |
| Aberth–Ehrlich | Simultaneous | Cubic convergence; robust in practice — the usual default | Needs a good initial distribution of starting points |
| Companion matrix eigenvalues | Linear algebra | Uses mature, well-tested QR machinery | O(n3); accuracy limited by the balancing of the companion matrix |
| Splitting circle | Divide and conquer | Near-optimal asymptotic complexity; certified variants exist | Substantially more complex to implement |
Simultaneous methods depend heavily on their starting configuration. The standard choice places the initial approximations on a circle whose radius reflects the coefficient magnitudes, slightly rotated to avoid symmetry. Starting all iterates at the same point causes immediate breakdown.
Section 03Precision management
Working precision must exceed the target accuracy by the number of digits lost to conditioning. In practice a computation is run at increasing precision until two successive runs agree to the required accuracy — an empirical but effective discipline.
- Set the working precision to a starting value, typically twice the target.
- Compute all roots at the current precision.
- Verify: substitute each root back and confirm the residual is consistent with the precision used. A large residual means the precision was insufficient.
- Compare with the previous run; if the agreed digits meet the target, accept.
- Otherwise double the precision and return to step 2.
Complex roots supply the archimedean embeddings of a number field. From these come the trace and norm as sums and products of conjugates, the logarithmic embedding used for units, and hence the regulator. A regulator is a determinant of logarithms of embedded units — and an under-resolved root propagates directly into it.
ReferenceFrequently asked questions
Should exact methods be used instead?
Where possible, yes — exact arithmetic on the algebraic number, using its minimal polynomial, avoids the question entirely. But quantities such as the regulator are genuinely real numbers with no finite exact representation, so numerical evaluation with certified error bounds is unavoidable.
How are real roots isolated exactly?
By Sturm sequences or by Descartes' rule applied to subdivided intervals, both of which give certified isolating intervals using only exact arithmetic. Numerical refinement then narrows an interval that is already guaranteed to contain exactly one root.
What accuracy does a regulator computation need?
Enough that the computed value is distinguishable from all plausible alternatives — in particular from small rational multiples of itself, since an error of a factor of 2 in the regulator is exactly the signature of having found a subgroup of the unit group rather than the whole of it.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.