Opened 9 years ago

Last modified 5 years ago

#13215 closed enhancement

Skew polynomials — at Version 58

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 Reviewers: Burcin Erocal
Report Upstream: N/A Work issues: see comment #25
Branch: u/arpitdm/skew_polynomials (Commits, GitHub, GitLab) Commit: e189fec13d005a7fba39a429876c501fe95c05da
Dependencies: #13214, #13303, #13640, #13641, #13642 Stopgaps:

Status badges

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

Change History (65)

comment:1 Changed 9 years ago by caruso

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by caruso

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

Changed 9 years ago by caruso

comment:3 Changed 9 years ago by caruso

File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch

comment:4 Changed 9 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 9 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 9 years ago by caruso

  • Status changed from needs_work to needs_review

comment:7 Changed 9 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 9 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 9 years ago by caruso (previous) (diff)

comment:9 Changed 9 years ago by caruso

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

comment:10 Changed 9 years ago by caruso

  • Cc caruso added

comment:11 Changed 9 years ago by jdemeyer

Please fill in your real name as Author.

comment:12 Changed 9 years ago by caruso

  • Authors set to Xavier Caruso

comment:13 Changed 9 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 9 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 9 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 9 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 9 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 9 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 9 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 9 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 9 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 9 years ago by caruso

Changed 9 years ago by caruso

comment:22 Changed 8 years ago by darij

  • Cc darij added

Changed 8 years ago by caruso

Changed 8 years ago by caruso

comment:23 Changed 8 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 8 years ago by caruso

comment:24 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:25 Changed 8 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 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 7 years ago by mmezzarobba

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

comment:30 Changed 6 years ago by panda314

  • Branch set to u/panda314/skew_polynomials

comment:31 Changed 6 years 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 5 years ago by arpitdm

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

comment:33 Changed 5 years 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 5 years 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 5 years ago by tscrim

  • Cc tscrim added

comment:36 Changed 5 years 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 5 years ago by dlucas

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

comment:38 Changed 5 years 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 5 years 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 5 years 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 5 years ago by arpitdm

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

comment:42 Changed 5 years 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 5 years 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 5 years 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 5 years 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 5 years 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 5 years 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 5 years 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 5 years ago by jsrn

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

comment:50 Changed 5 years 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 5 years ago by arpitdm

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

comment:52 Changed 5 years 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 5 years 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 5 years 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 5 years 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 5 years 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 5 years ago by arpitdm

  • Status changed from needs_work to needs_review

comment:58 Changed 5 years ago by arpitdm

  • Description modified (diff)
Note: See TracTickets for help on using tickets.