Opened 13 years ago

Closed 12 years ago

Last modified 12 years ago

# multivariate polynomial factorization over GF(p) in Sage is a total frickin' *EMBARRASSMENT*

Reported by: Owned by: was malb major sage-duplicate/invalid/wontfix commutative algebra

### Description

```teragon:~ was\$ sage
----------------------------------------------------------------------
| SAGE Version 2.10.1, Release Date: 2008-02-02                      |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading SAGE library. Current Mercurial branch is: abelian_rewrite
sage: R.<x,y,z> = GF(5)[]
sage: f = 2*y^9*z + 2*x^2*y^5*z^3 - y^9 - 2*x^4*z^2
sage: g = -2*x^2*y^9*z^4 - 2*x*y^3*z^11 - x^3*y^8*z - 2*x*z^8
sage: h = f*g
sage: time h.factor()
[hit control C after a few minutes!!]

WTF?!  Give me a break!
I mean this is pitiful, since in contrast, Magma takes 0.01 seconds.

sage: t = magma.cputime(); k.Factorization(); magma.cputime(t)
[
<z, 1>,
<x, 1>,
<y^9*z + x^2*y^5*z^3 + 2*y^9 + 4*x^4*z^2, 1>,
<x*y^9*z^3 + y^3*z^10 + 3*x^2*y^8 + z^7, 1>
]
0.01

Same behavior on any random reducible input!

------

Here's an old email Allan Steel sent me nearly 8 years ago about
exactly this sort of thing, where he calls Axioms performance on such
problems "some kind of a record!  (For absurdity?)".  He could
honestly say the same thing about Sage today (!) -- of course I really
mean Singular since that is what is doing the real work.

-------------------------------------

I found this so funny that I had to pass it on to everyone.

Paul Zimmermann keeps a web page with polynomial factorization challenges
and records at:

http://www.loria.fr/~zimmerma/mupad/

Here's the latest addition to it, which Paul Zimmermann inserted only
yesterday (near the end of the screen):

_Here_ is a degree 35 polynomial with 172 terms over F_5[x,y,z] to factor
(from MUG, Nivaldo Nunes de Medeiros Junior , January 1996). John
Abbott managed to factor it using Axiom in July 2000 on a 200MHz
Pentium in about 145000 seconds. Magma V2.6-2 factors it in 0.3 second
on a PII-400 under Linux.

I like the word "managed" -- sounds like a lot of effort!  In a mail
from John Abbot passed on to us, he actually says that the Axiom
machine was 150MHz, so I think that the 200MHz above is wrong.  But
allowing for Magma on a 400MHz machine versus Axiom on a 150MHz
machine, this gives a factor of:

145000 / 0.3 / (400/150) = 181250

This is somewhat ridiculous!   The Magma algorithm here is not an
extremely smart algorithm, and I'm surprised to see how amazingly slow
Axiom is for this!

The web page has the original poly and the Magma code too.  In the mail
passed on to us, Paul Zimmermann said that he only discovered yesterday
that Magma takes less than a second when he tried it!

I think this one must be some kind of a record!  (For absurdity?)

Allan
```

### comment:1 Changed 13 years ago by was

This looks very relevant:

### comment:2 Changed 13 years ago by was

• Summary changed from ticket: multivariate polynomial factorization over GF(p) in "three free world" is a total frickin' *EMBARRASSMENT* to ticket: multivariate polynomial factorization over GF(p) in Sage is a total frickin' *EMBARRASSMENT*

### comment:3 Changed 13 years ago by malb

• Summary changed from ticket: multivariate polynomial factorization over GF(p) in Sage is a total frickin' *EMBARRASSMENT* to multivariate polynomial factorization over GF(p) in Sage is a total frickin' *EMBARRASSMENT*

### comment:4 Changed 12 years ago by was

I tried this again today and:

```bsd:sage-3.2.alpha0 was\$ ./sage
----------------------------------------------------------------------
| SAGE Version 3.2.alpha0, Release Date: 2008-10-20                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------

sage: sage: R.<x,y,z> = GF(5)[]
sage: sage: f = 2*y^9*z + 2*x^2*y^5*z^3 - y^9 - 2*x^4*z^2
sage: sage: g = -2*x^2*y^9*z^4 - 2*x*y^3*z^11 - x^3*y^8*z - 2*x*z^8
sage: sage: h = f*g
sage: sage: time h.factor()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.08 s
z * x * (y^9*z + x^2*y^5*z^3 + 2*y^9 - x^4*z^2) * (x*y^9*z^3 + y^3*z^10 - 2*x^2*y^8 + z^7)
sage: sage: time h.factor()
[... wait for minutes!!!!...]
```

So, again I say - WTF?

William

### comment:5 Changed 12 years ago by was

• Resolution set to duplicate
• Status changed from new to closed

This is a dup of #1343

### comment:6 Changed 12 years ago by mabshoff

• Milestone changed from sage-3.2.1 to sage-duplicate/invalid/wontfix
Note: See TracTickets for help on using tickets.