I should point out the paper linked is *NOT* my paper. Bill.
On 21 Jan, 20:03, Bill Hart <goodwillh...@googlemail.com> wrote: > I worked through this problem in detail with univariate polynomial gcd > recently. It proved to be very difficult to beat Magma, though on the > whole I did in the end: > > http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd1... > > (Blue points are where I win, red where Magma wins - but ignore the > ones on the right, they are probably gone now). > > The heuristic GCD is the algorithm I used, which is similar to what > you are doing. The algorithm and bound I used are described in: > > http://arxiv.org/PS_cache/cs/pdf/0206/0206032v1.pdf > > with some modifications. > > 1) I used a slightly higher bound, specifically 6 bits higher to avoid > too many false positives > > 2) I realised that if I wish to prove that polynomial A divides > polynomial B I can do this by evaluating A and B at some point p and > computing the quotient Q using integer division. If there is a > remainder, you know immediately it doesn't divide. If it does divide, > you can prove that B | A by bounding the number of bits of the > coefficients of B*Q and checking that this is actually less than p. > Why does this provide a proof? Well certainly you agree that if B*Q = > A then B | A. So it boils down to doing the multiplication B*Q. One > way to do this is to use Kronecker substitution. I can evaluate B and > Q at some value p. So long as the coefficients of A are less than p, > then this will work. But you can see this is precisely the opposite of > dividing A evaluated at p by B evaluated at p. > > There is one trick one has to be careful about. One has to divide any > prospective GCD G by its content h before doing the above. But one can > do this by dividing H evaluated at p by h. > > This all works out much faster than doing polynomial divisions to > check, especially if one writes the code carefully. > > Bill. > > On 21 Jan, 09:54, parisse <bernard.pari...@ujf-grenoble.fr> wrote: > > > I come back to the topic of multivariate GCD which was discussed last > > year (http://groups.google.de/group/sage-devel/browse_thread/thread/ > > bc807fe1db5c8a9c/dafa6cd02b060c2f?lnk=gst&q=maxima+gcd#). During the > > last month, I have worked on speed improvements on giac gcd algorithm > > so that giac modular algorithm is 1 to 1.5* slower than magma for > > fermat tests (http://wiki.sagemath.org/MultivariateGCDBenchmarks, I > > can't test myself with magma, if someone want to test, I have put a 64- > > bits executable of icas on sage.math.washington.edu, to run it do > > export LD_LIBRARY_PATH=/home/parisse > > cd /home/parisse > > ./icas fermat_gcd_mod_?var > > Timings on sage are > > mod 1-d: 7.5e-5, 0.0022, 0.007 > > mod 2-d: 0.0004, 0.0016, 0.014, 0.06 > > mod 3-d: 0.0011, 0.0052, 0.048 > > mod 4-d: 0.0095, 0.03, 0.065) > > > I have a few questions related to the way one can prove that the > > answer you compute is the gcd, maybe someone here can answer. > > Let me briefly recall the multivariate modular gcd algorithm by > > interpolation, for example in 2 variables x,y. First we remove > > contents wrt to x and y, then find a majoration of the degree of the > > gcd wrt x, find the value of gcd(P(x,y),Q(x,y)) for degree+1 values of > > x that have the same degree in y (with some additionals checks on > > leading coefficients) and interpolate a polynomial G(x,y). > > The usual way of concluding is a check that G divides both P and Q. > > But it appears that for dense polynomials, if the degree of G and P/G, > > Q/G are about the same (like in the examples of the fermat testsuit), > > the division cost much more time than the whole gcd/interpolation > > process. Hence an alternative must be found to check if the > > interpolated G is really the gcd of P and Q. The way I have found is > > to interpolate the cofactor P/G as well (as a polynomial Pcof) and > > check that G*Pcof is P. The check is not done by doing the > > multiplication (which would be as costly as doing the division check), > > but by testing the equality P(xk,y)=G(xk,y)*Pcof(xk,y) for > > sufficiently many values of x (degree(P) + 1 + adjustements for > > leading coefficient). Additionnaly, total degree information is used > > to minimize a little the check (cf. file threaded.cc > > ofhttp://www-fourier.ujf-grenoble.fr/~parisse/giac/giac-0.9.0.tar.gzfor > > those interested). > > Now, that is a deterministic procedure. One could also use a > > probabilistic check, i.e. the probability that the interpolated G and > > Pcof verify G*Pcof=P at a random x point not used for interpolation is > > very small if G is not the gcd, because first all gcd(P(xk,y),Q(xk,y)) > > should have a same degree in y that would be too large for the xk used > > to interpolate, and second this would again be true for the > > additionnal random value. > > Hence a natural question: is there a more efficient way of checking > > that we have really reconstructed the gcd? What kind of check does > > magma? (assuming it does use the same recursive interpolation > > algorithm, but all alternatives I know require an expensive > > multiplication or division at the end of the process if the inputs are > > dense). --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
