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/
-~----------~----~----~----~------~----~------~--~---
