Re: [flint-devel] Z/pZ[x] factoring

[Burcin E. <bu...@er...>]

On Thu, 19 Mar 2009 23:12:49 +0000
Bill Hart <goo...@go...> wrote:

> I have been producing some timings for factoring polynomials over
> Z/pZ[x] against a recent version of Magma.
> 
> Here is the graph:
> 
> http://sage.math.washington.edu/home/wbhart/zpfactor.png
> 
> It appears that Magma is thrashing us, even with all the recent
> improvements to zmod_poly.
> 
> I don't know if Magma has been sped up or if we just mistimed in the
> past, but towards the left of that diagram we are 2-5 times slower
> than Magma, and on the right hand side it's more like 12 times slower.
> 
> The Berlekamp algorithm we use is a polynomial one, with a
> Gauss-Jordan elimination somewhere along the way. But I think there is
> a version of the algorithm which computes much more using matrix
> algebra.
> 
> As FLINT is a long way away from having fast matrices over Z/pZ I
> think it will be some time before we can beat Magma (again) on this
> benchmark. This is a little disappointing, but I'm sure it can be
> fixed in time.

Even if it's not an option for the main FLINT relase, we could patch
FLINT in Sage to use fflas-ffpack from linbox to get fast linear
algebra over Z/pZ.

Do you think it's worth the time to try implementing this other version
you mention? What do the factorization experts say? Andy?

Cheers,
Burcin