Factoring and Irreducibility Related Methods in Skew Polynomials

[arpitdm]

This ticket implements the following methods (all related to factorization and irreducible divisors) for skew polynomials over finite fields

• is_irreducible
• right_irreducible_divisor, left_irreducible_divisor (return a divisor)
• right_irreducible_divisors, left_irreducible_divisors (return an iterator over all divisors)
• count_irreducible_divisors
• factor (return a factorization)
• factorizations (return an iterator over all factorizations)
• count_factorizations

CC: @tscrim @xcaruso @johanrosenkilde @sagetrac-dlucas @vbraun

Component: algebra

Author: Xavier Caruso

Branch/Commit: d107cce

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/21264

[arpitdm]

Branch: u/arpitdm/irreducibility_factoring_skew_polynomials

[arpitdm]

comment:2

Please also note that the current code is more or less just what was in the original patch for #13215 related to Factoring and Irreducibility methods. No effort has been made yet to accommodate for changes in #13215 since this addition was factored out.

[arpitdm]

Changed branch from u/arpitdm/irreducibility_factoring_skew_polynomials to none

[arpitdm]

Author: Xavier Caruso

[xcaruso]

comment:4

Where is the code of this ticket?

Should I copy it from https://github.com/sagemath/sage-prod/files/10655943/trac_13215_skew_polynomials.patch.gz or can I find it somewhere on git?

[xcaruso]

Branch: u/caruso/skew_polynomial_finite_field

[xcaruso]

comment:6

OK, I found it.

---

Last 10 new commits:

16ce9e3	add testsuite
318a179	Merge branch 'pickling_frobenius' into skew_polynomial_finite_order
1ce658d	fix comparison of morphisms
2598cf2	implement a factory
75c220a	skip test_category
c7b937c	fix pyflakes
9e4ed51	fix non ascii and blocks
11fa8eb	100% coverage
20794e7	added factoring and irreducibility based methods as is, from the original #13215 ticket
4826d12	Merge branch 'u/arpitdm/irreducibility_factoring_skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomial_finite_field

[xcaruso]

Commit: 4826d12

[sagetrac-git]

Changed commit from 4826d12 to 14d9f26

[sagetrac-git]

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

86b0bdc	factorize methods _left_lcm_cofactor and _right_lcm_cofactor
49c64bb	remove class CenterSkewPolynomialRing and add doctest
1b0092f	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field
dc6995c	remove CenterSkewPolynomial_generic_dense in pxd
1725800	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field
81228f5	remove CenterSkewPolynomial_generic_dense and duplicate methods
1c513ff	fix import
253200f	remove obsolete import
7e4f15e	change coercion defaults
14d9f26	refactor code

[sagetrac-git]

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

1eee2b4	improve error message when coercion/conversion fails for the center
19c9e67	add doctests
5f3188c	default variable name for the center
a171b19	typos
9d11ad3	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field
e8f2b32	working_center
84f7d9e	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field
1bcdf9a	use working_center
3db3ff2	reduced norm of a constant polynomial
858c9e7	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field

[sagetrac-git]

Changed commit from 14d9f26 to 858c9e7

[xcaruso]

Changed dependencies from #13215, #21088, #21259, #21262 to #13215, #21088, #21262

[sagetrac-git]

Changed commit from 858c9e7 to cccfef5

[sagetrac-git]

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

329fcad	use tuple instead of list
b78d3ef	fix small bug
f17860f	deterministic choice of variable names
8417a05	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_field
440ae61	fix doctest
cccfef5	import correctly sig_on and sig_off

[sagetrac-git]

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

0e15a9e	better test in register_coercion
e92febe	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_order_rc0
fddbb5e	explicit check for no coercion
f7e08ff	Merge branch 'skew_polynomial_finite_field' into skew_polynomial_finite_field_rc0
1157219	more doctests
d156e48	100% coverage

[sagetrac-git]

Changed commit from cccfef5 to d156e48

[xcaruso]

Changed dependencies from #13215, #21088, #21262 to #13215, #21088, #21262, #29517

[sagetrac-git]

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

39eb017

small fixes

[sagetrac-git]

Changed commit from d156e48 to 39eb017

[tscrim]

comment:15

Can you rebase the branch off #21262 so the commits/changes specific to this ticket are easier to review?

Also there are added functions in skew_polynomial_element.pyx that do not have doctests and formatting should be

- some really long text that needs to be wrapped on
  multiple lines should have the text start on the
  same line as the first character that is not the
  bullet point/number

[xcaruso]

Changed commit from 39eb017 to e3f2b25

[sagetrac-git]

Changed commit from e8e9139 to 5897dfc

[xcaruso]

comment:21

I think I addressed all your remarks.

[tscrim]

comment:22

Thank you. So I have gotten a look at the C code and did another pass, and I have a few more comments. I think this will be the last batch.

Could you separate the main part of right_quo_rem (and same for the left) into a cdef that assumes an input in the parent? This should improve the C code in _left_lcm_cofactor (same for the right).

Instead of calling N.parent(), you can you the (inline) C function parent(N).

I think this could be simplified in type():

-i = [ n for n,_ in self._norm_factor ].index(N)
-m = self._norm_factor[i][1]
+m = -1
+for n, mp in self._norm_factor:
+    if n == N:
+        m = mp
+        break

This way you don't create a whole new list and have to iterate through the entire self._norm_factor nor obtain the index again.

It would be nice to put the imports

from sage.matrix.matrix_space import MatrixSpace
from sage.matrix.matrix2 import NotFullRankError

at the top-level. I guess this is the import loop we had on the other ticket? I still need to fix that...

I guess we don't know anything about the type of N in _rdivisor_c, correct?

In this line, do you really need to create a new list?

X = <SkewPolynomial_finite_field_dense>Q._new_c(Q._coeffs[:],Q._parent)

If so, then I think it is better to do list(Q._coeffs).

I still think the M = MatrixSpace(E,e,e)(lM).transpose() is relatively expensive and could be avoided. For example:

lM = [None] * e**2
for j in range(e):
    for i in range(e):
        coeffs = [skew_ring._retraction(X[t*r+i]) for t in range(d)]
        value = E(coeffs)
        lM[i*e+j] = value

-xx = PE(W.list() + [E(-1)])
+xx = PE((<list> W.list()) + [E(-1)])

I think instead of mul = lambda a,b: a*b and for the other in _irreducible_divisors, it would be better to have little inline cdef functions lmul and rmul (say in the pxd file) that you set mul to. This seems to make the C code better.

This is impossible: if len(a) < 0:. Did you mean if len(a) == 0, in which case it is faster to just do if not a:?

I am not 100% sure that this is safe:

cdef RingElement unit = <RingElement>self.leading_coefficient()

Is it possible to have something over a commutative base ring that whose elements are not a RingElement? There are such things, like the ring of symmetric functions (granted, this is not a finite field, but merely to point out such things can exists within Sage). There might not be any benefit for specifying the type here.

Take advantage of the caching:

-skew_ring(1)
+skew_ring.one()

So you don't have to create an intermediate object:

-cdef list indices = list(Permutations(len(factorsN)).random_element())
+from sage.misc.prandom import sample  # Do this import at the top level\
+m = len(factorsN)
+cdef list indices = <list> sample(range(1,m+1), m))

Missed one:

-maxcount = q_jordan(Partition(maxtype),cardE)
+maxcount = q_jordan(maxtype, cardE)

[sagetrac-git]

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

05c6bdf

make left_quo_rem and right_quo_rem cdef functions

[sagetrac-git]

Changed commit from 5897dfc to 05c6bdf

[xcaruso]

comment:24

Replying to @tscrim:

Could you separate the main part of right_quo_rem (and same for the left) into a cdef that assumes an input in the parent? This should improve the C code in _left_lcm_cofactor (same for the right).

It's done, I think. Please tell me if I've implemented correctly what you had in mind.

I tried to call the methods _left_quo_rem and _right_quo_rem in _irreducible_divisors but the following lines fail:

    quo_rem = SkewPolynomial_finite_field._right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

I don't know why exactly.

It would be nice to put the imports

from sage.matrix.matrix_space import MatrixSpace
from sage.matrix.matrix2 import NotFullRankError

at the top-level. I guess this is the import loop we had on the other ticket? I still need to fix that...

Yes, it creates import errors. And indeed, it would be nice to fix it.

I guess we don't know anything about the type of N in _rdivisor_c, correct?

Well, it's a polynomial. So probably an instance of the generic class Polynomial (or maybe even Polynomial_generic_dense) but I'm not sure it will always be the case.

Another point: From time to time, I got errors with sig_on() and sig_off(), e.g.:

sage: k.<a> = GF(5^4)
sage: Frob = k.frobenius_endomorphism(2)
sage: S.<x> = k['x', Frob]
sage: P = x^2 + a + a^25
sage: P.factor()
Traceback (most recent call last):
...
SystemError: calling remove_from_pari_stack() inside sig_on()

So, I've removed them and added a call to sig_check() in the methods _left_quo_rem and _right_quo_rem (which are called repeatedly by all nontrivial algorithms). Is this okay?

[tscrim]

comment:25

Replying to @xcaruso:

Replying to @tscrim:

Could you separate the main part of right_quo_rem (and same for the left) into a cdef that assumes an input in the parent? This should improve the C code in _left_lcm_cofactor (same for the right).

It's done, I think. Please tell me if I've implemented correctly what you had in mind.

I tried to call the methods _left_quo_rem and _right_quo_rem in _irreducible_divisors but the following lines fail:

    quo_rem = SkewPolynomial_finite_field._right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

I don't know why exactly.

So I think it is because Cython doesn't know that those should be function pointers and will have the same signature. You might be able to make them actual function pointers since you know everything is the correct type. However, I am not sure exactly how to do this as Cython tutorials don't seem to talk much about how to do function pointers, much less with cdef methods.

It would be nice to put the imports

from sage.matrix.matrix_space import MatrixSpace
from sage.matrix.matrix2 import NotFullRankError

at the top-level. I guess this is the import loop we had on the other ticket? I still need to fix that...

Yes, it creates import errors. And indeed, it would be nice to fix it.

This is now #29561, which fixes the import loop when I tested it.

I guess we don't know anything about the type of N in _rdivisor_c, correct?

Well, it's a polynomial. So probably an instance of the generic class Polynomial (or maybe even Polynomial_generic_dense) but I'm not sure it will always be the case.

That's fine. I just wanted to ask to see if I was missing something.

Another point: From time to time, I got errors with sig_on() and sig_off(), e.g.:

sage: k.<a> = GF(5^4)
sage: Frob = k.frobenius_endomorphism(2)
sage: S.<x> = k['x', Frob]
sage: P = x^2 + a + a^25
sage: P.factor()
Traceback (most recent call last):
...
SystemError: calling remove_from_pari_stack() inside sig_on()

So, I've removed them and added a call to sig_check() in the methods _left_quo_rem and _right_quo_rem (which are called repeatedly by all nontrivial algorithms). Is this okay?

I am pretty certain that is okay. Although I am not such a Cython expert to say it is surely correct.

[xcaruso]

comment:26

Replying to @xcaruso:

I tried to call the methods _left_quo_rem and _right_quo_rem in _irreducible_divisors but the following lines fail:

    quo_rem = SkewPolynomial_finite_field._right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

I don't know why exactly.

It's really weird. It really looks like a bug in a cython compiler. For instance,

    quo_rem = SkewPolynomial_finite_field.right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

sometimes works... but not always. (And I couldn't figure out on what it depends.)

[sagetrac-git]

Changed commit from 05c6bdf to 2ed055d

[sagetrac-git]

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

99b4ee7	Merge branch 'u/caruso/skew_polynomial_finite_field_rebased' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
eac641b	Making imports more local in matrices.
c5f5bd7	Merge branch 'u/tscrim/specific_imports_matrices-29561' of git://trac.sagemath.org/sage into skew_polynomial_finite_field_rc1
2ed055d	move imports

[tscrim]

comment:28

Replying to @xcaruso:

Replying to @xcaruso:

I tried to call the methods _left_quo_rem and _right_quo_rem in _irreducible_divisors but the following lines fail:

    quo_rem = SkewPolynomial_finite_field._right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

I don't know why exactly.

It's really weird. It really looks like a bug in a cython compiler. For instance,

    quo_rem = SkewPolynomial_finite_field.right_quo_rem
    quo_rem2 = SkewPolynomial_finite_field._left_quo_rem

sometimes works... but not always. (And I couldn't figure out on what it depends.)

That is strange. Well, I think that can be a mystery for another day for additional optimization. I have done everything I can see is natural to do. Thank you for caring care of all of those changes.

[xcaruso]

comment:29

Great!

Since, I merged #29561 in this ticket, I think it's better if I give a positive review to #29561 right now. We will see later for pyflakes issues.

[xcaruso]

Changed dependencies from #13215, #21088, #21262, #29517 to #13215, #21088, #21262, #29517, #29561

[sagetrac-git]

Changed commit from 2ed055d to d107cce

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

d107cce

Merge branch 'develop' into skew_polynomial_finite_field_rc1

[xcaruso]

comment:32

Conflict resolved.

[tscrim]

Changed dependencies from #13215, #21088, #21262, #29517, #29561 to none

[tscrim]

comment:33

Hi Volker, is there some reason this hasn't yet been merged in? All of the dependency tickets were closed (I removed them in case that is causing some issues with your scripts).

[vbraun]

Changed branch from u/caruso/skew_polynomial_finite_field_rebased to d107cce