On Dec 3, 2007 8:56 AM, mabshoff <[EMAIL PROTECTED]> wrote: > > > > On Dec 3, 5:24 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > > On Dec 3, 2007 8:01 AM, mabshoff > > > > > > > > > <[EMAIL PROTECTED]> wrote: > > > > > On Dec 3, 4:47 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > > > > 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/ > > > > > Is that a hint for somebody? :) > > > > > > 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. > > > > > CoCoA 4.7.x and CoCoALib share the same factorization code (modulo > > > interfacing code), but if Joel provides me with the script I can run > > > it on top of CoCoA and give some quick feedback about the speed. I am > > > also fairly certain the the author of the code (John Abbott) would > > > certainly like feedback because the implementation in CoCoALib is > > > supposed to be improved upon soon. > > > > The benchmark is just to factor this polynomial over QQ: > > > > 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; > > > > the unknowns are: > > > > p10,g0,g1,g2,g3,g4,X1,X2 > > > > Ok, CoCoA is faster than MacCaulay2 on a system slightly slower than > sage.math. But I seem to have uncovered a bug in CoCoA [the > interpreter] on the way: > > ------------------------------- > -- The current ring is R ::= Q[x,y,z]; > ------------------------------- > > Use R::=Q[a,b,c,d,e,f,g,h]; > T:=-a^170*g^10*h^10+a^130*g^10*h^5+a^130*g^5*h^10- > a^90*g^5*h^5+a^80*g^5*h^5-a^40*g^5-a^40*h^5+1; > For I:=1 To 10 Do > Time L:=Factor(T); PrintLn; > Print L; > EndFor; > > Cpu time = 0.79, User time = 1 > [[a^18gh - 1, 1], [a^8h - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [a^8g - > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [-1, 1]] > Cpu time = 0.80, User time = 1 > [[a^18gh - 1, 1], [a^8g - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^8h - 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + > 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [-1, 1]]ERROR: > maximum deg in destination polynomial too low > ERROR: maximum deg in destination polynomial too low > ERROR: maximum deg in destination polynomial too low > ERROR: maximum deg in destination polynomial too low > > Cpu time = 0.84, User time = 1 > [[a^8h - 1, 1], [a^8g - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 + > a^18gh + 1, 1], [a^18gh - 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [-1, 1]] > Cpu time = 0.62, User time = 1 > [[a^8h - 1, 1], [a^8g - 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [a^72g^4h^4 + > a^54g^3h^3 + a^36g^2h^2 + a^18gh + 1, 1], [a^18gh - 1, 1], [-1, 1]] > Cpu time = 0.88, User time = 0 > [[a^18gh - 1, 1], [a^8h - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [a^8g - > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [-1, 1]] > Cpu time = 0.69, User time = 1 > [[a^8g - 1, 1], [a^8h - 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + > 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [a^72g^4h^4 + > a^54g^3h^3 + a^36g^2h^2 + a^18gh + 1, 1], [a^18gh - 1, 1], [-1, 1]] > Cpu time = 0.68, User time = 1 > [[a^18gh - 1, 1], [a^8h - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [a^8g - > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [-1, 1]] > Cpu time = 0.64, User time = 1 > [[a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 + a^18gh + 1, 1], [a^18gh - 1, > 1], [a^8g - 1, 1], [a^8h - 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g > + 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [-1, 1]] > Cpu time = 0.70, User time = 0 > [[a^18gh - 1, 1], [a^8g - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^8h - 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + > 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + 1, 1], [-1, 1]] > Cpu time = 0.73, User time = 1 > [[a^18gh - 1, 1], [a^8h - 1, 1], [a^72g^4h^4 + a^54g^3h^3 + a^36g^2h^2 > + a^18gh + 1, 1], [a^8g - 1, 1], [a^32h^4 + a^24h^3 + a^16h^2 + a^8h + > 1, 1], [a^32g^4 + a^24g^3 + a^16g^2 + a^8g + 1, 1], [-1, 1]] > > So let me check with CoCoALib before saying anything definite, but it > looks like it could finally be a good reason to get CoCoALib into > Sage. I am also sure that the linear algebra used in CoCoALib is quite > slow and can probably be improved quite a bit.
This is not so good, really. We should be aiming to beat maple/magma, which do this factorization in 0.01 seconds or so. Where are our reverse engineering experts? How come Maple is so fast at this? -- 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/ -~----------~----~----~----~------~----~------~--~---
