Good point! I am confusing the two issues somewhat. The confusion arises in that there is an EZ-GCD and an EZ factorisation algorithm, and EEZ-GCD and an EEZ factorisation algorithm. In fact Magma uses a variant of the latter to factor multivariate polynomials. The EEZ-GCD algorithm was derived by the same author. For sparse polynomials this is in fact the GCD algorithm used by Magma rather than GCDHEU.
The first step in factorisation is factoring into squarefree factors and finding the content. This is all done using a GCD algorithm, for which my comments before apply. But the second step is factoring the squarefree factors themselves. For that you are using a factoring algorithm, which has some similarities to a GCD algorithm, but isn't strictly a GCD algorithm. I tend to confuse the two, especially since the strategies are somewhat similar. But the thing is, in the example given, most of the factors can be determined in the `content' stage. Here I'm obviously thinking of the content more generally than integer content. Here the content can be a polynomial. But the only thing required to find that content is a good GCD algorithm. For that we know what Magma does. Then all that is required is to factor the bivariate factors found, for which Magma uses a variant of van hoeij's algorithm, and to factor the remaining multivariate part, for which I'm betting Magma notices the obvious substitution which turns the problem into a simple univariate one. Finally one needs to demonstrate that the factors which remain are in fact irreducible. But this is trivial. In fact this whole factorisation can be done without any real work. Maybe SINGULAR just doesn't do any of these things. Bill. On 4 Dec, 07:31, "William Stein" <[EMAIL PROTECTED]> wrote: > On Dec 3, 2007 5:53 PM, Bill Hart <[EMAIL PROTECTED]> wrote: > > > > > > > On 3 Dec, 17:15, "William Stein" <[EMAIL PROTECTED]> wrote: > > > > This is not so good, really. We should be aiming to beat maple/magma, > > > which do this factorization in 0.01 seconds or so. Where are our reverse > > > engineering experts? How come Maple is so fast at this? > > > 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 think there's that much to reverse engineer. It's known what > > Magma does (well up to some practical tricks they use to get a little > > bit better performance). > > > I'm not intimately familiar with multivariable factorisation > > algorithms, so take any suggestions I make with a grain of salt, but > > perhaps Magma uses a GCDHEU and reduces to a two variable > > factorisation for which they can use a variant of van Hoeij. In the > > example given this might lead to early factors one could remove, > > reducing the problem. But I could also well be completely wrong. > > Perhaps try some examples where there are no factors with only only > > one or two variables and no "small" factors and see if Magma slows > > down considerably compared to SINGULAR. > > > Bill. > > -- > William Stein > Associate Professor of Mathematics > University of Washingtonhttp://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com 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/ -~----------~----~----~----~------~----~------~--~---
