Opened 10 years ago
Last modified 3 years ago
#6452 needs_work enhancement
Submodules of (ZZ/nZZ)^r
Reported by:  wdj  Owned by:  rlm 

Priority:  major  Milestone:  sage7.4 
Component:  linear algebra  Keywords:  
Cc:  cesarnda@…, dlucas, jsrn  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  
Report Upstream:  N/A  Work issues:  oldstyle print 
Branch:  u/vdelecroix/6452 (Commits)  Commit:  96ead16e9e3a3236e024d94d671a61eca56078ea 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket add some support to submodules of (ZZ/mZZ)^r
(e.g. containment, iteration). There is no new algorithm, we just use the code available for submodules of ZZ^r
and the Schmidt normal form of integer matrix.
Follow up: #19345
Attachments (2)
Change History (40)
Changed 10 years ago by
comment:1 Changed 10 years ago by
 Summary changed from codes over rings to [with patch, needs review] codes over rings
This applies to 4.1.alpha1. This passed sage testall except for
The following tests failed: sage t "devel/sage/doc/fr/tutorial/programming.rst" sage t "devel/sage/sage/misc/darwin_utilities.pyx" Total time for all tests: 6017.1 seconds
Neither of these failures seem related to this ticket.
comment:2 Changed 10 years ago by
 Summary changed from [with patch, needs review] codes over rings to [with patch, needs work] codes over rings
The patch doesn't contain the crucial file ring_code.pyx
. Maybe you forgot to add this file to the hg repository?
comment:3 Changed 9 years ago by
 Status changed from needs_work to needs_review
This latest patch fixes some problems prointed out in private emails from Dan Gordon.
comment:4 Changed 9 years ago by
 Summary changed from [with patch, needs work] codes over rings to [with patch, needs review] codes over rings
comment:5 Changed 9 years ago by
I can also say that the module in coding pass sage t, with this patch applied, in OS 10.6 on an imac. OS10.6 does not pass sage testall. However, I do have ubuntu 9.04 32bit installed under vmware on this machine and can test it there if desired.
comment:6 Changed 9 years ago by
 Status changed from needs_review to positive_review
comment:7 followup: ↓ 9 Changed 9 years ago by
 Status changed from positive_review to needs_work
 Summary changed from [with patch, needs review] codes over rings to [with patch, needs work] codes over rings
Is there any way we can get documentation for the cdef methods as well as possibly some more code comments? I'm just worried that there's no one who is able to maintain this code.
Also, it's not clear to me that there are not memory leak issues with this code as there are lots of malloc's and only one free.
comment:8 Changed 9 years ago by
 Cc cesarnda@… added
If someone can explain to me what those functions will do, I will add comments on them. As I said, I am basically doing a favor by posting a patch of someone else's code. I had to make a lot of additions to make it consistent with other parts of the codes library, but basically it is Cesar's code. Personally, I really don't understand the cython stuff.
Does this mean that the code will not be accepted?
comment:9 in reply to: ↑ 7 Changed 9 years ago by
 Report Upstream set to N/A
Replying to mhansen:
Is there any way we can get documentation for the cdef methods as well as possibly some more code comments? I'm just worried that there's no one who is able to maintain this code.
Also, it's not clear to me that there are not memory leak issues with this code as there are lots of malloc's and only one free.
As I said, I could try to add comments to the code, but I really don't know cython nearly well enough to deal with malloc issues.
I've emailed Cesar and not gotten any response about the memory leak issues.
Given that, should the status change to "resolve as won't fix"? That would be too bad since Sage could really use "linear codes" over rings.
comment:10 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:11 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:12 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:13 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:14 Changed 3 years ago by
 Branch set to public/6452
 Commit set to 1177056cb4942b0ce938a30537357bcb07f1bf19
comment:15 Changed 3 years ago by
 Cc dlucas jsrn added
 Milestone changed from sage6.4 to sage6.9
comment:16 Changed 3 years ago by
 Description modified (diff)
 Summary changed from [with patch, needs work] codes over rings to Codes over rings
comment:17 followup: ↓ 18 Changed 3 years ago by
I'm not particularly fond of this patch, I must admit. It doesn't seem very well thought out. I prefer not putting in code which is weak and not thought through, rather than superficially being able to claim that "Sage can do codes over rings". For instance, what can the code actually do right now, besides computing the list of codewords?
Some concrete complaints:
gen_mat
should (nowadays) begenerator_matrix
. The class has many nonhiddenbutactuallyprivateandstupidlynamed fields
self.codeSet
,self.minimum
, etc. They should be renamed and start with an underscore. next(self)
is not the way we implement iterators, AFAIK. The name
RingCode
is not sensible, since onlyZZ/mZZ
is supported.  The mathematical object of such a code is a free
ZZ/mZZ
module. Shouldn't this be reflected by some parent/category magic in__init__
? __latex__
is wrong: it says "Linear code". English is bad in some texts, e.g. for
length()
, a "the" is missing.  What's the point of
spanning_codewords
? The nomenclature is not used inLinearCode
, and function just returns the rows of the generator matrix anyway.
On a broader design level: I dislike that tons of computation is done at __init__
, in particular tabulating all codewords. In coding theory stuff that I have been involved in, we have tried very hard to postpone computation until it becomes necessary. In particular, construction should be cheap.
For instance, I think that e.g. the cardinality of such a code can be relatively easily computed without tabulating the entire code.
The design of ring codes should also think the new (well, almostaccepted) Encoder
and Decoder
structure into it: #18376, #18813.
Note that I did not run or test the code  I just looked at it.
comment:18 in reply to: ↑ 17 ; followup: ↓ 19 Changed 3 years ago by
Thanks for having a look. (disclaimer: I actually only ended up here because of this question on ask).
Replying to jsrn:
I'm not particularly fond of this patch, I must admit. It doesn't seem very well thought out. I prefer not putting in code which is weak and not thought through, rather than superficially being able to claim that "Sage can do codes over rings". For instance, what can the code actually do right now, besides computing the list of codewords?
Nothing I guess. But it is already something and it seems to be done efficiently.
Some concrete complaints:
 The mathematical object of such a code is a free
ZZ/mZZ
module. Shouldn't this be reflected by some parent/category magic in__init__
?
Nope. It is not necessarily free. The submodule of (ZZ/4ZZ)
generated by 2
is not free.
On a broader design level: I dislike that tons of computation is done at
__init__
, in particular tabulating all codewords. In coding theory stuff that I have been involved in, we have tried very hard to postpone computation until it becomes necessary. In particular, construction should be cheap.
I guess it would be reasonable to turn it into a function or method.
For instance, I think that e.g. the cardinality of such a code can be relatively easily computed without tabulating the entire code.
True. It would basically be equivalent to implement a generalized echelon form for matrices over ZZ/nZZ
that give you a "pseudobasis" of submodules of (ZZ/nZZ)^r
. I have no idea where to find such algorithm.
The design of ring codes should also think the new (well, almostaccepted)
Encoder
andDecoder
structure into it: #18376, #18813.
+1
Note that I did not run or test the code  I just looked at it.
The tests do not pass, but at least some examples run just nicely. Moreover, there was at least one person interested. This is why I thought it would be worse to make it a branch.
Vincent
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 3 years ago by
Nothing I guess. But it is already something and it seems to be done efficiently.
Well, it's perhaps efficient if what you want is to tabulate the entire code and immediately ask it for various stuff (like minimum distance). It's inefficient if you are only interested in some of the properties.
On the other hand, the implementation forces Cython on pretty base functionality. I'm not sure what kind of speedup Cython brings here as opposed to pure Python  after all, the actual work is done in finite field arithmetic. It would be interesting to compare and see whether Cython is worth it.
Nope. It is not necessarily free. The submodule of
(ZZ/4ZZ)
generated by2
is not free.
No of course you're right that it's not  the word "free" slipped in there by mistake. But it *is* a module.
I guess it would be reasonable to turn it into a function or method.
Minimum distance and minimum codeword computation should also be extracted from the code tabulation. I might want the list of codewords but not care about the minimum distance, and so computing the hamming weight of all the vectors is a huge waste.
True. It would basically be equivalent to implement a generalized echelon form for matrices over
ZZ/nZZ
that give you a "pseudobasis" of submodules of(ZZ/nZZ)^r
. I have no idea where to find such algorithm.
It's interesting: I'll think more on this. For instance, would the Hermite Normal form be sufficient?
The tests do not pass, but at least some examples run just nicely. Moreover, there was at least one person interested. This is why I thought it would be worse to make it a branch.
You are right, it would be nice to support codes over ZZ/mZZ
. I just want to avoid adding stuff that will have to be reformed through a heavy reviewing process just a bit further down the road ;)
comment:20 in reply to: ↑ 19 Changed 3 years ago by
Replying to jsrn:
True. It would basically be equivalent to implement a generalized echelon form for matrices over
ZZ/nZZ
that give you a "pseudobasis" of submodules of(ZZ/nZZ)^r
. I have no idea where to find such algorithm.It's interesting: I'll think more on this. For instance, would the Hermite Normal form be sufficient?
I don't think that it is enough to determine the structure. An example of a problem is if R=ZZ/4ZZ
and a matrix of the form
2 * * 0 2 * 0 0 2
If you have a vector which is a sum of its row with coefficients 0
or 2
then the leading coefficient vanish... and you lose the nice Hermite form!
But I guess that the Smith normal form would be of more help. If I intrepret correctly what I read, it tells you that any submodule of R^r
where R = ZZ/nZZ
is actually of the form R / (I1) + R / (I2) + ... + R / (Ik)
for some ideals I1
, ..., Ik
. These ideals are basically the product SAT
(which is diagonal) and the decomposition is explicitly given by T
(my source and notations from wikipedia).
comment:21 Changed 3 years ago by
I think you're right that the Smith form is exactly what is needed, for the reasons you mention. Ok, so that would be elegant to have in this patch :)
comment:22 followup: ↓ 23 Changed 3 years ago by
All right, I will try to do something. I had a more careful look at the code (and the corresponding master thesis) but I was not able to understand anything. With the Smith form it will also be straightforward to implement a (possibly very efficient) iterator over the elements of the module.
One non trivial point is to decide equality of submodules. The only canonical part of the Smith form is the diagonal matrix (which only gives you a hint about isomorphisms between submodules). But I guess that we can somehow echelonize the part corresponding to a given ideal. I would be much more happy with a clean reference...
Since this is more about submodules of (ZZ/nZZ)^r
I am not sure it should go at all inside sage.codings
. I would rather put it in sage.modules
. And (as I already told you), it would be better to factorize more between sage.modules
and sage.codings
when the code is only given by a generator matrix. So, for the sake of this ticket, my concrete proposal is:
 implement submodules of
(ZZ/nZZ)^r
with a canonical form  have an efficient iterator
If you think it is not too far from the original purpose of this ticket, I will modify the ticket description accordingly.
comment:23 in reply to: ↑ 22 ; followup: ↓ 24 Changed 3 years ago by
Replying to vdelecroix:
All right, I will try to do something. I had a more careful look at the code (and the corresponding master thesis) but I was not able to understand anything. With the Smith form it will also be straightforward to implement a (possibly very efficient) iterator over the elements of the module.
Nice, I didn't consider that.
One non trivial point is to decide equality of submodules. The only canonical part of the Smith form is the diagonal matrix (which only gives you a hint about isomorphisms between submodules). But I guess that we can somehow echelonize the part corresponding to a given ideal. I would be much more happy with a clean reference...
Since this is more about submodules of
(ZZ/nZZ)^r
I am not sure it should go at all insidesage.codings
. I would rather put it insage.modules
. And (as I already told you), it would be better to factorize more betweensage.modules
andsage.codings
when the code is only given by a generator matrix. So, for the sake of this ticket, my concrete proposal is:
 implement submodules of
(ZZ/nZZ)^r
with a canonical form have an efficient iterator
If you think it is not too far from the original purpose of this ticket, I will modify the ticket description accordingly.
Such a ticket would definitely make sense. And it seem to cover most of the functionality here (I mean, the minimum distance is right now just exhaustive checking distances...)
The distinction between vector subspaces and linear codes (given only by their generator matrix) is right now that the latter exposes a list of specialised coding theory functions. Such functions might be interesting for noncoding theorists, but probably won't be. That's an argument for having a special class which basically just wraps vector subspaces. Exactly the same argument could be made for submodules of (ZZ/nZZ)^r
. But no need to get ahead of ourselves here, though...
A different matter: the current patch is Cython. Do we want that? I remember Jeroen's advice to always try Cython only after you have determined that you really need the performance, and that Cython will give this to you.
comment:24 in reply to: ↑ 23 Changed 3 years ago by
Replying to jsrn:
Replying to vdelecroix: A different matter: the current patch is Cython. Do we want that? I remember Jeroen's advice to always try Cython only after you have determined that you really need the performance, and that Cython will give this to you.
Most of it will be in Python. Only the iterator can possibly be in Cython and it should not be more than 20 lines of code. But it makes sense to do it in a second time.
comment:25 Changed 3 years ago by
 Branch changed from public/6452 to u/vdelecroix/6452
 Commit changed from 1177056cb4942b0ce938a30537357bcb07f1bf19 to 708863f5754603bbed1abe786e7f718ce1e1c782
 Component changed from coding theory to linear algebra
 Description modified (diff)
 Status changed from needs_work to needs_review
 Summary changed from Codes over rings to Submodules of (ZZ/nZZ)^r
New commits:
708863f  Trac 6452: free module over ZZ/nZZ and submodules

comment:26 Changed 3 years ago by
 Commit changed from 708863f5754603bbed1abe786e7f718ce1e1c782 to acd707c558799cad8348f25b3a363eea26913452
comment:27 Changed 3 years ago by
 Commit changed from acd707c558799cad8348f25b3a363eea26913452 to ffbd6e833d08b51cf78c46065ac07f71f46d795d
Branch pushed to git repo; I updated commit sha1. New commits:
ffbd6e8  Trac 6452: simplification + more tests

comment:28 Changed 3 years ago by
 Description modified (diff)
 Milestone changed from sage6.9 to sage6.10
For the iterator, see #19345
comment:29 followup: ↓ 30 Changed 3 years ago by
Great work Vincent!
Just to be sure: is this "In review"? You made many changes but didn't change the state of "needs review".
I will look at it in detail later, and when I'm sure it's ready. But in any case, some preliminary remarks:
 Could you explain to me (reviewer) the reason for the patch in the category
files? Something with you using the
Facade
in a previously unthought case. Is this related to theFree
thing below?
FreeModule_ambient_IntegerModRing.span
never uses itscheck
argument.
 Since you compute the smith form at construction, then construction is expensive even when nothing is asked of the object afterwards. Is the argument for this that nothing interesting can be said about the module without computing the smith form anyway? Generally, I like construction to be cheap and postponing computation till the user asks it.
Generally, it looks pretty good though.
comment:30 in reply to: ↑ 29 Changed 3 years ago by
Hi,
Replying to jsrn:
Great work Vincent!
Thanks ;)
Just to be sure: is this "In review"? You made many changes but didn't change the state of "needs review".
It is in needs review. After the first commit, it appears that one doctest failed. And then, I found many typos and some better conventions. This is why there are so much commits afterwards. Shortly: it is ready and in needs review.
I will look at it in detail later, and when I'm sure it's ready. But in any case, some preliminary remarks:
 Could you explain to me (reviewer) the reason for the patch in the category files? Something with you using the
Facade
in a previously unthought case. Is this related to theFree
thing below?
Nope. There is no TestSuite(U).run()
anywhere for submodules. And this is the reason why.
A facade is a concept from the Sage category. A parent is a facade if its elements do not belong to itself, as for submodules
sage: F = FreeModule(ZZ,2) sage: U = F.span([F((3,0))]) sage: U.an_element().parent() is U False sage: U.an_element().parent() is F True
So U
is a facade for F
. But this is currently not properly done
sage: U in Sets().Facade() False
I did it for the submodules over ZZ/nZZ
. I will fix it later on for the other base rings as well and add some TestSuite
.
There are many generic tests in category (that are automatically run with the TestSuite
thing) but some of them do not care about facades. In particulal the _test_zero
and _test_one
that I modified.
FreeModule_ambient_IntegerModRing.span
never uses itscheck
argument.
True. I did it for compatibility with the other span
functions. Maybe I could remove it.
 Since you compute the smith form at construction, then construction is expensive even when nothing is asked of the object afterwards. Is the argument for this that nothing interesting can be said about the module without computing the smith form anyway? Generally, I like construction to be cheap and postponing computation till the user asks it.
Without this nothing can be computed (number of generators, cardinality). Note that I postponed the _lift
argument computation.
comment:31 Changed 3 years ago by
Note that in the other functions there is a already_echelonized
function that precisely prevent any computation (assuming that the fed data is in good shape). Perhaps we can add a already_schmidt_reduced
argument?
comment:32 Changed 3 years ago by
About facade sets, you can read the documentation of sage.categories.sets_cat.Sets.SubcategoryMethods.Facade
.
comment:33 Changed 3 years ago by
 Status changed from needs_review to needs_work
And I just notice that the other submodules are actually not facade sets... I should definitely follow the same convention!
comment:34 Changed 3 years ago by
 Commit changed from ffbd6e833d08b51cf78c46065ac07f71f46d795d to 96ead16e9e3a3236e024d94d671a61eca56078ea
comment:35 Changed 3 years ago by
 Status changed from needs_work to needs_review
Warning: this is a forced push (branch restarted from zero)
Disclaimer: since I had to get rid of facades it did not make sense to just revert all what I did before
Now, no worries about facades... they do not appear anymore. Needs review again.
Vincent
comment:36 Changed 3 years ago by
(ping)
comment:37 Changed 3 years ago by
there is an oldstyle print somewhere, see bot report
comment:38 Changed 3 years ago by
 Milestone changed from sage6.10 to sage7.4
 Status changed from needs_review to needs_work
 Work issues set to oldstyle print
applies to 4.1.alpha1