fredrikj.net / blog /

Wrapping up FLINT's Summer of Code 2014

October 3, 2014

The next version of FLINT will feature greatly enhanced linear algebra over the integers, thanks to interstellar work done by our two Google Summer of Code scholars this year: Abhinav Baid and Alex Best.

Abhinav implemented lattice reduction (LLL); Alex implemented Smith/Hermite normal form (SNF/HNF) and also improved our rank/nullspace/RREF computation. These have all been among the most-requested FLINT features for several years. Both Abhinav's and Alex's code has now been merged into the FLINT git trunk, and we will soon prepare to make a new release. This comes just in time as Sage now is switching its integer matrix implementation to a wrapper around FLINT's fmpz_mat_t.

The new FLINT functions are competitive with state-of-the-art implementations. Here are benchmark results (courtesy of Bill Hart) for LLL reducing an integer relations matrix of dimension d and entries from 10d to 40d bits in size, versus Damien Stehlé's fpLLL (the shown timings are in seconds):

FLINT:
d \ bits 10d 20d 30d 40d
32 0.04 0.1 0.16 0.22
64 0.84 1.82 2.97 4.48
96 4.69 10.78 17.77 27.64
128 16.27 38.32 66.07 108.37
160 42.33 109.62 196
fpLLL:
d \ bits 10d 20d 30d 40d
32 0.060.130.190.24
64 1.022.123.34.5
96 5.2411.6818.7526.01
128 17.842.5770.44101.36
160 46.56120.72199.08

We see that FLINT is very close to fpLLL. One of the most important features of the new LLL is that you can specify the input as a Gram matrix (no other open source implementation of LLL currently allows that).

Here are the ratios (courtesy of Alex) between FLINT's new HNF and the Pernet-Stein HNF implementation in Sage (lower is better, i.e. 0.5 means that FLINT is twice as fast):

d \ bits 2 4 8 16 32 64 128 256 512
300.68340.614560.66010.71350.72010.67850.60770.62470.7476
500.46840.53430.53280.40160.30730.23020.20700.20980.2480
700.55480.39180.35880.23410.15030.12100.10760.11170.1388
900.13790.15780.16130.22140.29540.44920.57130.54180.4356
1100.15960.15680.17620.21410.29790.45690.55110.51790.4471
1300.17470.18090.19320.29200.40410.51310.53670.50390.4196
1500.13840.21270.20920.26910.32020.48800.54380.51920.4914
1700.22670.18440.20160.26130.36570.51380.58390.56650.5127
1900.25710.26810.33820.29750.48020.51560.59380.65880.5198
2100.26540.26740.23510.35500.38330.56570.60140.67370.5325
2300.22980.35670.19020.35010.42480.60560.62490.65430.5789
2500.33250.30080.37820.31590.50640.61790.65440.63920.5813

A very nice speedup overall.

Regarding RREF, the git version of FLINT now computes the RREF or nullspace of a random 512 by 513 integer matrix with 1-bit entries in 0.35 seconds on my computer, whereas the old FLINT takes 14 seconds! Sage does it in 0.54 seconds.

There was a proposed third linear algebra-related GSoC project which we unfortunately did not get: optimizing linear algebra modulo small primes, mainly by wrapping BLAS (which would be an optional dependency for FLINT). Using BLAS is a trick which many computer algebra systems and libraries such as Linbox, IML, Sage, Magma, etc. use. This can give a speedup of 3x or more for matrices having several hundreds or thousands of rows. Since FLINT does not use this trick, it sometimes loses out to other implementations when working with very large matrices. Nonetheless, FLINT now generally seems to have linear algebra over the integers that is among the fastest available (if not the fastest) at least for matrices with up to a few hundred rows and columns.

The BLAS/optimization project should still be available next year, unless someone steps in and does the work before that. In any case, getting two GSoC slots was more than we had hoped for, since FLINT is a small and specialized project. Getting two excellent students, on top of that, has been a special pleasure! Huge thanks to Burcin Erocal, and of course Google, for making FLINT's GSoC participation possible this year. I was the primary mentor for Alex (and had to do very little mentoring); Curtis Bright and Bill Hart mentored Abhinav.