|
From: Bill H. <goo...@go...> - 2009-03-19 23:12:58
|
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. Bill. |