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 Washington http://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/ -~----------~----~----~----~------~----~------~--~---
