Submodules of (ZZ/nZZ)^r

[wdj]

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

[wdj]

applies to 4.1.alpha1

[wdj]

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.

[AlexGhitza]

The patch doesn't contain the crucial file ring_code.pyx. Maybe you forgot to add this file to the hg repository?

[wdj]

ignore the previous patch; this applies to 4.1.2.rc2

[wdj]

This latest patch fixes some problems prointed out in private emails from Dan Gordon.

[wdj]

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.

[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.

[wdj]

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?

[wdj]

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.

[vdelecroix]

Hello,

I updated a git branch with the patch provided + some corrections. It is not yet in working stage but not far from it!

Vincent

---

New commits:

​2d06681	new ring codes patch - wdj
​f162b9b	Trac 6452: fix imports
​eec91dd	Trac 6452: some doc formatting
​1177056	Trac 6452: fix some issues in the code

[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?

Some concrete complaints:

• gen_mat should (nowadays) be generator_matrix.
• The class has many non-hidden-but-actually-private-and-stupidly-named 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 only ZZ/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 in LinearCode, 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, almost-accepted) Encoder and Decoder structure into it: #18376, #18813.

Note that I did not run or test the code -- I just looked at it.

[vdelecroix]

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 "pseudo-basis" 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, almost-accepted) Encoder and Decoder 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

[jsrn]

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 speed-up 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 by 2 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 "pseudo-basis" 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 ;-)

[vdelecroix]

Replying to jsrn:

True. It would basically be equivalent to implement a generalized echelon form for matrices over ZZ/nZZ that give you a "pseudo-basis" 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).

[jsrn]

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 :-)

[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.

One non trivial point is to decide equality of sub-modules. 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.

[jsrn]

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 sub-modules. 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.

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 non-coding 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.

[vdelecroix]

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.

[vdelecroix]

New commits:

​708863f

Trac 6452: free module over ZZ/nZZ and submodules

[git]

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

​ebb2092	Trac 6452: adapt some tests to facade
​a5e3d23	Trac 6452: fix a doctest
​acd707c	Trac 6452: cleaner code + more doc

[git]

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

​ffbd6e8

Trac 6452: simplification + more tests

[vdelecroix]

For the iterator, see #19345

[jsrn]

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 the Free-thing below?

• FreeModule_ambient_IntegerModRing.span never uses its check 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.

[vdelecroix]

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 the Free-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 its check 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.

[vdelecroix]

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?

[vdelecroix]

About facade sets, you can read the documentation of sage.categories.sets_cat.Sets.SubcategoryMethods.Facade.

[vdelecroix]

And I just notice that the other submodules are actually not facade sets... I should definitely follow the same convention!

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​59ab945	Trac 6452: free modules over ZZ/nZZ and submodules
​96ead16	Trac 6452: fix a doctest

[vdelecroix]

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

[vdelecroix]

(ping)

[chapoton]

there is an old-style print somewhere, see bot report

[chapoton]

New commits:

​3e33bcb	Merge branch 'u/vdelecroix/6452' in 8.7.b6
​c93a30a	fix for py3

[chapoton]

this need a python3 refreshment, to avoid cmp and long

[embray]

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

[embray]

Ticket retargeted after milestone closed

[mkoeppe]

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.