The Macaulay2 code for factorization just calls the Singular-Factory library that we link against. So I don't know why it should be faster than Singular!
> Date: Mon, 3 Dec 2007 07:47:14 -0800 > From: "William Stein" <[EMAIL PROTECTED]> > To: sage-devel@googlegroups.com, [EMAIL PROTECTED], > "Mike Stillman" <[EMAIL PROTECTED]> > Subject: Re: [sage-devel] mpolynomial factorization > > On Dec 3, 2007 7:04 AM, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > I've been researching this slow mpolynomial factorization a bit more and > > haven't come up with any good news. Hans (from singular) replied to my > > forum > > post at > > http://singular.mathematik.uni-kl.de/forum/viewtopic.php?t=1652 > > It seems as though singular's random choices of evaluation points needs some > > tuning. I can't make a judgement whether it is a good algorithm on the > > whole. > > > > I had a little sage script running on my computer (a respectable but aging > > pentium 4) for the past 4 days. I rewrote it to use magma for the > > factorization (nothing else changed in the script) and ran it on sage.math. > > I can compute much more on sage.math with help from magma in 2 minutes than > > I > > did in 4 days at home. All that to say: bah humbug! > > That's a nice illustration of using the Sage interfaces :-) > > > Anyhow, is singular our only option for multivariate factorization? > > NO, there are other options, though none are in Sage standard yet. > > 1. I've heard the cocoa lib 5 can also do this, and perhaps do it > better, but I don't know. > I really hope somebody will download it and try it out to see what happens: > > http://cocoa.dima.unige.it/cocoalib/ > > It's a C++ library, so you'll have to write a bunch of code just to > test it, but there > might be a lot of examples. > > If Cocoalib and do factorization quickly, it might make for a compelling > reason > to include it in Sage. Also, Cocoa is small, builds quickly and easily, > etc. > > 2. Macaulay2 also factors multivariate polynomials. It does your test problem > on sage.math in 1.8 seconds every time, so it is vastly better than Singular > at > that example, but slower than Magma. > > sage: R.<p10,g0,g1,g2,g3,g4,X1,X2> = QQ[] > sage: macaulay2(R) > QQ [p10, g0, g1, g2, g3, g4, X1, X2, MonomialOrder => GRevLex, > MonomialSize => 16] > sage: 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; > sage: time t.factor() # using singular > give up after a while -- maybe 30 seconds?? > sage: s = macaulay2(t) > sage: time h = s.factor() > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > Wall time: 1.81 > sage: h > new Product from {new Power from {p10^8*X2-1, 1}, new Power from > {p10^8*X1-1, 1}, new Power from {-p10^18*X1*X2+1, 1}, new Power from > {p10^32*X2^4+p10^24*X2^3+p10^16*X2^2+p10^8*X2+1, 1}, new Power from > {p10^32*X1^4+p10^24*X1^3+p10^16*X1^2+p10^8*X1+1, 1}, new Power from > {p10^72*X1^4*X2^4+p10^54*X1^3*X2^3+p10^36*X1^2*X2^2+p10^18*X1*X2+1, > 1}} > > 3. Whatever Magma is doing, it's a really kick ass algorithm: > > sage: time h = k.Factorization() > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > Wall time: 0.01 > sage: h > > [ > <p10^8*X2 - 1, 1>, > <p10^8*X1 - 1, 1>, > <p10^18*X1*X2 - 1, 1>, > <p10^32*X2^4 + p10^24*X2^3 + p10^16*X2^2 + p10^8*X2 + 1, 1>, > <p10^32*X1^4 + p10^24*X1^3 + p10^16*X1^2 + p10^8*X1 + 1, 1>, > <p10^72*X1^4*X2^4 + p10^54*X1^3*X2^3 + p10^36*X1^2*X2^2 + p10^18*X1*X2 + 1, 1> > ] > > > In case you're interested, Mathematica -- which should likely be very > fast at this sort > of thing -- is slower than Macaulay2. > > sage: m = mathematica(t) > sage: m > 1 - p10^40*X1^5 - p10^40*X2^5 + p10^80*X1^5*X2^5 - p10^90*X1^5*X2^5 + > p10^130*X1^10*X2^5 + p10^130*X1^5*X2^10 - p10^170*X1^10*X2^10 > sage: time h=m.Factor() > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > Wall time: 3.57 > sage: h > -((-1 + p10^8*X1)*(1 + p10^8*X1 + p10^16*X1^2 + p10^24*X1^3 + p10^32*X1^4)* > (-1 + p10^8*X2)*(-1 + p10^18*X1*X2)*(1 + p10^8*X2 + p10^16*X2^2 + > p10^24*X2^3 + p10^32*X2^4)*(1 + p10^18*X1*X2 + p10^36*X1^2*X2^2 + > p10^54*X1^3*X2^3 + p10^72*X1^4*X2^4)) > > However, MAPLE IS BLAZINGLY FAST! > > sage: m = maple(t) > sage: t = maple.cputime() > sage: time h = m.factor() > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > Wall time: 0.10 > sage: print maple.cputime(t) > 0.0 > sage: h > > -(p10^8*X2-1)*(p10^32*X2^4+p10^24*X2^3+p10^16*X2^2+p10^8*X2+1)*(p10^8*X1-1)*( > p10^32*X1^4+p10^24*X1^3+p10^16*X1^2+p10^8*X1+1)*(p10^18*X1*X2-1)*(p10^72*X1^4* > X2^4+p10^54*X1^3*X2^3+p10^36*X1^2*X2^2+p10^18*X1*X2+1) > > SO -- find out what algorithm Maple or Magma is using and that's > probably the one for us. > There was a big discussion on sage-devel a few weeks ago about Maple > being "open source"... > > Of course as I mentioned before Maxima is crap for this calculation: > > sage: m = maxima(t) > sage: time k = m.factor() > [wait forever...] > > > Is there > > a guru out there that can vouch for or against their algorithm as a whole. > > Definitely I can't, but I've cc'd Dan Grayson and Mike Stillman, and > they might have > some comments about what's going on. Your M2 is vastly slower at that example > than Magma/Maple, but about the same as Mathematica. Any ideas why? > > > I've found this article (by Shuhong Gao): > > http://kiwistrawberry.us/research/multivariate-factoring.pdf > > which seems fairly recent and factors bivariate polynomials. The algorithm > > also uses random evaluation points to get down to a bivariate polynomial (I > > guess, for all I know, it's the same algorithm as singular uses). > > -- 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/ -~----------~----~----~----~------~----~------~--~---
