Opened 10 years ago

Last modified 13 days ago

#6452 needs_work enhancement

Submodules of (ZZ/nZZ)^r — at Version 25

Reported by: wdj Owned by: rlm
Priority: major Milestone: sage-8.9
Component: linear algebra Keywords:
Cc: cesarnda@…, dlucas, jsrn Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/6452 (Commits) Commit: 708863f5754603bbed1abe786e7f718ce1e1c782
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

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.

Change History (27)

Changed 10 years ago by wdj

applies to 4.1.alpha1

comment:1 Changed 10 years ago by wdj

  • 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 AlexGhitza

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

Changed 10 years ago by wdj

ignore the previous patch; this applies to 4.1.2.rc2

comment:3 Changed 10 years ago by wdj

  • 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 10 years ago by wdj

  • Summary changed from [with patch, needs work] codes over rings to [with patch, needs review] codes over rings

comment:5 Changed 10 years ago by 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.

comment:6 Changed 10 years ago by dgordon

  • Status changed from needs_review to positive_review

comment:7 follow-up: Changed 10 years ago by mhansen

  • 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 10 years ago by wdj

  • 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 10 years ago by wdj

  • 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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:13 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:14 Changed 4 years ago by vdelecroix

  • Branch set to public/6452
  • Commit set to 1177056cb4942b0ce938a30537357bcb07f1bf19

Hello,

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

Vincent


New commits:

2d06681new ring codes patch - wdj
f162b9bTrac 6452: fix imports
eec91ddTrac 6452: some doc formatting
1177056Trac 6452: fix some issues in the code
Last edited 4 years ago by vdelecroix (previous) (diff)

comment:15 Changed 4 years ago by vdelecroix

  • Cc dlucas jsrn added
  • Milestone changed from sage-6.4 to sage-6.9

comment:16 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from [with patch, needs work] codes over rings to Codes over rings

comment:17 follow-up: Changed 4 years ago by 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.

comment:18 in reply to: ↑ 17 ; follow-up: Changed 4 years ago by 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

comment:19 in reply to: ↑ 18 ; follow-up: Changed 4 years ago by 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 ;-)

comment:20 in reply to: ↑ 19 Changed 4 years ago by 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).

comment:21 Changed 4 years ago by 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 :-)

comment:22 follow-up: Changed 4 years ago by 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.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 4 years ago by 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.

comment:24 in reply to: ↑ 23 Changed 4 years ago by 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.

comment:25 Changed 4 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • 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:

708863fTrac 6452: free module over ZZ/nZZ and submodules
Note: See TracTickets for help on using tickets.