Allan Steel (June 29, 2006)
Magma V2.13 (now released) has an implementation of a new modular algorithm for computing the Hermite Normal Form of an integer matrix. On this page I compare this with other implementations.
The software and algorithms used (ALL compiled in 64bit x86_64 mode) are:
All software is called by invoking the relevant function for Hermite form computation with default arguments (i.e., no special options are used for any particular type of matrix).
The main comparison is between Magma's new modular algorithm and Magma's older classical algorithm; the other two systems are the easiest alternative implementations having Hermite form algorithms for which I could gather timings on a comparable machine up to a reasonable size (these were done more manually than for Magma).
n  Magma 2.13 
Magma 2.12 
Gap 4.4.7 
NTL 4.5 

100  0.04  0.09  0.39  0.77 
200  0.28  1.49  5.77  15.83 
300  1.01  7.92  38.59  106.17 
400  2.10  26.27  100.91  390.21 
500  4.40  68.16  
600  7.48  150.35  
700  11.00  293.05  
800  17.75  532.89  
900  24.74  911.95  
1000  34.22  1466.74  
1500  108.49  10663.31  
2000  273.71  41112.83 
Magma 2.13 
Magma 2.12 
Gap 4.4.7 


100  0.22  0.45  1.56 
200  2.20  7.40  24.56 
300  8.54  39.49  141.93 
400  22.73  131.77  494.41 
500  49.04  354.43  
600  96.88  813.89  
700  174.30  1711.01  
800  278.13  3146.46  
900  424.33  5366.81  
1000  621.61  8482.97  
1500  2754.22  53061.31  
2000  8007.49  194667.55 
n  Magma 2.13 
Magma 2.12 
Gap 4.4.7 
NTL 4.5 

100  0.01  0.06  0.22  0.13 
200  0.05  0.62  3.77  1.40 
300  0.14  3.14  17.77  4.96 
400  0.29  9.09  50.46  11.69 
500  0.53  21.29  135.67  24.34 
600  0.89  42.23  
700  1.37  78.74  
800  1.98  131.71  
900  2.69  212.02  
1000  3.54  318.40  
1500  10.62  1517.53  
2000  23.08  5690.77 
The resulting input matrix tends to have 3 to 6digit entries, and the diagonal of the Hermite form has many nontrivial entries, all of which factor into primes less than (n/10). This type of matrix is difficult for modular algorithms, since a heuristic method assuming that the 2nd or 3rd largest elementary divisor is small fails and an automatic strategy needs to take into account the fact that the largest elementary divisor may be large.
As an example, for n=100, the diagonal entries of the Hermite form of the matrix are: [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 6, 6, 6, 30, 6, 30, 30, 60, 60, 60, 60, 60, 120, 60, 60, 60, 120, 60, 120, 120, 120, 840, 840, 840, 2520, 2520, 2520, 2520, 2520 ].
For n=1000, the largest diagonal entry of the Hermite form is 69720375229712477164533808935312303556800 which factors as 2^6 * 3^4 * 5^2 * 7^2 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97.
n  Magma 2.13 
Magma 2.12 
Gap 4.4.7 
NTL 4.5 

100  0.03  0.10  0.79  0.50 
200  0.46  1.90  11.91  9.11 
300  1.70  12.51  59.76  55.33 
400  4.03  39.74  220.56  216.94 
500  8.87  101.30  577.43  656.20 
600  15.88  226.81  
700  26.62  446.91  
800  41.78  845.72  
900  67.36  1463.26  
1000  88.65  2371.11  
1500  419.79  16263.56  
2000  1137.13  61683.88 