Opened 5 years ago
Closed 8 months ago
#21264 closed enhancement (fixed)
Factoring and Irreducibility Related Methods in Skew Polynomials
Reported by: | arpitdm | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | algebra | Keywords: | |
Cc: | tscrim, caruso, jsrn, dlucas, vbraun | Merged in: | |
Authors: | Xavier Caruso | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | d107cce (Commits) | Commit: | d107cce7a4149822d323a8b5842af65255cbcd22 |
Dependencies: | Stopgaps: |
Description (last modified by )
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
Change History (34)
comment:1 Changed 5 years ago by
- Branch set to u/arpitdm/irreducibility_factoring_skew_polynomials
comment:2 Changed 5 years ago by
- Branch u/arpitdm/irreducibility_factoring_skew_polynomials deleted
comment:3 Changed 5 years ago by
comment:4 Changed 11 months ago by
Where is the code of this ticket?
Should I copy it from https://trac.sagemath.org/attachment/ticket/13215/trac_13215_skew_polynomials.patch or can I find it somewhere on git?
comment:5 Changed 11 months ago by
- Branch set to u/caruso/skew_polynomial_finite_field
comment:6 Changed 11 months ago by
- Commit set to 4826d123e5d1f2654383c49ed068c14d04cb3659
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
|
comment:7 Changed 11 months ago by
- Commit changed from 4826d123e5d1f2654383c49ed068c14d04cb3659 to 14d9f2612adffd6b2d4d169b47489e43320e12d8
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
|
comment:8 Changed 11 months ago by
- Commit changed from 14d9f2612adffd6b2d4d169b47489e43320e12d8 to 858c9e73dc094a48b65dcbb57505c818a293b3b2
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
|
comment:9 Changed 11 months ago by
- Dependencies changed from #13215, #21088, #21259, #21262 to #13215, #21088, #21262
comment:10 Changed 11 months ago by
- Commit changed from 858c9e73dc094a48b65dcbb57505c818a293b3b2 to cccfef57254ce650f8e0c0dd7809edcfc1572fe8
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
|
comment:11 Changed 11 months ago by
- Description modified (diff)
comment:12 Changed 11 months ago by
- Commit changed from cccfef57254ce650f8e0c0dd7809edcfc1572fe8 to d156e48bc58f1f4d489a67688848bf23b0b52211
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
|
comment:13 Changed 11 months ago by
- Dependencies changed from #13215, #21088, #21262 to #13215, #21088, #21262, #29517
- Milestone changed from sage-7.4 to sage-9.2
- Status changed from new to needs_review
comment:14 Changed 11 months ago by
- Commit changed from d156e48bc58f1f4d489a67688848bf23b0b52211 to 39eb017a453a103a014d1840feba2b4f06f8e874
Branch pushed to git repo; I updated commit sha1. New commits:
39eb017 | small fixes
|
comment:15 Changed 10 months ago by
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
comment:16 Changed 10 months ago by
- Branch changed from u/caruso/skew_polynomial_finite_field to u/caruso/skew_polynomial_finite_field_rebased
- Commit changed from 39eb017a453a103a014d1840feba2b4f06f8e874 to e3f2b25145a6feb8f725a461be60e1ff6ff3dba4
comment:17 Changed 10 months ago by
- Commit changed from e3f2b25145a6feb8f725a461be60e1ff6ff3dba4 to 96dab844189554f6568dd757e9bc5780b7b2114f
Branch pushed to git repo; I updated commit sha1. New commits:
96dab84 | add missing doctest in skew_polynomial_element
|
comment:18 Changed 10 months ago by
- Commit changed from 96dab844189554f6568dd757e9bc5780b7b2114f to e8e9139a8248126c0e6a742786b8628eb7a38836
Branch pushed to git repo; I updated commit sha1. New commits:
e8e9139 | add a reference to my paper with Le Borgne
|
comment:19 Changed 10 months ago by
- Reviewers set to Travis Scrimshaw
Thank you, that helped a lot. It looks good and quite impressive. However, I do have a few comments:
In _left_lcm_cofactor
, is while not V3.is_zero():
faster than while not V3:
? Experience tells me the latter is nearly always faster. Also would it make sense to have this be an inlined cdef function? Could you specify the types of some of the variables there (you can do this in def
methods too)? Same comment for the _right_lcm_cofactor
.
Could _reduced_norm_factored
also be an inlined cdef method? Same for all of the other hidden methods like _irreducible_divisors
(possibly not inlined)?
I would do it like this in type
to make it more clear what the loop is testing:
+ d = self.right_gcd(NS) + deg = d.degree() / degN + while deg == 0: - while True: - d = self.right_gcd(NS) - deg = d.degree()/degN - if deg == 0: - break if m >= 0: if deg == 1: type += m * [1] break m -= deg self = self // d type.append(deg) + d = self.right_gcd(NS) + deg = d.degree() / degN
Can you also specify the type of some of the variables, like the lists? This should make the C code cleaner and offer some micro speedups (especially if you use type.extend(m * [1])
instead of type += m * [1]
). Also, since the result is cached, you should ultimately make it a tuple (or some other immutable object).
Why do you initialize _types
to be None
instead of an empty dict? It seems like a reasonable thing to do and have an __init__
method to me.
This syntax is somewhat deprecated for j from 0 <= j < e:
-> for j in range(e):
.
The following are all for _rdivisor_c
:
I think it be faster to do:
-Integer((E.cardinality()-1)/2) +<Integer>( (E.cardinality()-1) // 2 )
Rather than compute lM
and then take the transpose, I think it would be must better to construct directly in transpose form (which requires a little more computation, but I think it is faster).
I would pull the if skew_ring.characteristic() == 2:
test outside of the while
loop and store it as a boolean variable. In that case you can also do zz = yy
to avoid an extra function call.
Back to general comments: It would be nice to be more PEP8 compliant and have things like if P1.degree() == degN: break
on 2 lines IMO.
I would restructure the last part fo left_irreducible_factor
as:
if not uniform: LD = P1 // P1.right_gcd(NS // D) if LD.degree() == degN: return LD while True: R = skew_ring.random_element((deg,deg)) if NS.right_gcd(R) == 1: break D = NS.right_gcd(D*R) LD = P1 // P1.right_gcd(NS // D) if LD.degree() == degN: return LD
Yes, there is some code repetition, but it make the overall logic easier IMO.
In _factor_uniform_c
, you know type[0]
is an int
, so I would explicitly make that cast if <int>(type[0]) > 1:
to simplify the C code. Actually, you might want to locally make the type
variable an array of int
s to not have to do these casts everywhere and speedup element access. For the q_jordan
, why is maxtype
being converted to a partition? This is not needed for the function AFAICS. (Side note, this might be a good reason to consider Cythonizing these low-level but important combinatorial objects.)
while 1:
-> while True:
In factor
:
- ``uniform`` -- a boolean (default: ``False``); whether the - output irreducible divisor should be uniformly distributed - among all possibilities + output irreducible divisor should be uniformly distributed + among all possibilities
Also sig_on
and sig_off
should not contain Python code I believe. Just put it around the self._factor_c()
call.
Also, our convention is the 1-line descriptions should end with a period/full-stop.
comment:20 Changed 10 months ago by
- Commit changed from e8e9139a8248126c0e6a742786b8628eb7a38836 to 5897dfc3410ed8f584de7ea7a83e9b8170e5390c
Branch pushed to git repo; I updated commit sha1. New commits:
5897dfc | address Travis' comments
|
comment:21 Changed 10 months ago by
I think I addressed all your remarks.
comment:22 follow-up: ↓ 24 Changed 10 months ago by
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)
comment:23 Changed 10 months ago by
- Commit changed from 5897dfc3410ed8f584de7ea7a83e9b8170e5390c to 05c6bdf8e1752ba678f93e4539948694c656b28e
Branch pushed to git repo; I updated commit sha1. New commits:
05c6bdf | make left_quo_rem and right_quo_rem cdef functions
|
comment:24 in reply to: ↑ 22 ; follow-ups: ↓ 25 ↓ 26 Changed 10 months ago by
Replying to tscrim:
Could you separate the main part of
right_quo_rem
(and same for the left) into acdef
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 NotFullRankErrorat 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?
comment:25 in reply to: ↑ 24 Changed 10 months ago by
Replying to caruso:
Replying to tscrim:
Could you separate the main part of
right_quo_rem
(and same for the left) into acdef
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_remI 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 NotFullRankErrorat 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 evenPolynomial_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()
andsig_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.
comment:26 in reply to: ↑ 24 ; follow-up: ↓ 28 Changed 10 months ago by
Replying to caruso:
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_remI 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.)
comment:27 Changed 10 months ago by
- Commit changed from 05c6bdf8e1752ba678f93e4539948694c656b28e to 2ed055d22430d7866fd6e4b6f046b90dc9907fc3
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
|
comment:28 in reply to: ↑ 26 Changed 10 months ago by
- Status changed from needs_review to positive_review
Replying to caruso:
Replying to caruso:
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_remI 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_remsometimes 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.
comment:29 Changed 10 months ago by
comment:30 Changed 10 months ago by
- Dependencies changed from #13215, #21088, #21262, #29517 to #13215, #21088, #21262, #29517, #29561
comment:31 Changed 10 months ago by
- Commit changed from 2ed055d22430d7866fd6e4b6f046b90dc9907fc3 to d107cce7a4149822d323a8b5842af65255cbcd22
- Status changed from positive_review to needs_review
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
|
comment:32 Changed 10 months ago by
- Status changed from needs_review to positive_review
Conflict resolved.
comment:33 Changed 9 months ago by
- Cc vbraun added
- Dependencies #13215, #21088, #21262, #29517, #29561 deleted
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).
comment:34 Changed 8 months ago by
- Branch changed from u/caruso/skew_polynomial_finite_field_rebased to d107cce7a4149822d323a8b5842af65255cbcd22
- Resolution set to fixed
- Status changed from positive_review to closed
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.