Wait a minute. I just realised something. The mod-1var GCD's in that
file are polynomials over GF(43051). I thought it meant it was the
modular GCD algorithm, meaning they were polynomials over ZZ whose GCD
was computed using the modular algorithm!!
The 1d polynomial GCD's over ZZ take less than 0.00018s, 0.0055s and
0.021s in FLINT (very approximate timings on a 1.8Ghz Opteron)!!
I haven't timed the mod-1var GCD's in FLINT.
Anyhow, here are the timings in Magma V2.14-15 on a 2.4GHz Opteron:
1d: 0.00168s, 0.01692s and 0.0453s
mod-1d: 0.00067s, 0.00981s, 0.0244s
Your timings (on a 2.2 Ghz Opteron!!)
1-d:0.00018, 0.009, 0.034
mod 1-d: 7.5e-5, 0.0022, 0.007
So you look to be well ahead of Magma! Did you do something special
for small moduli, such as packing multiple coefficients into a limb?
Anyhow, pretty amazing, well done!
Bill.
On 22 Jan, 14:06, Bill Hart <goodwillh...@googlemail.com> wrote:
> On 22 Jan, 08:11, parisse <bernard.pari...@ujf-grenoble.fr> wrote:
>
>
>
> > > Thanks for the nice paper by the way. :-)
>
> > I'm glad it was useful to someone despite not being published in a
> > standard journal.
>
> > > Do your timings you list include checking that the GCD is correct? Or
> > > are the divisions still to be done?
>
> > The timings I give include checking, but I do not use division to
> > check if it would take too much time. The checking is done by
> > computing P-G*Pcof for deg_x(P)+1 values of x. If it returns 0, then
> > P=G*Pcof. Interpolating the gcd and the cofactor already gives about
> > one half of the required equalities. For the remaining one, I also use
> > an additional information, the total degree of P-G*Pcof is known, and
> > if the equality holds for n values of x, the remaining degree in y can
> > not exceed the total degree - n. This improves a little bit the
> > efficiency of the check.
> > Unfortunately, I do not have access to a copy of magma, hence I don't
> > know exactly how my timings compare to those of magma. I would really
> > like to know how magma does the check (assuming it does a
> > deterministic check: this is really a problem with closed-source
> > software, we can never be sure if an answer is true or just pseudo-
> > true).
>
> I can time Magma for you on a 2.4GHz Opteron. I don't have access on a
> Core 2, but other people on this list do.
>
>
>
>
>
> > > According to the documentation on the Magma website:
>
> > > "For polynomials over the integers or rationals, a combination of
> > > three algorithms is used: (1) the heuristic evaluation `GCDHEU'
> > > algorithm of Char et al. ([CGG89] and [GCL92, section 7.7]), suitable
> > > for moderate-degree dense polynomials with several variables; (2) the
> > > EEZ-GCD algorithm of Wang ([Wan80], [MY73] and [GCL92, section 7.6]),
> > > based on evaluation and sparse ideal-adic multivariate Hensel lifting
> > > ([Wan78] and [GCL92, section 6.8]), suitable for sparse polynomials;
> > > (3) a recursive multivariate evaluation-interpolation algorithm
> > > (similar to that in [GCL92, section 7.4]), which in fact works
> > > generically over {Z} or most fields."
>
> > I guess this documentation was written well before Allan Steel
> > improved magma modular algorithm in 2005. My own experience with EEZ-
> > GCD is that it is only interesting for sparse polynomials where 0 is a
> > good evaluation point.
>
> > > I don't know any more than that.
>
> > > The timings you give are very good. I can only compare with
> > > polynomials in 1 variable. I think my timings are better than the ones
> > > you give, but I won't be able to tell for sure until FLINT 1.1 is used
> > > by Sage for GCD over ZZ (FLINT can't read from Sage python files). I'm
> > > also only doing my timings on an Opteron. I don't know what they are
> > > like on a Core 2.
>
> > I can give you the 1-d timings on an Opteron 275, 2.2 Ghz, mod-1-var:
> > 0.00018, 0.009, 0.034, 1-var: 0.00075, 0.044, 0.17. I focused on the
> > modular 1-var algorithm up to moderate degree since that is what is
> > called heavily for my multivariate GCD algorithm, the non modular 1-d
> > gcd is still in work and most probably improvable. Moreover I do not
> > plan to implement asymptotically fast 1-d GCD algorithms now.
>
> That's interesting. The Opteron timings are way slower than the Core 2
> timings. Do you know why that might be?
>
> I am sure FLINT is much faster than those timings. It will be
> interesting to get timings for Magma....
>
>
>
>
>
> > > Of course I used your paper in order to code the FLINT univariate GCD.
> > > I cite it in the actual code, and as of 1 minute ago, it is liked from
> > > the webpage of the FLINT project:
>
> > >http://www.flintlib.org/
>
> > Thanks!
>
> > > I'm currently doing some experiments with multivariable arithmetic in
> > > FLINT. But I am only at the stage of adding polynomials. :-(
>
> > Good luck!
>
> > > The method you suggest for doing the divisions sounds sensible to me.
> > > Does that still take longer than the actual GCD?
>
> > I'm not sure I understand your question. The "traditionnal" division
> > or multiplication of G by its cofactor (without interpolation) is
> > indeed much slower than computing (and even checking) the gcd because
> > it is (neglecting logarithmic terms) quadratic in the number of
> > monomials, and I observe this when I add the additional check that
> > P==G*(P/G). Multivariate multiplication using interpolation might be
> > as fast, up to a constant if compared to checking because it would be
> > difficult to use total degree information. Exact division could also
> > be done by interpolation, but more general division is another topic.
>
> Sorry, of course I meant to ask whether the check you are doing takes
> longer than the actual GCD itself.
>
> 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
-~----------~----~----~----~------~----~------~--~---
