[sage-devel] Re: singular gcd slow-down
2007/9/19, Joel B. Mohler [EMAIL PROTECTED]: On Wednesday 19 September 2007 16:22, William Stein wrote: I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. I'll be looking into implementing that. It makes me disgruntled to be at the mercy of mathematica (or pick your favorite big commercial m). :D. FYI, I plan on implementing a multivariate gcd algorithm for Sage over RR and CC some time next year. The algorithm is by Kaltofen et al. Here's the abstract: Abstract. We consider the problem of computing minimal real or complex deformations to the coefficients in a list of relatively prime real or complex multivariate polynomials such that the deformed polynomials have a greatest common divisor (GCD) of at least a given degree k. In addition,we restrict the deformed coefficients by a given set of linear constraints, thus introducing the linearly constrained approximate GCD problem. We present an algorithm based on a version of the structured There is already an implementation of the algorithm written in maple available here if anyone is interested: http://www4.ncsu.edu/~kaltofen/software/manystln/ didier -- Joel --~--~-~--~~~---~--~~ 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On 9/19/07, Joel B. Mohler [EMAIL PROTECTED] wrote:
As I wrote on sage-devel a bit earlier, I had some polynomials that were
causing singular gcd to slow down dramatically. I had thought this was
inconsistent, but upon more investigation it seems very consistent (on two
different computers).
Here's some singular code to illustrate the problem. The first one computes
the gcd slowly, but not too bad (several seconds).
http://sage.math.washington.edu/home/jbmohler/gcd_fast.singular
This one takes a long time on my computer (at least a couple of minutes).
http://sage.math.washington.edu/home/jbmohler/gcd_slow.singular
Those time indications are on a P4 2.4 ghz. Memory usage of the Singular
executable is listed in 'top' at 12 MB (which seems perfectly reasonable to
me). Note also that mathematica (on sage.math) can write the ratio of these
polynomials in reduced form with-in a second (I'm supposing it computes a gcd
on the way to doing this).
Just for clarity, why not just compute the GCD with mathematica?
Anyway, I'm more familiar with Magma, so I computed the
above GCD that is slow in Sage with Magma and it takes 0.08 seconds.
http://sage.math.washington.edu/home/was/tmp/g.m
The answer gcd is:
x0*x1*x3^2*x4^2*x5^2 - x0*x1*x3*x4*x5 - x3*x4*x5 + 1
What algorithm does Singular use for GCD's over QQ?
If you take the slow Singular script you posted and
change the characteristic from 0 to some prime number, e.g.,
389, then the calculation in Singular is... interestingly, exactly
0.08 seconds too (identical to Magma).
This suggests Magma is using a modular algorithm for polynomial
gcd over QQ, but Singular isn't.
it would be nice if somebody who actually knows something
about multivariate gcd's could comment on options for
modular algorithms, since we could just implement one in
Sage on top of Singular's blazingly fast mod-p GCD code.
I computed the semi-random polynomials from this python script:
http://sage.math.washington.edu/home/jbmohler/singular_vs_mathematica.py
Basically, they are products of binomials of the form
(1-{x0}^{e0}*...*{xn}^{en})
where the {ei} are chosen randomly from {0,1}. I multiply about 8-12 of these
together to get polynomials of approximately 2^8 to 2^12 monomials. There is
a huge speed difference between n=4 and n=5 (5 variables vs. 6 variables).
It also seems to make a difference if I select my {ei} from a larger set (say
{0,1,...,10}). This seems to be significantly faster (I'm guessing it's
because the gcd is of lower degree).
I've now reproduced this with the singular that is built from sage and also
with a singular build from the singular website (3.0.3-ix86-Linux).
Thanks
Joel
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~-~--~~~---~--~~
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/
-~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On Sep 19, 9:55 pm, William Stein [EMAIL PROTECTED] wrote:
On 9/19/07, Joel B. Mohler [EMAIL PROTECTED] wrote:
As I wrote on sage-devel a bit earlier, I had some polynomials that were
causing singular gcd to slow down dramatically. I had thought this was
inconsistent, but upon more investigation it seems very consistent (on two
different computers).
Here's some singular code to illustrate the problem. The first one computes
the gcd slowly, but not too bad (several seconds).
http://sage.math.washington.edu/home/jbmohler/gcd_fast.singular
This one takes a long time on my computer (at least a couple of minutes).
http://sage.math.washington.edu/home/jbmohler/gcd_slow.singular
Those time indications are on a P4 2.4 ghz. Memory usage of the Singular
executable is listed in 'top' at 12 MB (which seems perfectly reasonable to
me). Note also that mathematica (on sage.math) can write the ratio of these
polynomials in reduced form with-in a second (I'm supposing it computes a
gcd
on the way to doing this).
Just for clarity, why not just compute the GCD with mathematica?
Anyway, I'm more familiar with Magma, so I computed the
above GCD that is slow in Sage with Magma and it takes 0.08 seconds.
http://sage.math.washington.edu/home/was/tmp/g.m
The answer gcd is:
x0*x1*x3^2*x4^2*x5^2 - x0*x1*x3*x4*x5 - x3*x4*x5 + 1
What algorithm does Singular use for GCD's over QQ?
If you take the slow Singular script you posted and
change the characteristic from 0 to some prime number, e.g.,
389, then the calculation in Singular is... interestingly, exactly
0.08 seconds too (identical to Magma).
This suggests Magma is using a modular algorithm for polynomial
gcd over QQ, but Singular isn't.
it would be nice if somebody who actually knows something
about multivariate gcd's could comment on options for
modular algorithms, since we could just implement one in
Sage on top of Singular's blazingly fast mod-p GCD code.
Well, we had some more discussion in #sage-devel and rpw posted an
interesting link:
http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html
In summary: Singular's multivariate GCD is slower by orders of
magnitude. Magma's algorithms are described at:
http://www.msri.org/about/computing/docs/magma/html/text587.htm
I don't know how current the documentation is, though.
Cheers,
Michael
I computed the semi-random polynomials from this python script:
http://sage.math.washington.edu/home/jbmohler/singular_vs_mathematica.py
Basically, they are products of binomials of the form
(1-{x0}^{e0}*...*{xn}^{en})
where the {ei} are chosen randomly from {0,1}. I multiply about 8-12 of
these
together to get polynomials of approximately 2^8 to 2^12 monomials. There
is
a huge speed difference between n=4 and n=5 (5 variables vs. 6 variables).
It also seems to make a difference if I select my {ei} from a larger set
(say
{0,1,...,10}). This seems to be significantly faster (I'm guessing it's
because the gcd is of lower degree).
I've now reproduced this with the singular that is built from sage and also
with a singular build from the singular website (3.0.3-ix86-Linux).
Thanks
Joel
--
William Stein
Associate Professor of Mathematics
University of Washingtonhttp://wstein.org
--~--~-~--~~~---~--~~
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/
-~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On 9/19/07, mabshoff [EMAIL PROTECTED] Well, we had some more discussion in #sage-devel and rpw posted an interesting link: http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html In summary: Singular's multivariate GCD is slower by orders of magnitude. Magma's algorithms are described at: http://www.msri.org/about/computing/docs/magma/html/text587.htm I don't know how current the documentation is, though. I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. Who wants to be a hero -- like Jon Bober and number of partitions -- and implement this for Sage, so that multivariate GCD's aren't embarrassingly slow in Sage anymore? This slowness *has* been something reported to me on several occasions during the last 2 years: http://trac.sagemath.org/sage_trac/ticket/696 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On Wednesday 19 September 2007 15:55, William Stein wrote: Just for clarity, why not just compute the GCD with mathematica? Well, I am doing that. I assumed that I had found a slow corner case that singular folks would want to fix. I'm not entirely sure that this point how small that corner is ... or whether mathematica and magma are simply much faster with gcd's of this magnitude. Obviously, we would all be happier though if sage was at least in the ballpark for speed on this. It kind of hampers sage as an open source solution for what I'm doing ... it basically means I can only get about 4 numbers in my desired sequence vs. about 7 or 8 probably (but I haven't figured that out quite yet because of other optimization that is needed). -- Joel --~--~-~--~~~---~--~~ 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On 9/19/07, Joel B. Mohler [EMAIL PROTECTED] wrote: On Wednesday 19 September 2007 15:55, William Stein wrote: Just for clarity, why not just compute the GCD with mathematica? Well, I am doing that. I didn't mean for your program -- just for benchmarking purposes. I assumed that I had found a slow corner case that singular folks would want to fix. Definitely! Though I wonder if its really a corner case. I have had repeated problems with their GCD in char 0. I'm not entirely sure that this point how small that corner is ... Yep. or whether mathematica and magma are simply much faster with gcd's of this magnitude. I think they are over QQ, but only because I suspect Singular (or any open source general program at all for that matter!) just doesn't have a good algorithm implemented over QQ. Obviously, we would all be happier though if sage was at least in the ballpark for speed on this. I think it should be a high priority to make it nearly match in speed, and given how good singular is mod p I think this is reasonable to expect. It kind of hampers sage as an open source solution for what I'm doing ... it basically means I can only get about 4 numbers in my desired sequence vs. about 7 or 8 probably (but I haven't figured that out quite yet because of other optimization that is needed). It's truly embarrassing. 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On Sep 19, 4:22 pm, William Stein [EMAIL PROTECTED] wrote: On 9/19/07, mabshoff [EMAIL PROTECTED] Well, we had some more discussion in #sage-devel and rpw posted an interesting link: http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html In summary: Singular's multivariate GCD is slower by orders of magnitude. Magma's algorithms are described at: http://www.msri.org/about/computing/docs/magma/html/text587.htm I don't know how current the documentation is, though. I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. Who wants to be a hero -- like Jon Bober and number of partitions -- and implement this for Sage, so that multivariate GCD's aren't embarrassingly slow in Sage anymore? This slowness *has* been something reported to me on several occasions during the last 2 years: http://trac.sagemath.org/sage_trac/ticket/696 William It might be better to contribute such a implementation directly to singular. The current singular implementation is described at: http://www.singular.uni-kl.de/Manual/latest/sing_32.htm as using the algorithm described in: http://doi.acm.org/10.1145/800192.805698 --~--~-~--~~~---~--~~ 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On Sep 19, 10:52 pm, Jack Schmidt [EMAIL PROTECTED] wrote: On Sep 19, 4:22 pm, William Stein [EMAIL PROTECTED] wrote: SNIP Who wants to be a hero -- like Jon Bober and number of partitions -- and implement this for Sage, so that multivariate GCD's aren't embarrassingly slow in Sage anymore? This slowness *has* been something reported to me on several occasions during the last 2 years: http://trac.sagemath.org/sage_trac/ticket/696 that is http://trac.sagemath.org/sage_trac/ticket/694 now William Hello It might be better to contribute such a implementation directly to singular. In the end that might happen, but development in Singular is more complicated because only malb really knows the Singular code and memory management is more complicated, compiling cython code is much quicker and for prototyping that counts (at least in my opinion). The current singular implementation is described at: http://www.singular.uni-kl.de/Manual/latest/sing_32.htm as using the algorithm described in: http://doi.acm.org/10.1145/800192.805698 Cool. 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/ -~--~~~~--~~--~--~---
[sage-devel] Re: singular gcd slow-down
On Wednesday 19 September 2007 16:22, William Stein wrote: I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. I'll be looking into implementing that. It makes me disgruntled to be at the mercy of mathematica (or pick your favorite big commercial m). :D. -- Joel --~--~-~--~~~---~--~~ 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/ -~--~~~~--~~--~--~---
