> 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).
> 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.
> 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.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
