Opened 19 months ago
Last modified 8 months ago
#21088 needs_review enhancement
Base Class for Skew Polynomials over Finite Fields
Reported by:  arpitdm  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  coding theory  Keywords:  sd75 
Cc:  tscrim, caruso, jsrn, dlucas, jpflori  Merged in:  
Authors:  Xavier Caruso, Arpit Merchant  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/arpitdm/finite_fields_skew_polynomial (Commits)  Commit:  b0bc8cfa87b1d99907ded38cb600b7ebc5e6bfcc 
Dependencies:  #13215  Stopgaps: 
Description
General, dense, univariate Skew Polynomials and SkewPolynomial? Rings over generic commutative base rings are already supported in Ticket #13215. This ticket proposes adding functionality for additional methods and optimized algorithms for such Skew Polynomials specifically over Finite Fields. This includes:
 Class SkewPolynomial_finite_field(SkewPolynomial_generic_dense)
 Class SkewPolynomialRing_finite_field(SkewPolynomialRing_general)
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 #13215. Those will be added in separate tickets.
Change History (37)
comment:1 Changed 19 months ago by
 Branch set to u/arpitdm/finite_fields_skew_polynomial
comment:2 Changed 19 months ago by
 Commit set to f4b841336eb6c557013e3684668dbd5db851c343
comment:3 Changed 19 months ago by
 Commit changed from f4b841336eb6c557013e3684668dbd5db851c343 to 1a06b095a569eba51bf2efdc2f86712cfa7b49aa
comment:4 followup: ↓ 10 Changed 19 months ago by
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 moreorless immediately works. So I suggest those three functions should be in their own tickets.
 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
x^(q^i)
translates tox^i
in skew polynomials).
My suggestion is to call the function
minimal_vanishing_polynomial
. Given elements a1,...,an, it is defined as the (unique) minimaldegree polynomial p
such that p is monic (leading coefficient is 1) and p(ai) = 0 for i=1,...,n.
 The implementation of course also needs to be slightly modified:
 Given an empty list of points, return 1.
 Given a singleton point a, return x  sigma(a)/a. (use penandpaper to see that I am right)
 Given a list of points, use divide and conquer as you do now.
 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 qpowering everywhere. While were on it, you write "pow(a, pow(q, 0))" several places, but this is clearly just "a"!
x = self([0,1])
should bex = self._parent.gen()
.
 Instead of lines such as
y = [] y.append(blabla) return y
you should write
return [ blabla ]
 In multi_point_evaluation you have a duplicate line
r = ....
withreturn ...
. 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:self.multi_point_evaluation(R_A, A) + self.multi_point_evaluation(R_B, B)
.
 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
@cached_method
to minimum_subspace_polynomial.
 multi_point_evaluation is a fairly complicated procedure compared to just calling
n
times__call__
. Try to do timings to see if it is worth it. (Asymptotically, there is only a gain if some fast multiplication andquo_rem
of skew polynomials is implemented, which it isn't).
 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
pow(x, (pow(q,0)
withself._parent.one()
, andx = self([0,1])
withx = self._parent.gen()
.
 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
__call__
'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.
comment:5 Changed 19 months ago by
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?
comment:6 Changed 19 months ago by
Hello,
I have some more comments:
 Is there any reason why
cdef
methods inskew_polynomial_finite_field.pyx
are not doctested?  In the same module, a lot of methods do not respect documentation conventions. See
cdef SkewPolynomial_finite_field_dense _rgcd
for instance, whose documentation is this single sentence:Fast right gcd.
. Some methods (e.g._rightpow_
,_leftpow
) do not even have thisReturn(s) blah blah
line which explains what they're supposed to do... skew_polynomial_finite_field.pyx
's title isThis module implements skew polynomials over finite fields.
. I think it should be changed toSkew polynomials over finite fields
, or something equivalent. A lot of elements are not properly formatted in docstrings of
skew_polynomial_finite_field.pyx
: it should be<double backtick>self<double backtick>
instead ofself
, etc.  In
class SkewPolynomialRing_finite_field
, docstring oftwist_map
is not helpful as it saysReturn the twist map
.
comment:7 followup: ↓ 15 Changed 19 months ago by
cdef
methods/functions are not callable from Sage (i.e., python). They technically don't need to be doctested. However, there should be an EXAMPLES::
that has a function that (indirectly) calls the method/function in question.
comment:8 Changed 19 months ago by
 Commit changed from 1a06b095a569eba51bf2efdc2f86712cfa7b49aa to a6e93e12c1fefffde3615c8eab75a45b3c277ab2
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
b52fc95  using cached versions of 0 and 1 wherever applicable.

6fb186a  changed Returns to Return and Note to NOTE for consistency. Removed trailing whitespaces. codeformatting for True, False and None objects.

1204f2d  the current implementation of the :meth: __call__ was incorrect. added the correct and cythonized version.

7e076fa  moved module level docs to user entry point at the class level so that they are accessible at command line. added a SEEALSO block.

69fecc4  converted :meth: into a cpdef method with output type list. removed and directly use the attribute.

271bfac  removed some commented code and trailing whitespaces.

9a2fad2  merged changes from Tickets 13215 and 21088

eaca253  integrated skew polynomial finite field into sage. removed some compile and doctest errors.

7664060  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.

a6e93e1  added SEEALSO and TODO blocks and made small polishes to the documentation.

comment:9 followup: ↓ 11 Changed 19 months ago by
Classes SkewPolynomial_finite_field_dense
and SkewPolynomialRing_finite_field
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.
I'm right now, making as many of the polishing changes as applicable from the discussions on #13215.
comment:10 in reply to: ↑ 4 ; followup: ↓ 12 Changed 19 months ago by
Replying to jsrn:
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 moreorless immediately works. So I suggest those three functions should be in their own tickets.
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 WachterZeh would be valid and placed it there. Just to confirm again, should I create a new ticket and place them there?
 Given a singleton point a, return x  sigma(a)/a. (use penandpaper to see that I am right)
If the singleton point is 0, I simply return x and otherwise x  sigma(a)/a as you pointed out, right?
x = self([0,1])
should bex = self._parent.gen()
.
um.. you mean self.gen(), right? Because self._parent.gen() would give an error.
 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
@cached_method
to minimum_subspace_polynomial.
Done. And I'll report back with some timing results once I test that these are working properly.
comment:11 in reply to: ↑ 9 Changed 19 months ago by
Replying to arpitdm:
Classes
SkewPolynomial_finite_field_dense
andSkewPolynomialRing_finite_field
are now accessible at the command line.
I don't think these should be accessible from the command line. They should be called behindthescene when you use SkewPolynomialRing(R)
and R
is a finite field.
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.
OK.
I'm right now, making as many of the polishing changes as applicable from the discussions on #13215.
Good!
comment:12 in reply to: ↑ 10 Changed 19 months ago by
Replying to arpitdm:
Replying to jsrn: Based on the discussions before, the plan was to add these in the finite fields ticket.
Yes, at that point I hadn't realised that all the functions apply to general skew polynomial rings.
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 WachterZeh would be valid and placed it there.
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 wellenough versed in the basics of skew polynomials that you at least shouldn't try to put qpowers everywhere. I would have expected you just to put the functions it in the finite fieldclass 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.
Your "mistake" of course lead me to reflect upon it, which turned out for the better, but still.
Just to confirm again, should I create a new ticket and place them there?
Yes please, as they do not pertain specifically to finite fields.
 Given a singleton point a, return x  sigma(a)/a. (use penandpaper to see that I am right)
If the singleton point is 0, I simply return x and otherwise x  sigma(a)/a as you pointed out, right?
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.
x = self([0,1])
should bex = self._parent.gen()
.um.. you mean self.gen(), right? Because self._parent.gen() would give an error.
Yes I meant self.gen()
.
Done. And I'll report back with some timing results once I test that these are working properly.
OK.
comment:13 Changed 19 months ago by
I misspoke earlier. Horribly. I meant to say, that earlier, from sage.rings.polynomial.skew_polynomial_finite_field import *
was giving a NameError? because I hadn't added Extension to the src/module_list.py
file. And the lines in the skew_polynomial_ring_constructor.py
file. Not command line. My apologies.
comment:14 Changed 19 months ago by
 Commit changed from a6e93e12c1fefffde3615c8eab75a45b3c277ab2 to 130b1737fa64fe1613c53257ef0a74d24f8eadad
Branch pushed to git repo; I updated commit sha1. New commits:
130b173  improved documentation for skew_polynomials_finite_field.pyx file

comment:15 in reply to: ↑ 7 Changed 19 months ago by
Replying to tscrim:
cdef
methods/functions are not callable from Sage (i.e., python). They technically don't need to be doctested. However, there should be anEXAMPLES::
that has a function that (indirectly) calls the method/function in question.
The methods that call _rgcd
, _inplace_rrem
, 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.
comment:16 Changed 19 months ago by
 Commit changed from 130b1737fa64fe1613c53257ef0a74d24f8eadad to 15861b92f34893114ce4f12cf9c83ecda98223ce
Branch pushed to git repo; I updated commit sha1. New commits:
15861b9  documentation builds successfully.

comment:17 Changed 19 months ago by
 Status changed from new to needs_review
comment:18 Changed 19 months ago by
 Status changed from needs_review to needs_work
You need to merge with the newest #13215, I think. There's a failing doctest.
Best, Johan
comment:19 Changed 19 months ago by
Here are some mathematical comments:
 I would say (but I'm not sure) that the benefit of using a divideandconquer method for multipoint evaluation only appears if you are using fast multication algorithms
 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 divideandconquer method is only interesting when fast multiplication and halfgcd are available (but these should be hidden at some point in WachterZeh algorithm)
 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
CRT
(and then possibly letinterpolation
call it, but of course it is not mandatory).
comment:20 Changed 19 months ago by
Sorry, my last comment should go to ticket #21131. I just reposted it there.
comment:21 Changed 19 months ago by
 Commit changed from 15861b92f34893114ce4f12cf9c83ecda98223ce to a2c4f06f4ac65342098630ed345dad2f53659306
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
c034df8  removed unused private methods and imports

ac109c8  converted to standard copyright template

5137ef9  removed deprecated method getslice

b1e42c3  Merge commit 'aca3398a81b3688e1f2e69c5910b8214d13be925' of git://trac.sagemath.org/sage into skew_polynomials

f563aba  mod and floordiv modified to use coercion model. replaced type with isinstance.

26e4689  modified copyright banner

88196bf  some more fixes to the documentation.

eb78e69  small fixes to docstrings

2d67e0e  merging updates

a2c4f06  removed unused imports, signal statements. small fixes to documentation.

comment:22 Changed 19 months ago by
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.
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.
Html and pdf both docs also build.
comment:23 Changed 19 months ago by
 Status changed from needs_work to needs_review
comment:24 Changed 18 months ago by
I would suggest to add public methods for calling the fast cdef methods. What's your opinion?
comment:25 Changed 18 months ago by
@caruso I believe what you want is cpdef
.
comment:26 Changed 18 months ago by
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.
comment:27 Changed 18 months ago by
Then I don't quite understand comment:24.
comment:28 Changed 18 months ago by
Well, for instance, the patch provides the method _inplace_rrem
(which I assume to be faster than right_rem
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:
cpdef right_rem(self,other): R = self R._inplace_rrem(other) return R
But maybe it is not.
comment:29 Changed 18 months ago by
You would need to make a copy of self
. Just creating another reference to self
doesn't cause self
to not be changed by _inplace_rrem
. All that snippet does is what cpdef
would do (plus create the extra temp reference).
However, you are correct in that cdef
methods are faster (they are at the C level instead of the python level).
comment:30 Changed 18 months ago by
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 cpdef
does automatically for you.
comment:31 Changed 18 months ago by
If your proposed right_rem
is faster than the current noncdef right_rem
, then the current one should just be overridden, right?
In any case, timing tests should be performed before any code modifications.
comment:32 Changed 18 months ago by
I made a try. I added this method
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)
and compare timings:
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
So, the difference is not sensible.
comment:33 Changed 18 months ago by
 Keywords sd75 added
comment:34 Changed 13 months ago by
 Commit changed from a2c4f06f4ac65342098630ed345dad2f53659306 to c38c99a707b5f094c11223084af2ca2212e7736d
Branch pushed to git repo; I updated commit sha1. New commits:
c38c99a  merged previous conflicts

comment:35 Changed 13 months ago by
 Commit changed from c38c99a707b5f094c11223084af2ca2212e7736d to b0bc8cfa87b1d99907ded38cb600b7ebc5e6bfcc
Branch pushed to git repo; I updated commit sha1. New commits:
b0bc8cf  fixed doctest errors.

comment:36 Changed 13 months ago by
 Milestone changed from sage7.3 to sage7.6
comment:37 Changed 8 months ago by
 Cc jpflori added
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), multipoint 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.
Last 10 new commits:
removed side.py
added a section related to skew polynomils in the index file.
removed double imports and unused classes and methods
improved description of module, definition of skew polynomial, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of a couple of methods.
changes to incorporate merging and into
removed unnecessary imports
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.
same as previous commit
added the finite field files without karatsuba, center, irreducibility and factor stuff. cleaned up code. fixed doctest errors.
added missing documentation and some tests. added class SkewPolynomialRing_finite_field.