hnfproj

The hnfproj package provides C routines for efficiently computing the Hermite normal form of integer matrices.

This package requires both GMP (http://gmplib.org/) and ATLAS (http://math-atlas.sourceforge.net).

Download

Timings

M1 Medium Amazon EC2 instance: 64-bit Intel Xeon E5-2650 at 2GHz; 3.75 GiB RAM. GCC 4.6.3, ATLAS 3.10.1, GMP 5.1.1.

All times in seconds.

Random square

Random square matrices of dimension n (rows, in the table below) with entry of bitlength l (columns, below).

hnfproj

n 3 8 32 128 256 512
100 0.06 0.09 0.29 1.80 6.12 26.39
125 0.09 0.14 0.49 3.08 10.11 44.73
200 0.32 0.42 1.51 9.38 28.95 121.14
250 0.52 0.75 2.59 15.40 47.59 200.91
400 1.85 3.08 8.75 50.51 140.12 559.46
500 3.35 5.66 19.36 84.62 247.00 894.81
800 13.84 22.47 60.32 283.58 782.55 2715.43
1000 25.85 41.99 109.38 501.01 1313.00
1600 134.72 170.58 448.71 1755.24
2000 274.59 348.29 861.43
3200 1104.34 1624.62
4000 3214.17

Sage 5.5

n 3 8 32 128 256 512
100 0.58 0.70 0.81 2.12 5.74 22.60
125 0.76 0.83 1.09 3.42 11.90 37.20
200 2.15 2.29 3.21 10.73 33.00 114.00
250 3.75 3.78 5.50 18.03 56.40 213.00
400 11.50 12.15 16.98 60.67 164.33 552.00
500 20.20 22.50 30.42 99.47 279.67 1060.00
800 73.60 81.62 114.33 334.33 827.33 2560.00
1000 141.00 154.00 212.67 585.00 1456.67
1600 607.00 679.50 886.75 2030.00
2000 1365.00
3200
4000

For the following table only, experiments on larger matrices with 8-bit entries were performed on an 64-bit Intel Itanium2 at 1.3 GHz with 192 GB RAM. All times in seconds.

n hnfproj Sage 5.5
1000 74.23 659
1600 286.8 2590
2000 587.3 5663
3200 2587
4000 5408
6400 31790
8000 75810
10000 182300

Non-trivial Hermite form

Following the method of Jaeger and Wagner ("Efficient paralleizations of Hermite and Smith normal form algorithms", Parallel Computation, 35(6):345-57, 2009.), we construct a special class of matrices to provide particularly difficult examples. The (i,j)th entry of each matrix is (i-1)^(j-1) mod n. For prime n, the resulting matrix is nonsingular with many (generally more than n/2) non-trivial columns in Hermite form (denoted k in the table below).

n k hnfproj Sage 5.5
101 56 0.53 1.13
127 77 0.82 2.24
211 118 3.21 19.4
251 132 5.92 44.6
401 266 18.69 531
503 252 31.73 1520
809 503 117.23
1009663 222.72
16011060 836.51
20031041 1411.54

Random rectangular

Random rectangular matrices with 8-bit entries, n rows and n+1, n+100, or 2n columns.

hnfproj

n n+1 n+100 2n
100 0.12 0.67 0.67
200 0.54 2.35 4.10
400 3.82 15.55 51.91
500 6.61 25.53 103.42
800 26.26 89.37
1000

Sage 5.5

n n+1 n+100 2n
100 0.67 1.351.35
200 2.51 5.69 8.93
400 14.15 30.80 81.65
500 23.75 53.40 176.0
800 91.15 190.50
1000 41.99

References

C. Pauderis and A. Storjohann, Computing the invariant structure of integer matrices: fast algorithms into practice. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'13), ACM Press, 2013, 8pp. pdf

ECCAD'13 poster: Fast Heuristic Hermite Form

Authors