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

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

Here is the gcd graph. It isn't too bad, and clearly isn't the source
of the issues with the factoring timings:

http://sage.math.washington.edu/home/wbhart/zpgcd.png

Magma seems to have a faster basecase, though I don't know how that is possible.

I also don't know how it is possible that they are faster for moduli
of <= 8 bits. Nothing shows up in the timings for multiplication and
division, and that's about all GCD uses. So I'm a bit mystified by
that, especially in the basecase region.

Bill.

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