On Dec 3, 8:32 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> On Dec 3, 2007 11:15 AM, mabshoff
>
>
>
> <[EMAIL PROTECTED]> wrote:
> > On Dec 3, 7:49 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> > > 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.
>
> > I tend to agree, but there is a CoCoALib.spkg that needs a little work
> > and malb and I wrote some code to get multivariate polynomials working
> > with CoCoALib back in March, so there is relatively litte left to do.
>
> I am very much for having a cocoa optional spkg as soon as possible
> (tomorrow?), and support in Sage for using it.
CoCoA or [Ap]CoCoALib? CoCoA is trivial to do, but it will be binary.
> But I won't include anything standard in Sage unless there
> is a very compelling reason to do so. Everything we include makes
> porting, maintaining and distributing Sage
> that much harder, and we're pretty close to the limit as it is
> now. And things like getting Sage into Debian,
> etc., aren't really go to help much (if at all), since there's still OSX,
> other Linux distros, solaris, etc., to worry about.
ApCoCoALib compiles out of the box on all of the above and more, but I
agree with you that it needs to provide something sufficiently fast or
unique to become standard. That is the approximate algebraic
algorithms in ApCoCoALib, but we will see about that down the road.
> Along these lines, I think there is a very compelling need to include
> ATLAS in Sage as soon as we can (instead of using NETLIB BLAS
> and/or depending on something system-wide
> which might be broken), since it will so greatly improve the robustness
> of linear algebra in Sage. Next after that in importance is including
> the R statistical package in Sage. PolyBoRi should be a trivial-to-install
> optional package for a while before inclusion in standard Sage -- building
> PolyBoRi and R takes about the same time, and I think having R in every
> copy of Sage will be of interest to far more users.
>
Agreed, R & ATLAS should be the next thing to work on package-wise.
>
>
> > > 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#SECTION001...
>
> > > 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&d...
>
> > > 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!
>
> > IIRC that is the main problem with mv factoring, i.e. one algorithm
> > works very well on one class of polynomials while it can suck quite
> > badly at another. But this is mostly anecdotal, I never looked deeply
> > into this
>
> So we implement more than one algorithm.
>
But as far as I understand there is no [efficient] heuristic to choose
- but I am certainly not an expert on factorisation, so somebody
please enlighten us.
> William
Cheers,
Michael
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
