On Monday 31 March 2008 07:38:48 pm William Stein wrote: > On Mon, Mar 31, 2008 at 4:27 PM, Mike Hansen <[EMAIL PROTECTED]> wrote: > > Hi Roman, > > > > It seems that for characteristic 0, Maxima is quite a bit faster than > > Singular, but there's some overhead in talking to Maxima over the > > pexpect interface. In any case, it is still _way_ slower than what we > > need. For example, Maxima takes around 10 seconds to do the bivariate > > gcd of degree 100 listed here ( > > http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html ). Magma on > > the other hand takes 0.06 seconds. > > Even with the overhead Maxima is totally and completely unacceptable. > To take Joel Mohler's example of > > t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2 >^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1 > > I just tried this in Maxima, and it's been sitting there for about > *FIFTEEN MINUTES*:
I'm amazed maxima is so bad at that example -- it's really about as easy as it gets actually (there are 3 factors, one does not contain X1 and one does not contain X2 -- you really don't have to factor at all, just gcd a couple of times; then each of these 3 factors split again as a difference of 5th powers). I've been working very hard at this factoring for the last little bit as it's really caught my imagination. There's a bivariate factorization scheme by Gao using differential equations which seems like it might be a really good tool. The simple application of specializing to a prime to reduce the number of variable results in humongous coefficients and leads to a very slow univariate factoring problem. It also has other technical difficulties like spurious factors which are hard to resolve quickly. I think there are 2 parts left to solving the factoring riddle for ZZ (and possibly other bases, but I've been focusing on ZZ): 1) Fast basic arithmetic with a polydict -- I'm making headway 2) *Super-duper Fast* gcd algorithms -- this is going to be much harder than #1 and the factoring bit. It's utterly crucial to the factoring methods -- crucial for finding squarefree decompositions, crucial for picking off easy factors like my "hard" example has ... We need to implement every algorithm we can find for this, benchmark them every way we can, and develop good heuristics to choose amongst them. It can't be stressed enough that gcd is central to the entire undertaking. I'm hoping to have a first stab at industrial strength mpoly factoring over ZZ in time for 3.0. It won't have industrial strength speed because of the gcd going to singular, but a drop-in gcd replacement will make a world of difference. Singular manages to suck in utterly grand fashion for both gcd and factoring. I'm absolutely certain that we can beat them handily (but probably not in the next month :-). -- Joel --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
