Yes, indeed Magma does this. Bill.
On 4 Dec, 02:52, "Stephen Forrest" <[EMAIL PROTECTED]> wrote: > On Dec 3, 2007 8: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 don't really know anything about multivariate factorization, but the > following bit from _Modern Computer Algebra_ (2nd ed.) by von zur > Gathen and Gerhard is noteworthy: > > "Algorithm 16.22 [an algorithm for univariate factorization] can be > adapted to the factorization of polynomials in F[x,y], where F is a > field with effective univariate factorization This is the case, for > example, when F is a finite field (Chapter 14) or when F=Q, by the > above. The variant of Algorithm 16.22 is then merely a > (deterministic) polynomial time reduction from bivariate to univariate > polynomial factorization." (p. 481) > > This suggests that it may be wise to treat bivariate polynomials as a > special case. > > Steve --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
