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

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

I wonder if it is worthwhile trying to patch fflas-ffpack into FLINT
to see if it can speed up the existing Berlekamp.

Maybe the entire complexity and speed of the algorithm is being
dominated by the Gaussian elimination step in FLINT.

Probably fflas-ffpack has a function for doing this. So it might be
easy to patch it in, replacing the function
zmod_mat_row_reduce_gauss_jordan(zmod_mat_t mat) in zmod_mat.c in
FLINT.

Maybe that is all that is required. Everything else in that algorithm
should be _super_ fast it seems (I'm just about to check the GCD by
comparing it to Magma to make sure).

Bill.

2009/3/20 Bill Hart <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
>>
>