#4283: [with proto-patch]A Speed-up Patch for NTL's ZZXFactoring.c
---------------------------+------------------------------------------------
Reporter: anovocin | Owner: tbd
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.2
Component: factorization | Keywords: NTL, LLL, Univariate
---------------------------+------------------------------------------------
The goal of this patch is to speed-up NTL's factoring algorithm for
polynomials in Z[X]. The speed-up comes from using fpLLL rather than
NTL's native LLL algorithm. We do this by converting a ZZ_mat of ZZ's
(NTL's multi-precision integers) and passing them into a mat_ZZ<mpz_t>
matrix of mpz_t's (fpLLL's native format). Then run fpLLL on the new
matrix and pass the entries back to NTL. I don't replace NTL's LLL just
pass what should be an already reduced basis to NTL's LLL. (NTL computes
extra information that would require a hack into fpLLL to get and might
not be worth it.) This patch allows NTL to beat MAGMA on many examples
(it still is a little slower than MAGMA (but faster than SAGE) on
irreducible polynomials). I think that the cross over between Pari's
factoring and NTL's factoring should be re-evaluated (currently Pari is
used for polynomials of degree 30 through 300) if not just use NTL for all
polynomials now.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4283>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
