Sage: Ticket #18242: Use composed_op for QQbar exactification
https://trac.sagemath.org/ticket/18242
<p>
In <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a>, is implemented an algorithm for computing the composed sum, difference, product and division of two polynomials. That can be used to fasten exactification in QQbar.
</p>
<p>
See also <a class="new ticket" href="https://trac.sagemath.org/ticket/17886" title="enhancement: Faster qqbar operations using resultants (new)">#17886</a>.
</p>
<hr />
<p>
From the older description
</p>
<p>
Here is an example in which a fast algorithm for resultants makes a difference in timings:
</p>
<pre class="wiki">sage: from sage.calculus.calculus import minpoly
sage: ex = solve(x^4 + x^3 + sqrt(2)*x + 1 == 0, x)[0].rhs()
sage: time minpoly(ex, algorithm='algebraic')
Wall time: 6.81 s
x^8 + 2*x^7 + x^6 + 2*x^4 + 2*x^3 - 2*x^2 + 1
</pre><p>
in commit 12a1053f78c9efee9f3e6c88eb2c1c89d2db4312
it takes 31s; the difference in timings is in the computation of resultants.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18242
Trac 1.1.6perniciFri, 17 Apr 2015 18:35:55 GMTdependencies set
https://trac.sagemath.org/ticket/18242#comment:1
https://trac.sagemath.org/ticket/18242#comment:1
<ul>
<li><strong>dependencies</strong>
set to <em>17886</em>
</li>
</ul>
TicketperniciFri, 17 Apr 2015 18:37:55 GMTdependencies changed
https://trac.sagemath.org/ticket/18242#comment:2
https://trac.sagemath.org/ticket/18242#comment:2
<ul>
<li><strong>dependencies</strong>
changed from <em>17886</em> to <em>#17886</em>
</li>
</ul>
TicketperniciFri, 17 Apr 2015 19:11:10 GMTdescription, summary changed
https://trac.sagemath.org/ticket/18242#comment:3
https://trac.sagemath.org/ticket/18242#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18242?action=diff&version=3">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Added algorithm computing special resolvents</em> to <em>Added algorithm computing special resultants</em>
</li>
</ul>
TicketperniciSat, 18 Apr 2015 09:00:38 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/18242#comment:4
https://trac.sagemath.org/ticket/18242#comment:4
<ul>
<li><strong>changetime</strong>
changed from <em>04/17/15 19:11:10</em> to <em>04/17/15 19:11:10</em>
</li>
<li><strong>branch</strong>
set to <em>u/pernici/ticket/18242</em>
</li>
<li><strong>time</strong>
changed from <em>04/17/15 18:32:52</em> to <em>04/17/15 18:32:52</em>
</li>
</ul>
TicketmmezzarobbaSat, 18 Apr 2015 18:23:33 GMTcc, commit set
https://trac.sagemath.org/ticket/18242#comment:5
https://trac.sagemath.org/ticket/18242#comment:5
<ul>
<li><strong>cc</strong>
<em>mmezzarobba</em> added
</li>
<li><strong>commit</strong>
set to <em>99617e90a98946fb435481c39a9dbbf4afc1996a</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=db116160d1d082b38c8cd1f8f90bd20feaef942b"><span class="icon"></span>db11616</a></td><td><code>trac #17886: Compute binary operations using resultants.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d4b91b4a11d2a5dceb592f33a55c79de637b801"><span class="icon"></span>8d4b91b</a></td><td><code>Return a descriptor, not an algebraic number.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=234b2c4f3435531007c095d278a4c02da8ee2365"><span class="icon"></span>234b2c4</a></td><td><code>Choose roots field based on approximation field.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=12a1053f78c9efee9f3e6c88eb2c1c89d2db4312"><span class="icon"></span>12a1053</a></td><td><code>Name myself in list of authors</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=99617e90a98946fb435481c39a9dbbf4afc1996a"><span class="icon"></span>99617e9</a></td><td><code> Added algorithm computing special resultants.</code>
</td></tr></table>
TicketperniciMon, 20 Apr 2015 10:51:06 GMTcc, description changed; keywords set
https://trac.sagemath.org/ticket/18242#comment:6
https://trac.sagemath.org/ticket/18242#comment:6
<ul>
<li><strong>keywords</strong>
<em>qqbar</em> <em>resultant</em> <em>exactify</em> <em>minpoly</em> added
</li>
<li><strong>cc</strong>
<em>gagern</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/18242?action=diff&version=6">diff</a>)
</li>
</ul>
TicketgitSat, 25 Apr 2015 11:06:31 GMTcommit changed
https://trac.sagemath.org/ticket/18242#comment:7
https://trac.sagemath.org/ticket/18242#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>99617e90a98946fb435481c39a9dbbf4afc1996a</em> to <em>584f444a68d2afcd6eb955da5ba7b344df3e630c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5cf75a4629c27cc1b85efafe217713752f82b8ea"><span class="icon"></span>5cf75a4</a></td><td><code>eliminated a call to `roots`</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=584f444a68d2afcd6eb955da5ba7b344df3e630c"><span class="icon"></span>584f444</a></td><td><code>Fixed bug in `AlgebraicNumber.__pow__`.</code>
</td></tr></table>
TicketvdelecroixWed, 29 Apr 2015 17:35:44 GMT
https://trac.sagemath.org/ticket/18242#comment:8
https://trac.sagemath.org/ticket/18242#comment:8
<p>
What does the following test from <code>584f444</code> is doing in <code>sage.rings.qqbar</code>!?
</p>
<pre class="wiki">sage: from sage.calculus.calculus import minpoly
sage: x = SR.var('x')
sage: ex = solve(x^4 + x + 1 == 0, x)[0].rhs()
sage: minpoly(ex, algorithm='algebraic')
x^4 + x + 1
</pre><p>
Why isn't it in <code>sage.calculus.calculus</code>?
</p>
TicketgitFri, 01 May 2015 10:47:48 GMTcommit changed
https://trac.sagemath.org/ticket/18242#comment:9
https://trac.sagemath.org/ticket/18242#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>584f444a68d2afcd6eb955da5ba7b344df3e630c</em> to <em>f37f86d8ac9aebcdd248301454545a7235f7dc1a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f37f86d8ac9aebcdd248301454545a7235f7dc1a"><span class="icon"></span>f37f86d</a></td><td><code>Changed test.</code>
</td></tr></table>
TicketgitSat, 02 May 2015 08:55:32 GMTcommit changed
https://trac.sagemath.org/ticket/18242#comment:10
https://trac.sagemath.org/ticket/18242#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>f37f86d8ac9aebcdd248301454545a7235f7dc1a</em> to <em>e0626dcabde6434cedd0c8736df198065b7a01d6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e0626dcabde6434cedd0c8736df198065b7a01d6"><span class="icon"></span>e0626dc</a></td><td><code>Added ``-`` and ``/`` operations using ``BFSS`` algorithm</code>
</td></tr></table>
TicketvdelecroixSat, 02 May 2015 10:10:32 GMT
https://trac.sagemath.org/ticket/18242#comment:11
https://trac.sagemath.org/ticket/18242#comment:11
<p>
Hello,
</p>
<p>
This ticket is still in state "new" but here are some remarks.
</p>
<p>
I would make this ticket independent of <a class="new ticket" href="https://trac.sagemath.org/ticket/17886" title="enhancement: Faster qqbar operations using resultants (new)">#17886</a> and ignore completely the potential application to <code>QQbar</code> (considering it in another ticket). It would be more flexible that way.
</p>
<p>
You implemented functions but I guess some of them would better be methods over polynomials (that is methods of <code>polynomial.polynomial_element.Polynomial</code>). For example, the <code>hadamard_product</code> or even the <code>composed_sum</code>. So move them. For <code>_hadamard_exp</code> it is only well defined in zero characteristic, so I am not sure what is the most appropriate; what do you think?
</p>
<p>
Did you do some serious benchmark to see which methods is faster depending on <code>p1</code> and <code>p2</code>? I guess it might aslo depends on the sparseness of the polynomials, the size of the coefficients.
</p>
<ol><li><code>newton_sum</code>
</li></ol><ul><li>I would rather add the power series ring object <code>R</code> as an argument. Building a ring is always costly.
</li></ul><ul><li>In
<pre class="wiki">p2 = R(QQ(1)/p1)
</pre>You would better do
<pre class="wiki">p2 = ~R(p1)
</pre>you would avoid computing <code>1/p1</code> in the fraction field.
</li></ul><ul><li>It would be faster to return <code>p3.truncate()</code> or <code>res.truncate()</code> instead of adding a truncation argument
</li></ul><ul><li>the argument name <code>typ</code> is horrible. Be more explicit about what it is. "a related expression" is not an explanation of the output!
</li></ul><ol start="2"><li>In <code>hadamard_product</code> there is no need to build the list of coefficients. You can access the coefficients of a polynomial <code>p</code> through <code>p[i]</code>. So just do
<pre class="wiki">def hadamard_product(p1, p2):
R = p1.parent()
return R([p1[i]*p2[i] for i in range(min(p1.degree(), p2.degree())+1)])
</pre>(I recall that this function must move as a method of univariate polynomials)
</li></ol><ol start="3"><li><code>composed_product</code>
</li></ol><ul><li>you duplicated the code for <code>BFSS</code>... moreover if the argument <code>algorithm</code> is neither <code>"resultant"</code> nor <code>"BFSS"</code> an error should be raised.
</li></ul><ul><li>I guess that the resultant method works in any characteristic?
</li></ul><p>
Sided note: the Bostan-Flajolet-Salvy-Schost deals with any characteristic. So it would be interesting to have a more general implementation.
</p>
<p>
Vincent
</p>
TicketvdelecroixSat, 02 May 2015 10:12:16 GMT
https://trac.sagemath.org/ticket/18242#comment:12
https://trac.sagemath.org/ticket/18242#comment:12
<p>
Note: I opened <a class="new ticket" href="https://trac.sagemath.org/ticket/18333" title="task: Cleanup and speedup in QQbar (new)">#18333</a> as a "task ticket" for the global cleaning of <code>QQbar</code>. Any comments, suggestions and reviews of tickets mentioned there are welcome!
</p>
TicketperniciSun, 03 May 2015 18:42:00 GMT
https://trac.sagemath.org/ticket/18242#comment:13
https://trac.sagemath.org/ticket/18242#comment:13
<p>
Hello Vincent,
I opened <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> implementing <code>composed_sum</code> and <code>composed_product</code> in <code>polynomial_element.pyx</code>,
taking into account most of your comments.
</p>
<p>
"hadamard_exp" appears as a method raising an exception if the polynomial is not on rationals.
</p>
<p>
I suspect that <code>newton_sum</code> method is not efficient, and it might be somewhere else in
Sage. As long as it is called by <code>composed_sum</code>, the time spent in <code>newton_sum</code> is negligible.
</p>
<p>
There is a small benchmark test, confirming the fact that the "BFSS" algorithm is asymptotically faster.
</p>
<p>
I do not plan to look at the "BFSS" algorithm in any characteristics.
</p>
<p>
I do not think I will open another ticket before <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> is merged, because I do not know how to
manage tickets depending on other tickets, or how to add the dependence on both <a class="new ticket" href="https://trac.sagemath.org/ticket/17886" title="enhancement: Faster qqbar operations using resultants (new)">#17886</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a>.
</p>
TicketvdelecroixSun, 03 May 2015 18:53:31 GMT
https://trac.sagemath.org/ticket/18242#comment:14
https://trac.sagemath.org/ticket/18242#comment:14
<p>
Hi Mario,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18242#comment:13" title="Comment 13">pernici</a>:
</p>
<blockquote class="citation">
<p>
Hello Vincent,
I opened <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> implementing <code>composed_sum</code> and <code>composed_product</code> in <code>polynomial_element.pyx</code>,
taking into account most of your comments.
</p>
</blockquote>
<p>
What is the intersection between this ticket and <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a>? I think from now it is better to discuss on <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> right?
</p>
<blockquote class="citation">
<p>
I do not plan to look at the "BFSS" algorithm in any characteristics.
</p>
</blockquote>
<p>
This is fine. Just add a <code>NOTE</code> somewhere like
</p>
<pre class="wiki">.. NOTE::
The BFSS algorithm could be implemented in any characteristic but it currently only works in characteristic zero (see paper XYZ).
</pre><p>
</p>
<blockquote class="citation">
<p>
I do not think I will open another ticket before <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> is merged, because I do not know how to
manage tickets depending on other tickets, or how to add the dependence on both <a class="new ticket" href="https://trac.sagemath.org/ticket/17886" title="enhancement: Faster qqbar operations using resultants (new)">#17886</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a>.
</p>
</blockquote>
<p>
Tickets depending on other tickets have two flavour:
</p>
<ul><li>from the trac point of view, this is just logical order (you just have to fill the dependency field in the ticket description)
</li><li>from the git point of view, if X depends on Y, it means that the branch of Y is based on top of X
</li></ul><p>
You are free to rebase git branch on other git branches. Or change the git branch on some ticket to some other branch.
</p>
<p>
Vincent
</p>
TicketvdelecroixSun, 03 May 2015 19:02:48 GMT
https://trac.sagemath.org/ticket/18242#comment:15
https://trac.sagemath.org/ticket/18242#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18242#comment:14" title="Comment 14">vdelecroix</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I do not plan to look at the "BFSS" algorithm in any characteristics.
</p>
</blockquote>
<p>
This is fine. Just add a <code>NOTE</code> somewhere like
</p>
</blockquote>
<p>
Ha nice. It is already there!
</p>
TicketvdelecroixMon, 18 Jan 2016 19:58:38 GMTsummary, description, milestone changed
https://trac.sagemath.org/ticket/18242#comment:16
https://trac.sagemath.org/ticket/18242#comment:16
<ul>
<li><strong>summary</strong>
changed from <em>Added algorithm computing special resultants</em> to <em>Use composed_op for QQbar exactification</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/18242?action=diff&version=16">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.7</em> to <em>sage-7.1</em>
</li>
</ul>
<p>
To me, it would make more sense to use directly <code>composed_op</code> in <a class="new ticket" href="https://trac.sagemath.org/ticket/17886" title="enhancement: Faster qqbar operations using resultants (new)">#17886</a> and close this ticket as duplicate.
</p>
Ticket