Polynomial Arithmetic and GCD
Polynomial Representation and Storage
Dense and sparse polynomial representations, coefficient domains, and the normalisation invariants every implementation must maintain.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0554
Polynomials are the second substrate of this subject, after integers. A number field is a quotient of a polynomial ring, prime decomposition is polynomial factorisation modulo a prime, and resultants drive discriminant computation.
Dense and sparse
| Representation | Storage | Suits |
|---|---|---|
| Dense array of coefficients | Proportional to the degree | Almost everything in this collection |
| Sparse list of exponent-coefficient pairs | Proportional to the number of terms | Very high degree with few terms |
Coefficient domains
- Over a finite field
- Coefficients do not grow. Costs are honest operation counts. This is the friendly case.
- Over the integers
- Coefficients grow during GCD and elimination, exactly as matrix entries do. The dominant practical concern.
- Over the rationals
- Almost always cleared to integers first by multiplying through by the common denominator.
- Over a number field
- Coefficients are themselves algebraic numbers with their own representation. Costs compound.
Normalisation invariants
- The leading coefficient is non-zero, so the degree is unambiguous.
- The zero polynomial has a canonical form and a conventional degree, usually negative infinity or minus one.
- Over a field, polynomials are often kept monic; over the integers, primitive with positive leading coefficient.
Cost baseline
| Operation | Cost in coefficient operations |
|---|---|
| Addition, subtraction | O(max degree) |
| Multiplication | O(d_1 d_2) schoolbook |
| Division with remainder | O(d_1 - d_2 + 1) times d_2 |
| Evaluation at a point | O(d) by Horner |
| GCD over a field | O(d^2) |
The structural parallel with integers runs deep and is worth keeping in view: representation, division, GCD, and even the fast multiplication methods all mirror the integer case. See multiprecision representation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.1.1. 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.