[flint-devel] FLINT 1.4 Released!

[Bill H. <goo...@go...>]

I've just released FLINT 1.4. Get it at http://www.flintlib.org/

This release contains a large number of *****speedups*****. Note that
the zmod_poly_gcd, xgcd, gcd_invert and resultant speedups also speed
up the associated fmpz_poly functions. The gcd_invert, resultant and
xgcd speedups are asymptotically fast and practically much faster. The
gcd functions are much faster than they were.

Here is a graph comparing zmod_poly_gcd with Magma:

http://sage.math.washington.edu/home/wbhart/zpgcd8.png

And here is one comparing fmpz_poly_gcd with Magma (note the scale is
a factor of 20 for the brightest points!!):

http://sage.math.washington.edu/home/wbhart/gcd.png

There are also some *****critical bug fixes****** in this release.
Users are advised to update to the latest version.

Here is a summary of the changes and additions in this release:

   * Sped up zmod_poly division in case where operands are the same length
   * Sped up zmod_poly division in case where operands have lengths
differing by 1
   * Fixed a bug in zmod_poly_gcd for polynomials of zero length
   * Sped up zmod_poly_gcd considerably (both euclidean and half gcd)
   * Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably
   * Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast
   * Made zmod_poly_resultant asymptotically fast
   * Added optimised zmod_poly_rem function
   * Fixed a divide by zero bug in zmod_poly_factor_berlekamp
   * Added test code for z_factor_tinyQS and z_factor_HOLF
   * Fixed many bugs in the z_factor code, tinyQS and mpQS
   * Corrected numerous typos in the documentation and added missing
descriptions
   * Added F_mpz_cmp function
   * Added documentation to the manual for the new F_mpz module

As usual I have tested on 64 and 32 bit machines, including Cygwin and
valgrinded the new code.

There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end
of this year. In particular I need to address:

* The zmod_poly_factor function is still waaaay slower than Magma -
probably due to Magma having fast linear algebra over Z/pZ, including
strassen multiplication
* The fmpz_poly_divrem function is not asymptotically fast (there is
still a log factor which can be removed by using newton iteration) -
though we still beat Magma everywhere
* The fmpz_poly_pseudo_rem function is not asymptotically fast at all,
it is quadratic time
* There is no fmpz_poly_rem function
* We don't have zmod_poly_compose or zmod_poly_evaluate yet
* The heuristic fmpz_poly_gcd tricks need to be propagated to xgcd,
resultant and invmod functions and even the division functions
* We don't have a modular division algorithm yet

Enjoy!!

Bill.