On 26 Jan, 07:24, parisse <bernard.pari...@ujf-grenoble.fr> wrote:
> On Jan 25, 10:22 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > FLINT is faster of course! (Well for 1d anyway, :-) )
>
> > But seriously, Bernard's original contention that giac is within 1.5
> > times what Magma will do is about right, and for small problems giac
> > is actually faster! I haven't done timings for Magma's Z[x1, ..., xn]
> > GCD yet, only the Z/pZ[x1, ...., xn]. Obviously with asymptotically
> > fast algorithms, giac would be winning outright.
>
> For 1-d and 2-d, giac would clearly benefit from asymptotically faster
> algorithms (and the 32 bit version of giac calls NTL for large 1-d
> gcd, I just could not get NTL linking with giac on 64 bits), but for 3-
> d it is not so clear since the partial degree are at most 60 if my
> recollection is correct, and for 4-d it's at most 20. I should give a
> try to FLINT, perhaps it would link easier. How does it compare to
> NTL?
Well, FLINT ought to be faster at plain univariate GCD than NTL,
whether over Z or Z/pZ. You probably need to use the functions in the
NTL-interface module to convert between NTL format polynomials and
FLINT polynomials.
>
>
>
> > Here I repeat the times:
>
> > Magma:
>
> > mod-1d: 0.00067s, 0.00981s, 0.0244s
> > mod-2d: 0.00089s, 0.00374s, 0.0256s, 0.08549s
> > mod-3d: 0.00185s, 0.0069s, 0.05491s
> > mod-4d: 0.006s, 0.028s, 0.071s
>
> > giac:
>
> > mod-1d: 0.00038, 0.02, 0.026
> > mod-2d: 0.00052, 0.0024, 0.03, 0.15 (0.112)
> > mod-3d: 0.004, 0.0085, 0.22 (0.198)
> > mod-4d: 0.012, 0.048, 0.12 (0.12)
>
> I'm a bit surprised by the last 3-d timing, since all your other
> timings are faster than mine except this one (where I get between 0.11
> or 0.12 and I would have expected 0.09 or 0.1 on your faster
> Opteron).
When I redo the Magma timings I'll check this one again, just to make
sure.
> It also shows that magma improved since 2005. A reason that might
> explain the difference in timings might be that giac multivariate
> polynomials are in distributed form while magma are in recursive form
> (is this true?), the latter form being more efficient for dense
> polynomials.
>
> > I'll eventually do timings for polynomials over the integers for Magma
> > as well. I should also give Magma the benefit of running the timings
> > more than once and taking minimum times.
>
> Thanks again for your tests!
Bill.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
