On Dec 3, 2007 10:08 AM, Joel B. Mohler <[EMAIL PROTECTED]> wrote:
>
> On Mon, Dec 03, 2007 at 09:19:38AM -0800, mabshoff wrote:
> > On Dec 3, 6:15 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> > > On Dec 3, 2007 8:56 AM, mabshoff
> > > <[EMAIL PROTECTED]> wrote:
> > > > Cpu time = 0.80, User time = 1
> > >
> > > This is not so good, really.
> >
> > I know, but it seems to beat every open source package out there. And
> > multivariate factorization isn't "easy" as far as I understand. And
> > the linear algebra used in factorlib is quite naive IIRC, so there is
> > certainly room to improve. And the multivariate factorization code in
> > CoCoALib is completely stand alone and is also under the GPL.
>
> No, I agree this isn't the fastest in the world, but it's a great big gigantic
> improvement over the current state of affairs with singular. It's fast enough
> that it would totally make my current project feasible with all open code.
>
> Thanks for checking out cocoa for me Micheal. So, if I write an spkg and
> patch
> for the factorization method, what is the chance that it gets included in 2.9?
> Or is "somebody" now motivated to do this?
You could also use Macaulay2 -- it only takes twice as long as Cocoa for
this problem, and it's already fairly well integrated with Sage; it's via expect
too, so all that the user of your code needs is that M2 is installed somewhere
on their system.
That said -- we *really* really really need to find out what the RIGHT algorithm
is for this sort of factorization -- it's clearly not whatever is in
Macaulay2, Cocoa,
and Singular. As another data point, note that Reduce (which is installed
on sage.math) can do this factorization *instantly* also. Try it:
8:
factorize(-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);
72 4 4 54 3 3 36 2 2 18
{{ - (p10 *x1 *x2 + p10 *x1 *x2 + p10 *x1 *x2 + p10 *x1*x2 + 1),
1},
32 4 24 3 16 2 8
{p10 *x1 + p10 *x1 + p10 *x1 + p10 *x1 + 1,1},
32 4 24 3 16 2 8
{p10 *x2 + p10 *x2 + p10 *x2 + p10 *x2 + 1,1},
18
{p10 *x1*x2 - 1,1},
8
{p10 *x1 - 1,1},
8
{p10 *x2 - 1,1}}
---
This directory might have the source code:
/usr/local/reduce/packages/factor
/usr/local/reduce/packages/poly
Reduce code looks like gobledegook to me, though... so I can't tell yet.
Fortunately, the Reduce page about this command is here:
http://www.uni-koeln.de/REDUCE/3.6/doc/reduce/node119.html#SECTION001220000000000000000
and it says: "REDUCE is capable of factorizing univariate and
multivariate polynomials that have integer coefficients, finding all
factors that also have integer coefficients. The package for doing
this was written by Dr. Arthur C. Norman and Ms. P. Mary Ann Moore at
The University of Cambridge. It is described in P. M. A. Moore and A.
C. Norman, ``Implementing a Polynomial Factorization and GCD
Package'', Proc. SYMSAC '81, ACM (New York) (1981), 109-116." That
paper is here:
http://portal.acm.org/ft_gateway.cfm?id=806379&type=pdf&coll=portal&dl=ACM
It seems a little suspicious that an algorithm from 1981 also maybe
implemented in 1981 would blow
away Singular/Cocoa/Macaulay2/Maxima -- at least for certain inputs -- though!
> As a sidenote, I should add, that it's a great credit to sage that I could so
> easily pull in magma and get the job done anyhow. That's a killer feature.
> (But, I know, I'm preaching to the choir.)
:-) I'll quote you in a talk or grant application.
-- 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/
-~----------~----~----~----~------~----~------~--~---
