The GCD is used in the first stage of any factoring algorithm, to find the content (GCD of all the coefficients) and to factor into squarefree factors (using GCD(f, f') where f' is the derivative).
But your example is special. The example you give can be factored by hand in 5 minutes because there basically is a trivial trick for the second stage, assuming the sensible thing was done in the content stage. Thus it is basically all GCD. Which means SINGULAR is doing something really silly. It should be instant. Magma apparently has a lot of this sort of thing, i.e. dealing with special cases using special tricks. In the univariate case, factorisation over finite fields can be done mainly with exponentiations and GCD's, so GCD is important there too. Factorisation over Z usually starts as a factorisation over a finite field and gets lifted one way or another to a full factorisation. In the case where one uses Hensel lifting, Van Hoeij's method avoids the exponential explosion that occurs in trying to combine all the factors one gets mod p^k into factors over Z by resorting to LLL lattice reduction. This gives a polynomial time algorithm instead of an exponential one. In the case of multivariable factorisation, the idea is basically to reduce the problem to univariate polynomial factorisation. This is usually done by substituting integers for all but one of the variables (the so-called evaluation step - this is where your evaluation points come from that the SINGULAR guy is talking about). There are numerous stategies for reducing to the univariate case. But most of them revolve around similar sorts of tricks as those used in GCD algorithms, after all, a divisor is a factor. The EEZ stategy for reduction to the univariate case and subsequent lifting, used in Magma, lifts a solution using ideal-adic multivariate hensel lifting. But once again, in the example you gave, this step should never need to be done since your polynomial has special properties. In your case the steps of the algorithm (which actually do something) should be: 1) Find the content, considering your polynomial to be a univariate polynomial in X1 (uses GCD only) 2) Find the content, considering your polynomial to be a univariate polynomial in X2 (uses GCD only) 3) Factor the contents found using bivariate van Hoeij (uses GCD, exponentiation, Hensel lifting and LLL) 4) Factor the cofactor by making the substitution Z = p10^18*X1*X2 and do the resulting univariate factorisation using univariate van Hoeij (uses GCD, exponentiation, Hensel lifting and LLL) 5) Check the irreducibility of all factors using substitutions (uses a primality test) So no true multivariate factoring algorithm is needed in your special case. As I say, I'm no expert on multivariable factoring, and what I don't know is: a) Whether some of these steps are not needed because they are taken care of efficiently by ordinary multivariable factoring techniques which only depend on choosing evaluation points in an efficient way. b) Whether a technique such as what I am suggesting is practical for polynomials in many variables. Probably not. It is probably a special case. Bill. On 4 Dec, 12:02, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote: > On Tuesday 04 December 2007 02:31, William Stein wrote: > > > > > > I think we discussed this on the list before. For univariate you want > > > van hoeij's algorithm and for multivariate some variant of GCDHEU or > > > EZGCD. > > > > I think the algorithm Singular are using, EZGCD, is probably pretty > > > good. They just need to work on improving it perhaps. Magma uses van > > > Hoeij's algorithm for univariate factorization and the multivariate > > > case is basically reduced to this. They use GCDHEU I believe for the > > > multivariate case. Maple probably uses both GCDHEU and EZGCD and tries > > > to choose the best one. > > > I'm a little confused -- before we were discussing multivariate *GCD* in > > the context of "magma is way faster than Singular for this example that > > Joel came up with". Now we're talking about multivariate polynomial > > factorization. What's the connection between the two problems, which > > you're sort of identifying above? > > I don't know what the connection is, but Hans himself saw some connection > between the two in his response > athttp://www.singular.uni-kl.de/forum/viewtopic.php?t=1652 > I actually e-mailed Hans back yesterday to inquire about using the > multi-modular gcd inside factorize. It seems worth a try to get better > performance in my case (although I'm beginning to believe that my case is > special somehow). > > -- > Joel --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
