(i) the first r rows of A are nonzero and the remaining rows are zero;
(ii) for 1 ≤ i ≤ r, if aiji is the first nonzero entry in row i of A, then j1 < j2 < ⋯ < jr;
(iii) aiji > 0 for 1 ≤ i ≤ r;
(iv) if 1 ≤ k < i ≤ r, then 0 ≤ akji < aiji.
The algorithm used in our BCMATH program is the LLL-based method in the paper Extended gcd and Hermite normal form algorithms via lattice basis reduction,
George Havas, Bohdan S. Majewski, Keith R. Matthews, Experimental Mathematics, Vol 7 (1998) 125-136 with parameter α = 1. (See slides and corrections to paper.) Also see the examples.
One desirable feature of this algorithm, apart from controlling coefficient explosion, is that if r < m, then the entries of P are expected to be small, with the last m - r rows of P forming a ℤ-basis for the integer lattice of row vectors X such that XA = 0.
Last modified 10th September 2011
Return to main page