Opened 10 years ago

Last modified 6 weeks ago

#6452 needs_work enhancement

Submodules of (ZZ/nZZ)^r

Reported by: wdj Owned by: rlm
Priority: major Milestone: sage-8.8
Component: linear algebra Keywords:
Cc: cesarnda@…, dlucas, jsrn Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: public/ticket/6452 (Commits) Commit: c93a30add9a6cfb66197558ba0261b566d022bb4
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.

Follow up: #19345

Attachments (2)

trac_6452-codes-over-rings.patch (929 bytes) - added by wdj 10 years ago.
applies to 4.1.alpha1
trac_6452-ring-codes.patch (18.0 KB) - added by wdj 10 years ago.
ignore the previous patch; this applies to 4.1.2.rc2

Download all attachments as: .zip

Change History (44)

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 9 years ago by dgordon

  • Status changed from needs_review to positive_review

comment:7 follow-up: Changed 9 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 9 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 9 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

comment:26 Changed 4 years ago by git

  • Commit changed from 708863f5754603bbed1abe786e7f718ce1e1c782 to acd707c558799cad8348f25b3a363eea26913452

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

ebb2092Trac 6452: adapt some tests to facade
a5e3d23Trac 6452: fix a doctest
acd707cTrac 6452: cleaner code + more doc

comment:27 Changed 4 years ago by git

  • Commit changed from acd707c558799cad8348f25b3a363eea26913452 to ffbd6e833d08b51cf78c46065ac07f71f46d795d

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

ffbd6e8Trac 6452: simplification + more tests

comment:28 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-6.9 to sage-6.10

For the iterator, see #19345

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

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

comment:31 Changed 4 years ago by 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?

comment:32 Changed 4 years ago by vdelecroix

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

comment:33 Changed 4 years ago by vdelecroix

  • 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 4 years ago by git

  • Commit changed from ffbd6e833d08b51cf78c46065ac07f71f46d795d to 96ead16e9e3a3236e024d94d671a61eca56078ea

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

59ab945Trac 6452: free modules over ZZ/nZZ and submodules
96ead16Trac 6452: fix a doctest

comment:35 Changed 4 years ago by vdelecroix

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

(ping)

comment:37 Changed 3 years ago by chapoton

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

comment:38 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.10 to sage-7.4
  • Status changed from needs_review to needs_work
  • Work issues set to old-style print

comment:39 Changed 7 weeks ago by chapoton

  • Branch changed from u/vdelecroix/6452 to public/ticket/6452
  • Commit changed from 96ead16e9e3a3236e024d94d671a61eca56078ea to c93a30add9a6cfb66197558ba0261b566d022bb4
  • Status changed from needs_work to needs_info
  • Work issues old-style print deleted

New commits:

3e33bcbMerge branch 'u/vdelecroix/6452' in 8.7.b6
c93a30afix for py3

comment:40 Changed 7 weeks ago by chapoton

  • Milestone changed from sage-7.4 to sage-8.8

comment:41 Changed 7 weeks ago by chapoton

  • Status changed from needs_info to needs_review

comment:42 Changed 6 weeks ago by chapoton

  • Status changed from needs_review to needs_work

this need a python3 refreshment, to avoid cmp and long

Note: See TracTickets for help on using tickets.