On Dec 15, 2007 7:19 AM, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > Hmm, this is interesting. Singular may be frightening for factoring with some > big bad examples, but it seems we've got some work to do for the small cases. > sage: R.<y,z>=QQ[] # singular > sage: r=y^37-1 > sage: timeit r.factor() > 1000 loops, best of 3: 1.04 ms per loop > sage: S.<x>=ZZ[] # NTL, but the factoring code converts to pari. > sage: s=x^37-1 > sage: timeit s.factor() > 100 loops, best of 3: 5.2 ms per loop > The moral might be: conversions are costly (but we already knew that).
Note that NTL does implement factoring in ZZ[] and moreover it does so asymptotically *very* quickly. It's only for small degree where I once noticed pari being faster and made that the default -- and maybe that had to do with bad turning when building NTL! So you might want to consider wrapping ZZ[] factoring via NTL, which I'm sure you can easily do since you led the charge for rewraping all of NTL! > > I've written a factoring routine which implements the idea which was floated > by William from the gcdheu algorithm. A paper of Fateman simply calls it > Kronecker's trick -- specialize at a large number and factor the resulting > integer or polynomial of lower degree. The whole thing hinges around an > appropriate definition of "large" which I can't find or testing after the > fact that we chose large enough. > > So far, my mpoly over ZZ factoring code reduces to a univariate and factors > that. Profiling indicates that the univariate factoring is a significant > hunk of my time -- I guess that means my all-python book-keeping is > respectable. Oh, and my kroneckers trick algorithm for my special case > absolutely clobbers singular, but I don't think that is really a great shock. Nice! How does it compare to Maple and Magma and Reduce? -- William --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
