Opened 5 years ago

Closed 8 months ago

#13215 closed enhancement (fixed)

Skew polynomials

Reported by: caruso Owned by: tbd
Priority: major Milestone: sage-7.4
Component: algebra Keywords: skew polynomials, sd75
Cc: tfeulner, caruso, burcin, jsrn, dlucas, tscrim Merged in:
Authors: Xavier Caruso, Arpit Merchant, Johan Rosenkilde Reviewers: Burcin Erocal, David Lucas, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 7cb0cce (Commits) Commit: 7cb0ccebabc3eeabab0e3765941ad4a1b79cab1c
Dependencies: Stopgaps:

Description (last modified by arpitdm)

If R is a ring equipped with an endomorphism sigma, the ring of skew polynomials over (R,sigma) is the ring of usual polynomials over R with the modified multiplication given by the rule X*a = sigma(a)*X.

Skew polynomials play an important role in several domains like coding theory or Galois representations theory in positive characteristic.

This ticket provides:

  1. a basic implementation of skew polynomials over any commutative ring (including addition, multiplication, euclidean division, gcd...)
  2. construction of skew polynomial rings

Attachments (7)

trac_13215_skew_polynomials.2.patch (265.9 KB) - added by caruso 5 years ago.
trac_13303_invert_polynomial_quotient_rings.patch (3.5 KB) - added by caruso 5 years ago.
trac_13640_qjordan.patch (5.1 KB) - added by caruso 5 years ago.
trac_13641_short_repr_morphism.patch (1.2 KB) - added by caruso 5 years ago.
trac_13642_modular_exp_polynomial.patch (3.7 KB) - added by caruso 4 years ago.
trac_13214_hom_finite_field.patch (58.4 KB) - added by caruso 4 years ago.
trac_13215_skew_polynomials.patch (254.4 KB) - added by caruso 4 years ago.

Download all attachments as: .zip

Change History (257)

comment:1 Changed 5 years ago by caruso

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by caruso

  • Dependencies set to #13214
  • Description modified (diff)

Changed 5 years ago by caruso

comment:3 Changed 5 years ago by caruso

File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch

comment:4 Changed 5 years ago by tfeulner

  • Cc tfeulner added
  • Status changed from needs_review to needs_work

With your changes it is now possible to test some element in an Univariate Quotient Polynomial Ring to be a unit and to compute its inverse. Unfortunately, this computation gives wrong results:

sage: Z16x.<x> = Integers(16)[]
sage: GR.<y> =  Z16x.quotient(x**2 + x+1 )
sage: (2*y).is_unit()
True
sage: (2*y)^(-1)
15*y + 15
sage: (2*y)*(2*y)^(-1)
2

Thomas

comment:5 Changed 5 years ago by caruso

Thanks for catching this!

I've updated my patch. (I've simply decided to raise a NotImplementedError? when the base ring is not a field and, by the way, I've added some doctests.)

PS: apply patch trac_13215_skew_polynomials.patch and forget trac_13215_skew_polynomials.2.patch (is it possible to remove it?)

comment:6 Changed 5 years ago by caruso

  • Status changed from needs_work to needs_review

comment:7 Changed 5 years ago by tfeulner

Maybe you should produce a seperate trac ticket for the fix of

sage: (2*y)^(-1)
...
NotImplementedError: The base ring (=Ring of integers modulo 16) is not a field

By the way, I know that this is a problem which also occurs for usual polynomials (because of the default definition of the reduce function). Do you have any idea how to fix this:

sage: Z16x.<x> = SkewPolynomialRing(Integers(16)) 
sage: # Z16x.<x> = Integers(16)[] # has the same behaviour
sage: GR.<y> =  Z16x.quotient(x**2 + x+1 )
sage: I = GR.ideal(4)
sage: I.reduce(6)
6

comment:8 Changed 5 years ago by caruso

Ok, I split my patch in two parts and I open a new ticket (cf #13303).

I'm afraid I don't understand quite well the problem with reduce. Could you explain it a bit more please?

Last edited 5 years ago by caruso (previous) (diff)

comment:9 Changed 5 years ago by caruso

  • Dependencies changed from #13214 to #13214, #13303
  • Description modified (diff)

comment:10 Changed 5 years ago by caruso

  • Cc caruso added

comment:11 Changed 5 years ago by jdemeyer

Please fill in your real name as Author.

comment:12 Changed 5 years ago by caruso

  • Authors set to Xavier Caruso

comment:13 Changed 5 years ago by tfeulner

Hi Xavier,

you are right this is a more general problem. I started a discussion on https://groups.google.com/d/topic/sage-devel/s5y604ZPiQ8/discussion. The function reduce() does what it says returning an element of the ring. But in the definition of a QuotientRing? there is the following assumption

I.reduce(x)==I.reduce(y) \iff x-y \in I, and x-I.reduce(x) \in I, for all x \in R.

With this default behaviour, the quotient ring is just a copy of the original ring R.

Best, Thomas

comment:14 Changed 5 years ago by burcin

  • Cc burcin added
  • Component changed from experimental package to algebra

It would be great to have all this in Sage. Thanks a lot for your work.

I haven't had a chance to look at the patches yet. I will try to make some time available for this in the coming weeks. For now, I have two questions,

  • Did you consider using Singular's noncommutative component, Plural, as a basic data structure for skew polynomials? I expect the arithmetic to be much faster with Plural than a new implementation in Cython.
  • Can the patches be broken down into smaller components for easier review?

comment:15 follow-up: Changed 5 years ago by caruso

I haven't heard about Plural before that... so, I haven't considered using it for skew polynomials yet. I will compare how fast is the arithmetic with Plural and with my own implementation in Cython and let you know.

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by burcin

Thanks for the prompt response! I am attending a workshop this week and I haven't had a chance to read through your patch properly yet. So please excuse me if I am completely off the mark in my response below. :)

Replying to caruso:

I haven't heard about Plural before that... so, I haven't considered using it for skew polynomials yet. I will compare how fast is the arithmetic with Plural and with my own implementation in Cython and let you know.

Your patch provides more functionality than Plural, for example gcd's and factoring. The coefficient domains supported by Plural are also limited. I suppose your implementation supports more general coefficient domains, basically anything Sage already knows about.

It would be good to have a clear comparison between Plural and your implementation first. But I imagine having two skew polynomial classes in Sage, a generic implementation from your patch and one based on Plural. We could probably share the high level functionality not provided by Plural using the category framework.

I am not opposed to just including your patch and think about the Plural part later as an optimization if you say that your implementation is more capable.

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

I don't know yet. It depends on how many functionally independent parts there are. For instance, the short representations for morphisms can be an independent piece that is trivial to review. The hash functions for morphisms would also be a separate bug fix. Actually, I attempted to fix that a long time ago at #9016.

comment:17 follow-up: Changed 5 years ago by caruso

I had a quick look at the documentation of Plural but I didn't find how to create a skew polynomial ring (i.e. I don't know how to represent a skew polynomial ring as a G-algebra). Could you please learn me this?

comment:18 in reply to: ↑ 17 Changed 5 years ago by burcin

  • Description modified (diff)

Replying to caruso:

I had a quick look at the documentation of Plural but I didn't find how to create a skew polynomial ring (i.e. I don't know how to represent a skew polynomial ring as a G-algebra). Could you please learn me this?

For example, QQ[n, S:n->n+1] :

sage: A.<n, S> = FreeAlgebra(QQ, 2)
sage: R.<n, S> = A.g_algebra({S*n: n*S + 1})
sage: R
Noncommutative Multivariate Polynomial Ring in n, S over Rational Field, nc-relations: {S*n: n*S + 1}
sage: S*n
n*S + 1
sage: S^2*n
n*S^2 + 2*S

After applying the patches on this ticket and its dependencies, I get the following error:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
sage: x*t
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
sage: %debug
> /home/burcin/sage/sage-5.2/skewpolynomial_element.pyx(347)sage.rings.polynomial.skewpolynomial_element.SkewPolynomial._list_c (sage/rings/polynomial/skewpolynomial_element.c:4716)()

comment:19 in reply to: ↑ 16 ; follow-up: Changed 5 years ago by burcin

  • Reviewers set to Burcin Erocal
  • Status changed from needs_review to needs_work

Replying to burcin:

Replying to caruso:

Ok, I will split my patch in several components. (Is two enough or are you expecting more than that?).

I don't know yet. It depends on how many functionally independent parts there are. For instance, the short representations for morphisms can be an independent piece that is trivial to review. The hash functions for morphisms would also be a separate bug fix. Actually, I attempted to fix that a long time ago at #9016.

From a cursory reading of attachment:trac_13215_skew_polynomials.patch, I see these separate parts that should have a ticket of its own:

  • short representations for morphisms
  • hash functions for morphisms (#9016)
  • q_jordan
  • modular exponentiation of polynomial_element

A few comments (not a full review):

  • the operator / always constructs the quotient domain in Sage, even if exact division is possible. Since in this case we need a generic Ore localization for /, I suggest you only implement exact division with // and raise an error on /.
    +    sage: d = a * b
    +    sage: d/b == a   # Right division
    +    True
    +
    +    sage: c/b
    +    Traceback (most recent call last):
    +    ...
    +    ValueError: the division is not exact
    
  • For the constructor, why don't you check if the argument of the __getitem__ method is a Morphism instead of this:
          from sage.categories.morphism import Morphism
           if isinstance(x,tuple) and len(x) == 2 and isinstance(x[1],Morphism):
    
    This should remove the limitation of having to specify the variable name on the right hand side as documented here:
    +One can also use a shorter syntax::
    +
    +    sage: S.<x> = R['x',sigma]; S
    +    Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
    +
    +Be careful, with the latter syntax, one cannot omit the name of the 
    +variable neither in LHS nor in RHS. If we omit it in LHS, the variable 
    +is not created::
    +
    +    sage: Sy = R['y',sigma]; Sy
    +    Skew Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
    +    sage: y.parent()
    +    Traceback (most recent call last):
    +    ...
    +    NameError: name 'y' is not defined    
    +
    +If we omit it in RHS, sage tries to create a polynomial ring and fails::
    +
    +    sage: Sz.<z> = R[sigma]
    +    Traceback (most recent call last):
    +    ...
    +    ValueError: variable names must be alphanumeric, but one is 'Ring endomorphism of Univariate Polynomial Ring in t over Integer Ring
    +      Defn: t |--> t + 1' which is not.
    
  • There is a class SkewPolynomialRing_finite_field defined in sage/rings/polynomial/skewpolynomial_ring.py. There is also a file sage/rings/polynomial/skewpolynomial_finite_field.pyx. It seems that the class defined in the latter does not use the latter:
    cdef class SkewPolynomial_finite_field_dense (SkewPolynomial_generic_dense):
    
  • I suggest using skew_polynomial in the file names instead of skewpolynomial.
  • Are the Left and Right objects defined in sage/structure/side.py really necessary? If Right is the default, can't you just have a keyword argument left=<bool>?
  • There are many functions missing a docstring or tests. Here is partial coverage output:
    $ ./sage -coverage devel/sage/sage/rings/polynomial/skew*
    ----------------------------------------------------------------------
    devel/sage/sage/rings/polynomial/skewpolynomial_element.pyx
    ERROR: Please add a `TestSuite(s).run()` doctest.
    SCORE devel/sage/sage/rings/polynomial/skewpolynomial_element.pyx: 78% (58 of 74)
    
    Missing documentation:
    	 * __hash__(self):
    	 * __richcmp__(left, right, int op):
    	 * __nonzero__(self):
    	 * _is_atomic(self):
    	 * __lshift__(self, k):
    	 * __rshift__(self, k):
    	 * is_gen(self):
    	 * make_generic_skewpolynomial(parent, coeffs):
    	 * Element _call_(self, x):
    	 * __init__(self, domain, codomain):
    	 * Element _call_(self, x):
    	 * Element _call_with_args(self, x, args=(), kwds={}):
    	 * section(self):
    
    
    Missing doctests:
    	 * SkewPolynomial _new_constant_poly(self,RingElement a,Parent P,char check=0):
    	 * is_unit(self):
    	 * __copy__(self):
    
    
    Possibly wrong (function name doesn't occur in doctests):
    	 * ModuleElement _add_(self, ModuleElement right):
    	 * ModuleElement _sub_(self, ModuleElement right):
    	 * ModuleElement _neg_(self):
    	 * ModuleElement _lmul_(self, RingElement right):
    	 * ModuleElement _rmul_(self, RingElement left):
    	 * RingElement _mul_(self, RingElement right):
    	 * RingElement _div_(self, RingElement right):
    
    ----------------------------------------------------------------------
    
    ----------------------------------------------------------------------
    devel/sage/sage/rings/polynomial/skewpolynomial_finite_field.pyx
    ERROR: Please add a `TestSuite(s).run()` doctest.
    SCORE devel/sage/sage/rings/polynomial/skewpolynomial_finite_field.pyx: 82% (29 of 35)
    
    Missing documentation:
    	 * __init__(self, parent, x=None, int check=1, is_gen=False, int construct=0, **kwds):
    	 * reduced_norm_factor(self):
    	 * _factorizations_rec(self):
    
    
    Missing doctests:
    	 * _irreducible_divisors(self,side):
    	 * __init__(self,parent,cutoff=0):
    	 * __repr__(self):
    
    
    Possibly wrong (function name doesn't occur in doctests):
    	 * RingElement _mul_(self, RingElement right):
    
    ----------------------------------------------------------------------
    
    ----------------------------------------------------------------------
    devel/sage/sage/rings/polynomial/skewpolynomial_ring_constructor.py
    SCORE devel/sage/sage/rings/polynomial/skewpolynomial_ring_constructor.py: 100% (1 of 1)
    ----------------------------------------------------------------------
    
    ----------------------------------------------------------------------
    devel/sage/sage/rings/polynomial/skewpolynomial_ring.py
    SCORE devel/sage/sage/rings/polynomial/skewpolynomial_ring.py: 42% (17 of 40)
    
    Missing documentation:
    	 * _call_ (self, x):
    	 * __init__(self,domain,codomain,embed,order):
    	 * _repr_(self):
    	 * _call_(self,x):
    	 * section(self):
    	 * __init__ (self, skew_ring, names=None, sparse=False, element_class=None):
    	 * __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None):
    	 * __init__(self, base_ring, map, name, sparse, element_class):
    	 * __reduce__(self):
    	 * _element_constructor_(self, x=None, check=True, is_gen = False, construct=False, **kwds):
    	 * _coerce_map_from_(self, P):
    	 * __cmp__(left, right):
    	 * _repr_(self):
    	 * _latex_(self):
    	 * gens_dict(self):
    	 * __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None):
    	 * __init__(self, base_ring, map, name, sparse, element_class):
    
    
    Missing doctests:
    	 * _repr_ (self):
    	 * _latex_ (self):
    	 * parameter(self):
    	 * is_sparse(self):
    	 * _new_retraction_map(self,alea=None):
    	 * _retraction(self,x,newmap=False,alea=None):
    
    ----------------------------------------------------------------------
    
    

comment:20 Changed 5 years ago by burcin

Here is some more information from Viktor Levandovskyy about Plural and skew polynomials rings over finite fields with the frobenius map.

> Plural can be used in the following situations:
> Let |F|=p^k, where p is a prime.
> *) always possible: k = 1,2 and k = p-1,p.
> *) For k=3,...,p-2 there's no general statement, sometimes
> works, sometimes not. Depends on p and k
> *) k>p: impossible (with Plural)

comment:21 in reply to: ↑ 19 Changed 5 years ago by caruso

  • Dependencies changed from #13214, #13303 to #13214, #13303, #13640, #13641, #13642
  • Description modified (diff)
  • Status changed from needs_work to needs_review

Thanks a lot for all your comments!

Replying to burcin:

  • short representations for morphisms
  • hash functions for morphisms (#9016)
  • q_jordan
  • modular exponentiation of polynomial_element

Ok, I've done it (see tickets #13640, #13641 #13642 and old ticket #13214 for "hash functions for morphisms").

After applying the patches on this ticket and its dependencies, I get the following error:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Skew Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring twisted by t |--> t + 1
sage: x*t
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
sage: %debug
> /home/burcin/sage/sage-5.2/skewpolynomial_element.pyx(347)sage.rings.polynomial.skewpolynomial_element.SkewPolynomial._list_c (sage/rings/polynomial/skewpolynomial_element.c:4716)()

It's now fixed. (I haven't really understood what was the problem. It worked well on sage 5.1.0. I just removed some inline somewhere.)

  • the operator / always constructs the quotient domain in Sage, even if exact division is possible. Since in this case we need a generic Ore localization for /, I suggest you only implement exact division with // and raise an error on /.

Done.

  • For the constructor, why don't you check if the argument of the __getitem__ method is a Morphism instead of this:
          from sage.categories.morphism import Morphism
           if isinstance(x,tuple) and len(x) == 2 and isinstance(x[1],Morphism):
    
    This should remove the limitation of having to specify the variable name on the right hand side as documented here:

It's not possible to remove this limitation this way because of the preparser (you see in the following example that the variable 'x' doesn't appear in the first instruction on the last line).

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: preparse(S.<x> = k[Frob])
sage: preparse("S.<x> = k[Frob]")
'S = k[Frob]; (x,) = S._first_ngens(1)'
  • I suggest using skew_polynomial in the file names instead of skewpolynomial.

Done.

  • Are the Left and Right objects defined in sage/structure/side.py really necessary? If Right is the default, can't you just have a keyword argument left=<bool>?

Sometimes, Left is the default (for lcm). I agree that we can just have a boolean argument but, when I wrote this code, I thought that it was more elegant to do this way. Anymay, I can change if you insist :-).

  • There are many functions missing a docstring or tests.

I've added some documentation and doctests (but I'm still far from a 100% coverage).

Changed 5 years ago by caruso

Changed 5 years ago by caruso

comment:22 Changed 4 years ago by darij

  • Cc darij added

Changed 4 years ago by caruso

Changed 4 years ago by caruso

comment:23 Changed 4 years ago by caruso

  • Description modified (diff)

I've posted an updated version of this patch which should apply at the top of sage 5-10 (hopefully).

Changed 4 years ago by caruso

comment:24 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:25 Changed 4 years ago by darij

Needs to be rebased on sage-5.12beta5. The patch fails to apply to sage/structure/all.py.

I'd do it myself but when I try to open the file in gedit, I get: "The file you opened has some invalid characters. If you continue editing this file you could corrupt this document. You can also choose another character encoding and try again." Might be some accents or umlauts on names.

comment:26 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 2 years ago by mmezzarobba

  • Status changed from needs_review to needs_work
  • Work issues set to see comment #25

comment:30 Changed 14 months ago by panda314

  • Branch set to u/panda314/skew_polynomials

comment:31 Changed 14 months ago by git

  • Commit set to f6305cee0d39c2a1a3727482af453c59791a9e1c

Branch pushed to git repo; I updated commit sha1. New commits:

f6305ceRevert "adding examples involving min_symbolic and max_symbolic"(did changes in the wrong ticket)

comment:32 Changed 11 months ago by arpitdm

  • Branch changed from u/panda314/skew_polynomials to u/arpitdm/skew_polynomials

comment:33 Changed 11 months ago by arpitdm

  • Cc jsrn dlucas added
  • Commit changed from f6305cee0d39c2a1a3727482af453c59791a9e1c to de61ca43086bcdef18a4171915064fdc469d2036

New commits:

d915c13merging the skew_polynomial ticket 13215 in local repository
447ddb3Extensions for skew_polynomial_element and skew_polynomial_finite field added.
05cc01bThe methods PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT are not supported by Sage anymore and are replaced by the method type. The Cython comparison function is updated to _cmp_ supported in other rings in Sage.
241b98dThe methods PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT are not supported by Sage anymore and are replaced by the method type.
98277cdRewrote the construction of skew polynomial ring according to the new conventions. Original code had placed it in the /sage/rings/rings.pyx file but the current location has moved to the getitem method of /sage/category/ring.py
de61ca4Importing ring_element, integral_domain and principal_ideal_domain were throwing deprecation warnings. Updated the import statements according to Tickets 19167 and 20011.

comment:34 Changed 11 months ago by git

  • Commit changed from de61ca43086bcdef18a4171915064fdc469d2036 to 9d21b5420c9464630854756ad4747ab766b96f4e

Branch pushed to git repo; I updated commit sha1. New commits:

9d21b54module that implements class 'Side' with Left and Right as the two instances.

comment:35 Changed 11 months ago by tscrim

  • Cc tscrim added

comment:36 Changed 10 months ago by git

  • Commit changed from 9d21b5420c9464630854756ad4747ab766b96f4e to 9c526ad250d8053e5b9184219e7e3cfc4186c097

Branch pushed to git repo; I updated commit sha1. New commits:

9c526adFixed doctests caused by deprecation warnings, inability to access private variables, AttributeError in accessing of parent, and .

comment:37 Changed 10 months ago by dlucas

  • Branch changed from u/arpitdm/skew_polynomials to u/dlucas/skew_polynomials

comment:38 Changed 10 months ago by dlucas

  • Commit changed from 9c526ad250d8053e5b9184219e7e3cfc4186c097 to 18c7982a3d363ad004760d91e874783eab4c72ae
  • Milestone changed from sage-6.4 to sage-7.3

I fixed one of the remaining bugs related to coercion of integers to a skew polynomial ring element. Some bugs still remain.


New commits:

9de7bc1Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
a06c2bfMerge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
18c7982Fixed bug with integer coercion

comment:39 Changed 10 months ago by jsrn

A little thing I noted: is_SkewPolynomial should be removed, I think. Sage moved away from that kind of functions. The category framework should be used instead, but I don't think we need to find a replacement for it just now.

comment:40 Changed 10 months ago by tscrim

A better idiom is to just use isinstance(S, SkewPolynomialRing_general) as it is explicit (and there is no category for skew polynomial rings).

comment:41 Changed 10 months ago by arpitdm

  • Branch changed from u/dlucas/skew_polynomials to u/arpitdm/skew_polynomials

comment:42 Changed 10 months ago by jsrn

  • Commit changed from 18c7982a3d363ad004760d91e874783eab4c72ae to dd5c575e26faaa88140e67c92130085b28e8b0a2

One of the bugs in the doctest has to do with failing in the proper manner when the twist map is not invertible (this is the TypeError: bad operand type for unary ~ bug). This is because self._map ** n is being called with negative n, which will then try to invert self._map using the unary ~ operator which is not supported by self._map of type Homomorphism_im_gens.

But the code was always supposed to fail! The doc-test just expected the error NotImplementedError?, while the error nowadays is this unhelpful unary-~-stuff.

One solution is therefore simply to catch the strange error and rethrow a NotImplementedException?. The following patch should be put in skew_polynomial_ring.py (the line numbers are not completely correct):

@@ -534,9 +534,18 @@ class SkewPolynomialRing_general(sage.algebras.algebra.Algebra,UniqueRepresentat
         try:
             return self._maps[n]
         except KeyError:
-            map = self._map**n
-            self._maps[n] = map
-            return map
+            if n >= 0:
+                map = self._map**n
+                self._maps[n] = map
+                return map
+            else:
+                try:
+                    map = self._map**n
+                except TypeError:
+                    raise NotImplementedError("Inversion of the twist map %s" % self._map)
+                self._maps[n] = map
+                return map
+                    

Best, Johan


New commits:

c6183bcMerge branch 'develop' into temp3
dd5c575Editing declarations of cython functions so as to make them compatible.

comment:43 Changed 10 months ago by jsrn

Note that I didn't modify any code: the two commits just appear under my message because arpitdm didn't leave a comment after his last push.

comment:44 Changed 10 months ago by git

  • Commit changed from dd5c575e26faaa88140e67c92130085b28e8b0a2 to 378b2cf7afb5d891b535b980fff85b4c9a6ef8ca

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

81a291fAdded more sig_on/sig_off
dce652eFix some imports
a7b8815commented out suspicious __copy__ method
dd821ecA few more sig_on/off and cleaning up some commented out code
d5fad11sig_on/off almost everywhere in finite field pyx (omitted factoring/irreducible stuff)
df59050Fixed bug with crashing add for finite fields by declaring SkewPolynomial.__normalize
a92d241Fixed segfault with _pow_ by declaring some _inplace_* already in SkewPolynomial class
bb36f9aSuspicious reuse of list of coefficients made into a safe copy
544ca8dFix x._pow_(2) by calling ._new_c instead of _parent (I don't know why this worked!)
378b2cffixed indentation error

comment:45 Changed 10 months ago by arpitdm

Cherry-picked commits based on fixes by Johan. The segfault from before is now fixed. Various doctest errors still remain. Now breaking up this ticket into smaller pieces so that it will be easier to manage.

comment:46 Changed 10 months ago by git

  • Commit changed from 378b2cf7afb5d891b535b980fff85b4c9a6ef8ca to 60dc3329dcaf4ce971b68867999f02d71b2f989a

Branch pushed to git repo; I updated commit sha1. New commits:

f3a9209removed skew_polynomial_finite_field files
09dc81dremoved the irreducibility, center and finite field stuff from this file
ff60603removed finite_fields stuff from file
97c7770removed extension from module_list.py
60dc332removed empty class CenterSkewPolynomial_generic_dense

comment:47 Changed 10 months ago by arpitdm

The current ticket now contains only the basic framework for skew polynomials. All features related to finite fields, irreducibility, center and karatsuba multiplication will be put into a separate ticket. The aim is to fix the failed doctests in the skew_polynomial_element.pyx file and then refactor the code, improve/add documentation and tests, phase out "side".

comment:48 Changed 10 months ago by git

  • Commit changed from 60dc3329dcaf4ce971b68867999f02d71b2f989a to 5b886b3be18614e3e41abd9a8eed11efefffff91

Branch pushed to git repo; I updated commit sha1. New commits:

5b886b3Fixed NotImplementedError and other standalone errors.

comment:49 Changed 10 months ago by jsrn

  • Branch changed from u/arpitdm/skew_polynomials to u/jsrn/skew_polynomials

comment:50 Changed 10 months ago by jsrn

  • Commit changed from 5b886b3be18614e3e41abd9a8eed11efefffff91 to 21be4d87405946f2f2ea3c415b4b2537b0ef6a80

Fixed some nasty errors, and some not so nasty ones.


New commits:

fa9f2a3Remove __cmp__
1061067missing return statement
21be4d8Fixed some doctests

comment:51 Changed 10 months ago by arpitdm

  • Branch changed from u/jsrn/skew_polynomials to u/arpitdm/skew_polynomials

comment:52 Changed 10 months ago by git

  • Commit changed from 21be4d87405946f2f2ea3c415b4b2537b0ef6a80 to c65088d27f07256875c1aaccfd89264601b1e642

Branch pushed to git repo; I updated commit sha1. New commits:

c0250feEdits to documentation, clean up code
3c758feminor edit to a documentation
f0bd901merging changes
0189fc2implemented special case for def is_unit when base ring is an integral domain
17ce5ecMerge branch 'partially_refactored_skew_polynomials' into skew_polynomials
c65088dfixed doctest that was mistakenly edited before

comment:53 Changed 10 months ago by git

  • Commit changed from c65088d27f07256875c1aaccfd89264601b1e642 to d7f51f9b2772e692b5914b71757d7fcc14d05e53

Branch pushed to git repo; I updated commit sha1. New commits:

71e77derenamed lmonic as left_monic, rmonic as right_monic and removed def monic.
99664e6renamed lquo_rem and rquo_rem as left_quo_rem and right_quo_rem. removed def quo_rem. split def is_divisible_by into def is_left_divisible_by and is_right_divisible_by. Same for def divides. replaced all instances in this file accordingly.
783f8dfrenamed lxgcd and rxgcd as left_xgcd and right_xgcd. removed def xgcd.
2a4f087renamed lgcd and rgcd as left_gcd and right_gcd. removed def gcd.
cd44a5afixed doctest errors from left_gcd. renamed llcm and rlcm as left_lcm and right_lcm. removed def lcm.
bc2a863removed sig_on/sig_off from everywhere.
d7f51f9small cleanup

comment:54 Changed 10 months ago by git

  • Commit changed from d7f51f9b2772e692b5914b71757d7fcc14d05e53 to 98d357d6ba074e39cb28004edfda42b36136024f

Branch pushed to git repo; I updated commit sha1. New commits:

f0f31b9removed def coeffs since it has been deprecated in polynomial_element.pyx. modified def coefficients to support return of only non-zero entries as well as all.
883146fadded methods def reverse, def number_of_terms and def is_one.
cebe0b4added __copy__, evaluation of polynomial and is_constant methods.
98d357dremoved from pow method in Class SkewPolynomial_generic_dense. Added documentation and tests to all the remaining functions and classes.

comment:55 Changed 9 months ago by git

  • Commit changed from 98d357d6ba074e39cb28004edfda42b36136024f to e189fec13d005a7fba39a429876c501fe95c05da

Branch pushed to git repo; I updated commit sha1. New commits:

49f2626added a couple of tests. fixed typos in documentation.
56982a2added documentation and tests. fixed doctests.
1808bb3small documentation for normalize function.
e189fecremoved side.py

comment:56 Changed 9 months ago by arpitdm

We planned on breaking up this skew polynomials ticket into five pieces namely:

  1. Ticket A - The main framework. Skew polynomials, basic operations, coercions, skew polynomial rings, etc.
  2. Ticket B - Class SkewPolynomial_finite_field_dense, class SkewPolynomialRing_finite_field and related methods
  3. Ticket C - cdef class SkewPolynomial_finite_field_karatsuba and related methods
  4. Ticket D - class SectionSkewPolynomialCenterInjection?, class SkewPolynomialCenterInjection?, class CenterSkewPolynomialRing? and related methods
  5. Ticket E - Irreducibility and Factoring related methods.

The current ticket #13215 has been modified to cover Ticket A. I will post an update here with the links to the remaining tickets once they have been created. For now, based on discussions, the main framework has been refactored, appended to, edited, documented and tested. I'm now opening this ticket for review.

comment:57 Changed 9 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:58 Changed 9 months ago by arpitdm

  • Description modified (diff)

comment:59 follow-ups: Changed 9 months ago by dlucas

  • Status changed from needs_review to needs_work

Hello,

I started reviewing your work. For now, I mostly read documentation and checked formatting, without focusing on the code itself. Here are my comments:

Generic comments:

  • For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.
  • I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

skew_polynomial_ring_constructor.py

  • I might be wrong, but it does not seem to have any reason to get both input name and names. The argument in the NOTE block sounds weird to me, especially when reading the code: it seems to be some kind of argument for later enhancements (multivariate skew polynomial rings), as for now it does not work if the list contains more than one element. Furthermore, the input names is only used to set name if the latter is None, and dropped just after. And in any case, I think it's better to use only one input and use type checks. I propose to remove names, rename name into variable_names, and use sanity checks: if it's a string, or a list with a single string, use it, otherwise return an appropriate error. I also suggest to add a line in the note block to say that multivariate rings are not supported (it's only detailed in tests for now).
  • Can you please explicit what LHS/RHS means?
  • There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
  • INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?
  • As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).
  • Module title says "constructorS for skew polynomial rings", while there's only one method in this module. </quibbling>
  • Module documentation itself is not great. I think it might be a good idea to add a few links to skew_polynomial_ring.py, and even to give a small definition of a skew polynomial ring in this module.

skew_polynomial_ring.py

  • The short description of this module: "Sage implements dense skew univariate polynomials over commutative rings.", seems unhelpful. I'd rather replace it by something explaining the purpose of this module.
  • I think the definition can be enhanced a bit: for instance, you find references to "twisting" all over the examples, but it's not defined everywhere. Reading what's in the DEFINITION block should be enough to understand the terminology used in the module, even if you're not familiar with skew polynomials at all.
  • Same remark as above regarding LHS/RHS.
  • Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.
  • Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...
  • There are a few methods in this file which are commented. If these are no longer useful, I suggest to remove them instead of commeting them.
  • In some methods, documentation is not really helpful: see twist_map for instance. If says "Return the twist map [...]" which is not very informative...
  • While I'm talking about it, would it be possible to explain why this method might fail if you pass a negative number as input? The sentence "Sometimes it succeeds" seems to imply it's more or less random, but if you could investigate this a bit it would lead to a more satisfying documentation.

skew_polynomial_element.py

  • Same remark as above regarding the definition of a skew polynomial ring.
  • Same remark as above regarding imported packages.
  • Same remark as above regarding informativeness of docstrings for some methods.
  • Same remark as above regarding documentation itself: a few methods (e.g. conjugate) do not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Best,

David

comment:60 in reply to: ↑ 59 ; follow-up: Changed 9 months ago by tscrim

Replying to dlucas:

  • I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

  • Can you please explicit what LHS/RHS means?

I think these are such common abbreviations for Left(Right)-Hand Side that being explicit about them will add some clutter.

  • There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
  • As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).

I disagree with these comments. This is documenting an upcoming feature, it helps keeps the API consistent with future plans and other parts of Sage, and tells someone reading the code what is currently not implemented.

  • Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

I treat this more as a strong guideline than a hard rule, but with that being said, anything more non-trivial should at least document its inputs (e.g., the __init__ would be useful).

I agree with the rest of David's comments.

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

comment:61 Changed 9 months ago by tscrim

  • Work issues see comment #25 deleted

One last thing, make sure all functions have doctests.

comment:62 in reply to: ↑ 59 ; follow-up: Changed 9 months ago by arpitdm

Replying to dlucas:

  • For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring
  • I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

Placing the experimental warning (like I did above) is not the right way to do it because it does not throw an error. Do I instead place this line at the start of every class in all the three files instead?

skew_polynomial_ring_constructor.py

  • I might be wrong, but it does not seem to have any reason to get both input name and names. The argument in the NOTE block sounds weird to me, especially when reading the code: it seems to be some kind of argument for later enhancements (multivariate skew polynomial rings), as for now it does not work if the list contains more than one element. Furthermore, the input names is only used to set name if the latter is None, and dropped just after. And in any case, I think it's better to use only one input and use type checks. I propose to remove names, rename name into variable_names, and use sanity checks: if it's a string, or a list with a single string, use it, otherwise return an appropriate error. I also suggest to add a line in the note block to say that multivariate rings are not supported (it's only detailed in tests for now).

I agree. names and name are both not required and variable_names along with tests to check type of the input is cleaner. I've made this change.

  • Can you please explicit what LHS/RHS means?

Like @tscrim mentions, I think LHS/RHS are extremely common terms that are used almost everywhere and perhaps don't need explicit description.

  • There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.

There are a lot of places where a NotImplementedError? is raised and not just in this ticket but in other polynomial files as well. I think it makes more sense to have them if they are already there. However, there is then the inconsistency in that derivations in skew polynomials are not implemented and are marked as todo as is the multivariate case in some places. Still, I argue for keeping sparse as it is since it is integrated in the framework already unlike the other two. And with the experimental warning showing up, changing this will not create too much trouble.

  • INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?

An endomorphism that admits an inverse is an automorphism and skew polynomial rings AFAIK are based on automorphisms. Please correct me if I'm mistaken in this. If so, the places where it says that the twist map is not invertible, maybe should say that twist map should be invertible. And accordingly, the name can be changed to base_ring_automorphism.

  • Module documentation itself is not great. I think it might be a good idea to add a few links to skew_polynomial_ring.py, and even to give a small definition of a skew polynomial ring in this module.

Understood. I've made changes and expanded on the definitions and examples from other files. Same goes for all other notes (below) about improving explanations.

  • Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.

I tried to do that with the ones I thought were not needed/deprecated. I've obviously missed a few. I'll go over this once again.

  • Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

Is there a reference doc or something where I can go through the mandatory documentation template? Or is it that Description, Input, Output, Examples, Tests - should these be present for every method? A lot of places, it doesn't make sense to have all of this.

  • In some methods, documentation is not really helpful: see twist_map for instance. not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Oh right! I mentioned this in the email thread with Johan except that I somehow messed up the name. I wasn't sure of what this method was doing.

comment:63 in reply to: ↑ 62 ; follow-up: Changed 9 months ago by dlucas

Replying to arpitdm:

Replying to dlucas:

  • For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring

Yup! I you're not sure of what you're doing, here's a way to test it: run sage --docbuild src/doc/en/reference/polynomial_rings html, it will compile the doc and give you an address. Copy-paste this address in your browser, and click on "index" in the page which opens. If what you added in index.rst works, you should see it here (and you'll be able to check its formatting as well).

  • I would also use the experimental decorator here: the code in itself seems stable, but it will allow us to make later name changes (for instance) without putting deprecation warnings all over the place. In particular, I have in mind later implementations of sparse rings and multivariate rings, which might trigger some renaming in the classes implemented here.

Placing the experimental warning (like I did above) is not the right way to do it because it does not throw an error. Do I instead place this line at the start of every class in all the three files instead?

Mmh, I reconsidered my position on this thanks to Travis' comment: as we'll not change the public API (which is the method in skew_polynomial_ring_constructor.py), I don't think it's necessary to put experimental warnings everywhere, as long as we're future proof as Travis suggests.

  • Can you please explicit what LHS/RHS means?

Like @tscrim mentions, I think LHS/RHS are extremely common terms that are used almost everywhere and perhaps don't need explicit description.

Yes, you're both right, let's drop that and keep LHS/RHS.

  • There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.

There are a lot of places where a NotImplementedError? is raised and not just in this ticket but in other polynomial files as well. I think it makes more sense to have them if they are already there. However, there is then the inconsistency in that derivations in skew polynomials are not implemented and are marked as todo as is the multivariate case in some places. Still, I argue for keeping sparse as it is since it is integrated in the framework already unlike the other two. And with the experimental warning showing up, changing this will not create too much trouble.

Yes, thinking again about it, I think you're both right. It's better to be future proof, and if it's used elsewhere in polynomials, there's definitely no trouble in doing so.

  • INPUT block could be enhanced: I would rather explain what's name (or variable_names if you agree with my comment above) instead of just saying "a string". I would also rename sigma to something more indicative. What about base_ring_endomorphism?

An endomorphism that admits an inverse is an automorphism and skew polynomial rings AFAIK are based on automorphisms. Please correct me if I'm mistaken in this. If so, the places where it says that the twist map is not invertible, maybe should say that twist map should be invertible. And accordingly, the name can be changed to base_ring_automorphism.

Err, yes my bad. base_ring_automorphism sounds good :)

  • Some imports are not necessary anymore, e.g. import sage.misc.latex as latex.

I tried to do that with the ones I thought were not needed/deprecated. I've obviously missed a few. I'll go over this once again.

Don't worry, it's quite tricky.

  • Some methods here do not follow the mandatory documentation template. For instance, __init__ does not have a short description, nor an INPUT block...

Is there a reference doc or something where I can go through the mandatory documentation template? Or is it that Description, Input, Output, Examples, Tests - should these be present for every method? A lot of places, it doesn't make sense to have all of this.

You can read this tutorial for Sage developers. But I agree this is not strong rules: while I do follow the "short description, jump line, optional long description" for my methods, I only write an OUTPUT block when the output is not obvious from reading the short description. I always write an INPUT block when there's input arguments, as I think that even if the names of the input arguments seems obvious, it's always nice to have an explicit definition. EXAMPLES are of course mandatory. TESTS are not, I think you should only use them when you want to run a few more tests which do not really make sense for the user. For instance, I use TESTS to doctest sanity checks. It's nice to add a doctest to ensure everything is sanitized, but it's of little interest for the user.

  • In some methods, documentation is not really helpful: see twist_map for instance. not have a short description, while make_generic_skew_polynomial does not have documentation at all!

Oh right! I mentioned this in the email thread with Johan except that I somehow messed up the name. I wasn't sure of what this method was doing.

Oh ok! I'll read it and try to understand what it does.

Best,

David

comment:64 in reply to: ↑ 63 ; follow-up: Changed 9 months ago by arpitdm

Replying to dlucas:

Replying to arpitdm:

Replying to dlucas:

  • For now, there's nothing related to skew polynomials in the index file, so it won't be possible for the user to access the documentation through the online reference manual. Can you please add a dedicated section in the related index file? See src/doc/en/reference/polynomial_rings/index.rst.

I read up a little on Sphinx documentation and from what I understand, I need to add the following in the file you mentioned, right?

@sage.misc.superseded.experimental(trac_number=13215)
Skew Polynomials
----------------

.. toctree::
   :maxdepth: 2

   sage/rings/polynomial/skew_polynomial_element
   sage/rings/polynomial/skew_polynomial_ring_constructor
   sage/rings/polynomial/skew_polynomial_ring

Yup! I you're not sure of what you're doing, here's a way to test it: run sage --docbuild src/doc/en/reference/polynomial_rings html, it will compile the doc and give you an address. Copy-paste this address in your browser, and click on "index" in the page which opens. If what you added in index.rst works, you should see it here (and you'll be able to check its formatting as well).

That command you mentioned didn't work. I get the following error message.

'src/doc/en/reference/polynomial_rings' is not a recognized document. Type 'sage --docbuild -D' for a list
of documents, or 'sage --docbuild --help' for more help.

I've made the other changes according to the discussions above.

comment:65 in reply to: ↑ 60 ; follow-ups: Changed 9 months ago by jsrn

Replying to tscrim:

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

Was there supposed to be some ending of this sentence?

  • There's an option sparse=False which, if set to True, returns a NotImplementedError. I suggest to remove it for now in order to not confuse the user, and reinstate it later when it will be fully implemented. In this case, also remove all references to this feature in the documentation.
  • As I suggest to remove some not implemented but planned features, it might be a good idea to add a TODO block as a reminder of these features (sparse rings, multivariate rings).

I disagree with these comments. This is documenting an upcoming feature, it helps keeps the API consistent with future plans and other parts of Sage, and tells someone reading the code what is currently not implemented.

This is debatable: sparse skew polynomials are not very useful whenever there is a derivation (since sparsity is not retained well across operations), and it's not very clear what a multivariate skew ring is. The most natural generalisation of this structure is Ore polynomials, but that would likely be a separate class. I don't think it makes sense to leave implementation artifacts that will, most likely, never lead to real implementations. In the odd case that they *would* lead to implementations, we could reinstate them with no penalty.

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

That's arguably true. To be fair: Xavier Caruso made the code, and Arpit just tried to get it into shape with less than full-rewrite-workload. That said, I would be concerned about subclassing commutative classes that commutative-only code creeps into the skew polynomials: for instance if someone later on adds a method to the parent class and forgets to explicitly overwrite or remove this method in the skew polynomial class. It's really only all the basics that are shared btw commutative/non-commutative: all the substantial and complex properties are not shared at all.

comment:66 in reply to: ↑ 65 Changed 9 months ago by jsrn

Replying to jsrn:

This is debatable: sparse skew polynomials are not very useful whenever there is a derivation (since sparsity is not retained well across operations),

Oh, I just remembered that this patch doesn't provide skew polynomials with derivations :-D So then this comment might be somewhat moot ;-)

The most natural generalisation of this structure is Ore polynomials,

One would perhaps add skew polynomials with derivations before full-fledged Ore rings, though :-)

Best, Johan

comment:67 in reply to: ↑ 65 ; follow-up: Changed 9 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

It is okay to change class names as long as the public API doesn't change (although this can entail unpickling issues in either case). I would instead future-proof this by

Was there supposed to be some ending of this sentence?

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Also, from a cursory glance, there seems to be a lot of duplication with the current implementations of polynomials (i.e., the elements). I feel there could be a lot of simplification of the code by either subclassing or creating a mix-in (cython) class that overrides the _mul_ of polynomials. Is there a reason why you didn't do this? This might entail doing some refactoring/abstracting of the polynomial code though, but it should make the implementation of skew polynomials a lot easier (and bug proof).

That's arguably true. To be fair: Xavier Caruso made the code, and Arpit just tried to get it into shape with less than full-rewrite-workload.

I thank them both for working on this and pushing it forward.

That said, I would be concerned about subclassing commutative classes that commutative-only code creeps into the skew polynomials: for instance if someone later on adds a method to the parent class and forgets to explicitly overwrite or remove this method in the skew polynomial class. It's really only all the basics that are shared btw commutative/non-commutative: all the substantial and complex properties are not shared at all.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

Last edited 9 months ago by tscrim (previous) (diff)

comment:68 in reply to: ↑ 67 ; follow-up: Changed 9 months ago by jsrn

Replying to tscrim:

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Ah ok. You're right: aim for a good API. I think that the experimental decorator is still a good idea for such a big, brand-new feature, though. That what it was introduced for.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

I agree that this would be nice and should be looked at. However, can I suggest that this is for another ticket (cf. Reviewer's Checklist The perfect is the enemy of the good?http://doc.sagemath.org/html/en/developer/reviewer_checklist.html).

That way, improvements could progress on both ends (improving code sharing between the polynomial types, while improving skew poly functionality, and the coding theory constructions that we will build using skew polynomials).

comment:69 in reply to: ↑ 68 ; follow-up: Changed 9 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

That must of gotten lost when I had connectivity issues. This was suppose to be "by using a consistent API".

Ah ok. You're right: aim for a good API. I think that the experimental decorator is still a good idea for such a big, brand-new feature, though. That what it was introduced for.

In this case we have very similar features that we have had for a long time, in addition to a certain amount of stability with the code. By that, I think we shouldn't scare users with such a warning.

I don't want to diminish their work, but sometimes after having the code there and looking ahead, major refactoring can be needed. However, there would likely need to be refactoring of the usual commutative polynomials to address the issue you brought up. There could also be ways to factor out common code from other algebras across Sage. So in short, what I'm suggesting is to have a common abstract base class for both for the basic/core functionality. If there is only a little overlap (I really haven't looked), then we can just continue in our current fashion.

I agree that this would be nice and should be looked at. However, can I suggest that this is for another ticket (cf. Reviewer's Checklist The perfect is the enemy of the good?http://doc.sagemath.org/html/en/developer/reviewer_checklist.html).

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

That way, improvements could progress on both ends (improving code sharing between the polynomial types, while improving skew poly functionality, and the coding theory constructions that we will build using skew polynomials).

If only I had time... :P

comment:70 in reply to: ↑ 64 ; follow-up: Changed 9 months ago by dlucas

Replying to arpitdm:

That command you mentioned didn't work. I get the following error message.

'src/doc/en/reference/polynomial_rings' is not a recognized document. Type 'sage --docbuild -D' for a list
of documents, or 'sage --docbuild --help' for more help.

I've made the other changes according to the discussions above.

Oh, my mistake, sage --docbuild reference/polynomial_rings html is enough... By the way, don't forget to rebuild before compiling documentation. If you don't, changes you made to the docstrings/tests since your last rebuild will not be considered.

Best,

David

comment:71 in reply to: ↑ 70 Changed 9 months ago by arpitdm

Hi David,

The name and names that we had agreed upon changing to variable_names is giving a problem I did not notice until I was testing stuff today. I think the reason they exist is not just to facilitate multi-variate rings but also to support the diamond bracket notation. S.<x> = SkewPolynomialRing(R, sigma) and without it gives TypeError? (unexpected keyword argument). Also, this is a syntax present in other ring constructors in Sage. And while we don't support multivariate rings for Skew Polynomials, perhaps this feature might be added later on and we do need the diamond notation. Is there an alternate way in Sage to capture the diamond bracket or should we revert back to the original?

comment:72 Changed 9 months ago by dlucas

Hello,

Oh, ok I was not aware of that. I tested it on my side, and indeed whenever you use diamond bracket, it expects an argument called names. Xavier's comments on the NOTE block makes sense now.

In that case, what about removing the argument name and keep only names? Then, through input sanitization, allow only string, list containing one string, fail with a specific error if one passes a list with several strings in it explaining multivariate ring is not yet supported, and fail with a generic error message, e.g. "You can only pass a string, or a list of string for input names" otherwise. I think it does the trick.

David

comment:73 in reply to: ↑ 69 ; follow-up: Changed 9 months ago by jsrn

Replying to tscrim:

In this case we have very similar features that we have had for a long time, in addition to a certain amount of stability with the code. By that, I think we shouldn't scare users with such a warning.

You have a point. The names and conventions are unlikely to change within the limited scope of this ticket. For the follow-up tickets containing the rest of Caruso's code the experimental decorator could be considered.

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

I don't think it makes it harder to refactor later on than now: it's exactly the same work, since the full implementation of skew polynomials has already been written, doctested etc. That's one reason I would suggest leaving it for a future ticket.

comment:74 in reply to: ↑ 73 Changed 9 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

I'm not asking for perfection. If we do decide to subclass, then it just makes it somewhat harder to refactor once this is included. Just to be clear, I am just raising the question, not making the refactoring a requirement.

I don't think it makes it harder to refactor later on than now: it's exactly the same work, since the full implementation of skew polynomials has already been written, doctested etc. That's one reason I would suggest leaving it for a future ticket.

It just means we have to deal with getting old pickles to work, which might be non-trivial (granted, Sage is not always successful with this).

comment:75 follow-ups: Changed 9 months ago by tscrim

You do want to use names:

sage: preparse('R.<x> = PolynomialRing(ZZ)')
"R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)"

Some notes on the code from a skim through:

  • You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.
  • Kill with fire and holy water is_* methods. They just trivially call isinstance.
  • You can use
    self._no_generic_basering_coercion = True
    
    to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.
  • _cmp_ is planned to be removed. Use _richcmp_ instead.
  • You should lazy import the ring constructor.
  • You are double importing things in the element class; only keep the cimport's.

comment:76 in reply to: ↑ 75 ; follow-up: Changed 9 months ago by jsrn

Hi Travis,

You seem to understand these things quite well, and we had quite some problems with getting this code to work, so could you please elaborate on the following things:

Replying to tscrim:

  • You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.

That would be great. Can you give us the full list of the methods for which we can do this, or point us to how we can figure it out?

  • You can use
    self._no_generic_basering_coercion = True
    
    to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.

To be precise, do you mean that can insert the above line in SkewPolynomialRing_general.__init__ just before the call to Algebra.__init__, and then remove the call to self._unset_coercions_used()? Or is there more to it?

  • _cmp_ is planned to be removed. Use _richcmp_ instead.

Are you talking about SkewPolynomial._cmp_? We spent many hours debugging the comparison code because it threw strange errors and segfaults. To avoid me spending many more hours, could I ask you to tell us exactly how to write the correct comparison code then?

Simon King's tutorial on implementing algebraic structures should be updated to be more informative on this, I think.

  • You should lazy import the ring constructor.

Do you mean sage.rings.ring in skew_polynomial_ring.py? Why is exactly that one important to lazily import?

Thanks for the help!

Best, Johan

comment:77 in reply to: ↑ 75 ; follow-up: Changed 9 months ago by arpitdm

Replying to tscrim: To add to what Johan is asking,

  • Kill with fire and holy water is_* methods. They just trivially call isinstance.

Which "is_" methods are you referring to? I couldn't really find any that call isinstance directly apart from the is_SkewPolynomialRing. For example, is_finite returns true if the base ring is finite and has order 1 and false otherwise. And so on. Each have minor conditions that the user could of course check themselves if need be, but its not always a one line call and its not always obvious what methods are available to the user so that they may verify. Should such methods then still be removed?

  • You are double importing things in the element class; only keep the cimport's.

Could you elaborate with a tiny example or something what you mean by this?

Again, thank you for your help!

Best, Arpit.

comment:78 in reply to: ↑ 77 Changed 9 months ago by tscrim

Replying to arpitdm:

Replying to tscrim: To add to what Johan is asking,

  • Kill with fire and holy water is_* methods. They just trivially call isinstance.

Which "is_" methods are you referring to? I couldn't really find any that call isinstance directly apart from the is_SkewPolynomialRing. For example, is_finite returns true if the base ring is finite and has order 1 and false otherwise. And so on. Each have minor conditions that the user could of course check themselves if need be, but its not always a one line call and its not always obvious what methods are available to the user so that they may verify. Should such methods then still be removed?

Sorry, I misspoke slightly. It is the is_* functions, which as you say are things like is_SkewPolynomialRing.

  • You are double importing things in the element class; only keep the cimport's.

Could you elaborate with a tiny example or something what you mean by this?

You should make this change:

-from sage.structure.element import Element, AlgebraElement
 from sage.structure.element cimport Element, AlgebraElement, ModuleElement
 from sage.structure.parent cimport Parent
-from polynomial_compiled import CompiledPolynomialFunction
 from polynomial_compiled cimport CompiledPolynomialFunction

comment:79 in reply to: ↑ 76 Changed 9 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

  • You seem to be using the exact same format of polynomials, which contains a lot of old code. For example, don't implement a _repr_() that just calls (a Python function) _repr(). This is useless (even in the usual polynomial ring code it seems); instead just implement _repr_(). Similarly, there are a number of methods you could simply cpdef.

That would be great. Can you give us the full list of the methods for which we can do this, or point us to how we can figure it out?

Anything python method (a def) which only calls a cdef method. Another example is list calling _list_c. IIRC, you can't do this for __hash__ because this is a Python special method. I think _list_c is the only other one (and you can replace this by just calling the attribute __coeffs).

  • You can use
    self._no_generic_basering_coercion = True
    
    to avoid constructing the coercion from the base ring when initializing the skew polynomial ring.

To be precise, do you mean that can insert the above line in SkewPolynomialRing_general.__init__ just before the call to Algebra.__init__, and then remove the call to self._unset_coercions_used()? Or is there more to it?

Yes, exactly.

  • _cmp_ is planned to be removed. Use _richcmp_ instead.

Are you talking about SkewPolynomial._cmp_? We spent many hours debugging the comparison code because it threw strange errors and segfaults. To avoid me spending many more hours, could I ask you to tell us exactly how to write the correct comparison code then?

You can look at src/sage/rings/real_arb.pyx or src/sage/rings/real_double.pyx for example. We can include the _cmp_ as it is now, but it means some more hardship when we finally start converting.

Simon King's tutorial on implementing algebraic structures should be updated to be more informative on this, I think.

Yes, it should be. It was written before we really had to worry about going to Python3.

  • You should lazy import the ring constructor.

Do you mean sage.rings.ring in skew_polynomial_ring.py? Why is exactly that one important to lazily import?

It is the thing which imports the rest of the code (once the is_* functions are gone). So all of the other files are not imported on startup, which helps keep that down because this is not a "common" object that the average user will use (IMO).

Thanks for the help!

Thank you for the good discussions and work.

comment:80 Changed 9 months ago by git

  • Commit changed from e189fec13d005a7fba39a429876c501fe95c05da to 22eab5df8c479f46d780c09625d3c7b790b3c816

Branch pushed to git repo; I updated commit sha1. New commits:

1f62ef4added a section related to skew polynomils in the index file.
abbd05eremoved double imports and unused classes and methods
8b337c5improved description of module, definition of skew polynomial, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of a couple of methods.
e0f3f42changes to incorporate merging and into
0c8f6ecremoved unnecessary imports
0641ecfimproved 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.
22eab5dsame as previous commit

comment:81 Changed 9 months ago by arpitdm

Stuff fixed in the commits above based on latest set of discussions:

  1. Improved descriptions for element, ring and ring constructor files
  2. Improved definitions.
  3. Input sanitization and INPUT block for init methods
  4. name and names merged into a single names argument.
  5. Improved documentation and tests for twist_map, make_generic_skew_polynomial` and other such methods.
  6. Removed all functions that trivially called isinstance. Merged _repr_ and _repr into _repr_.
  7. Improved call to coercion, removed double imports, removed unnecessary imports. Added lazy import where possible.
  8. Solving any doctests that came up in the course of the aforementioned changes.

Please let me know if I have missed something and of course any other changes that ought to be made. I'm now opening this for review.

comment:82 Changed 9 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:83 Changed 9 months ago by jsrn

Sounds great!

Did you look at the _cmp_ thing that Travis brought up? Best, Johan

comment:84 Changed 9 months ago by dlucas

  • Status changed from needs_review to needs_work

Hello,

Good work on docstrings and module documentation, it's much better now. However, I have some comments:

  • documentation does not compile: it seems you have some formatting errors in bullet lists.
  • you used single backquote notation at some places in the documentation where it should be double backquotes, e.g. in SkewPolynomial class, you wrote self between single backquotes (which triggers LaTeX formatting) instead of double.
  • a few lines below, default: False, False should be between double backquotes.
  • you kept the import import sage.misc.latex as latex. I'm quite sure you can remove it, but in that case, you'll have to change latex.latex(self.base_ring()) to self.base_ring()._latex_() (l. 359, skew_polynomial_ring.py). There's probably some more to change.

Apart from that, it looks good to me. Patchbot says some doctests fails, but according to which doctests are failing, I'm quite sure it's not because of this ticket.

Best,

David

comment:85 Changed 9 months ago by git

  • Commit changed from 22eab5df8c479f46d780c09625d3c7b790b3c816 to dc5fb565e1a2b126a86034cb1d1c5936c41b3d19

Branch pushed to git repo; I updated commit sha1. New commits:

1c717dbresolved single and double back tick formatting inconsistencies.
6f4d80aresolved back tick inconsistencies from other files
dc5fb56replaced method _cmp_ with _richcmp_. removed latex import.

comment:86 Changed 9 months ago by arpitdm

I think I managed to replace the _cmp_ method with _richcmp_. Please let me know if I did it incorrectly or something. Back tick inconsistencies are resolved. The latex import in skew_polynomial_element.pyx was removable, but the skew_polynomial_ring did not allow it. It threw up errors and I think its because the latex method of the self._map does not support it.

Also, I don't understand what is going wrong when I try to build the documentation. I can't find any indentation errors.

[polynomia] loading pickled environment... not yet created
[polynomia] WARNING: intersphinx inventory '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv' not fetchable due to <type 'exceptions.IOError'>: [Errno 2] No such file or directory: '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv'
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:20: WARNING: Definition list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:30: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.make_generic_skew_polynomial:12: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:70: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:105: WARNING: Literal block expected; none found.
[polynomia] /home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_sequence.py:docstring of sage.rings.polynomial.multi_polynomial_sequence:3: WARNING: citation not found: CMR05
[polynomia] Exception occurred:
[polynomia] File "/home/arpit/Documents/GSOC_16/sage/src/sage_setup/docbuild/ext/multidocs.py", line 286, in link_static_files
[polynomia] os.symlink(master_static_dir, static_dir)
[polynomia] OSError: [Errno 17] File exists
[polynomia] The full traceback has been saved in /tmp/sphinx-err-IsQg2Y.log, if you want to report the issue to the developers.
[polynomia] Please also report this if it was a user error, so that a better error message can be provided next time.
[polynomia] A bug report can be filed in the tracker at <https://github.com/sphinx-doc/sphinx/issues>. Thanks!
Error building the documentation.
Traceback (most recent call last):
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1629, in main
    builder()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 710, in _wrapper
    getattr(DocBuilder, build_type)(self, *args, **kwds)
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 103, in f
    runsphinx()
  File "/home/arpit/Documents/GSOC_16/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 215, in runsphinx
    raise exception
OSError: [polynomia] WARNING: intersphinx inventory '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv' not fetchable due to <type 'exceptions.IOError'>: [Errno 2] No such file or directory: '/home/arpit/Documents/GSOC_16/sage/local/share/doc/sage/inventory/en/reference/objects.inv'


Note: incremental documentation builds sometimes cause spurious
error messages. To be certain that these are real errors, run
"make doc-clean" first and try again.

comment:87 Changed 9 months ago by dlucas

Well, I don't know what happens... Here's what I have on my local machine:

[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:20: WARNING: Definition list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:30: WARNING: Literal block expected; none found.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.left_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_gcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_lcm:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.right_xgcd:11: WARNING: Bullet list ends without a blank line; unexpected unindent.
[polynomia] docstring of sage.rings.polynomial.skew_polynomial_element.make_generic_skew_polynomial:12: WARNING: Literal block expected; none found.
[polynomia] /home/david/Desktop/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:73: WARNING: Literal block expected; none found.
[polynomia] /home/david/Desktop/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/skew_polynomial_ring_constructor.py:docstring of sage.rings.polynomial.skew_polynomial_ring_constructor.SkewPolynomialRing:108: WARNING: Literal block expected; none found.
Error building the documentation.
Traceback (most recent call last):
  File "/home/david/Desktop/sage/local/lib/python/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/home/david/Desktop/sage/local/lib/python/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1630, in main
    builder()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 710, in _wrapper
    getattr(DocBuilder, build_type)(self, *args, **kwds)
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 103, in f
    runsphinx()
  File "/home/david/Desktop/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 215, in runsphinx
    raise exception
OSError: [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

This is the kind of error sphinx returns when there's no blank line after a bullet list. Usually, it's because you did not indented properly if you put several lines in a single bullet. It should be like this:

- my first line
  and my second line

so it's not 4 whitespaces, it has to be aligned with the first character of the line above.

Anyway, for your issues, I'd say run make doc-clean and make.

David

Last edited 9 months ago by dlucas (previous) (diff)

comment:88 Changed 9 months ago by git

  • Commit changed from dc5fb565e1a2b126a86034cb1d1c5936c41b3d19 to 0de3552ca85ee36a91cb41bff993e0eaebe25ecb

Branch pushed to git repo; I updated commit sha1. New commits:

54099acfixed errors that came up while building documentation
0de3552reference for CMR05 was missing from the docs in multi_polynomial_sequence.py file. Added that.

comment:89 Changed 9 months ago by arpitdm

Hi David,

I finally managed to make sense of the error messages that were showing up in the documentation. For instance, [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

Represents some error in the 16th line of the documentation of the file and so on..

And like you suggested, one set of errors was because it indented incorrectly. Anyway, I think I've solved all the issues (docs build successfully on my system) and I do get a path to all the html files. Can you please confirm this?

comment:90 Changed 9 months ago by dlucas

Hello,

I finally managed to make sense of the error messages that were showing up in the documentation. For instance, [polynomia] docstring of sage.rings.polynomial.skew_polynomial_element:16: WARNING: Literal block expected; none found.

Oh, sorry, I thought you knew how to read these! Otherwise, I would have told you... It's not the most intuitive error message for sure, and I had some troubles with Sphinx compiler messages when I started working on Sage :).

I just pulled your branch and I'm recompiling the reference manual. If everything goes smoothly, I don't have other remarks, so if Johan and Travis agree, we can set this to positive_review.

comment:91 Changed 9 months ago by dlucas

  • Reviewers changed from Burcin Erocal to Burcin Erocal, David Lucas
  • Status changed from needs_work to needs_review

And it worked just fine. So, documentation compiles, tests passes, you fixed what we asked you to, I'm fine with it. If no one objects, I'll set this to positive_review.

David

comment:92 follow-up: Changed 9 months ago by tscrim

  • Status changed from needs_review to needs_work

The important thing is the first comment. The rest is more polish, but I think a fair amount more is needed.

  • All methods and functions must have doctests (e.g., the one added to map.pyx and hidden methods). Also, I think you should remove the commented out code.
  • You should remove this line from module_list.py:
    # depends = numpy_depends),
    
  • I would swap these lines in rings.py:
                
    -            from sage.categories.morphism import Morphism
                 if isinstance(arg, tuple):
    +                from sage.categories.morphism import Morphism
                     if len(arg) == 2 and isinstance(arg[1], Morphism):
                        from sage.rings.polynomial.skew_polynomial_ring_constructor import SkewPolynomialRing
                        return SkewPolynomialRing(self, arg[1], names=arg[0])
                     
    
  • Remove all trailing whitespace (well, at least do not add any).
  • In skew_polynomial_element.pyx, there are a number of things that need to be in latex mode (and an equation using the .. MATH:: block).
  • I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).
  • You should make list into a cpdef with an output type of list and remove _list_c.
  • For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.
  • You should use the cached version of 0 instead of going through coercion and getting a new object in memory:
             try:
                 l = (<SkewPolynomial>self)._list_c()[n]
                 return l
             except IndexError:
    -            c = self.base_ring()(0)
    -            return c
    +            return self.base_ring().zero()
    
  • Use Python3 syntax for errors: raise IndexError("skew polynomials are immutable").
  • Similar to above: self.parent()(0) -> self.parent().zero().
  • is_nilpotent should have a short description of what the method should do (as well as the intended operation).
  • Returns -> Return in a few first-line of docstrings.
  • .. Note:: -> .. NOTE:: (this is a consistency thing).
  • You have a blank .. SEEALSO:: in __floordiv__.
  • is_left_divisible_by doesn't have a short description. Similar for other such methods.
  • Error messages should start with a lowercase letter (this was something we've agreed upon in somewhat more recent history).
  • There is a preference to have ``True`` in code formatting since it is a Python object/concept.
  • Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

I might have some more comments later too. However this is looking very good and it will be a great addition to Sage.

Also, the _richcmp_ looks correct (although I don't have time right now to run any serious tests).

comment:93 Changed 9 months ago by jsrn

  • Authors changed from Xavier Caruso to Xavier Caruso, Arpit Merchant, Johan Rosenkilde
  • Reviewers changed from Burcin Erocal, David Lucas to Burcin Erocal, David Lucas, Travis Scrimshaw

comment:94 follow-up: Changed 9 months ago by jsrn

The implemented operator evaluation __call__ is incorrect. For instance, 1(a) = a and x(a) = sigma(a) in a correct implementation, but that is not the case here. The following implementation works:

    if eval_pt not in self._parent:
        raise TypeError("Evaluation point must be a ring element")
    sigma = self._parent.twist_map()
    coefficients = self.coefficients(sparse=False)
    sum = self._parent.zero()
    a = eval_pt
    for c in coefficients:
        sum += c * a
        a = sigma(a)
    return sum

I think we should make an effort to cythonize this method. Could you try that Arpit?

Best, Johan

comment:95 Changed 9 months ago by git

  • Commit changed from 0de3552ca85ee36a91cb41bff993e0eaebe25ecb to 6fb186ab4b9eedb41596053854996263e85c5fe7

Branch pushed to git repo; I updated commit sha1. New commits:

35364a9removed commented code. added documentation and test for :meth: inverse.
cede096removed commented line of code.
17450faimport of Morphism moved to inside of statement so that it acts like a lazy import.
5a36953removed all trailing whitespaces. removed commented code from skew_polynomial_element.pxd.
bd45351converted to Python3 syntax for errors. edited error messages to start with lower case letters.
c203856code formatting for True, False and None Python objects. added latex typsetting in docs. added descriptions for some methods that didn't have them.
b52fc95using cached versions of 0 and 1 wherever applicable.
6fb186achanged Returns to Return and Note to NOTE for consistency. Removed trailing whitespaces. codeformatting for True, False and None objects.

comment:96 in reply to: ↑ 92 ; follow-up: Changed 9 months ago by arpitdm

Replying to tscrim:

  • All methods and functions must have doctests (e.g., the one added to map.pyx and hidden methods). Also, I think you should remove the commented out code.

I am still going over the methods to check whether there are any remaining. And I still have some commented code to remove.

  • I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).

Could you please explain with an example maybe, what this means? Or maybe refer me to some method in some file from where I can read and understand.

  • You should make list into a cpdef with an output type of list and remove _list_c.

class SkewPolynomial_general inherits from class SkewPolynomial. The _list_c method is implemented in the former while in the latter it is not. Are you suggesting that I remove _list_c from both classes and only have a cpdef list list(self) in the latter class?

  • For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.

There is no __coeffs attribute in class SkewPolynomial and it is actually defined in class SkewPolynomial_general. Is it Python convention to access from one class, an attribute with double leading underscores of another class? If so, what is the correct way of doing that?

  • Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

comment:97 in reply to: ↑ 94 Changed 9 months ago by arpitdm

Replying to jsrn:

The implemented operator evaluation __call__ is incorrect. For instance, 1(a) = a and x(a) = sigma(a) in a correct implementation, but that is not the case here. The following implementation works:

Oh! I now recall having this discussion before. Thank you for pointing it out again.

I think we should make an effort to cythonize this method. Could you try that Arpit?

Yup. On it. :)

Best, Arpit

comment:98 in reply to: ↑ 96 ; follow-up: Changed 9 months ago by tscrim

Replying to arpitdm:

Replying to tscrim:

  • I would move most-to-all of the module-level doc to the user entry point and then have a .. SEEALSO:: block referencing said doc, so it is visible from the ? on the command line. This also applies to the parent class(es?) (i.e. module-level to class-level).

Could you please explain with an example maybe, what this means? Or maybe refer me to some method in some file from where I can read and understand.

I would make a change like this:

 """
 Top/Module-level
 
-Description
 """
 class Foo:
     """
     Class-level.
+
+    Description
     """

That way when you do Foo?, you get Description. You also want some cross-linking so that someone using the online doc has links to follow to get to Description.

  • You should make list into a cpdef with an output type of list and remove _list_c.

class SkewPolynomial_general inherits from class SkewPolynomial. The _list_c method is implemented in the former while in the latter it is not. Are you suggesting that I remove _list_c from both classes and only have a cpdef list list(self) in the latter class?

  • For __iter__, just iterate over self.__coeffs. Actually, a similar statement applies to many other places you call _list_c where you don't expose it to the user or modify the list (e.g., __getitem__ and _richcmp_. The multivariate and sparse versions should be overriding these methods anyways.

There is no __coeffs attribute in class SkewPolynomial and it is actually defined in class SkewPolynomial_general. Is it Python convention to access from one class, an attribute with double leading underscores of another class? If so, what is the correct way of doing that?

Don't make it double underscore (you can also do the explicit name-mangling). In general, I avoid double underscores so you can use the hidden attributes in subclasses (unless you really wanted it to be completely hidden from all subclasses, which is very rare).

  • Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

ABC = Abstract Base Class, so the methods you have that just raise a NotImplementedError (e.g., _inplace_add), you should have them be blank (modulo a docstring and a doctest of a concrete implementation) with a @abstract_method. These then get picked up by a failure of the TestSuite.

comment:99 Changed 9 months ago by git

  • Commit changed from 6fb186ab4b9eedb41596053854996263e85c5fe7 to 271bface01f93c8dca5a1fb104da139224ae1e66

Branch pushed to git repo; I updated commit sha1. New commits:

1204f2dthe current implementation of the :meth: __call__ was incorrect. added the correct and cythonized version.
7e076famoved module level docs to user entry point at the class level so that they are accessible at command line. added a SEEALSO block.
69fecc4converted :meth: into a cpdef method with output type list. removed and directly use the attribute.
271bfacremoved some commented code and trailing whitespaces.

comment:100 in reply to: ↑ 98 Changed 9 months ago by arpitdm

Replying to tscrim:

  • Actually, a number of functions that use _list_c should be moved to the concrete class (and maybe an @abstract_method placeholder done in the ABC.

Could you please elaborate a little what you mean by this? I'm not sure I follow.

ABC = Abstract Base Class, so the methods you have that just raise a NotImplementedError (e.g., _inplace_add), you should have them be blank (modulo a docstring and a doctest of a concrete implementation) with a @abstract_method. These then get picked up by a failure of the TestSuite.

I tried adding the @abstract_method to the cdef void _inplace_add method and I got an error message saying "Cdef functions/classes cannot take arbitrary decorators." According to their docs, I don't think decorators are implemented yet.

comment:101 Changed 9 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:102 Changed 9 months ago by tscrim

Oh, I missed that they were cdef methods. I don't think you need to declare anything for them for ABCs, but I am not completely sure if Cython allows this.

comment:103 follow-up: Changed 9 months ago by dlucas

  • Status changed from needs_review to needs_work

Hello,

Some doctests are still missing. If you're not sure you documented everything, use the following command: sage -coverage <path_to_files>. On my side, it returns:

david@david:~/Desktop/sage/src/sage/rings/polynomial$ sage -coverage skew_polynomial_*
------------------------------------------------------------------------
SCORE skew_polynomial_element.pyx: 97.4% (76 of 78)

Missing doctests:
     * line 327: cpdef SkewPolynomial _new_constant_poly(self, RingElement a, Parent P, char check=0)
     * line 892: def is_nilpotent(self)

Possibly wrong (function name doesn't occur in doctests):
     * line 2434: def mod(self, other)
     * line 3129: cpdef Element _call_with_args(self, x, args=(), kwds={})
------------------------------------------------------------------------
SCORE skew_polynomial_ring_constructor.py: 100.0% (1 of 1)
------------------------------------------------------------------------
SCORE skew_polynomial_ring.py: 78.9% (15 of 19)

Missing documentation:
     * line 129: def __classcall__(cls, base_ring, map, name=None, sparse=False, element_class=None)

Missing doctests:
     * line 191: def __reduce__(self)
     * line 514: def parameter(self)
     * line 567: def is_sparse(self)

Also, documentation does not compile:

sage.rings.polynomial.skew_polynomial_ring.SkewPolynomialRing_general:53: 
WARNING: Block quote ends without a blank line; unexpected unindent.
  • line 872 in skew_polynomial_element.pyx, I think it would be better to return an error message with the exception ValueError.
  • There are some undocumented methods/classes in skew_polynomial_element.pyx (starting at line 2776 with _left_pow).
  • There's still one old style raise statement (l. 494 in skew_polynomial_ring.py).

David

comment:104 Changed 9 months ago by jsrn

  • Branch changed from u/arpitdm/skew_polynomials to u/jsrn/skew_polynomials

comment:105 Changed 9 months ago by jsrn

  • Commit changed from 271bface01f93c8dca5a1fb104da139224ae1e66 to 4a33c5fd34940d28a3824971a4fe4710c04ab2b2

I fixed a minor issue with src/module_list.py.


New commits:

362fff7Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into 13215_skew_polynomials
4a33c5fmv skew_polynomial_element in module_list

comment:106 follow-up: Changed 9 months ago by jsrn

  • Is there any sense to the function make_generic_skew_polynomial? Shouldn't it just be removed? (incidentally, I don't see the sense of sage.rings.polynomial.polynomial_element.make_generic_polynomial either, which presumably was the inspiration to make_generic_skew_polynomial.)
  • You created _leftpow_ and _rightpow_ from __pow__ to avoid the optional argument side. But they are not standard magic functions, so there's no sense in them being underscore-methods. Rather, they should be called something different. E.g power_left_mod and power_right_mod, where modulus is now a mandatory argument.
  • I'm worried about the _inplace_* methods: they are not doc-tested but are also not indirectly used anywhere (except _inplace_pow which is used in _leftpow and _inplace_rmul which is used in _inplace_pow). I only tried to read _inplace_add yet, but already found one bug (duplicate line `x += y[len(x):]`). I would prefer that these methods be removed, possibly reinstated at a later time when they will be used (and hence at least slightly doctested). I believe they were more arduously used in the Karatsuba or factorisation implementations?

Best, Johan

comment:107 in reply to: ↑ 103 Changed 9 months ago by arpitdm

Replying to dlucas:

  • line 892: def is_nilpotent(self)

The is_nilpotent method is not implemented since order of the automorphism is not supported in Sage yet. How about if I remove this method completely and place the note instead in def is_unit? Or should I leave it as it is?

Possibly wrong (function name doesn't occur in doctests):

  • line 3129: cpdef Element _call_with_args(self, x, args=(), kwds={})

There is a cpdef Element _call_(self, x) method that does exactly the same thing as the above method. Do we need to keep both or can we keep the more general _call_with_args and remove _call_?

comment:108 in reply to: ↑ 106 Changed 9 months ago by arpitdm

  • Is there any sense to the function make_generic_skew_polynomial? Shouldn't it just be removed? (incidentally, I don't see the sense of sage.rings.polynomial.polynomial_element.make_generic_polynomial either, which presumably was the inspiration to make_generic_skew_polynomial.)

Yup. I believe that was the inspiration. And I agree. If one wants to make a generic skew polynomial using coefficients, it can be directly done without using this method.

  • I'm worried about the _inplace_* methods: they are not doc-tested but are also not indirectly used anywhere (except _inplace_pow which is used in _leftpow and _inplace_rmul which is used in _inplace_pow). I only tried to read _inplace_add yet, but already found one bug (duplicate line `x += y[len(x):]`). I would prefer that these methods be removed, possibly reinstated at a later time when they will be used (and hence at least slightly doctested). I believe they were more arduously used in the Karatsuba or factorisation implementations?

Yes. They are used in factorizations and center related methods. Which is why it was not possible to add indirect tests for them either. Alright, removing _inplace_add, _inplace_sub and _inplace_rmul.

comment:109 Changed 9 months ago by git

  • Commit changed from 4a33c5fd34940d28a3824971a4fe4710c04ab2b2 to 7134b7e0af8f1764aa8d8d71d2ef7f3a6582bd8f

Branch pushed to git repo; I updated commit sha1. New commits:

a921040Changed unfortunate parameter name
f43767aSome minor doc and error message modifications
7c5c511Modelled SkewPolynomialBaseringInjection more closely on PolynomialBaseringInjection
d6fd904Fix Cython warning
7134b7eRemoved _call_with_args

comment:110 Changed 9 months ago by jsrn

I fixed some other stuff that I came across. Most importantly, I changed the parent type of SkewPolynomialBaseringInjection so that it mimics PolynomialBaseringInjection: I'm not fully understanding the extend of what this means, but if PolynomialBaseringInjection should be a Morphism and not a RingHomomorphism, then I don't see why it should be different for SkewPolynomialBaseringInjection.

I also removed _call_with_args: as the name says, it's there for supporting calling an object that takes more than one argument. This makes sense in the very general PolynomialBaseringInjection as the example in the source shows. But it doesn't (yet) make any sense for skew polynomial rings, so I've removed it for now. If it should ever be useful, someone can add it at that time. For now, it will simply throw a (somewhat meaningful) error when one tries to apply more than one argument to a call to a SkewPolynomialBaseringInjection.

comment:111 Changed 9 months ago by caruso

Many many thanks (to all of you) for all your hard work on this ticket! I really appreciate it and apologize for being silent for such a long time.

I'm looking forward to seeing you soon in SageDays? 75.

comment:112 Changed 9 months ago by arpitdm

  • Branch changed from u/jsrn/skew_polynomials to u/arpitdm/skew_polynomials

comment:113 Changed 9 months ago by arpitdm

  • Commit changed from 7134b7e0af8f1764aa8d8d71d2ef7f3a6582bd8f to dfb6b1db991b198e5616994625726e07a067b56f
  • Status changed from needs_work to needs_review

New commits:

d48fea6fixed documentation errors
fae0483fixed documentation
dfb6b1dremoved unused methods. modified leftpow and rightpow methods.

comment:114 Changed 9 months ago by jsrn

There's a bug in right_lcm. I don't yet know what it is but here is an example which makes it blow up:

k.<a> = GF(3^2,'a')
sigma = k.frobenius_endomorphism()
S.<x> = k['x', sigma]
(x^2 + 1*x + a).right_lcm(x - a)
<BOOM>
NotImplementedError: the leading coefficient is not a unit

Since we're over a field, it must be the ZeroDivisionError causing this, which should never happen.

I also don't see why we should catch the ZeroDivisionError: it is never expected behaviour that V3 is 0?

As an aside, the naming in this and related methods is terrible: R means two very different things in 10 lines, and the skew polynomial variables should not be capitalised.

Best, Johan

comment:115 Changed 9 months ago by caruso

The problem comes from the multiplication by the skew polynomial 0 which does not work as expected (it returns a polynomial of positive degree):

sage: k.<a> = GF(5^2)
sage: S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
sage: zero = S(0)*x
sage: zero.degree()
1
sage: zero + 1
 + 1
Last edited 9 months ago by caruso (previous) (diff)

comment:116 Changed 9 months ago by jsrn

  • Branch changed from u/arpitdm/skew_polynomials to u/jsrn/skew_polynomials

comment:117 Changed 9 months ago by jsrn

  • Commit changed from dfb6b1db991b198e5616994625726e07a067b56f to ca15975841eaa6a05537b626297baf1bcda6d896

Thanks Xavier: it turned out that the problem was even with S(0), which got represented as [0] instead of []. I fixed it now and added a test for posterity.


New commits:

291c28cFixed construct-0 bug
ca15975Fix doctest

comment:118 Changed 9 months ago by git

  • Commit changed from ca15975841eaa6a05537b626297baf1bcda6d896 to ba6a753d47d8158d0c14e129f91d15fb71a64b27

Branch pushed to git repo; I updated commit sha1. New commits:

ba6a753Fix mathematically incorrect doc-string

comment:119 Changed 9 months ago by jsrn

Small doc-string fix in the lcm-functions.

comment:120 follow-up: Changed 9 months ago by jdemeyer

  • Status changed from needs_review to needs_work

Just skimming the code, not a full review...

  1. All this
            if op == 0:
                return x < y
            elif op == 1:
                return x <= y
            elif op == 2:
                return x == y
            elif op == 3:
                return x != y
            elif op == 4:
                return x > y
            else:
                return x >= y
    

can be replaced by return PyObject_RichCompare(x, y, op), see src/sage/structure/coerce.pyx for an example.

  1. Lots of private methods are unused:
        cdef void _inplace_add(self, SkewPolynomial_generic_dense right)
        cdef void _inplace_sub(self, SkewPolynomial_generic_dense right)
        cdef void _inplace_lmul(self, SkewPolynomial_generic_dense right)
        cpdef _leftpow_(self,right,modulus=*)
    

Since these are private, I see no point in implementing them.

  1. The .pxd file contains too much stuff. In particular, the following all seems unused:
    include "cysignals/signals.pxi"
    include "../../ext/cdefs.pxi"
    include '../../ext/stdsage.pxi'
    
    from sage.rings.integer cimport Integer
    from polynomial_compiled cimport CompiledPolynomialFunction
    

Some of this might be needed in .pyx files, but then it should be in the .pyx file. The include statements for cdefs.pxi and stdsage.pxi should be replaced instead by the relevant cimport statements.

  1. Use the standard copyright template from http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files
  1. __getslice__ is deprecated.
  1. __mod__ should use the coercion model (#269).
  1. __floordiv__ should use the coercion model (#2034).
  1. Replace trac #13215 by :trac:`13215`
  1. In several places, you use exact type checks of the form type(x) is foo. Why not isinstance(x, foo)?

comment:121 Changed 9 months ago by jdemeyer

  1. according to the patchbot, the documentation does not build.

comment:122 Changed 9 months ago by dlucas

Hello Jeroen,

  1. according to the patchbot, the documentation does not build.

The patchbot might have used an older version of this ticket, because documentation builds just fine on my side.

David

comment:123 Changed 9 months ago by arpitdm

  • Branch changed from u/jsrn/skew_polynomials to u/arpitdm/skew_polynomials

comment:124 in reply to: ↑ 120 ; follow-up: Changed 9 months ago by arpitdm

  • Commit changed from ba6a753d47d8158d0c14e129f91d15fb71a64b27 to f563aba916b4155a9485c46ebbbdfe3404a2c8f1

Hi Jeroen,

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

Also, as David mentioned, the documentation builds on my system as well. I don't know the patchbot is suggesting otherwise.

Best, Arpit.


New commits:

d48fea6fixed documentation errors
fae0483fixed documentation
dfb6b1dremoved unused methods. modified leftpow and rightpow methods.
2ea89c1merged new updates from remote
5c9f2f3modified richcmp method. removed some inplace methods.
c034df8removed unused private methods and imports
ac109c8converted to standard copyright template
5137ef9removed deprecated method getslice
b1e42c3Merge commit 'aca3398a81b3688e1f2e69c5910b8214d13be925' of git://trac.sagemath.org/sage into skew_polynomials
f563abamod and floordiv modified to use coercion model. replaced type with isinstance.

comment:125 Changed 9 months ago by jdemeyer

  • Dependencies #13214, #13303, #13640, #13641, #13642 deleted

comment:126 Changed 9 months ago by jdemeyer

Just a remark (feel free to change this or not): there is no point in writing cdef list here since you're not using the fact that it's a list:

        cdef list x = (<SkewPolynomial>left)._coeffs
        cdef list y = (<SkewPolynomial>right)._coeffs
        return PyObject_RichCompare(x, y, op)

In general one should avoid such pointless type declarations.

In this case, it doesn't hurt since Cython knows anyway that it's a list (_coeffs is declared to be a list).

comment:127 in reply to: ↑ 124 ; follow-up: Changed 9 months ago by jdemeyer

Replying to arpitdm:

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

You forgot to change the copyright statements. Apart from that, it looks ok.

comment:128 in reply to: ↑ 127 Changed 9 months ago by arpitdm

Replying to jdemeyer:

Replying to arpitdm:

I've made changes to the ticket based on your comments. Please do let me know if I've made a mistake and if there are any other changes I should be making.

You forgot to change the copyright statements. Apart from that, it looks ok.

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

As for the cdef list, I went with the rest of the code on the ticket which declares things similarly at the time. But I can change that.

comment:129 follow-up: Changed 9 months ago by dlucas

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

Actually, there's a template for copyrights in Sage (Jeroen sent you the link yesterday).

The copyright statements in this ticket are like this:

#############################################################################
#    Copyright (C) 2012 Xavier Caruso <xavier.caruso@normalesup.org>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#                  http://www.gnu.org/licenses/
#****************************************************************************

while they should be like this

#*****************************************************************************
#       Copyright (C) 2013 YOUR NAME <your email>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
#                  http://www.gnu.org/licenses/
#*****************************************************************************

David

Last edited 9 months ago by dlucas (previous) (diff)

comment:130 in reply to: ↑ 129 Changed 9 months ago by jsrn

Replying to arpitdm:

By copyright, do you mean add names inside the block too? I added myself and Johan as authors (commit ac109c8)

You misspelled my last name. But I've actually recently changed my name to "Johan Rosenkilde".

Replying to dlucas:

while they should be like this

#*****************************************************************************
#       Copyright (C) 2013 YOUR NAME <your email>

OK, stupid copyright stuff leading to an uncomfortable discussion: I think the copyright name should be retained as Xavier Caruso. Arpit should add his name in the list of AUTHORS as he has done (but he should of course fix the rest of the banner).

Best, Johan

comment:131 Changed 9 months ago by dlucas

OK, stupid copyright stuff leading to an uncomfortable discussion: I think the copyright name should be retained as Xavier Caruso. Arpit should add his name in the list of AUTHORS as he has done (but he should of course fix the rest of the banner).

Yes, I agree.

comment:132 Changed 9 months ago by git

  • Commit changed from f563aba916b4155a9485c46ebbbdfe3404a2c8f1 to 26e46890a9e6dff7f0f6f69ce7a9bf28f88bc3de

Branch pushed to git repo; I updated commit sha1. New commits:

26e4689modified copyright banner

comment:133 Changed 9 months ago by arpitdm

Hello,

I've updated the copyright banner.

@Johan: Sorry for misspelling your name.

I've kept the inplace_pow and inplace_rmul methods because they are being used by power_right_mod and power_left_mod. I'm now opening it for review.

Best, Arpit.

comment:134 Changed 9 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:135 follow-up: Changed 9 months ago by dlucas

  • Status changed from needs_review to needs_work

Hello,

There's still some small issues here:

  • ValueError line 836 in skew_polynomial_element.pyx does not have any error message to explain to the user why this exception was raised.
  • There's one old raise statement l.528 in skew_polynomial_ring.py (raise IndexError, "generator n not defined")
  • Some methods in skew_polynomial_element,pyx are still undocumented. Even if I'm kind of ok with _call_ not having a short description, I'm definitely not fine with a constructor (l. 2945) without any description of its input parameters...

Back to needs_work.

David

comment:136 Changed 9 months ago by git

  • Commit changed from 26e46890a9e6dff7f0f6f69ce7a9bf28f88bc3de to 88196bfd70fca121e6e343a03ff2c3119254a671

Branch pushed to git repo; I updated commit sha1. New commits:

88196bfsome more fixes to the documentation.

comment:137 in reply to: ↑ 135 Changed 9 months ago by arpitdm

  • ValueError line 836 in skew_polynomial_element.pyx does not have any error message to explain to the user why this exception was raised.
  • There's one old raise statement l.528 in skew_polynomial_ring.py (raise IndexError, "generator n not defined")
  • Some methods in skew_polynomial_element,pyx are still undocumented. Even if I'm kind of ok with _call_ not having a short description, I'm definitely not fine with a constructor (l. 2945) without any description of its input parameters...

My apologies for missing out on these. I've made the changes now. Back to needs_review. :)

comment:138 Changed 9 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:139 follow-ups: Changed 9 months ago by dlucas

Hello,

It seems good to me. I just have two remarks:

  • You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).
  • There's a broken doctest:
    File "../rings/polynomial/rings.py", line 744, in sage.rings.polynomial.rings.Rings.ParentMethods.__getitem__
    Failed example:
        k['x',Frob]
    Expected:
        Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by Frobenius Endomorphism x |-> x^5 on Finite Field in t of size 5^3
    Got:
        Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by t |--> t^5
    
    

Apart from that, I'm fine with your changes, tests pass and a lot of work have been done here. Issues found by reviewers have been fixed, and if no one objects, I'll set this to positive_review on the next iteration.

Best,

David

comment:140 in reply to: ↑ 139 ; follow-up: Changed 9 months ago by arpitdm

  • You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).

I looked up online if it was required to write an error message along with ZeroDivisionError since it seems pretty obvious what the error is. It seems, that depending on the situation, this error can mean different things and people write "infinity", "not valid" or simply "division by zero" as an error message after raising the error (python 3 docs). And my thinking behind adding an error message for NotImplementedError is to allow the user to understand the reason behind this not being implemented. Should I remove them?

comment:141 in reply to: ↑ 140 Changed 9 months ago by dlucas

Replying to arpitdm:

  • You wrote error messages for every exception, including ZeroDivisionError and NotImplementedError. IMHO, it's not necessary to write (for instance) ZeroDivisionError("division by zero is not valid"). To be honest, I would have been fine with it... But you wrote ZeroDivisionError: division by zero is not valid which I think is not compatible with Python 3 (not sure though).

I looked up online if it was required to write an error message along with ZeroDivisionError since it seems pretty obvious what the error is. It seems, that depending on the situation, this error can mean different things and people write "infinity", "not valid" or simply "division by zero" as an error message after raising the error (python 3 docs). And my thinking behind adding an error message for NotImplementedError is to allow the user to understand the reason behind this not being implemented. Should I remove them?

Oh, ok I understand. If it is advised in Python documentation, please do not revert what you did :).

David

comment:142 in reply to: ↑ 139 Changed 9 months ago by arpitdm

  • There's a broken doctest:
    File "../rings/polynomial/rings.py", line 744, in sage.rings.polynomial.rings.Rings.ParentMethods.__getitem__
    Failed example:
        k['x',Frob]
    Expected:
        Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by Frobenius Endomorphism x |-> x^5 on Finite Field in t of size 5^3
    Got:
        Skew Polynomial Ring in x over Finite Field in t of size 5^3 twisted by t |--> t^5
    
    

There isn't a rings.py file in sage/rings/polynomial. That was moved to sage/categories and the doctest passes there. Maybe you have some portion of an older version of this ticket?

comment:143 Changed 9 months ago by dlucas

Mmh maybe... But it's weird though because I recompiled 7.3 a few days ago, then made a branch and pulled your branch from #13215. I have the latest version of this ticket on my local branch (commit 88196bf) and there's a file rings.py in rings/polynomial. Even with my clean version of 7.3 as it's available from download (I always keep a clean version of the develop branch), I can find such a file...

Anyway, as git log rings/polynomial/rings.py returns nothing while git log categories/rings.py returns your commits, I probably messed up somewhere.

So, I guess we're good to go now. If no one objects, I'll set this ticket to positive review.

David

comment:144 Changed 9 months ago by dlucas

  • Status changed from needs_review to positive_review

As no one objected, I set this ticket to positive review.

Best,

David

comment:145 follow-ups: Changed 9 months ago by jsrn

  • Status changed from positive_review to needs_work

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

Therefore, it is not clear that the syntax f(a) should mean operator evaluation. Perhaps it should be e.g. f(a, 'operator') etc. or something different. In any case, it demonstrates that this module is maybe not as mature as we had initially assumed.

Best, Johan

comment:146 in reply to: ↑ 145 Changed 9 months ago by arpitdm

Hi,

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

This reminds me of the three approaches to evaluating a skew polynomial we discussed once before. One of them was, given a skew polynomial p and a point a, p(a) = p.right_quo_rem(x-a) (resp. left). Which I believe is what you are referring to? I think we now have the features to support this generalization of the remainder evaluation method in the non-commutative case. Or perhaps, we add an option to the call method. It takes as argument the algorithm "remainder" (or "operator") and default is set to one of them. That way the third approach of using normal basis can also be easily added if need be in the future.

Best, Arpit.

comment:147 in reply to: ↑ 145 Changed 9 months ago by tscrim

  • Milestone changed from sage-7.3 to sage-7.4

Replying to jsrn:

Sorry to object, but I would like to re-insist on adding the experimental decorator on construction of skew polynomials. The reason is that I'm right now talking to a researcher in skew polynomials (Felice Manganiello), and he is making me aware of considerations that might mean some restructuring down the road. In particular, his natural notion of evaluation is *not* operator evaluation, but rather right (resp. left) modulo of x-a.

Therefore, it is not clear that the syntax f(a) should mean operator evaluation. Perhaps it should be e.g. f(a, 'operator') etc. or something different. In any case, it demonstrates that this module is maybe not as mature as we had initially assumed.

The only thing I would agree with being marked experimental in this case would be the evaluation (i.e., __call__), which would be the only thing that would really see this (behavioral) change. I also think we should take the time to get this consistent with the conventions of skew polynomial research. Could you give Felice access to the code to experiment with (in particular, to get feedback on what additional features he would want and bottlenecks)?

comment:148 follow-up: Changed 9 months ago by tscrim

Did anyone look at the compiled documentation? I highly doubt the pdf documentation would build because \base_ring_endomorphism is not valid latex.

Looking more closely, there are also some incorrect statements about the code and many overly verbose statements (e.g., the definition of an automorphism). I'm going over the doc and code now trying to clean things up. However, you currently have an issue in that the skew polynomials themselves do not pickle (which was caught by a TestSuite(S).run() test I'm adding). Feel free to push changes and I can merge them into my branch once this is fixed.

comment:149 Changed 9 months ago by vbraun

PDF docs don't build

comment:150 Changed 9 months ago by dlucas

My mistake, I did not try to compile the pdf documentation, only the html one... I'll check this as well from now on.

David

comment:151 Changed 9 months ago by git

  • Commit changed from 88196bfd70fca121e6e343a03ff2c3119254a671 to eb78e694bde02c73c14aae8fb2238b49ef5bba8a

Branch pushed to git repo; I updated commit sha1. New commits:

eb78e69small fixes to docstrings

comment:152 Changed 9 months ago by tscrim

I often forget to also check that the pdf docs build, but you can usually see bad latex formatting on the html docs IIRC.

Let me also clarify my last comment about pushing, I would prefer pushed changes that fix the pickling. I'm taking care of the docstrings and appreciate not having to deal with trivial merge conflicts.

comment:153 in reply to: ↑ 148 Changed 9 months ago by arpitdm

Replying to tscrim:

Did anyone look at the compiled documentation? I highly doubt the pdf documentation would build because \base_ring_endomorphism is not valid latex.

My mistake too. I did not check for pdf docs. They build now.

Looking more closely, there are also some incorrect statements about the code and many overly verbose statements (e.g., the definition of an automorphism). I'm going over the doc and code now trying to clean things up. However, you currently have an issue in that the skew polynomials themselves do not pickle (which was caught by a TestSuite(S).run() test I'm adding). Feel free to push changes and I can merge them into my branch once this is fixed.

Can you explain a little more about pickling? Or maybe direct me to a link that does?

comment:154 follow-up: Changed 9 months ago by tscrim

Pickling is how Python allows you to save data. In particular, you want

sage: loads(dumps(x)) == x
True

for (essentially) any object x.

comment:155 in reply to: ↑ 154 Changed 9 months ago by arpitdm

Hi,

Pickling is how Python allows you to save data. In particular, you want

sage: loads(dumps(x)) == x
True

for (essentially) any object x.

So I ran some examples and here's what I have so far. When the base ring is a finite field of the form GF(q^m), pickling succeeds, but unpickling does not. Specifically, it fails to recognize or coerce the exponent m as an integer, I think. I tried pickling various other skew polynomials over Integer Ring, Rational Field, etc. and it works just fine. I don't understand where the problem is coming from. Also,

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x', Frob]
sage: loads(dumps(S)) == S
Traceback:
...
ValueError: (ValueError('exponent must be an integer',), <function SkewPolynomialRing at 0x7f02ca186140>, (Finite Field in t of size 5^3, Identity endomorphism of Finite Field in t of size 5^3, 'x', False))

sage: loads(dumps(k)) == k
True
sage: loads(dumps(Frob)) == Frob
False

comment:156 Changed 9 months ago by tscrim

The bigger problem is that a skew polynomial itself does not pickle:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = SkewPolynomialRing(R, sigma)
sage: loads(dumps(x))
---------------------------------------------------------------------------
PicklingError                             Traceback (most recent call last)
...
PicklingError: Can't pickle <type 'dictproxy'>: attribute lookup __builtin__.dictproxy failed

With that being said, the above pickling issue with the Frobenius endomorphism is a separate issue that necessitates a ticket:

sage: loads(dumps(Frob))
Identity endomorphism of Finite Field in t of size 5^3

in addition to this independent issue:

sage: Frob.parent() is Hom(k, k)
True
sage: Hom(k, k)(Frob)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unable to coerce <type 'sage.rings.finite_rings.hom_finite_field_givaro.FrobeniusEndomorphism_givaro'>

comment:157 Changed 9 months ago by arpitdm

Yes. I was able to recreate this error earlier myself. But I figured that the correct pickling of the ring was dependent on the correct pickling of the underlying automorphism and every other attribute for that matter.

How can I resolve these coercion errors? Any pointers would be really helpful. I have no idea where these stem from.

Best, Arpit.

comment:158 Changed 9 months ago by tscrim

Well, the pickling issue doesn't stem from coercion, nor does it have to do with the pickling of the parent (which worked okay). It is likely that you need to implement a __reduce__ method.

The conversion failure of Frob above is likely coming from the generic code for Homset being too strict, but as I said, this is an independent issue.

comment:159 Changed 9 months ago by git

  • Commit changed from eb78e694bde02c73c14aae8fb2238b49ef5bba8a to ec196113af6d216fb1fdeb1896eca677213d0510

Branch pushed to git repo; I updated commit sha1. New commits:

ec19611added a reduce method to support pickling and unpickling of skew polynomials

comment:160 Changed 9 months ago by arpitdm

I've added a __reduce__ method that pickles and unpickles a skew polynomial and a skew polynomial ring over a non-finite base ring correctly now. The error in the earlier example you mentioned is now resolved. However, the problem with the finite fields case persists. I haven't managed to swat that bug away yet. Any ideas on what is causing that?

comment:161 Changed 9 months ago by tscrim

The (un)pickling of the Frobenius (well, perhaps its base class) is not setting the _power correctly:

sage: Frob.power()
1
sage: loads(dumps(Frob)).power()
0

The solution is probably to make the __reduce__ less generic. This will need to be a separate ticket (which we don't have to make as a dependency of this one).

comment:162 follow-up: Changed 9 months ago by jsrn

About the experimental warning: @arpitdm: yes, what you describe is exactly the other evaluation notions, so it is not complicated to implement them - it is only a matter of discussing interface. For progressing with our GSoC, I strongly prefer to take that discussion in a follow-up ticket (e.g. during SD75) and just mark skew polynomials with the experimental warning.

@tscrim: Marking *only* __call__ is certainly an option, and will be less disconcerting to users who wants to take skew polynomials into use soon, and I am also sort of OK with this. However, I prefer to mark the entire module as experimental: this __call__ issue might just be the first example of other similar conventions. Felice has already asked for a trac account and will look at the functionality when he has time. But in the interest of being able to continue with our other goals, I would strongly prefer to get this major ticket closed before we are sure everything has converged, and the point of the experimental decorator is exactly to be able to do that.

Best, Johan

comment:163 Changed 9 months ago by jsrn

  • Branch changed from u/arpitdm/skew_polynomials to u/jsrn/skew_polynomials

comment:164 Changed 9 months ago by jsrn

  • Commit changed from ec196113af6d216fb1fdeb1896eca677213d0510 to f78efb1e18976aefa66f3a1937e92d9c571c4293

I renamed power_left_mod to left_power_mod similarly for right. I suggested the old names myself, but realised that it's much better if all such sided operations begin with left/right (and all the other sided operations already do).

Best, Johan


New commits:

15ac350Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into 13215_skew_polynomials
f78efb1power_left/right_mod -> left/right_power_mod

comment:165 in reply to: ↑ 162 Changed 9 months ago by arpitdm

Replying to jsrn:

About the experimental warning: @arpitdm: yes, what you describe is exactly the other evaluation notions, so it is not complicated to implement them - it is only a matter of discussing interface. For progressing with our GSoC, I strongly prefer to take that discussion in a follow-up ticket (e.g. during SD75) and just mark skew polynomials with the experimental warning.

Agreed. We can keep that for SD75.

@tscrim: Marking *only* __call__ is certainly an option, and will be less disconcerting to users who wants to take skew polynomials into use soon, and I am also sort of OK with this. However, I prefer to mark the entire module as experimental: this __call__ issue might just be the first example of other similar conventions. Felice has already asked for a trac account and will look at the functionality when he has time. But in the interest of being able to continue with our other goals, I would strongly prefer to get this major ticket closed before we are sure everything has converged, and the point of the experimental decorator is exactly to be able to do that.

If we are placing the experimental decorator, which I think we should, I second placing it over the entire skew polynomial ticket. Because call is not the only one that will be changed. Derivations are missing. Anyone who is working on skew polynomial research will probably point that out immediately. And there could be a bunch of changes to accommodate that.

comment:166 follow-up: Changed 9 months ago by tscrim

  • Branch changed from u/jsrn/skew_polynomials to public/rings/skew_polynomials-13215
  • Commit changed from f78efb1e18976aefa66f3a1937e92d9c571c4293 to 92ae069efadad32431ebd83ffa6dd42ccb291b4e

I've gone through and made some cleanup to the documentation and code. I've made the SkewPolynomial actually behave like an ABC that can be subclassed to sparse skew polynomials (mainly, removed the _coeffs attribute).

I strongly disagree with marking the entire class with @experimental. For example, all of the changes I did would not require any deprecation, i.e., the public API and behavior was unchanged. If you know you must change the API/behavior to accommodate something, then this code has no business being in Sage and you should just go ahead and do it. If the behavior could undergo (radical) changes, then the code isn't (IMO) correct and should not be included.

(Personally, I see very little use-cases for @experimental and no real use at the top-level. People who will actually experiment with the code will be those who can just get the code from the trac server (which requires no login). By marking something at the top-level, nobody will really use the code because there are no guarantees.)


New commits:

11fc028Merge branch 'u/arpitdm/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
c2bfcd7Merge branch 'u/arpitdm/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
225a66aInitial round of docstring and code fixing.
05587a9Merge branch 'u/jsrn/skew_polynomials' of trac.sagemath.org:sage into public/rings/skew_polynomials-13215
92ae069Moving things around so the ABC actually is the ABC for univariate skew polynomials.

comment:167 Changed 9 months ago by tscrim

  • Status changed from needs_work to needs_review

comment:168 in reply to: ↑ 166 Changed 9 months ago by jsrn

Hi Travis,

Replying to tscrim:

I've gone through and made some cleanup to the documentation and code. I've made the SkewPolynomial actually behave like an ABC that can be subclassed to sparse skew polynomials (mainly, removed the _coeffs attribute).

Great!

I strongly disagree with marking the entire class with @experimental. For example, all of the changes I did would not require any deprecation, i.e., the public API and behavior was unchanged. If you know you must change the API/behavior to accommodate something, then this code has no business being in Sage and you should just go ahead and do it. If the behavior could undergo (radical) changes, then the code isn't (IMO) correct and should not be included.

(Personally, I see very little use-cases for @experimental and no real use at the top-level. People who will actually experiment with the code will be those who can just get the code from the trac server (which requires no login). By marking something at the top-level, nobody will really use the code because there are no guarantees.)

I see we disagree on the @experimental decorator itself. It is a "local beta", in that it says: "you can count on this functionality being in Sage soon in roughly the same shape. If you want to use it already, be prepared that the API might change mildly". It facilitates Request-for-comments from developers who believe they have well-designed some module, but acknowledge that they might not have considered everything. This goes doubly for math code, since any given math structure can be considered from so many angles, and usually the initial developer considers mostly just one. It allows building other new stuff on top of it (which we really need now: #20970), which postponing the ticket wouldn't, and that new stuff might not need an @experimental warning itself (for #20970, skew polynomials is just a tool, and its exact API has roughly no bearing on the API of the Gabidulin codes).

The decorator was originally suggested because without it, it is difficult to start introducing the "basic" modules on a new set of functionality, since one can only really judge its design once many things have been developed on top of it. This happened for us in coding theory, where we felt forced to have our own fork of Sage and develop for nine months before making the first pushes to Sage, greatly complicating the development process.

See also the discussion here: https://groups.google.com/forum/#!topic/sage-devel/LXWs6KOw0Lk. This ticket is exactly one of the intended use cases for this decorator.

I still insist on the module-wide experimental warning here. I expect I will be active in polishing the skew polynomial module in the coming months, and I really don't want to be burdened/limited by deprecation considerations all the time. On the other hand, we really need this ticket to go into Sage to proceed with the GSoC, and at least >95% of the current functionality and API is good.

comment:169 follow-up: Changed 9 months ago by tscrim

From the discussion above, there are suggestions of major behavioral and API changes, not mild. While this is not the hill I necessarily want to die on, I do have a use-case for this code. By saying the module is "subject to change without notice" means I can't build upon it because it could break all of my code, as well as yours for #20970. You say you only need this as a tool, but suppose #20970 is merged before this is stable and then you force whomever has to make changes to this code to also fix your code (which defeats the entire point) or your code gets broken if it is something not doctested.

You also seem stuck on the idea the code has to be merged in order to proceed with GSoC. You can build other code on top of this, and this doesn't need to be merged by the end of the program for the GSoC to be considered successful (granted, it took a little too long for the knot theory GSoC code to get merged).

Additionally, if 95% of the code is set, then mark the 5% with @experimental if you think it is that likely to change. If you disagree, then I am forced to disagree with your assessment of the completeness of the code. As a reminder, internal changes do not need to be deprecated (for example, none of the changes I pushed would not require one).

comment:170 Changed 9 months ago by tscrim

If you feel we are at an impasse, then we can ask on sage-devel.

comment:171 in reply to: ↑ 169 Changed 9 months ago by jsrn

Replying to tscrim:

From the discussion above, there are suggestions of major behavioral and API changes, not mild.

I don't consider the __call__ discussion a major change. My current idea for accommodating multiple notions of evaluation would be to throw a warning/error when __call__ is used before "setting" the default evaluation on the skew polynomial ring in question. That's a completely local change (local to __call__. But as I mentioned, I prefer to postpone that discussion to a later ticket.

While this is not the hill I necessarily want to die on, I do have a use-case for this code. By saying the module is "subject to change without notice" means I can't build upon it because it could break all of my code, as well as yours for #20970. You say you only need this as a tool, but suppose #20970 is merged before this is stable and then you force whomever has to make changes to this code to also fix your code (which defeats the entire point) or your code gets broken if it is something not doctested.

As I said, I imagine that it would be an overlapping set of developers (at least me) who would improve skew polynomials in the forseeable future, as well as use it before it was "stable", in e.g. #20970. This is, once again, what I would regard the common use-case of @experimental (whoever adds some feature usually needs it him/herself).

If you want to build upon this code yourself, I also don't understand your stance: not having @experimental means that any near-future sensible change to this module's API will be clumsy to accommodate. If you have made use of this module in the mean-time, either included in Sage or not, there's two possible outcomes: the improvement is not done, or it is done and your code will start spewing warnings. I don't see how either outcomes are better than what would happen with the @experimental warning on.

You also seem stuck on the idea the code has to be merged in order to proceed with GSoC. You can build other code on top of this, and this doesn't need to be merged by the end of the program for the GSoC to be considered successful (granted, it took a little too long for the knot theory GSoC code to get merged).

You know how it is: unmerged code just has a much larger probability of rotting on trac or ending up causing a huge workload for the mentors/other interessants of the project. We already have a queue of 4 tickets waiting for this one, and I really want to pop most of them before GSoC runs out!

Additionally, if 95% of the code is set, then mark the 5% with @experimental if you think it is that likely to change.

But I don't *know* what could change! It's my assessment that this is pretty close to stable, and Xavier, Arpit, David, Burcin, you, and me have thought things pretty well through. But it *is* a large, new structure to Sage.

If you disagree, then I am forced to disagree with your assessment of the completeness of the code. As a reminder, internal changes do not need to be deprecated (for example, none of the changes I pushed would not require one).

I am somewhat shocked at how vehemently you are against the @experimental decorator. Discussion on sage-devel it is, I guess...

comment:173 follow-up: Changed 8 months ago by jsrn

The discussion on sage-devel seems to have tapered off, so we need to take a decision here. We got two pieces of input: leif suggested a compromise with a warning in the doc, and wstein seemed to favour something like not pre-importing the module until the module is deemed "stable".

IMHO, neither of the two shared your concerns of not being able to build upon the module, and seemed OK with the idea of accepting not-completely-stable code into Sage. Conversely, they apparently didn't really like @experimental in the current form either.

I like both of the alternative suggestions less than just including the module and defining it as stable, handling any possible deprecation warnings that might arise in the near future. However, I still claim that using @experimental on the module is the right way to go.

But in the interest of progressing, I leave it to you Travis: if you are still strongly against a module-level @experimental, let's drop it. I guess you are still OK with having @experimental on call, together with a sensible message in the doc, e.g.

    WARNING::

        Currently only "operator evaluation" of skew polynomials is implemented. There are two other common notions of evaluation of `f(x)` at some `a` from the base ring, namely the remainder after left or right modulo by `x-a`. The current calling convention might change in the future to accommodate these.

Best, Johan

comment:174 in reply to: ↑ 173 Changed 8 months ago by tscrim

Replying to jsrn:

But in the interest of progressing, I leave it to you Travis: if you are still strongly against a module-level @experimental, let's drop it. I guess you are still OK with having @experimental on call, together with a sensible message in the doc, e.g.

    WARNING::

        Currently only "operator evaluation" of skew polynomials is implemented.
        There are two other common notions of evaluation of `f(x)` at some `a`
        from the base ring, namely the remainder after left or right modulo by `x-a`.
        The current calling convention might change in the future to accommodate these.

I still strongly am against a module-level @experimental, but I think this is a good compromise. Positive review on my part once this is done. Thank you for your input and work on this!

comment:175 Changed 8 months ago by chapoton

from the patchbot:

+inside file:  b/src/sage/rings/polynomial/skew_polynomial_ring_constructor.py
+@@ -0,0 +1,207 @@
++            ....:     print S
+python2-only print syntax inserted on 1 non-empty lines
+Traceback (most recent call last):
+  File "/nfs4/home6/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/patchbot.py", line 1053, in test_a_ticket
+    baseline=baseline, **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 368, in oldstyle_print
+    msg="python2-only print syntax", **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 214, in exclude_new
+    raise ValueError(full_msg)
+ValueError: python2-only print syntax inserted on 1 non-empty lines
+inside file:  b/src/sage/rings/polynomial/skew_polynomial_element.pyx
+@@ -0,0 +1,3019 @@
++        INPUT::
+inside file:  b/src/sage/rings/polynomial/skew_polynomial_ring.py
+@@ -0,0 +1,732 @@
++        INPUT::
+Bad Input/Output blocks inserted on 2 non-empty lines
+Traceback (most recent call last):
+  File "/nfs4/home6/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/patchbot.py", line 1053, in test_a_ticket
+    baseline=baseline, **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 352, in input_output_block
+    msg="Bad Input/Output blocks", **kwds)
+  File "/usr/labri/vdelecro/.local/lib/python2.7/site-packages/sage_patchbot/plugins.py", line 214, in exclude_new
+    raise ValueError(full_msg)
+ValueError: Bad Input/Output blocks inserted on 2 non-empty lines

comment:176 Changed 8 months ago by dlucas

Oh, you managed to get some feedback from the patchbot? I was actually slightly worried about the Python 2 only syntax, but I do not know any efficient way to test for this locally...

David

comment:177 follow-up: Changed 8 months ago by arpitdm

Based on the conclusions reached above, I tried adding the experimental warning to the call method. And I get an error message while building Sage that seems to that it is not possible to add the experimental decorator at all.

Error compiling Cython file:
------------------------------------------------------------
...
        else:
            n = self._new_c([],P)
        return n

    @experimental(trac_number=13215)
    def __call__(self, eval_pt):
   ^
------------------------------------------------------------

sage/rings/polynomial/skew_polynomial_element.pyx:336:4: special functions of cdef classes cannot have decorators

Is there an alternate way to add the experimental warning?

comment:178 Changed 8 months ago by git

  • Commit changed from 92ae069efadad32431ebd83ffa6dd42ccb291b4e to 4b863456690dd1bc167fcad1621878ca0771abd3

Branch pushed to git repo; I updated commit sha1. New commits:

4b86345fixed INPUT/OUTPUT syntax in docs. updated print statement to python3 syntax

comment:179 Changed 8 months ago by arpitdm

I think I've managed to rectify the patchbot errors. How can I check if there are further patchbot errors?

comment:180 Changed 8 months ago by chapoton

Patchbots should soon come back. Then you have to wait for one of them to look at your ticket. Or run your own patchbot.

comment:181 in reply to: ↑ 177 Changed 8 months ago by jsrn

Replying to arpitdm:

Based on the conclusions reached above, I tried adding the experimental warning to the call method. And I get an error message while building Sage that seems to that it is not possible to add the experimental decorator at all.

Ah ok, that's a snag. Have you tried looking up the source code for @experimental in sage/misc/superseded.py? You should be able to just print the warning manually as the first line of __call__. Perhaps add a comment mentioning this emulates @experimental such that it can be found if one greps "@experimental".

Best, Johan

comment:182 Changed 8 months ago by tscrim

That's right, it's a Cython issue because double-underscore methods need to be assigned to slots at compile time (or at least be handled in a special way), so decorators don't work on them. I agree with comment:181, just issue the warning yourself.

comment:183 Changed 8 months ago by git

  • Commit changed from 4b863456690dd1bc167fcad1621878ca0771abd3 to 8553b9349afd40e5ae5d5a26811826b6a647ec5d

Branch pushed to git repo; I updated commit sha1. New commits:

8553b93added a manual experimental warning to the '__call__' method

comment:184 Changed 8 months ago by arpitdm

Hello,

I've added the experimental warning to the __call__ method manually based on the source code for experimental as suggested by @jsrn. There are a couple of doctests that "fail" because they issue the experimental warning before returning the correct answer. Should I modify the doctests or keep them as it is?

Best, Arpit.

comment:185 Changed 8 months ago by tscrim

You need to make sure all doctests pass, so you need to include the warning in the doctest output.

Last edited 8 months ago by tscrim (previous) (diff)

comment:186 Changed 8 months ago by dlucas

As warnings are issued only once per session, you can fix this by triggering the experimental warning in a specific "doctest" at the top of the file. See what have been done in rings/asymptotic/asymptotic_ring.py for instance.

comment:187 Changed 8 months ago by git

  • Commit changed from 8553b9349afd40e5ae5d5a26811826b6a647ec5d to 137b58b1a96e9c4830a057b62a8a432bb7bb773f

Branch pushed to git repo; I updated commit sha1. New commits:

137b58bfixed small doctest errors

comment:188 Changed 8 months ago by arpitdm

  • Status changed from needs_review to needs_work

Done. Fixed! I'm opening it for review.

comment:189 Changed 8 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:190 Changed 8 months ago by jsrn

Is there a reason you didn't add a single doctest at the top for triggering the warning, as David suggested?

comment:191 follow-ups: Changed 8 months ago by tscrim

  • Status changed from needs_review to needs_work

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

@arpitdm If you are going to do a redirection, which is good for if evaluation does change provided you give it a more descriptive name (and include it as part of the public API), I believe you can just mark the (Python) function with the decorator without problem (as it is no longer a special method).

comment:192 in reply to: ↑ 191 Changed 8 months ago by dlucas

Replying to tscrim:

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

Is that a recent behaviour? Because triggering the experimental warning once works just fine in the file I referenced above. I also used this myself in #20284 and it also worked perfectly.

comment:193 in reply to: ↑ 191 Changed 8 months ago by jsrn

Replying to tscrim:

@jsm @dlucas Warnings for doctests are handled different than in a session. For deprecation warnings, these are done every time the deprecation message is hit, and I believe that behavior extends to all warnings.

As David, I have my doubts about this too...

@arpitdm If you are going to do a redirection, which is good for if evaluation does change provided you give it a more descriptive name (and include it as part of the public API), I believe you can just mark the (Python) function with the decorator without problem (as it is no longer a special method).

Agree, since you did an indirection anyway. operator_eval is a more descriptive name. Then the two others that we might add later on could be left_mod_eval and right_mod_eval; not too long, uses very common abbreviations, and all follow the same style.

comment:194 Changed 8 months ago by tscrim

It's also quite possible that classes and methods/functions are handled differently by the decorator.

comment:195 Changed 8 months ago by caruso

Here is another issue:

sage: k = GF(5^3)
sage: S.<x> = SkewPolynomialRing(k, k.frobenius_endomorphism())
sage: x.right_quo_rem(Graphics())
...
zsh: segmentation fault (core dumped)  sage

As far as understand, one has to use the decorator @coerce_binop for all binary operations.

comment:196 follow-up: Changed 8 months ago by arpitdm

@tscrim, @jsrn - Just to clarify, there is a __call__ magic function for evaluation of the polynomial which calls an _call function. Are you suggesting that I rename the latter to operator_eval?

@Caruso - What does Graphics()`

comment:197 Changed 8 months ago by caruso

Graphics() is an empty plot. It is not a skew polynomials; that's the point.

comment:198 follow-up: Changed 8 months ago by caruso

Do you really need the __call__ function for this ticket? Otherwise, I would suggest to forget it for now and reintroduce it only when needed.

comment:199 in reply to: ↑ 196 Changed 8 months ago by jsrn

Replying to arpitdm:

@tscrim, @jsrn - Just to clarify, there is a __call__ magic function for evaluation of the polynomial which calls an _call function. Are you suggesting that I rename the latter to operator_eval?

Yes.

comment:200 in reply to: ↑ 198 Changed 8 months ago by jsrn

Replying to caruso:

Do you really need the __call__ function for this ticket? Otherwise, I would suggest to forget it for now and reintroduce it only when needed.

We need it for Gabidulin codes (for which we need #21131)

comment:201 Changed 8 months ago by git

  • Commit changed from 137b58b1a96e9c4830a057b62a8a432bb7bb773f to 2d4a1409011f4dda2bb0bbd2d0c8970e9824dafb

Branch pushed to git repo; I updated commit sha1. New commits:

cf14817Merge branch 'public/rings/skew_polynomials-13215' of git://trac.sagemath.org/sage into skew_polynomials
2d4a140triggered experimental warning at the top of the session

comment:202 Changed 8 months ago by arpitdm

A helper function def _call has been added that acts as a helper function to accommodate for operator evaluation. The def operator_eval is available as a public method. And the experimental warning is triggered at the top of the module. The segmentation fault due to Graphics() for def right_quo_rem (resp. left) have been resolved.

comment:203 Changed 8 months ago by git

  • Commit changed from 2d4a1409011f4dda2bb0bbd2d0c8970e9824dafb to 5dcea53ec25b2cc19873230ce697ec3720d95238

Branch pushed to git repo; I updated commit sha1. New commits:

5dcea53adding coerce_binop decorator to relevant methods

comment:204 Changed 8 months ago by arpitdm

The coerce_binop decorator is added to the relevant methods to resolve the remaining segmentation fault methods.

comment:205 Changed 8 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:206 follow-up: Changed 8 months ago by tscrim

  • Status changed from needs_review to needs_work
  • You need to change the docstring of _call to reflect that its existence is only because of @experimental:
    Helper function for the ``__call__`` method to accommodate
    the ``@experimental`` decorator.
    
  • I think you should make operator_eval into a cpdef method as it will likely be an important method (and should have a C version). You also need to change
    -(<RingElement> c)*a
    +c * a
    
    so the skew polynomial ring can support non-RingElement classes as a coefficients and to avoid an unneeded type check by Cython.
  • You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.
  • Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

comment:207 in reply to: ↑ 206 ; follow-up: Changed 8 months ago by jsrn

Replying to tscrim:

  • You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.

Seems like the gain would currently be very small, since these methods now mostly do not call each other internally. If this changes later on, the private method can be added at this time.

  • Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

Usual commutative polynomials have a monic method. This is the analogue for non-commutative polynomials.

Best, Johan

comment:208 in reply to: ↑ 207 ; follow-ups: Changed 8 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

  • You have added extra coercion checks for each step of things like left_xgcd. I feel that you would be better having a public method that does @coerce_binop and then private (cdef?) functions that assume both elements belong to the same parent. If you don't think this is so important, than don't feel compelled to change it.

Seems like the gain would currently be very small, since these methods now mostly do not call each other internally. If this changes later on, the private method can be added at this time.

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

  • Are the *_monic methods useful to have at the public namespace (instead of (effectively hidden) cdef methods)? I feel one can just divide by the leading coefficient and that this operation will not be called frequently by a user.

Usual commutative polynomials have a monic method. This is the analogue for non-commutative polynomials.

Only for univariate, and in that case all it does is divide by the leading coefficient. However, in that case it extends the base ring so the leading coefficient is a unit, which is different than the behavior here. Also, I don't necessarily see the point of having monic in the public API for commutative polynomials (and don't take that as a guide for what must/should be included in the API).

comment:209 Changed 8 months ago by git

  • Commit changed from 5dcea53ec25b2cc19873230ce697ec3720d95238 to 8c283a85ca2c04b1598ce6efaa8768939a59283b

Branch pushed to git repo; I updated commit sha1. New commits:

8c283a8made operator_eval a cpdef method. small fix to the operator_eval method.

comment:210 in reply to: ↑ 208 Changed 8 months ago by jsrn

Replying to tscrim:

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

It's mostly the relative gain that's important, which is still low as long as the functions don't call each other a lot.

Only for univariate, and in that case all it does is divide by the leading coefficient. However, in that case it extends the base ring so the leading coefficient is a unit, which is different than the behavior here. Also, I don't necessarily see the point of having monic in the public API for commutative polynomials (and don't take that as a guide for what must/should be included in the API).

I think it's a handy helper function that I think people will expect. I've used monic for univariate polynomials many times. (for multivariate polynomials, it's much more ambiguous what can be meant so the helper function is less useful).

comment:211 in reply to: ↑ 208 Changed 8 months ago by caruso

Replying to tscrim:

However this feels it could be used in tight loops, and so while individual calls are marginal, the net sum over 10000 loops can add up. I leave it up to you.

Maybe, we can leave as it currently is for this ticket and come back to this in ticket #21088 where inplace fast functions are designed.

comment:212 in reply to: ↑ 208 Changed 8 months ago by arpitdm

I've made the operator_eval method a cpdef method. And I've edited the docstring to mention that it is a helper function to accommodate the @experimentaldecorator.

Best, Arpit.

comment:213 Changed 8 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:214 Changed 8 months ago by tscrim

I am okay with the current state. Any other objections?

comment:215 Changed 8 months ago by git

  • Commit changed from 8c283a85ca2c04b1598ce6efaa8768939a59283b to 1f441357f62c17e394431028166f01adc3012c37

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

b9d1ecdFixed some of the doctests I just broke
6efcd02more doc
8a991b7more doc
69e3398Evaluation outside the base ring is *not* possible
472193bimprove __call__ doc
4300204More various doc
36cc788Rephrase the same phrase repeated many times
dd8b275More doc string fixes
47ba6f0There should not be a mod, but rather left_mod and right_mod
1f44135Doc fixes for the last methods

comment:216 Changed 8 months ago by jsrn

I went through all docs a last time, polishing many docs and also modifying a few tests and even an implementation or two. Please review.

Best, Johan

comment:217 follow-up: Changed 8 months ago by tscrim

I disagree with the following:

  • This is probably not true:
          - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
            should be normalized to be monic. This parameter must be passed as a
            named argument.
    
    At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.
  • This change make it seem like there is one unique skew polynomial ring (to rule them all :P).
    -    Return the globally unique skew polynomial ring with given
    -    properties and variable name or names.
    +    Return the globally unique skew polynomial ring.
    
  • The part about the general case not being implemented should be in a .. NOTE:: or .. WARNING:: block:
             r"""
             Return ``True`` if this skew polynomial is a unit.
     
    -        .. NOTE::
    +        When the base ring `R` is an integral domain, then a skew polynomial `f`
    +        is a unit if and only if degree of `f` is `0` and `f` is then a unit in
    +        `R`.
     
    -            When the base ring `R` is an integral domain, then a skew
    -            polynomial `f` is a unit if and only if degree of `f` is
    -            `0` and `f` is then a unit in `R`. The general case is not
    -            yet implemented.
    +        The case when `R` is not an integral domain is not yet implemented.
     
             EXAMPLES::
    
  • You should revert this change so we keep it under 80 characters/line:
                 else:
                     return False
             else:
    -            raise NotImplementedError("support for determining if skew polynomial"
    -                                      " is a unit is not available when the base"
    -                                      " ring of the parent skew polynomial"
    -                                      " ring is not an integral domain")
    +            raise NotImplementedError("is_unit is not implemented for skew polynomial rings over base rings which are not integral domains.")
     
         def is_nilpotent(self):
             r"""
    
  • You should not break :trac:`13215` across multiple lines (I might just be paranoid for this one though).
  • AFAIK, only operator evaluation is implemented, so I don't understand this removal:
             .. NOTE::
     
    -            Currently, only "operator evaluation" of skew polynomials is implemented
    -            (see :meth:`.operator_eval`).
                 There are two other common notions of evaluation of `f(x)` at some element `a`
                 from the base ring, namely the remainder after left or right modulo by `x-a`.
    
  • `__call__` is not latex, it should be :meth:`__call__` (or ``__call__``).

Otherwise all your changes look good to me.

comment:218 Changed 8 months ago by git

  • Commit changed from 1f441357f62c17e394431028166f01adc3012c37 to ef7fbe02c45e876bf17e54e4467db815ca0be428

Branch pushed to git repo; I updated commit sha1. New commits:

8ae28e0monic can be passed as unnamed. And rm *-args from left_xgcd
ef7fbe0Fix reviewer's other comments

comment:219 in reply to: ↑ 217 ; follow-up: Changed 8 months ago by jsrn

Thanks for carefully going through all the modifications.

Replying to tscrim:

  • This is probably not true:
          - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
            should be normalized to be monic. This parameter must be passed as a
            named argument.
    
    At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.

Indeed. I've chatted with Xavier, and the original reason for the "This parameter must be passed as named argument" (and perhaps the * in left_xgcd) is the broken behaviour of coerce_binop. This has now been fixed, see #21322. Therefore I've now set the doc and the code to what it should be as soon as #21322 is merged.

  • This change make it seem like there is one unique skew polynomial ring (to rule them all :P).

OK, that change was a bit fast ;-)

  • The part about the general case not being implemented should be in a .. NOTE:: or .. WARNING:: block:

I found this overkill, which is why I removed it. But if you insist.

  • You should revert this change so we keep it under 80 characters/line:

I disagree. It makes the source code look terrible. Also:

$ grep  '.\{80,\}' -r src/sage | grep "raise" | wc -l 
4703

So the 80 chars/line is defacto not a convention upheld in raise-statements.

  • You should not break :trac:`13215` across multiple lines (I might just be paranoid for this one though).

Indeed. Emacs reflow doesn't understand Sphinx magic syntax probably doesn't allow line breaks :-)

  • AFAIK, only operator evaluation is implemented, so I don't understand this removal:
             .. NOTE::
     
    -            Currently, only "operator evaluation" of skew polynomials is implemented
    -            (see :meth:`.operator_eval`).
                 There are two other common notions of evaluation of `f(x)` at some element `a`
                 from the base ring, namely the remainder after left or right modulo by `x-a`.
    

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

  • `__call__` is not latex, it should be :meth:`__call__` (or ``__call__``).

Indeed.

Otherwise all your changes look good to me.

Great!

comment:220 Changed 8 months ago by caruso

Another remark: Should we define the methods left_quo and right_quo as well? And create aliases left_rem and right_rem for left_mod and right_mod respectively?

comment:221 in reply to: ↑ 219 ; follow-up: Changed 8 months ago by tscrim

Replying to jsrn:

Thanks for carefully going through all the modifications.

Thank you for your work on this (and dealing with my griping).

Replying to tscrim:

  • This is probably not true:
          - ``monic`` -- boolean (default: ``True``). Return whether the right gcd
            should be normalized to be monic. This parameter must be passed as a
            named argument.
    
    At least I don't see a reason why must go monic=True as an argument (for everything but left_xgcd). Actually, I don't see why left_xgcd has unlimited number of arguments but right_xgcd does not.

Indeed. I've chatted with Xavier, and the original reason for the "This parameter must be passed as named argument" (and perhaps the * in left_xgcd) is the broken behaviour of coerce_binop. This has now been fixed, see #21322. Therefore I've now set the doc and the code to what it should be as soon as #21322 is merged.

Does #21322 need to be a dependency of this ticket then?

  • You should revert this change so we keep it under 80 characters/line:

I disagree. It makes the source code look terrible. Also:

$ grep  '.\{80,\}' -r src/sage | grep "raise" | wc -l 
4703

So the 80 chars/line is defacto not a convention upheld in raise-statements.

It makes the source code look fine if you are using < ~160 chars wide editors. We do try to stick to ~80 character lines overall in the code, but it is not absolute. Plus, there is a big difference between 90 chars and ~160 chars. IMO, a more fair comparison would be to look at how many raise statements are 80,90,100,100+ lines. I do not see the gain for the long line unless you have an editor with a very large character line limit (literally).

  • AFAIK, only operator evaluation is implemented, so I don't understand this removal:
             .. NOTE::
     
    -            Currently, only "operator evaluation" of skew polynomials is implemented
    -            (see :meth:`.operator_eval`).
                 There are two other common notions of evaluation of `f(x)` at some element `a`
                 from the base ring, namely the remainder after left or right modulo by `x-a`.
    

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

comment:222 Changed 8 months ago by git

  • Commit changed from ef7fbe02c45e876bf17e54e4467db815ca0be428 to 81b8fb8c2b1f4430388e27e3028422caeb28d0a9

Branch pushed to git repo; I updated commit sha1. New commits:

a649c67fixes to the documentation
f54e80eremoved method reverse
1336c57small fixes to the documentation
81b8fb8small fixes to the ring_constructor file

comment:223 Changed 8 months ago by arpitdm

I went through the docs once and clarified them in some places where it was not clear/missing and made some small changes to standardize the docs whereever possible.

Based on discussions with @caruso and @jsrn, the def reverse method is inappropriate in that, reversing a skew polynomial actually involves creating a new skew polynomial ring over the inverse twist map. And that requires more consideration since twist map cannot always be inverted in Sage and also perhaps since "dual_ring" or something like that could also be nice to have.

Best, Arpit.

comment:224 Changed 8 months ago by darij

  • Cc darij removed

comment:225 follow-up: Changed 8 months ago by tscrim

Changes like:

@@ -134,7 +134,7 @@ cdef class SkewPolynomial(AlgebraElement):
     where `\sigma` is the base ring automorphism. This is called
     the *operator evaluation* method.
 
-    EXAMPLES:
+    EXAMPLES::
 
     We illustrate some functionalities implemented in this class.
 

are wrong because text follows, not (indented) code. So the last commit should be reverted. Also, I disagree with changing the .. TODO:: block because it is a TODO.

One other thing I just noticed, a better test than if not isinstance(base_ring, ring.CommutativeRing): would be if base_ring not in Rings().Commutative(): as it is a mathematical check, not an implementation check.

It is also okay to have methods that rely on others than can error out in certain cases when implementations are not done yet. Just FYI.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

comment:226 Changed 8 months ago by git

  • Commit changed from 81b8fb8c2b1f4430388e27e3028422caeb28d0a9 to b6e77d2507948d131b48224ef3c217a79f79bb51

Branch pushed to git repo; I updated commit sha1. New commits:

b6e77d2fixed html documentation build errors

comment:227 in reply to: ↑ 225 ; follow-up: Changed 8 months ago by arpitdm

  • EXAMPLES:

+ EXAMPLES:: }}} are wrong because text follows, not (indented) code. So the last commit should be reverted.

I just checked whether the html documentation builds and in this particular case, it did not give an error while in a couple of other places it did.

Also, I disagree with changing the .. TODO:: block because it is a TODO.

Do you mean, changing the name from TODO to NOTE or the description as well?

One other thing I just noticed, a better test than if not isinstance(base_ring, ring.CommutativeRing): would be if base_ring not in Rings().Commutative(): as it is a mathematical check, not an implementation check.

Okay. I will change that.

It is also okay to have methods that rely on others than can error out in certain cases when implementations are not done yet. Just FYI.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

I was just trying to follow the conventions in other files where I saw that r""" is used everywhere. So while, I was going through the code, I figured, it didn't hurt to change it.

comment:228 in reply to: ↑ 227 Changed 8 months ago by tscrim

Replying to arpitdm:

Also, I disagree with changing the .. TODO:: block because it is a TODO.

Do you mean, changing the name from TODO to NOTE or the description as well?

You made a change .. TODO:: -> .. NOTE::, where the message is describing a TODO.

You also did not need to change r""" for every docstring (it doesn't hurt, but it is only necessary when you have escape \ characters).

I was just trying to follow the conventions in other files where I saw that r""" is used everywhere. So while, I was going through the code, I figured, it didn't hurt to change it.

Yes, it's perfectly fine (in some aspects, it should be the standard way we do docstrings in Sage). This was another just FYI and future reference.

comment:229 Changed 8 months ago by git

  • Commit changed from b6e77d2507948d131b48224ef3c217a79f79bb51 to 97ba596ec01b04bc06190bfe7e544f608be03545

Branch pushed to git repo; I updated commit sha1. New commits:

27c05c6improved check on commutativity of base ring
97ba596reverted NOTE back to TODO

comment:230 Changed 8 months ago by git

  • Commit changed from 97ba596ec01b04bc06190bfe7e544f608be03545 to 35fcdf24bfd2824a59c9053662ea5f133e94363e

Branch pushed to git repo; I updated commit sha1. New commits:

92564c5rewrap
35fcdf2Merge branch 'public/rings/skew_polynomials-13215' of trac.sagemath.org:sage into 13215_skew_polynomials

comment:231 in reply to: ↑ 221 ; follow-up: Changed 8 months ago by jsrn

Replying to tscrim:

Does #21322 need to be a dependency of this ticket then?

Not in our opinion: what we do here is the intended behaviour of coerce_binop, and the decorated methods works as well as all other methods in Sage decorated with coerce_binop. So #21322 is just a (already known) bug that should be fixed.

It makes the source code look fine if you are using < ~160 chars wide editors.

??? The line is 141 chars. Also, having a < 160 chars editor doesn't make the old 4-line wrapping look good.

We do try to stick to ~80 character lines overall in the code, but it is not

absolute.

Indeed my point before.

Plus, there is a big difference between 90 chars and ~160 chars. IMO, a more fair comparison would be to look at how many raise statements are 80,90,100,100+ lines. I do not see the gain for the long line unless you have an editor with a very large character line limit (literally).

    $ grep  '.\{100,\}' -r src/sage | grep "raise" | wc -l
    1628

    $ grep  '.\{120,\}' -r src/sage | grep "raise" | wc -l
    588

    $ grep  '.\{140,\}' -r src/sage | grep "raise" | wc -l
    210

Also, btw:

    $ grep  '.\{140,\}' -r src/sage | wc -l
    10459

So it's not like you're not likely to come across a long line in your editor while editing Sage codes.

  • AFAIK, only operator evaluation is implemented, so I don't understand this removal:
             .. NOTE::
     
    -            Currently, only "operator evaluation" of skew polynomials is implemented
    -            (see :meth:`.operator_eval`).
                 There are two other common notions of evaluation of `f(x)` at some element `a`
                 from the base ring, namely the remainder after left or right modulo by `x-a`.
    

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

It says "The current calling convention might change in the future to accommodate these. Therefore, the current method has been marked as experimental.". Try to read the doc-string in its entirety -- it really does say everything.

Best, Johan

comment:232 Changed 8 months ago by jsrn

Oh yeah, forgot to add about the whole wrapping thing: I now pushed a compromise where the line is wrapped in two but takes up 92 chars.

comment:233 Changed 8 months ago by jsrn

  • Keywords sd75 added

comment:234 Changed 8 months ago by arpitdm

This ticket is still open for review. Are there any further objections?

-Arpit.

comment:235 in reply to: ↑ 231 ; follow-up: Changed 8 months ago by tscrim

Replying to jsrn:

Replying to tscrim:

It makes the source code look fine if you are using < ~160 chars wide editors.

??? The line is 141 chars. Also, having a < 160 chars editor doesn't make the old 4-line wrapping look good.

It makes it more consistent and it is a standard way to split long lines of text by PEP8.

We do try to stick to ~80 character lines overall in the code, but it is not

absolute.

Indeed my point before.

I can accept the 92 char lines as a compromise.

Also, btw:

    $ grep  '.\{140,\}' -r src/sage | wc -l
    10459

So it's not like you're not likely to come across a long line in your editor while editing Sage codes.

There are a number of lines that are forced to be long because they are large numbers with no spaces. Plus, I have no idea exactly how many lines of code we have in Sage, but this smells of a fallacy.

  • AFAIK, only operator evaluation is implemented, so I don't understand this removal:
             .. NOTE::
     
    -            Currently, only "operator evaluation" of skew polynomials is implemented
    -            (see :meth:`.operator_eval`).
                 There are two other common notions of evaluation of `f(x)` at some element `a`
                 from the base ring, namely the remainder after left or right modulo by `x-a`.
    

The entirety of the __call__ doc reads better now, IMHO: the first line clearly states that operator evaluation is considered. So the note doesn't need to repeat this.

The key word is "only", and the __call__ doc does not mention this (nor is it anywhere else IIRC).

It says "The current calling convention might change in the future to accommodate these. Therefore, the current method has been marked as experimental.". Try to read the doc-string in its entirety -- it really does say everything.

I very carefully had read it, and no, it does not say everything. It does not say that this is the only type of evaluation currently implemented. I know this is dangerously close to bikeshedding because this is only visible at the code level. Yet, I think it is important to state why we are (currently) doing things this way: there currently is no other option.

comment:236 Changed 8 months ago by git

  • Commit changed from 35fcdf24bfd2824a59c9053662ea5f133e94363e to e72a8cc6627f68c38c2ae84ccd52bfe9c9e10fd5

Branch pushed to git repo; I updated commit sha1. New commits:

e72a8ccreinstate as per reviewer's insistence

comment:237 in reply to: ↑ 235 ; follow-up: Changed 8 months ago by jsrn

Replying to tscrim:

I very carefully had read it, and no, it does not say everything. It does not say that this is the only type of evaluation currently implemented. I know this is dangerously close to bikeshedding because this is only visible at the code level. Yet, I think it is important to state why we are (currently) doing things this way: there currently is no other option.

Bikeshedding indeed...

comment:238 in reply to: ↑ 237 Changed 8 months ago by jsrn

Replying to jsrn:

Bikeshedding indeed...

Sorry for this grumbling. I shouldn't reply to comments before my morning coffee.

Anyway, it seems the issues are getting exponentially less important, so perhaps we can positive review this ticket soon. Best, Johan

comment:239 Changed 8 months ago by tscrim

  • Status changed from needs_review to positive_review

Sorry I have a bit of a stick up my @$* about this, but I'd like to get this right. So we don't have to deal with issues because someone came along and changed things due to a lack of documentation.

Anyways, I believe we are at a positive review.

comment:240 Changed 8 months ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs fail

[docpdf] LaTeX Warning: Hyper reference `sage/rings/polynomial/skew_polynomial_element:s
[docpdf] age.rings.polynomial.skew_polynomial_element.SkewPolynomialBaseringInjection' o
[docpdf] n page 471 undefined on input line 39011.
[docpdf] 
[docpdf] ! Missing { inserted.
[docpdf] <to be read again> 
[docpdf]                    _
[docpdf] l.39015 The current semantics of \(__
[docpdf]                                      call__\) are experimental, so a warning...
[docpdf] 
[docpdf] ? 
[docpdf] ! Emergency stop.
[docpdf] <to be read again> 
[docpdf]                    _
[docpdf] l.39015 The current semantics of \(__
[docpdf]                                      call__\) are experimental, so a warning...
[docpdf] 
[docpdf] !  ==> Fatal error occurred, no output PDF file produced!
[docpdf] Transcript written on polynomial_rings.log.

comment:241 Changed 8 months ago by git

  • Commit changed from e72a8cc6627f68c38c2ae84ccd52bfe9c9e10fd5 to 204be6593bf4ec184c87292f96eeba22c3038087

Branch pushed to git repo; I updated commit sha1. New commits:

204be65fix doc building error

comment:242 Changed 8 months ago by tscrim

  • Status changed from needs_work to positive_review

I'm assuming that you wanted this back to needs review.

comment:243 Changed 8 months ago by jsrn

Indeed, thanks. I seem to have too many things on my stack today ;-)

comment:244 Changed 8 months ago by tscrim

This is now one less. :)

comment:245 Changed 8 months ago by vbraun

  • Status changed from positive_review to needs_work

Fails on 32-bit

sage -t --long src/sage/rings/polynomial/skew_polynomial_element.pyx
**********************************************************************
File "src/sage/rings/polynomial/skew_polynomial_element.pyx", line 299, in sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.__hash__
Failed example:
    h = hash(a); h
Expected:
    -1717348446110052408
Got:
    -368406584
**********************************************************************
1 item had failures:
   1 of   6 in sage.rings.polynomial.skew_polynomial_element.SkewPolynomial.__hash__
    [722 tests, 1 failure, 0.57 s]

comment:246 Changed 8 months ago by tscrim

Ah, right 32v64 bit. @jsm @arpitdm I would just make the doctest hash(a) == hash(a) and you can set a positive review on my behalf once that is done.

comment:247 Changed 8 months ago by git

  • Commit changed from 204be6593bf4ec184c87292f96eeba22c3038087 to ddb5d7fddfa598de92c5935ea7aeed7c309f03ad

Branch pushed to git repo; I updated commit sha1. New commits:

ddb5d7fMerge branch 'public/rings/skew_polynomials-13215' of trac.sagemath.org:sage into 13215_skew_polynomials

comment:248 Changed 8 months ago by git

  • Commit changed from ddb5d7fddfa598de92c5935ea7aeed7c309f03ad to 7cb0ccebabc3eeabab0e3765941ad4a1b79cab1c

Branch pushed to git repo; I updated commit sha1. New commits:

7cb0ccehash doctest as per reviewer's suggestion

comment:249 Changed 8 months ago by jsrn

  • Status changed from needs_work to positive_review

Done. Let's try again :-)

comment:250 Changed 8 months ago by vbraun

  • Branch changed from public/rings/skew_polynomials-13215 to 7cb0ccebabc3eeabab0e3765941ad4a1b79cab1c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.