The fastest Hermite form calculation

Since winter 2013/2014 I am researching the problem of integer matrice HNF calculation. My view of the issue, current status of research and intermediate results are detailed below.

Since approximately 2011, the fastest open-source HNF subroutine is part of computer algebra/library Sage. Note that the subroutine is written for the most part in Python language. Mathematical article describing the algorithm is available at author's page. Studying the source code I found that implementation is in beta/unfinished/abandoned state, and decided to improve it .

March 2014 I implemented a decreasing modulo algorithm to count Hermite form of a small-determinant matrice. The subroutine is in C and uses FLINT library. My benchmark shows that the procedure is more than twice faster than Sage subroutine. I am using FLINT library because it is faster in many ways than other libraries (such as NTL, IML or Sage). I delved deeply into Sage and FLINT, found some defects in FLINT and reported them via github mechanism. I appreciate helpful advices from FLINT developers I received early 2014 on the forum. While testing/benchmarking software, I created Python wrapping over many subroutines of FLINT, as well as my C subroutines. My software can be automagically installed on an AMD/Intel 64-bit Linux desktop computer via portage software manager. I usually test/benchmark any code, before putting it online. Which means, everything should work without errors. If you find error, your bug-report is welcome.

Replacing Sage subroutine to count HNF of small-det matrice with mine did not bring any noticeable speed-up. I re-implemented HNF calculation in Python to retrieve profiling information. It turns out that small-det HNF takes very small time compared to double_det() solve_system_with_difficult_last_row(). I went further and replaced slower subroutines called by Sage code with faster FLINT subroutines. Difficult part was selection of a way to solve set of linear equation: IML subroutine was sometimes faster and sometimes slower than FLINT subroutine. After I solved the issue, my Python program became noticeably faster than Sage, in counting HNF of a square non-singular big matrice with big entries:

I turned my attention to double-determinant calculation. To count double-det, Sage calls usual determinant calculation. Benchmarks show that FLINT is the champion in counting determinant of big and fat matrice (FLINT is faster than Sage or NTL, for big n and bits). FLINT finds a big determinant divisor, then corrects it by calculating det modulo some small primes. Both subroutines fmpz_mat_det_divisor() and mpz_mat_det_modular_given_divisor() are sub-optimal. fmpz_mat_det_divisor() counts two bounds N and D, such that always N>D, then takes maximum of the two, which happens to be N, and forgets D. mpz_mat_det_modular_given_divisor() counts LUP decomposition, which is extraneous information, since diagonal of row-reduced form is enough to count determinant. Besides, FLINT implementation of elementary matrice operations over residue ring is sub-optimal: for instance, FLINT general subroutine to multiply matrix is 2.5 time slower than my subroutine, when modulo is 64-bit, as shown by my benchmark.

Replacing LUP decomposition with block Gauss, I created an asymptotically faster procedure to count determinant. Why I say that it is asymptotically faster? Because time ratio FLINT/mine found at last column appears to steadily grow, as n increases.

Now that my determinant calculation is the fastest in the open-source world, I should be able to write a subroutine that counts double-determinant faster than Sage does it.

Within Google Summer of Code, a C subroutine to compute HNF within FLINT is being developed by Alex Best. 26 Aug he published benchmark of his code, but not the code itself. If a code that counts HNF that fast actually exists, it is faster than mine. However, as of today (28 Aug) HNF code found at Alex Best's page is dated 18 Aug and slower than Sage. Which means my subroutine is currently the fastest.

UPDATE. As of november 2014, Alex Best HNF is the fastest. My benchmark of his code is part of my package RAZIN.

Github is ill, working link to RAZIN is here.