Sage: Ticket #21088: Base Class for Skew Polynomials over Finite Fields
https://trac.sagemath.org/ticket/21088
<p>
General, dense, univariate Skew Polynomials and <a class="missing wiki">SkewPolynomial?</a> Rings over generic commutative base rings are already supported in Ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>. This ticket proposes adding functionality for additional methods and optimized algorithms for such Skew Polynomials specifically over Finite Fields. This includes:
</p>
<ol><li>Class SkewPolynomial_finite_field(SkewPolynomial_generic_dense)
</li><li>Class SkewPolynomialRing_finite_field(SkewPolynomialRing_general)
</li></ol><p>
Note: There are a number of additional functionalities such as a class for Karatsuba multiplication in finite fields, center of skew polynomial ring, factorization and irreducibility that were written in the original <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>. Those will be added in separate tickets.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/21088
Trac 1.1.6arpitdmMon, 25 Jul 2016 00:08:14 GMTbranch set
https://trac.sagemath.org/ticket/21088#comment:1
https://trac.sagemath.org/ticket/21088#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/arpitdm/finite_fields_skew_polynomial</em>
</li>
</ul>
TicketarpitdmMon, 25 Jul 2016 00:14:00 GMTcommit set
https://trac.sagemath.org/ticket/21088#comment:2
https://trac.sagemath.org/ticket/21088#comment:2
<ul>
<li><strong>commit</strong>
set to <em>f4b841336eb6c557013e3684668dbd5db851c343</em>
</li>
</ul>
<p>
I've added the relevant classes and methods fixed all doctest errors that remained, added missing documentation and tests, and cleaned up the code. I am facing a couple of tiny issues with the minimum subspace polynomial (MSP), multi-point evaluation (MPE) and interpolation methods. I think I should have them ready in a short while.
Please let me know what else I can add to this ticket. If there isn't anything, then I'll open the ticket for review once I add MSP, MPE and interpolation.
</p>
<hr />
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=e189fec13d005a7fba39a429876c501fe95c05da"><span class="icon"></span>e189fec</a></td><td><code>removed side.py</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=1f62ef479a43b2402d4cf824c8b476aea40b9402"><span class="icon"></span>1f62ef4</a></td><td><code>added a section related to skew polynomils in the index file.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=abbd05ee2ed097aac032318d79001134f87fa9e7"><span class="icon"></span>abbd05e</a></td><td><code>removed double imports and unused classes and methods</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=8b337c5eb2e3f3d88864660487ce93db06fba517"><span class="icon"></span>8b337c5</a></td><td><code>improved description of module, definition of skew polynomial, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of a couple of methods.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=e0f3f421848b9a594a09e431d4eb0ac58e2b1d46"><span class="icon"></span>e0f3f42</a></td><td><code>changes to incorporate merging and into</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=0c8f6ec5fdae4746ce5b2989b426f78733ad3385"><span class="icon"></span>0c8f6ec</a></td><td><code>removed unnecessary imports</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=0641ecf3c9652b5479b967874a600cfd8a81c967"><span class="icon"></span>0641ecf</a></td><td><code>improved description of module, definition of skew polynomial ring, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of some methods. cleaned up code.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=22eab5df8c479f46d780c09625d3c7b790b3c816"><span class="icon"></span>22eab5d</a></td><td><code>same as previous commit</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=e46f7785524ade7db547b89dc27ab20f6459d368"><span class="icon"></span>e46f778</a></td><td><code>added the finite field files without karatsuba, center, irreducibility and factor stuff. cleaned up code. fixed doctest errors.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f4b841336eb6c557013e3684668dbd5db851c343"><span class="icon"></span>f4b8413</a></td><td><code>added missing documentation and some tests. added class SkewPolynomialRing_finite_field.</code>
</td></tr></table>
TicketgitMon, 25 Jul 2016 18:45:21 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:3
https://trac.sagemath.org/ticket/21088#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>f4b841336eb6c557013e3684668dbd5db851c343</em> to <em>1a06b095a569eba51bf2efdc2f86712cfa7b49aa</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="https://git.sagemath.org/sage.git/commit/?id=d49392ef39ca1d25cf48be649f0c2540b6e6cc48"><span class="icon"></span>d49392e</a></td><td><code>resolved single and double back tick formatting inconsistencies.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1a06b095a569eba51bf2efdc2f86712cfa7b49aa"><span class="icon"></span>1a06b09</a></td><td><code>added methods for multi-point evaluation, minimum subspace polynomial and interpolation</code>
</td></tr></table>
TicketjsrnWed, 27 Jul 2016 14:32:22 GMT
https://trac.sagemath.org/ticket/21088#comment:4
https://trac.sagemath.org/ticket/21088#comment:4
<p>
I've been thinking about whether the functions minimum_subspace_polynomial, multi_point_evaluation and interpolation_polynomial make any sense for general skew polynomial rings. I politely doubt that you were really considering this when you put the functions in SkewPolynomial_general (since the current implementation not at all works for general skew polynomial rings). But it turns out they *do* make sense and the algorithms more-or-less immediately works. So I suggest those three functions should be in their own tickets.
</p>
<ul><li>It seems minimum_subspace_polynomial *does* make sense in general, but it should be called something different and the implementation should be fixed. Firstly, the name and your current implementation is a verbose translation from linearized polynomials. This obviously leads to confusion and incorrect behaviour for even skew polynomials over finite fields with twist map the frobenius (for instance, in linearized polynomials <code>x^(q^i)</code> translates to <code>x^i</code> in skew polynomials).
</li></ul><blockquote>
<p>
My suggestion is to call the function <code>minimal_vanishing_polynomial</code>. Given elements a1,...,an, it is defined as the (unique) minimal-degree polynomial p
</p>
</blockquote>
<blockquote>
<p>
such that p is monic (leading coefficient is 1) and p(ai) = 0 for i=1,...,n.
</p>
</blockquote>
<ul><li>The implementation of course also needs to be slightly modified:
</li></ul><ul><li>Given an empty list of points, return 1.
</li></ul><ul><li>Given a singleton point a, return x - sigma(a)/a. (use pen-and-paper to see that I am right)
</li></ul><ul><li>Given a list of points, use divide and conquer as you do now.
</li></ul><ul><li>Then multi_point_evaluation also makes sense, and it's implementation is close to what you have now: as I've mentioned before, you should use sigma instead of q-powering everywhere. While were on it, you write "pow(a, pow(q, 0))" several places, but this is clearly just "a"!
</li></ul><ul><li><code>x = self([0,1])</code> should be <code>x = self._parent.gen()</code>.
</li></ul><ul><li>Instead of lines such as
</li></ul><pre class="wiki"> y = []
y.append(bla-bla)
return y
</pre><blockquote>
<p>
you should write
</p>
</blockquote>
<pre class="wiki"> return [ bla-bla ]
</pre><ul><li>In multi_point_evaluation you have a duplicate line <code>r = ....</code> with <code>return ...</code>. Worse, that line is incorrect: you shouldn't convert to sets, then union, then convert back to a list (you lose ordering of evaluations, and the user *wants* to know that e.g. multiple input evaluates to, say, 1). Just concatenate the two lists: <code>self.multi_point_evaluation(R_A, A) + self.multi_point_evaluation(R_B, B)</code>.
</li></ul><ul><li>minimum_subspace_polynomial and multi_point_evaluation are mutually recursive and will generate the same minimum subspace polynomials an exponential number of times right now. We need to add caching: add <code>@cached_method</code> to minimum_subspace_polynomial.
</li></ul><ul><li>multi_point_evaluation is a fairly complicated procedure compared to just calling <code>n</code> times <code>__call__</code>. Try to do timings to see if it is worth it. (Asymptotically, there is only a gain if some fast multiplication and <code>quo_rem</code> of skew polynomials is implemented, which it isn't).
</li></ul><ul><li>With minimum_subspace_polynomial and multi_point_evaluation then interpolation_polynomial also makes sense for general skew polynomials. The implementation you wrote immediately works, except that you again should replace <code>pow(x, (pow(q,0)</code> with <code>self._parent.one()</code>, and <code>x = self([0,1])</code> with <code>x = self._parent.gen()</code>.
</li></ul><ul><li>Note that all three functions are easily tested: for the minimum_subspace_polynomial, just check the degree of the output and that it evaluates to zero on all the input poins. For multi_point_evaluation, just check that the evaluations match using single <code>__call__</code>'s. For interpolation_polynomial just check that the degree is less than the number of points, and that the output evaluates correctly at all input. Be sure to test your functions on skew polynomials over finite fields, both with sigma being the Frobenius or a power of Frobenius, and also on skew polynomials over another ring.
</li></ul>
TicketjsrnWed, 27 Jul 2016 14:33:28 GMT
https://trac.sagemath.org/ticket/21088#comment:5
https://trac.sagemath.org/ticket/21088#comment:5
<p>
The point of the specialised implementations over finite fields is to have improved performance. Do you have timing results to demonstrate that each arithmetic operation is now faster than with the generic implementation?
</p>
TicketdlucasThu, 28 Jul 2016 08:36:26 GMT
https://trac.sagemath.org/ticket/21088#comment:6
https://trac.sagemath.org/ticket/21088#comment:6
<p>
Hello,
</p>
<p>
I have some more comments:
</p>
<ul><li>Is there any reason why <code>cdef</code> methods in <code>skew_polynomial_finite_field.pyx</code> are not doctested?
</li><li>In the same module, a lot of methods do not respect documentation conventions. See <code>cdef SkewPolynomial_finite_field_dense _rgcd</code> for instance, whose documentation is this single sentence: <code>Fast right gcd.</code>. Some methods (e.g. <code>_rightpow_</code>, <code>_leftpow</code>) do not even have this <code>Return(s) blah blah</code> line which explains what they're supposed to do...
</li><li><code>skew_polynomial_finite_field.pyx</code>'s title is <code>This module implements skew polynomials over finite fields.</code>. I think it should be changed to <code>Skew polynomials over finite fields</code>, or something equivalent.
</li><li>A lot of elements are not properly formatted in docstrings of <code>skew_polynomial_finite_field.pyx</code>: it should be <code><double backtick>self<double backtick></code> instead of <code>self</code>, etc.
</li><li>In <code>class SkewPolynomialRing_finite_field</code>, docstring of <code>twist_map</code> is not helpful as it says <code>Return the twist map</code>.
</li></ul>
TickettscrimThu, 28 Jul 2016 16:30:42 GMT
https://trac.sagemath.org/ticket/21088#comment:7
https://trac.sagemath.org/ticket/21088#comment:7
<p>
<code>cdef</code> methods/functions are not callable from Sage (i.e., python). They technically don't need to be doctested. However, there should be an <code>EXAMPLES::</code> that has a function that (indirectly) calls the method/function in question.
</p>
TicketgitThu, 28 Jul 2016 16:32:15 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:8
https://trac.sagemath.org/ticket/21088#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>1a06b095a569eba51bf2efdc2f86712cfa7b49aa</em> to <em>a6e93e12c1fefffde3615c8eab75a45b3c277ab2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b52fc9528249625e9498ac43f48376d4235f8b9d"><span class="icon"></span>b52fc95</a></td><td><code>using cached versions of 0 and 1 wherever applicable.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=6fb186ab4b9eedb41596053854996263e85c5fe7"><span class="icon"></span>6fb186a</a></td><td><code>changed Returns to Return and Note to NOTE for consistency. Removed trailing whitespaces. codeformatting for True, False and None objects.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1204f2d240bedaa2c7eef1bcba144b73150d9308"><span class="icon"></span>1204f2d</a></td><td><code>the current implementation of the :meth: __call__ was incorrect. added the correct and cythonized version.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=7e076fa503d41f940a4a363d92621369c128a0a5"><span class="icon"></span>7e076fa</a></td><td><code>moved module level docs to user entry point at the class level so that they are accessible at command line. added a SEEALSO block.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=69fecc4c93cfb17f0e348069a95b44e53ac79236"><span class="icon"></span>69fecc4</a></td><td><code>converted :meth: into a cpdef method with output type list. removed and directly use the attribute.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=271bface01f93c8dca5a1fb104da139224ae1e66"><span class="icon"></span>271bfac</a></td><td><code>removed some commented code and trailing whitespaces.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9a2fad2d0183dd5b3f5dae7da2628f9d8b52bf26"><span class="icon"></span>9a2fad2</a></td><td><code>merged changes from Tickets 13215 and 21088</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=eaca2535762165b7ace9896a3993d8ae7fb03eb8"><span class="icon"></span>eaca253</a></td><td><code>integrated skew polynomial finite field into sage. removed some compile and doctest errors.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=76640607bcbecccf6b969483cc112db06c6dd0d5"><span class="icon"></span>7664060</a></td><td><code>removed leftpow and rightpow methods from SkewPolynomial_finite_field_dense class because they require the 'bound' method which in turn requires 'center'. this will be added in another separate ticket with the rest of the center stuff.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a6e93e12c1fefffde3615c8eab75a45b3c277ab2"><span class="icon"></span>a6e93e1</a></td><td><code>added SEEALSO and TODO blocks and made small polishes to the documentation.</code>
</td></tr></table>
TicketarpitdmThu, 28 Jul 2016 16:44:47 GMT
https://trac.sagemath.org/ticket/21088#comment:9
https://trac.sagemath.org/ticket/21088#comment:9
<p>
Classes <code>SkewPolynomial_finite_field_dense</code> and <code>SkewPolynomialRing_finite_field</code> are now accessible at the command line. I've fixed the documentation for the latter class. I removed MPE, MVP, Interpolation, _leftpow_, _rightpow_ methods. The first three I am adding as a new ticket in a short while. The last two because they depend on "center"-related stuff and that comes in a later ticket.
</p>
<p>
I'm right now, making as many of the polishing changes as applicable from the discussions on <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>.
</p>
TicketarpitdmThu, 28 Jul 2016 17:00:27 GMT
https://trac.sagemath.org/ticket/21088#comment:10
https://trac.sagemath.org/ticket/21088#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:4" title="Comment 4">jsrn</a>:
</p>
<blockquote class="citation">
<p>
I've been thinking about whether the functions minimum_subspace_polynomial, multi_point_evaluation and interpolation_polynomial make any sense for general skew polynomial rings. I politely doubt that you were really considering this when you put the functions in SkewPolynomial_general (since the current implementation not at all works for general skew polynomial rings). But it turns out they *do* make sense and the algorithms more-or-less immediately works. So I suggest those three functions should be in their own tickets.
</p>
</blockquote>
<p>
Based on the discussions before, the plan was to add these in the finite fields ticket. That meant these had to either go in the general or finite field ring classes. I looked up some papers and found that the theory for polynomial interpolation of skew polynomial rings exists, although I didn't really try and study any of that. I just went kinda assumed that the algorithms by Wachter-Zeh would be valid and placed it there.
Just to confirm again, should I create a new ticket and place them there?
</p>
<blockquote class="citation">
<ul><li>Given a singleton point a, return x - sigma(a)/a. (use pen-and-paper to see that I am right)
</li></ul></blockquote>
<p>
If the singleton point is 0, I simply return x and otherwise x - sigma(a)/a as you pointed out, right?
</p>
<blockquote class="citation">
<ul><li><code>x = self([0,1])</code> should be <code>x = self._parent.gen()</code>.
</li></ul></blockquote>
<p>
um.. you mean self.gen(), right? Because self._parent.gen() would give an error.
</p>
<blockquote class="citation">
<ul><li>minimum_subspace_polynomial and multi_point_evaluation are mutually recursive and will generate the same minimum subspace polynomials an exponential number of times right now. We need to add caching: add <code>@cached_method</code> to minimum_subspace_polynomial.
</li></ul></blockquote>
<p>
Done. And I'll report back with some timing results once I test that these are working properly.
</p>
<p>
</p>
TicketjsrnThu, 28 Jul 2016 18:19:17 GMT
https://trac.sagemath.org/ticket/21088#comment:11
https://trac.sagemath.org/ticket/21088#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:9" title="Comment 9">arpitdm</a>:
</p>
<blockquote class="citation">
<p>
Classes <code>SkewPolynomial_finite_field_dense</code> and <code>SkewPolynomialRing_finite_field</code> are now accessible at the command line.
</p>
</blockquote>
<p>
I don't think these should be accessible from the command line. They should be called behind-the-scene when you use <code>SkewPolynomialRing(R)</code> and <code>R</code> is a finite field.
</p>
<blockquote class="citation">
<p>
I've fixed the documentation for the latter class. I removed MPE, MVP, Interpolation, _leftpow_, _rightpow_ methods. The first three I am adding as a new ticket in a short while. The last two because they depend on "center"-related stuff and that comes in a later ticket.
</p>
</blockquote>
<p>
OK.
</p>
<blockquote class="citation">
<p>
I'm right now, making as many of the polishing changes as applicable from the discussions on <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>.
</p>
</blockquote>
<p>
Good!
</p>
TicketjsrnThu, 28 Jul 2016 18:30:28 GMT
https://trac.sagemath.org/ticket/21088#comment:12
https://trac.sagemath.org/ticket/21088#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:10" title="Comment 10">arpitdm</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:4" title="Comment 4">jsrn</a>:
Based on the discussions before, the plan was to add these in the finite fields ticket.
</p>
</blockquote>
<p>
Yes, at that point I hadn't realised that all the functions apply to general skew polynomial rings.
</p>
<blockquote class="citation">
<p>
That meant these had to either go in the general or finite field ring classes. I looked up some papers and found that the theory for polynomial interpolation of skew polynomial rings exists, although I didn't really try and study any of that. I just went kinda assumed that the algorithms by Wachter-Zeh would be valid and placed it there.
</p>
</blockquote>
<p>
I don't know what to reply to that. If you don't *know*, then 1) try to figure it out, using math; and if you fail at that 2) ask (and we will try to do step 1 ourselves). By now you should be well-enough versed in the basics of skew polynomials that you at least shouldn't try to put q-powers everywhere. I would have expected you just to put the functions it in the finite field-class since that is the only case that you studied. If you thought it might apply generally, you should prove it and/or discuss with us.
</p>
<p>
Your "mistake" of course lead me to reflect upon it, which turned out for the better, but still.
</p>
<blockquote class="citation">
<p>
Just to confirm again, should I create a new ticket and place them there?
</p>
</blockquote>
<p>
Yes please, as they do not pertain specifically to finite fields.
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>Given a singleton point a, return x - sigma(a)/a. (use pen-and-paper to see that I am right)
</li></ul></blockquote>
<p>
If the singleton point is 0, I simply return x and otherwise x - sigma(a)/a as you pointed out, right?
</p>
</blockquote>
<p>
0 is not a valid input. 0 does not span a vector space (well, it spans a vector space of dimension 0), and *any* skew polynomial evaluates to 0 on 0.
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li><code>x = self([0,1])</code> should be <code>x = self._parent.gen()</code>.
</li></ul></blockquote>
<p>
um.. you mean self.gen(), right? Because self._parent.gen() would give an error.
</p>
</blockquote>
<p>
Yes I meant <code>self.gen()</code>.
</p>
<blockquote class="citation">
<p>
Done. And I'll report back with some timing results once I test that these are working properly.
</p>
</blockquote>
<p>
OK.
</p>
TicketarpitdmThu, 28 Jul 2016 19:18:02 GMT
https://trac.sagemath.org/ticket/21088#comment:13
https://trac.sagemath.org/ticket/21088#comment:13
<p>
I misspoke earlier. Horribly. I meant to say, that earlier, <code>from sage.rings.polynomial.skew_polynomial_finite_field import *</code> was giving a <a class="missing wiki">NameError?</a> because I hadn't added Extension to the <code>src/module_list.py</code> file. And the lines in the <code>skew_polynomial_ring_constructor.py</code> file. Not command line. My apologies.
</p>
TicketgitThu, 28 Jul 2016 21:44:08 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:14
https://trac.sagemath.org/ticket/21088#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>a6e93e12c1fefffde3615c8eab75a45b3c277ab2</em> to <em>130b1737fa64fe1613c53257ef0a74d24f8eadad</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="https://git.sagemath.org/sage.git/commit/?id=130b1737fa64fe1613c53257ef0a74d24f8eadad"><span class="icon"></span>130b173</a></td><td><code>improved documentation for skew_polynomials_finite_field.pyx file</code>
</td></tr></table>
TicketarpitdmThu, 28 Jul 2016 21:48:25 GMT
https://trac.sagemath.org/ticket/21088#comment:15
https://trac.sagemath.org/ticket/21088#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:7" title="Comment 7">tscrim</a>:
</p>
<blockquote class="citation">
<p>
<code>cdef</code> methods/functions are not callable from Sage (i.e., python). They technically don't need to be doctested. However, there should be an <code>EXAMPLES::</code> that has a function that (indirectly) calls the method/function in question.
</p>
</blockquote>
<p>
The methods that call <code>_rgcd</code>, <code>_inplace_rrem</code>, etc have not been added to this ticket. These are part of another ticket that I will create a little later. The indirect doctests for these methods can be added at that point.
</p>
TicketgitThu, 28 Jul 2016 23:12:14 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:16
https://trac.sagemath.org/ticket/21088#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>130b1737fa64fe1613c53257ef0a74d24f8eadad</em> to <em>15861b92f34893114ce4f12cf9c83ecda98223ce</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="https://git.sagemath.org/sage.git/commit/?id=15861b92f34893114ce4f12cf9c83ecda98223ce"><span class="icon"></span>15861b9</a></td><td><code>documentation builds successfully.</code>
</td></tr></table>
TicketarpitdmThu, 28 Jul 2016 23:13:39 GMTstatus changed
https://trac.sagemath.org/ticket/21088#comment:17
https://trac.sagemath.org/ticket/21088#comment:17
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketjsrnMon, 01 Aug 2016 12:45:13 GMTstatus changed
https://trac.sagemath.org/ticket/21088#comment:18
https://trac.sagemath.org/ticket/21088#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
You need to merge with the newest <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>, I think. There's a failing doctest.
</p>
<p>
Best,
Johan
</p>
TicketcarusoMon, 01 Aug 2016 23:21:18 GMT
https://trac.sagemath.org/ticket/21088#comment:19
https://trac.sagemath.org/ticket/21088#comment:19
<p>
Here are some mathematical comments:
</p>
<ul><li>I would say (but I'm not sure) that the benefit of using a divide-and-conquer method for multi-point evaluation only appears if you are using fast multication algorithms
</li><li>the problem of "minimum subspace polynomial" reduces to the computation of some lcm: the minimum subspace polynomial of a family (a_1, ..., a_n) (with a_i nonzero for all i) is the left lcm of the degree 1 skew polynomials (X - sigma(a_i)/a_i). Again I think that computing it using a divide-and-conquer method is only interesting when fast multiplication and half-gcd are available (but these should be hidden at some point in Wachter-Zeh algorithm)
</li><li>the interpolation problem is just a noncommutative CRT: finding P such that P(a_i)=b_i is equivalent to finding a skew polynomial P which is congruent to b_i modulo (X - sigma(a_i)/a_i). I think that it would be interesting in any case to implement a method <code>CRT</code> (and then possibly let <code>interpolation</code> call it, but of course it is not mandatory).
</li></ul>
TicketcarusoMon, 01 Aug 2016 23:25:37 GMT
https://trac.sagemath.org/ticket/21088#comment:20
https://trac.sagemath.org/ticket/21088#comment:20
<p>
Sorry, my last comment should go to ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/21131" title="enhancement: Interpolation, Minimal Vanishing Polynomial and Multi Point Evaluation ... (closed: fixed)">#21131</a>. I just reposted it there.
</p>
TicketgitFri, 12 Aug 2016 12:56:44 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:21
https://trac.sagemath.org/ticket/21088#comment:21
<ul>
<li><strong>commit</strong>
changed from <em>15861b92f34893114ce4f12cf9c83ecda98223ce</em> to <em>a2c4f06f4ac65342098630ed345dad2f53659306</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=c034df844e697939c159552844b089e787bededd"><span class="icon"></span>c034df8</a></td><td><code>removed unused private methods and imports</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=ac109c82509d2ab9bcf7539cd1b7b86a5b1a563b"><span class="icon"></span>ac109c8</a></td><td><code>converted to standard copyright template</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=5137ef91cbdc7fe0d7712905da336d5a92716713"><span class="icon"></span>5137ef9</a></td><td><code>removed deprecated method getslice</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b1e42c3f1b032ca62389dd68ded1fece79678955"><span class="icon"></span>b1e42c3</a></td><td><code>Merge commit 'aca3398a81b3688e1f2e69c5910b8214d13be925' of git://trac.sagemath.org/sage into skew_polynomials</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=f563aba916b4155a9485c46ebbbdfe3404a2c8f1"><span class="icon"></span>f563aba</a></td><td><code>mod and floordiv modified to use coercion model. replaced type with isinstance.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=26e46890a9e6dff7f0f6f69ce7a9bf28f88bc3de"><span class="icon"></span>26e4689</a></td><td><code>modified copyright banner</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=88196bfd70fca121e6e343a03ff2c3119254a671"><span class="icon"></span>88196bf</a></td><td><code>some more fixes to the documentation.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=eb78e694bde02c73c14aae8fb2238b49ef5bba8a"><span class="icon"></span>eb78e69</a></td><td><code>small fixes to docstrings</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=2d67e0ee0dc4afb7720844ab088f379ff7f8331b"><span class="icon"></span>2d67e0e</a></td><td><code>merging updates</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a2c4f06f4ac65342098630ed345dad2f53659306"><span class="icon"></span>a2c4f06</a></td><td><code>removed unused imports, signal statements. small fixes to documentation.</code>
</td></tr></table>
TicketarpitdmFri, 12 Aug 2016 13:03:14 GMT
https://trac.sagemath.org/ticket/21088#comment:22
https://trac.sagemath.org/ticket/21088#comment:22
<p>
There are several methods that do not have doctests because they are private methods that are used by center, factorization, etc. related methods. Those will be part of another ticket as decided earlier.
</p>
<p>
Otherwise, documentation is updated. Code is scrubbed and cleaned. Remaining tests pass and these classes and modules are called upon when the the base ring is a finite field.
</p>
<p>
Html and pdf both docs also build.
</p>
TicketarpitdmFri, 12 Aug 2016 13:03:33 GMTstatus changed
https://trac.sagemath.org/ticket/21088#comment:23
https://trac.sagemath.org/ticket/21088#comment:23
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketcarusoWed, 17 Aug 2016 12:44:38 GMT
https://trac.sagemath.org/ticket/21088#comment:24
https://trac.sagemath.org/ticket/21088#comment:24
<p>
I would suggest to add public methods for calling the fast cdef methods. What's your opinion?
</p>
TickettscrimWed, 17 Aug 2016 12:49:38 GMT
https://trac.sagemath.org/ticket/21088#comment:25
https://trac.sagemath.org/ticket/21088#comment:25
<p>
@caruso I believe what you want is <code>cpdef</code>.
</p>
TicketcarusoWed, 17 Aug 2016 12:54:18 GMT
https://trac.sagemath.org/ticket/21088#comment:26
https://trac.sagemath.org/ticket/21088#comment:26
<p>
No, I do not think so because most of the current cdef methods are inplace (they modify self) and we do not want such a behaviour for a public method.
</p>
TickettscrimWed, 17 Aug 2016 13:24:32 GMT
https://trac.sagemath.org/ticket/21088#comment:27
https://trac.sagemath.org/ticket/21088#comment:27
<p>
Then I don't quite understand <a class="ticket" href="https://trac.sagemath.org/ticket/21088#comment:24" title="Comment 24">comment:24</a>.
</p>
TicketcarusoWed, 17 Aug 2016 13:31:09 GMT
https://trac.sagemath.org/ticket/21088#comment:28
https://trac.sagemath.org/ticket/21088#comment:28
<p>
Well, for instance, the patch provides the method <code>_inplace_rrem</code> (which I assume to be faster than <code>right_rem</code> since it is a cdef method - but maybe I am wrong, I do not really know). So I'm wondering whether it would be interesting to add a "caller" method like this:
</p>
<pre class="wiki">cpdef right_rem(self,other):
R = self
R._inplace_rrem(other)
return R
</pre><p>
But maybe it is not.
</p>
TickettscrimWed, 17 Aug 2016 13:37:14 GMT
https://trac.sagemath.org/ticket/21088#comment:29
https://trac.sagemath.org/ticket/21088#comment:29
<p>
You would need to make a copy of <code>self</code>. Just creating another reference to <code>self</code> doesn't cause <code>self</code> to not be changed by <code>_inplace_rrem</code>. All that snippet does is what <code>cpdef</code> would do (plus create the extra temp reference).
</p>
<p>
However, you are correct in that <code>cdef</code> methods are faster (they are at the C level instead of the python level).
</p>
TickettscrimWed, 17 Aug 2016 13:40:17 GMT
https://trac.sagemath.org/ticket/21088#comment:30
https://trac.sagemath.org/ticket/21088#comment:30
<p>
That's not to say I'm against have public methods that create the copy and then manipulate (in fact, +1 to doing this). I'm just saying you do need to do a little bit more than simply redirecting, which declaring something <code>cpdef</code> does automatically for you.
</p>
TicketjsrnThu, 18 Aug 2016 09:04:07 GMT
https://trac.sagemath.org/ticket/21088#comment:31
https://trac.sagemath.org/ticket/21088#comment:31
<p>
If your proposed <code>right_rem</code> is faster than the current non-cdef <code>right_rem</code>, then the current one should just be overridden, right?
</p>
<p>
In any case, timing tests should be performed before any code modifications.
</p>
TicketcarusoTue, 23 Aug 2016 05:53:18 GMT
https://trac.sagemath.org/ticket/21088#comment:32
https://trac.sagemath.org/ticket/21088#comment:32
<p>
I made a try. I added this method
</p>
<pre class="wiki">cpdef test_quo_rem(self,other):
if not isinstance(other,SkewPolynomial_generic_dense):
raise TypeError
cdef SkewPolynomial_finite_field_dense R = self.parent()(list(self))
Q = R._rquo_inplace_rem(other)
return (Q,R)
</pre><p>
and compare timings:
</p>
<pre class="wiki">sage: k = GF(5^3)
sage: S.<x> = SkewPolynomialRing(k,k.frobenius_endomorphism())
sage: A = S.random_element(degree=1000)
sage: B = S.random_element(degree=500,monic=True)
sage: %timeit A.right_quo_rem(B)
1 loop, best of 3: 610 ms per loop
sage: %timeit A.test_quo_rem(B)
1 loop, best of 3: 642 ms per loop
</pre><p>
So, the difference is not sensible.
</p>
TicketjsrnWed, 24 Aug 2016 15:21:47 GMTkeywords set
https://trac.sagemath.org/ticket/21088#comment:33
https://trac.sagemath.org/ticket/21088#comment:33
<ul>
<li><strong>keywords</strong>
<em>sd75</em> added
</li>
</ul>
TicketgitTue, 07 Feb 2017 15:00:07 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:34
https://trac.sagemath.org/ticket/21088#comment:34
<ul>
<li><strong>commit</strong>
changed from <em>a2c4f06f4ac65342098630ed345dad2f53659306</em> to <em>c38c99a707b5f094c11223084af2ca2212e7736d</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="https://git.sagemath.org/sage.git/commit/?id=c38c99a707b5f094c11223084af2ca2212e7736d"><span class="icon"></span>c38c99a</a></td><td><code>merged previous conflicts</code>
</td></tr></table>
TicketgitTue, 07 Feb 2017 17:04:17 GMTcommit changed
https://trac.sagemath.org/ticket/21088#comment:35
https://trac.sagemath.org/ticket/21088#comment:35
<ul>
<li><strong>commit</strong>
changed from <em>c38c99a707b5f094c11223084af2ca2212e7736d</em> to <em>b0bc8cfa87b1d99907ded38cb600b7ebc5e6bfcc</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="https://git.sagemath.org/sage.git/commit/?id=b0bc8cfa87b1d99907ded38cb600b7ebc5e6bfcc"><span class="icon"></span>b0bc8cf</a></td><td><code>fixed doctest errors.</code>
</td></tr></table>
TicketarpitdmTue, 07 Feb 2017 17:06:52 GMTmilestone changed
https://trac.sagemath.org/ticket/21088#comment:36
https://trac.sagemath.org/ticket/21088#comment:36
<ul>
<li><strong>milestone</strong>
changed from <em>sage-7.3</em> to <em>sage-7.6</em>
</li>
</ul>
TicketjpfloriThu, 22 Jun 2017 09:57:05 GMTcc changed
https://trac.sagemath.org/ticket/21088#comment:37
https://trac.sagemath.org/ticket/21088#comment:37
<ul>
<li><strong>cc</strong>
<em>jpflori</em> added
</li>
</ul>
TicketcarusoThu, 02 Apr 2020 16:26:47 GMT
https://trac.sagemath.org/ticket/21088#comment:38
https://trac.sagemath.org/ticket/21088#comment:38
<p>
I don't understand the relevance of this ticket: it seems that it only implements <code>cdef</code> methods which are never called (and probably not faster than the current available methods). Then, I would propose to close it (with resolution <code>wontfix</code>). Any objection?
</p>
TicketjsrnFri, 03 Apr 2020 07:29:39 GMT
https://trac.sagemath.org/ticket/21088#comment:39
https://trac.sagemath.org/ticket/21088#comment:39
<p>
I believe the point of this ticket was (as it says in the note of the ticket description) as a stepping stone towards including the finite field-specialised functions you originally wrote in <a class="closed ticket" href="https://trac.sagemath.org/ticket/13215" title="enhancement: Skew polynomials (closed: fixed)">#13215</a>. If you want to abandon those in any case, and you don't consider other finite field-specialised functions in the near future, I have no objection closing this ticket.
</p>
TicketcarusoFri, 03 Apr 2020 19:01:41 GMTstatus changed; commit, branch deleted
https://trac.sagemath.org/ticket/21088#comment:40
https://trac.sagemath.org/ticket/21088#comment:40
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>commit</strong>
<em>b0bc8cfa87b1d99907ded38cb600b7ebc5e6bfcc</em> deleted
</li>
<li><strong>branch</strong>
<em>u/arpitdm/finite_fields_skew_polynomial</em> deleted
</li>
</ul>
<p>
As I said, unless I missed something, this ticket is almost empty: it only provides several <code>cdef</code> methods <code>inplace_*</code> that are (1) copies of the non-inplace methods and (2) never called. So, I think that we can abandon this ticket without regret.
</p>
TicketcarusoFri, 03 Apr 2020 19:02:43 GMTcomponent, milestone changed
https://trac.sagemath.org/ticket/21088#comment:41
https://trac.sagemath.org/ticket/21088#comment:41
<ul>
<li><strong>component</strong>
changed from <em>coding theory</em> to <em>algebra</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-7.6</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
TicketchapotonTue, 28 Apr 2020 08:25:15 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/21088#comment:42
https://trac.sagemath.org/ticket/21088#comment:42
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>wontfix</em>
</li>
</ul>
Ticket