Hermite Normal Form Timings Page

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.

Processor and Software Versions

For each matrix in each class of random matrices, the Hermite form of it is computed using 4 different implementations (at least where applicable and practical). All computations are performed on an Opteron 254 processor (2.8GHz) and times are given in seconds.

The software and algorithms used (ALL compiled in 64-bit 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).

Generic Square

For each n, the input matrix is an n by n matrix with random entries in the range -9 to 9. Note that for this kind of matrix, the new modular algorithm has heuristic complexity O(n^3), and the timing ratio for n=1000, 2000 is extremely close to 8, as expected.

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    

Generic Double Columns

For each n, the input matrix is an n by (2*n) matrix with random entries in the range -9 to 9. This is much harder than the square case (for both modular and classical algorithms), since all of the right half of the Hermite form H has entries comparable in size to the n-th column of H, so it is much harder to obtain a modular algorithm which computes all the extra columns effectively. I exclude NTL, since it cannot handle the case that there are more columns than rows.

   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  

Unimodular

For each n, we start with the n by n identity matrix and then do 10*n row operations on the matrix by randomly adding or subtracting a random row from another random row. The resulting matrix thus has determinant 1 or -1 (and tends to have one- or two-digit entries), so its Hermite form is the identity matrix, of course, but this can be non-trivial to prove. NTL's modular technique helps it here somewhat.

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    

Non-trivial Diagonal With Smooth Entries

For each n, we start with the n by n zero matrix and then set each diagonal entry to a random integer between 1 and (n/10). We then do (10*n) row operations on the matrix by randomly adding or subtracting a random row from another random row and (10*n) column operations on the matrix by randomly adding or subtracting a random column from another random column.

The resulting input matrix tends to have 3- to 6-digit entries, and the diagonal of the Hermite form has many non-trivial 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