Sage: Ticket #10284: Infinite loop in gcd() via pynac-0.2.1
https://trac.sagemath.org/ticket/10284
<p>
This bug was fixed in GiNaC 1.5.x but pynac forked off the 1.4.x branch. See
</p>
<p>
<a class="ext-link" href="http://www.ginac.de/ginac.git?p=ginac.git;a=commit;h=edf1ae46a926d0a718063c149b78c1b9a7ec2043"><span class="icon"></span>http://www.ginac.de/ginac.git?p=ginac.git;a=commit;h=edf1ae46a926d0a718063c149b78c1b9a7ec2043</a>
</p>
<p>
Translated to sage syntax from the GiNaC 1.5.x unit tests:
</p>
<pre class="wiki">u = var('u')
v = var('v')
w = var('w')
x = var('x')
y = var('y')
z = var('z')
e = 792*z^8*w^4*x^3*y^4*u^7 + 24*z^4*w^4*x^2*y^3*u^4 + \
264*z^8*w^3*x^2*y^7*u^5 + 198*z^4*w^5*x^5*y*u^6 + 110*z^2*w^3*x^5*y^4*u^6 \
- 120*z^8*w*x^4*u^6 - 480*z^5*w*x^4*y^6*u^8 - 720*z^7*x^3*y^3*u^7 + \
165*z^4*w^2*x^4*y*u^5 + 450*z^8*w^6*x^2*y*u^8 + 40*z^2*w^3*x^3*y^3*u^6 - \
288*z^7*w^2*x^3*y^6*u^6 + 250*z^6*w^4*x^2*y^4*u^8 + \
576*z^7*w^7*x^2*y^4*u^8 - 80*z^6*w^2*x^5*y^3*u^7 - 144*z^8*w^4*x^5*u^7 + \
120*z^4*w*x^2*y^6*u^6 + 320*z^5*w^5*x^2*y^7*u^8 + 192*z^7*w^6*x*y^7*u^6 - \
12*z^4*w^3*x^3*y^5*u^6 - 36*z^4*w^4*x^4*y^2*u^8 + 72*z^4*w^5*x^3*u^6 - \
20*z^2*w^2*x^4*y^5*u^8 + 660*z^8*w*x^2*y^4*u^6 + 66*z^4*w^4*x^4*y^4*u^4 + \
440*z^6*w^2*x^3*y^7*u^7 - 30*z^4*w*x^3*y^2*u^7 - 48*z^8*w^3*x^4*y^3*u^5 + \
72*z^6*w^2*x*y^6*u^4 - 864*z^7*w^3*x^4*y^3*u^8 + 480*z^7*w^4*x*y^4*u^7 + \
60*z^4*w^2*x^2*u^5 + 375*z^8*w^3*x*y*u^7 + 150*z^8*w^5*x*y^4*u^6 + \
180*z^6*x*y^3*u^5 + 216*z^6*w^3*x^2*y^3*u^6;
E = e.polynomial(QQ)
G = gcd(E, e.diff(x).polynomial(QQ))
G # Singular gets it correct: u^4*z^2
g = gcd(e, e.diff(x)) # pynac falls into an infinite loop
# also there is potential for a wrong answer
</pre><p>
So, it appears as if we need to use Singular or sync to at least GiNaC 1.5.8 .
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10284
Trac 1.1.6burcinThu, 18 Nov 2010 16:04:55 GMT
https://trac.sagemath.org/ticket/10284#comment:1
https://trac.sagemath.org/ticket/10284#comment:1
<p>
Replying to <a class="closed ticket" href="https://trac.sagemath.org/ticket/10284" title="defect: Infinite loop in gcd() via pynac-0.2.1 (closed: invalid)">bgoodri</a>:
</p>
<blockquote class="citation">
<p>
This bug was fixed in GiNaC 1.5.x but pynac forked off the 1.4.x branch. See
</p>
<p>
<a class="ext-link" href="http://www.ginac.de/ginac.git?p=ginac.git;a=commit;h=edf1ae46a926d0a718063c149b78c1b9a7ec2043"><span class="icon"></span>http://www.ginac.de/ginac.git?p=ginac.git;a=commit;h=edf1ae46a926d0a718063c149b78c1b9a7ec2043</a>
</p>
</blockquote>
<p>
<snipped example>
</p>
<blockquote class="citation">
<p>
So, it appears as if we need to use Singular or sync to at least GiNaC 1.5.8 .
</p>
</blockquote>
<p>
If there isn't a straightforward way to adopt the patch that went into GiNaC 1.5.x, I don't think it's worth the time to sync the gcd code in pynac with the latest version in GiNaC.
</p>
<p>
Multivariate gcd is a hard problem. IMHO, we should have a single, well-tested, fast implementation and use that everywhere in Sage, rather than rely on the efforts of each upstream developer team to implement their own with a unique set of bugs.
</p>
<p>
Using Factory as a library doesn't look too hard:
</p>
<p>
<a class="ext-link" href="http://www.singular.uni-kl.de/svn/trunk/factory/examples/gcd.cc"><span class="icon"></span>http://www.singular.uni-kl.de/svn/trunk/factory/examples/gcd.cc</a>
</p>
<p>
The README file is helpful, although I'm not sure if there is any other documentation available:
</p>
<p>
<a class="ext-link" href="http://www.singular.uni-kl.de/svn/trunk/factory/README"><span class="icon"></span>http://www.singular.uni-kl.de/svn/trunk/factory/README</a>
</p>
<p>
I'm quite sure we would get good feedback from the current developers if the issues are discussed at the libsingular-devel list:
</p>
<p>
<a class="ext-link" href="http://groups.google.com/group/libsingular-devel"><span class="icon"></span>http://groups.google.com/group/libsingular-devel</a>
</p>
<p>
It seems that once the necessary changes are made in pynac to use Factory for gcd's, it would be straightforward to plug in another library, perhaps giac, later.
</p>
TicketbgoodriThu, 18 Nov 2010 19:07:48 GMT
https://trac.sagemath.org/ticket/10284#comment:2
https://trac.sagemath.org/ticket/10284#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10284#comment:1" title="Comment 1">burcin</a>:
</p>
<p>
All valid points. Maybe we should move the discussion to sage-devel to get more input?
</p>
<p>
If you want a quick hack fix for this particular bug, I think it would suffice to add some logic to py_gcd to coerce rational expressions with a .polynomial(QQ) and call gcd() from sage/rings/polynomial/multi_polynomial_libsingular instead of gcd() from sage/rings/arith . I tried that a couple of days ago and it was insufficient to fix <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/10268" title="enhancement: adding GiNaC method to simplify_rational (needs_work)">#10268</a>, but it would presumably fix this bug. Not that <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/10268" title="enhancement: adding GiNaC method to simplify_rational (needs_work)">#10268</a> is a killer feature but GiNaC does seem to have a significant speed advantage over Maxima at simplifying rationals.
</p>
<p>
As for the more general GiNaC / pynac vs. Singular / Factory comparison (not to mention giac), I haven't investigated enough to have a super strong opinion about it. I agree it would be easier to maintain if there were only one interface. On the other hand, it is good to make it possible to use whatever might be fastest and have the most features for a particular problem. Also, in both cases, we are lagging behind upstream, but they have a lot of the same algorithms now. Singular 3.1-2 fixed / improved a lot of multivariate polynomial stuff but sage currently ships with 3.0-something. Similarly, GiNaC 1.5.8 fixed this bug and 1.5.0 added a lot of functionality in the polynomials/ directory, but pynac is based on 1.4-something.
</p>
<p>
What I like about (the latest) GiNaC is that it is closer to the sage SR concept, whereas Singular is more literal about its rings. For example, you can do this
</p>
<pre class="wiki">goodrich@Y560:/tmp$ ginsh
ginsh - GiNaC Interactive Shell (ginac V1.5.8)
__, _______ Copyright (C) 1999-2010 Johannes Gutenberg University Mainz,
(__) * | Germany. This is free software with ABSOLUTELY NO WARRANTY.
._) i N a C | You are welcome to redistribute it under certain conditions.
<-------------' For details type `warranty;'.
Type ?? for a list of help topics.
> f = Pi^2 - 1;
-1+Pi^2
> g = Pi + 1;
1+Pi
> normal(f/g);
-1+Pi
> quit;
</pre><p>
and similarly with other transcendental numbers and trig and so forth. AFAIK, Singular would throw an error about QQness instead of determining that Pi - 1 was the greatest common factor.
</p>
<p>
There is a lot to like about Singular too, which is probably why William wrote those things in TODO.txt and the docstrings. Some of that seems to have changed in the last couple of years though.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/10284#comment:3
https://trac.sagemath.org/ticket/10284#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/10284#comment:4
https://trac.sagemath.org/ticket/10284#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/10284#comment:5
https://trac.sagemath.org/ticket/10284#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/10284#comment:6
https://trac.sagemath.org/ticket/10284#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketrwsSat, 31 Jan 2015 07:43:00 GMT
https://trac.sagemath.org/ticket/10284#comment:7
https://trac.sagemath.org/ticket/10284#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10284#comment:1" title="Comment 1">burcin</a>:
</p>
<blockquote class="citation">
<p>
Using Factory as a library doesn't look too hard:
</p>
</blockquote>
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/17703" title="defect: use giac for symbolic multivar gcd (closed: wontfix)">#17703</a>.
</p>
TicketrwsWed, 01 Jun 2016 07:45:11 GMT
https://trac.sagemath.org/ticket/10284#comment:8
https://trac.sagemath.org/ticket/10284#comment:8
<p>
(Optionally) fixed in Pynac-0.6.6.
</p>
TicketrwsThu, 24 Nov 2016 14:06:03 GMTdependencies set
https://trac.sagemath.org/ticket/10284#comment:9
https://trac.sagemath.org/ticket/10284#comment:9
<ul>
<li><strong>dependencies</strong>
set to <em>pynac-0.7.1</em>
</li>
</ul>
<p>
Unconditionally fixed in pynac git master by adding a libfactory interface and using its GCD. Fix will be in pynac-0.7.1.
</p>
TicketrwsThu, 24 Nov 2016 16:05:09 GMTdependencies changed
https://trac.sagemath.org/ticket/10284#comment:10
https://trac.sagemath.org/ticket/10284#comment:10
<ul>
<li><strong>dependencies</strong>
changed from <em>pynac-0.7.1</em> to <em>#21963</em>
</li>
</ul>
TicketrwsTue, 20 Dec 2016 14:37:00 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/10284#comment:11
https://trac.sagemath.org/ticket/10284#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
Fixed via pynac-0.7.1, the doctest is already included in <code>expression.pyx</code>.
</p>
TicketchapotonFri, 06 Jan 2017 08:58:31 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/10284#comment:12
https://trac.sagemath.org/ticket/10284#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
ok
</p>
TicketvbraunSat, 21 Jan 2017 18:03:11 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/10284#comment:13
https://trac.sagemath.org/ticket/10284#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
</ul>
Ticket