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. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
