Sage: Ticket #6452: Submodules of (ZZ/nZZ)^r
https://trac.sagemath.org/ticket/6452
<p>
This ticket add some support to submodules of <code>(ZZ/mZZ)^r</code> (e.g. containment, iteration). There is no new algorithm, we just use the code available for submodules of <code>ZZ^r</code> and the Schmidt normal form of integer matrix.
</p>
<p>
Follow up: <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/19345" title="enhancement: Fast lexicographic iterator for module over ZZ/nZZ (needs_work)">#19345</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/6452
Trac 1.1.6wdjWed, 01 Jul 2009 01:07:07 GMTattachment set
https://trac.sagemath.org/ticket/6452
https://trac.sagemath.org/ticket/6452
<ul>
<li><strong>attachment</strong>
set to <em>trac_6452-codes-over-rings.patch</em>
</li>
</ul>
<p>
applies to 4.1.alpha1
</p>
TicketwdjWed, 01 Jul 2009 01:09:02 GMTsummary changed
https://trac.sagemath.org/ticket/6452#comment:1
https://trac.sagemath.org/ticket/6452#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>codes over rings</em> to <em>[with patch, needs review] codes over rings</em>
</li>
</ul>
<p>
This applies to 4.1.alpha1. This passed sage -testall except for
</p>
<pre class="wiki">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
</pre><p>
Neither of these failures seem related to this ticket.
</p>
TicketAlexGhitzaSat, 11 Jul 2009 09:16:17 GMTsummary changed
https://trac.sagemath.org/ticket/6452#comment:2
https://trac.sagemath.org/ticket/6452#comment:2
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] codes over rings</em> to <em>[with patch, needs work] codes over rings</em>
</li>
</ul>
<p>
The patch doesn't contain the crucial file <code>ring_code.pyx</code>. Maybe you forgot to add this file to the hg repository?
</p>
TicketwdjSun, 18 Oct 2009 19:49:52 GMTattachment set
https://trac.sagemath.org/ticket/6452
https://trac.sagemath.org/ticket/6452
<ul>
<li><strong>attachment</strong>
set to <em>trac_6452-ring-codes.patch</em>
</li>
</ul>
<p>
ignore the previous patch; this applies to 4.1.2.rc2
</p>
TicketwdjSun, 18 Oct 2009 19:52:43 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:3
https://trac.sagemath.org/ticket/6452#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
This latest patch fixes some problems prointed out in private emails from Dan Gordon.
</p>
TicketwdjSun, 18 Oct 2009 19:52:57 GMTsummary changed
https://trac.sagemath.org/ticket/6452#comment:4
https://trac.sagemath.org/ticket/6452#comment:4
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] codes over rings</em> to <em>[with patch, needs review] codes over rings</em>
</li>
</ul>
TicketwdjSun, 18 Oct 2009 20:00:54 GMT
https://trac.sagemath.org/ticket/6452#comment:5
https://trac.sagemath.org/ticket/6452#comment:5
<p>
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.
</p>
TicketdgordonFri, 30 Oct 2009 01:46:14 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:6
https://trac.sagemath.org/ticket/6452#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketmhansenSat, 31 Oct 2009 07:48:59 GMTstatus, summary changed
https://trac.sagemath.org/ticket/6452#comment:7
https://trac.sagemath.org/ticket/6452#comment:7
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] codes over rings</em> to <em>[with patch, needs work] codes over rings</em>
</li>
</ul>
<p>
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.
</p>
<p>
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.
</p>
TicketwdjTue, 17 Nov 2009 00:22:53 GMTcc set
https://trac.sagemath.org/ticket/6452#comment:8
https://trac.sagemath.org/ticket/6452#comment:8
<ul>
<li><strong>cc</strong>
<em>cesarnda@…</em> added
</li>
</ul>
<p>
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.
</p>
<p>
Does this mean that the code will not be accepted?
</p>
TicketwdjTue, 22 Dec 2009 12:05:08 GMTupstream set
https://trac.sagemath.org/ticket/6452#comment:9
https://trac.sagemath.org/ticket/6452#comment:9
<ul>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:7" title="Comment 7">mhansen</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
<p>
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.
</p>
</blockquote>
<p>
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.
</p>
<p>
I've emailed Cesar and not gotten any response about the memory leak issues.
</p>
<p>
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.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/6452#comment:10
https://trac.sagemath.org/ticket/6452#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/6452#comment:11
https://trac.sagemath.org/ticket/6452#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/6452#comment:12
https://trac.sagemath.org/ticket/6452#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/6452#comment:13
https://trac.sagemath.org/ticket/6452#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketvdelecroixSun, 13 Sep 2015 22:49:24 GMTcommit, branch set
https://trac.sagemath.org/ticket/6452#comment:14
https://trac.sagemath.org/ticket/6452#comment:14
<ul>
<li><strong>commit</strong>
set to <em>1177056cb4942b0ce938a30537357bcb07f1bf19</em>
</li>
<li><strong>branch</strong>
set to <em>public/6452</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
I updated a git branch with the patch provided + some corrections. It is not yet in final stage but not far from it!
</p>
<p>
Vincent
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2d0668135b680d2fd59c9916221a475bf0819665"><span class="icon"></span>2d06681</a></td><td><code>new ring codes patch - wdj</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f162b9bd07df0a2fb51a6808f810771c098b24fb"><span class="icon"></span>f162b9b</a></td><td><code>Trac 6452: fix imports</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=eec91dd8fed3da6b337aedb6dcb63fd66bf026a4"><span class="icon"></span>eec91dd</a></td><td><code>Trac 6452: some doc formatting</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1177056cb4942b0ce938a30537357bcb07f1bf19"><span class="icon"></span>1177056</a></td><td><code>Trac 6452: fix some issues in the code</code>
</td></tr></table>
TicketvdelecroixSun, 13 Sep 2015 22:51:28 GMTcc, milestone changed
https://trac.sagemath.org/ticket/6452#comment:15
https://trac.sagemath.org/ticket/6452#comment:15
<ul>
<li><strong>cc</strong>
<em>dlucas</em> <em>jsrn</em> added
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-6.9</em>
</li>
</ul>
TicketvdelecroixSun, 13 Sep 2015 22:54:35 GMTdescription, summary changed
https://trac.sagemath.org/ticket/6452#comment:16
https://trac.sagemath.org/ticket/6452#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/6452?action=diff&version=16">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] codes over rings</em> to <em>Codes over rings</em>
</li>
</ul>
TicketjsrnMon, 14 Sep 2015 14:58:55 GMT
https://trac.sagemath.org/ticket/6452#comment:17
https://trac.sagemath.org/ticket/6452#comment:17
<p>
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?
</p>
<p>
Some concrete complaints:
</p>
<ul><li><code>gen_mat</code> should (nowadays) be <code>generator_matrix</code>.
</li><li>The class has many non-hidden-but-actually-private-and-stupidly-named fields
<code>self.codeSet</code>, <code>self.minimum</code>, etc. They should be renamed and start with an underscore.
</li><li><code>next(self)</code> is not the way we implement iterators, AFAIK.
</li><li>The name <code>RingCode</code> is not sensible, since only <code>ZZ/mZZ</code> is supported.
</li><li>The mathematical object of such a code is a free <code>ZZ/mZZ</code> module. Shouldn't
this be reflected by some parent/category magic in <code>__init__</code>?
</li><li><code>__latex__</code> is wrong: it says "Linear code".
</li><li>English is bad in some texts, e.g. for <code>length()</code>, a "the" is missing.
</li><li>What's the point of <code>spanning_codewords</code>? The nomenclature is not used in
<code>LinearCode</code>, and function just returns the rows of the generator matrix
anyway.
</li></ul><p>
On a broader design level: I dislike that tons of computation is done at <code>__init__</code>, 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.
</p>
<p>
For instance, I think that e.g. the cardinality of such a code can be relatively easily computed without tabulating the entire code.
</p>
<p>
The design of ring codes should also think the new (well, almost-accepted) <code>Encoder</code> and <code>Decoder</code> structure into it: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18376" title="enhancement: New encoding structure for linear codes (closed: fixed)">#18376</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/18813" title="enhancement: New decoding structure for linear codes (closed: fixed)">#18813</a>.
</p>
<p>
Note that I did not run or test the code -- I just looked at it.
</p>
TicketvdelecroixMon, 14 Sep 2015 15:55:59 GMT
https://trac.sagemath.org/ticket/6452#comment:18
https://trac.sagemath.org/ticket/6452#comment:18
<p>
Thanks for having a look. (disclaimer: I actually only ended up here because of <a class="ext-link" href="http://ask.sagemath.org/question/29424/liner-code-over-integerring/"><span class="icon"></span>this question on ask</a>).
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:17" title="Comment 17">jsrn</a>:
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
Nothing I guess. But it is already something and it seems to be done efficiently.
</p>
<blockquote class="citation">
<p>
Some concrete complaints:
</p>
<ul><li>The mathematical object of such a code is a free <code>ZZ/mZZ</code> module. Shouldn't
this be reflected by some parent/category magic in <code>__init__</code>?
</li></ul></blockquote>
<p>
Nope. It is not necessarily free. The submodule of <code>(ZZ/4ZZ)</code> generated by <code>2</code> is <strong>not</strong> free.
</p>
<blockquote class="citation">
<p>
On a broader design level: I dislike that tons of computation is done at <code>__init__</code>, 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.
</p>
</blockquote>
<p>
I guess it would be reasonable to turn it into a function or method.
</p>
<blockquote class="citation">
<p>
For instance, I think that e.g. the cardinality of such a code can be relatively easily computed without tabulating the entire code.
</p>
</blockquote>
<p>
True. It would basically be equivalent to implement a generalized echelon form for matrices over <code>ZZ/nZZ</code> that give you a "pseudo-basis" of submodules of <code>(ZZ/nZZ)^r</code>. I have no idea where to find such algorithm.
</p>
<blockquote class="citation">
<p>
The design of ring codes should also think the new (well, almost-accepted) <code>Encoder</code> and <code>Decoder</code> structure into it: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18376" title="enhancement: New encoding structure for linear codes (closed: fixed)">#18376</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/18813" title="enhancement: New decoding structure for linear codes (closed: fixed)">#18813</a>.
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
Note that I did not run or test the code -- I just looked at it.
</p>
</blockquote>
<p>
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.
</p>
<p>
Vincent
</p>
TicketjsrnTue, 15 Sep 2015 07:33:21 GMT
https://trac.sagemath.org/ticket/6452#comment:19
https://trac.sagemath.org/ticket/6452#comment:19
<blockquote class="citation">
<p>
Nothing I guess. But it is already something and it seems to be done efficiently.
</p>
</blockquote>
<p>
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.
</p>
<p>
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.
</p>
<blockquote class="citation">
<p>
Nope. It is not necessarily free. The submodule of <code>(ZZ/4ZZ)</code> generated by <code>2</code> is <strong>not</strong> free.
</p>
</blockquote>
<p>
No of course you're right that it's not -- the word "free" slipped in there by mistake. But it *is* a module.
</p>
<blockquote class="citation">
<p>
I guess it would be reasonable to turn it into a function or method.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
True. It would basically be equivalent to implement a generalized echelon form for matrices over <code>ZZ/nZZ</code> that give you a "pseudo-basis" of submodules of <code>(ZZ/nZZ)^r</code>. I have no idea where to find such algorithm.
</p>
</blockquote>
<p>
It's interesting: I'll think more on this. For instance, would the Hermite Normal form be sufficient?
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
You are right, it would be nice to support codes over <code>ZZ/mZZ</code>. 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 ;-)
</p>
TicketvdelecroixFri, 02 Oct 2015 02:48:35 GMT
https://trac.sagemath.org/ticket/6452#comment:20
https://trac.sagemath.org/ticket/6452#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:19" title="Comment 19">jsrn</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
True. It would basically be equivalent to implement a generalized echelon form for matrices over <code>ZZ/nZZ</code> that give you a "pseudo-basis" of submodules of <code>(ZZ/nZZ)^r</code>. I have no idea where to find such algorithm.
</p>
</blockquote>
<p>
It's interesting: I'll think more on this. For instance, would the Hermite Normal form be sufficient?
</p>
</blockquote>
<p>
I don't think that it is enough to determine the structure. An example of a problem is if <code>R=ZZ/4ZZ</code> and a matrix of the form
</p>
<pre class="wiki">2 * *
0 2 *
0 0 2
</pre><p>
If you have a vector which is a sum of its row with coefficients <code>0</code> or <code>2</code> then the leading coefficient vanish... and you lose the nice Hermite form!
</p>
<p>
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 <code>R^r</code> where <code>R = ZZ/nZZ</code> is actually of the form <code>R / (I1) + R / (I2) + ... + R / (Ik)</code> for some ideals <code>I1</code>, ..., <code>Ik</code>. These ideals are basically the product <code>SAT</code> (which is diagonal) and the decomposition is explicitly given by <code>T</code> (my source and notations from <a class="ext-link" href="https://en.wikipedia.org/wiki/Smith_normal_form"><span class="icon"></span>wikipedia</a>).
</p>
TicketjsrnFri, 02 Oct 2015 22:33:56 GMT
https://trac.sagemath.org/ticket/6452#comment:21
https://trac.sagemath.org/ticket/6452#comment:21
<p>
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 :-)
</p>
TicketvdelecroixFri, 02 Oct 2015 22:53:42 GMT
https://trac.sagemath.org/ticket/6452#comment:22
https://trac.sagemath.org/ticket/6452#comment:22
<p>
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.
</p>
<p>
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...
</p>
<p>
Since this is more about submodules of <code>(ZZ/nZZ)^r</code> I am not sure it should go at all inside <code>sage.codings</code>. I would rather put it in <code>sage.modules</code>. And (as I already told you), it would be better to factorize more between <code>sage.modules</code> and <code>sage.codings</code> when the code is <strong>only</strong> given by a generator matrix. So, for the sake of this ticket, my concrete proposal is:
</p>
<ul><li>implement submodules of <code>(ZZ/nZZ)^r</code> with a canonical form
</li><li>have an efficient iterator
</li></ul><p>
If you think it is not too far from the original purpose of this ticket, I will modify the ticket description accordingly.
</p>
TicketjsrnFri, 02 Oct 2015 23:12:04 GMT
https://trac.sagemath.org/ticket/6452#comment:23
https://trac.sagemath.org/ticket/6452#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:22" title="Comment 22">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Nice, I didn't consider that.
</p>
<blockquote class="citation">
<p>
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...
</p>
<p>
Since this is more about submodules of <code>(ZZ/nZZ)^r</code> I am not sure it should go at all inside <code>sage.codings</code>. I would rather put it in <code>sage.modules</code>. And (as I already told you), it would be better to factorize more between <code>sage.modules</code> and <code>sage.codings</code> when the code is <strong>only</strong> given by a generator matrix. So, for the sake of this ticket, my concrete proposal is:
</p>
<ul><li>implement submodules of <code>(ZZ/nZZ)^r</code> with a canonical form
</li><li>have an efficient iterator
</li></ul><p>
If you think it is not too far from the original purpose of this ticket, I will modify the ticket description accordingly.
</p>
</blockquote>
<p>
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...)
</p>
<p>
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 <code>(ZZ/nZZ)^r</code>. But no need to get ahead of ourselves here, though...
</p>
<p>
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.
</p>
TicketvdelecroixSat, 03 Oct 2015 00:42:29 GMT
https://trac.sagemath.org/ticket/6452#comment:24
https://trac.sagemath.org/ticket/6452#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:23" title="Comment 23">jsrn</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:22" title="Comment 22">vdelecroix</a>:
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.
</p>
</blockquote>
<p>
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.
</p>
TicketvdelecroixSun, 04 Oct 2015 01:38:50 GMTstatus, description, component, summary, branch, commit changed; author set
https://trac.sagemath.org/ticket/6452#comment:25
https://trac.sagemath.org/ticket/6452#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/6452?action=diff&version=25">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Vincent Delecroix</em>
</li>
<li><strong>component</strong>
changed from <em>coding theory</em> to <em>linear algebra</em>
</li>
<li><strong>summary</strong>
changed from <em>Codes over rings</em> to <em>Submodules of (ZZ/nZZ)^r</em>
</li>
<li><strong>branch</strong>
changed from <em>public/6452</em> to <em>u/vdelecroix/6452</em>
</li>
<li><strong>commit</strong>
changed from <em>1177056cb4942b0ce938a30537357bcb07f1bf19</em> to <em>708863f5754603bbed1abe786e7f718ce1e1c782</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=708863f5754603bbed1abe786e7f718ce1e1c782"><span class="icon"></span>708863f</a></td><td><code>Trac 6452: free module over ZZ/nZZ and submodules</code>
</td></tr></table>
TicketgitSun, 04 Oct 2015 18:16:27 GMTcommit changed
https://trac.sagemath.org/ticket/6452#comment:26
https://trac.sagemath.org/ticket/6452#comment:26
<ul>
<li><strong>commit</strong>
changed from <em>708863f5754603bbed1abe786e7f718ce1e1c782</em> to <em>acd707c558799cad8348f25b3a363eea26913452</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ebb2092f8b542ddc69faf295c873a887a4f4cfbc"><span class="icon"></span>ebb2092</a></td><td><code>Trac 6452: adapt some tests to facade</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a5e3d234a5c5f508c6713b24c76a8e4d4d3bcfd3"><span class="icon"></span>a5e3d23</a></td><td><code>Trac 6452: fix a doctest</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=acd707c558799cad8348f25b3a363eea26913452"><span class="icon"></span>acd707c</a></td><td><code>Trac 6452: cleaner code + more doc</code>
</td></tr></table>
TicketgitSun, 04 Oct 2015 18:31:32 GMTcommit changed
https://trac.sagemath.org/ticket/6452#comment:27
https://trac.sagemath.org/ticket/6452#comment:27
<ul>
<li><strong>commit</strong>
changed from <em>acd707c558799cad8348f25b3a363eea26913452</em> to <em>ffbd6e833d08b51cf78c46065ac07f71f46d795d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ffbd6e833d08b51cf78c46065ac07f71f46d795d"><span class="icon"></span>ffbd6e8</a></td><td><code>Trac 6452: simplification + more tests</code>
</td></tr></table>
TicketvdelecroixSun, 04 Oct 2015 22:22:44 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/6452#comment:28
https://trac.sagemath.org/ticket/6452#comment:28
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/6452?action=diff&version=28">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-6.10</em>
</li>
</ul>
<p>
For the iterator, see <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/19345" title="enhancement: Fast lexicographic iterator for module over ZZ/nZZ (needs_work)">#19345</a>
</p>
TicketjsrnMon, 05 Oct 2015 00:23:10 GMT
https://trac.sagemath.org/ticket/6452#comment:29
https://trac.sagemath.org/ticket/6452#comment:29
<p>
Great work Vincent!
</p>
<p>
Just to be sure: is this "In review"? You made many changes but didn't change the state of "needs review".
</p>
<p>
I will look at it in detail later, and when I'm sure it's ready. But in any case, some preliminary remarks:
</p>
<ul><li>Could you explain to me (reviewer) the reason for the patch in the category
files? Something with you using the <code>Facade</code> in a previously unthought case.
Is this related to the <code>Free</code>-thing below?
</li></ul><ul><li><code>FreeModule_ambient_IntegerModRing.span</code> never uses its <code>check</code> argument.
</li></ul><ul><li>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.
</li></ul><p>
Generally, it looks pretty good though.
</p>
TicketvdelecroixMon, 05 Oct 2015 01:06:24 GMT
https://trac.sagemath.org/ticket/6452#comment:30
https://trac.sagemath.org/ticket/6452#comment:30
<p>
Hi,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6452#comment:29" title="Comment 29">jsrn</a>:
</p>
<blockquote class="citation">
<p>
Great work Vincent!
</p>
</blockquote>
<p>
Thanks ;-)
</p>
<blockquote class="citation">
<p>
Just to be sure: is this "In review"? You made many changes but didn't change the state of "needs review".
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
I will look at it in detail later, and when I'm sure it's ready. But in any case, some preliminary remarks:
</p>
<ul><li>Could you explain to me (reviewer) the reason for the patch in the category
files? Something with you using the <code>Facade</code> in a previously unthought case.
Is this related to the <code>Free</code>-thing below?
</li></ul></blockquote>
<p>
Nope. There is no <code>TestSuite(U).run()</code> anywhere for submodules. And this is the reason why.
</p>
<p>
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
</p>
<pre class="wiki">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
</pre><p>
So <code>U</code> is a <strong>facade</strong> for <code>F</code>. But this is currently not properly done
</p>
<pre class="wiki">sage: U in Sets().Facade()
False
</pre><p>
I did it for the submodules over <code>ZZ/nZZ</code>. I will fix it later on for the other base rings as well and add some <code>TestSuite</code>.
</p>
<p>
There are many generic tests in category (that are automatically run with the <code>TestSuite</code> thing) but some of them do not care about facades. In particulal the <code>_test_zero</code> and <code>_test_one</code> that I modified.
</p>
<blockquote class="citation">
<ul><li><code>FreeModule_ambient_IntegerModRing.span</code> never uses its <code>check</code> argument.
</li></ul></blockquote>
<p>
True. I did it for compatibility with the other <code>span</code> functions. Maybe I could remove it.
</p>
<blockquote class="citation">
<ul><li>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.
</li></ul></blockquote>
<p>
Without this nothing can be computed (number of generators, cardinality). Note that I postponed the <code>_lift</code> argument computation.
</p>
TicketvdelecroixMon, 05 Oct 2015 01:08:51 GMT
https://trac.sagemath.org/ticket/6452#comment:31
https://trac.sagemath.org/ticket/6452#comment:31
<p>
Note that in the other functions there is a <code>already_echelonized</code> function that precisely prevent any computation (assuming that the fed data is in good shape). Perhaps we can add a <code>already_schmidt_reduced</code> argument?
</p>
TicketvdelecroixMon, 05 Oct 2015 01:56:20 GMT
https://trac.sagemath.org/ticket/6452#comment:32
https://trac.sagemath.org/ticket/6452#comment:32
<p>
About facade sets, you can read the documentation of <code>sage.categories.sets_cat.Sets.SubcategoryMethods.Facade</code>.
</p>
TicketvdelecroixMon, 05 Oct 2015 02:01:34 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:33
https://trac.sagemath.org/ticket/6452#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
And I just notice that the other submodules are actually <strong>not</strong> facade sets... I should definitely follow the same convention!
</p>
TicketgitMon, 05 Oct 2015 03:37:43 GMTcommit changed
https://trac.sagemath.org/ticket/6452#comment:34
https://trac.sagemath.org/ticket/6452#comment:34
<ul>
<li><strong>commit</strong>
changed from <em>ffbd6e833d08b51cf78c46065ac07f71f46d795d</em> to <em>96ead16e9e3a3236e024d94d671a61eca56078ea</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=59ab945d983a57c5e9676767c21094facb0e5ff3"><span class="icon"></span>59ab945</a></td><td><code>Trac 6452: free modules over ZZ/nZZ and submodules</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=96ead16e9e3a3236e024d94d671a61eca56078ea"><span class="icon"></span>96ead16</a></td><td><code>Trac 6452: fix a doctest</code>
</td></tr></table>
TicketvdelecroixMon, 05 Oct 2015 03:39:03 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:35
https://trac.sagemath.org/ticket/6452#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Warning: this is a forced push (branch restarted from zero)
</p>
<p>
Disclaimer: since I had to get rid of facades it did not make sense to just revert all what I did before
</p>
<p>
Now, no worries about facades... they do not appear anymore. Needs review again.
</p>
<p>
Vincent
</p>
TicketvdelecroixMon, 07 Dec 2015 21:25:32 GMT
https://trac.sagemath.org/ticket/6452#comment:36
https://trac.sagemath.org/ticket/6452#comment:36
<p>
(ping)
</p>
TicketchapotonTue, 12 Jul 2016 09:59:50 GMT
https://trac.sagemath.org/ticket/6452#comment:37
https://trac.sagemath.org/ticket/6452#comment:37
<p>
there is an old-style print somewhere, see bot report
</p>
TicketchapotonFri, 29 Jul 2016 06:59:35 GMTstatus, milestone changed; work_issues set
https://trac.sagemath.org/ticket/6452#comment:38
https://trac.sagemath.org/ticket/6452#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>old-style print</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.10</em> to <em>sage-7.4</em>
</li>
</ul>
TicketchapotonTue, 05 Mar 2019 10:17:52 GMTstatus, commit, branch changed; work_issues deleted
https://trac.sagemath.org/ticket/6452#comment:39
https://trac.sagemath.org/ticket/6452#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
<li><strong>commit</strong>
changed from <em>96ead16e9e3a3236e024d94d671a61eca56078ea</em> to <em>c93a30add9a6cfb66197558ba0261b566d022bb4</em>
</li>
<li><strong>work_issues</strong>
<em>old-style print</em> deleted
</li>
<li><strong>branch</strong>
changed from <em>u/vdelecroix/6452</em> to <em>public/ticket/6452</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=3e33bcb2b59c56c205419b1191955467cee6d334"><span class="icon"></span>3e33bcb</a></td><td><code>Merge branch 'u/vdelecroix/6452' in 8.7.b6</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=c93a30add9a6cfb66197558ba0261b566d022bb4"><span class="icon"></span>c93a30a</a></td><td><code>fix for py3</code>
</td></tr></table>
TicketchapotonTue, 05 Mar 2019 10:18:07 GMTmilestone changed
https://trac.sagemath.org/ticket/6452#comment:40
https://trac.sagemath.org/ticket/6452#comment:40
<ul>
<li><strong>milestone</strong>
changed from <em>sage-7.4</em> to <em>sage-8.8</em>
</li>
</ul>
TicketchapotonTue, 05 Mar 2019 12:52:23 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:41
https://trac.sagemath.org/ticket/6452#comment:41
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketchapotonThu, 07 Mar 2019 20:33:46 GMTstatus changed
https://trac.sagemath.org/ticket/6452#comment:42
https://trac.sagemath.org/ticket/6452#comment:42
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
this need a python3 refreshment, to avoid cmp and long
</p>
Ticket