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

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

I reckon you could get a 5 times speedup if you implemented the other
algorithm from Sage, if you had linear algebra as fast as Magma. But
last I checked, fflas-ffpack was not there speedwise yet. I had code
running about twice that speed in FLINT and within 30% of what Magma
had. Obviously I didn't implement the other versions of Berlekamp
using it though.

So, maybe you could get a 2 times speedup with fflas-ffpack and
implementing the other Berlekamp algorithms in Sage.

Obviously 2 times is worth it from my point of view. I don't know how
long it will be before I have fast linear algebra. Depends what I get
done when visiting William in a couple of weeks time. But it is likely
to be at least 6 months before I get factoring over Z/pZ really fast.

Bill.

2009/3/20 Burcin Erocal <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
>
> ------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> software that enables intelligent coding and step-through debugging.
> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>