Integer Matrix Normal Forms
Coefficient Explosion in Hermite Normal Form Computation
Why intermediate entries in normal form computation grow so violently, how to recognise it, and the three standard mitigations.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0538
Coefficient explosion is the characteristic failure mode of exact integer linear algebra. The input is small, the output is small, and the computation in between produces numbers with thousands of digits. Recognising it is the first step to avoiding it.
The mechanism
Each elimination step replaces a pair of entries by a GCD using Bezout coefficients, and those coefficients multiply into every other entry of the affected columns. The growth compounds across steps.
Recognising it
| Symptom | Interpretation |
|---|---|
| Runtime grows far faster than the cube of the dimension | Entry growth, not operation count |
| Memory use climbs steadily during a single computation | Intermediates being stored |
| Small perturbation of the input changes runtime by orders of magnitude | Pivot choice is driving the growth |
| Output entries much smaller than peak memory suggests | Classic swell — the answer was always small |
Three mitigations
Modular computation
Work modulo a known determinant multiple. Entries are bounded by construction. The standard fix when such a multiple is available — see the modular HNF.
Lattice reduction
Apply LLL before or during the computation so the working basis stays short. See LLL-based HNF.
Pivot selection
Choose pivots with small Bezout coefficients — typically the smallest non-zero entry. Cheap, always worth doing, but not sufficient alone.
Choosing a mitigation
- Is a determinant multiple known?
- Yes — use the modular algorithmBounded growth, simplest fix
- No — continue
- Is the matrix large or ill-conditioned?
- Yes — LLL-based reductionHigher constant, controls growth
- No — careful pivoting may sufficeMeasure before assuming
Not unique to Hermite form
The same phenomenon affects Smith normal form computation, fraction-free Gaussian elimination, polynomial GCD over the integers, and resultant computation. The mitigations are the same in each case — modular methods where a bound exists, reduction where it does not.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.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.