Sage: Ticket #16500: New recursive constructions of Orthogonal Arrays
https://trac.sagemath.org/ticket/16500
<p>
Here they are ! They have been sitting on my HD for a long time <code>:-P</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16500
Trac 1.1.6ncohenThu, 19 Jun 2014 15:22:41 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:1
https://trac.sagemath.org/ticket/16500#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenThu, 19 Jun 2014 15:33:50 GMTbranch set
https://trac.sagemath.org/ticket/16500#comment:2
https://trac.sagemath.org/ticket/16500#comment:2
<ul>
<li><strong>branch</strong>
set to <em>u/ncohen/16500</em>
</li>
</ul>
TicketgitThu, 19 Jun 2014 15:34:00 GMTcommit set
https://trac.sagemath.org/ticket/16500#comment:3
https://trac.sagemath.org/ticket/16500#comment:3
<ul>
<li><strong>commit</strong>
set to <em>70f7046fea49d3ae47cfd3670a9c53f34791e462</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=004833af803033e08e71011d4e69462de8909283"><span class="icon"></span>004833a</a></td><td><code>trac #16347: Wilson's construction with two truncated groups</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f5069f0dd30bd698489fa047b6fdabd7b8cdaf03"><span class="icon"></span>f5069f0</a></td><td><code>trac #16347: Merged with 6.3.beta4</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f182d3691892b0b1cdde8f4ab61df26845eb3e8b"><span class="icon"></span>f182d36</a></td><td><code>trac #16499: Cheap speedup in the OA recursive constructions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=70f7046fea49d3ae47cfd3670a9c53f34791e462"><span class="icon"></span>70f7046</a></td><td><code>trac #16500: New recursive constructions of Orthogonal Arrays</code>
</td></tr></table>
TicketvdelecroixThu, 19 Jun 2014 21:20:52 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:4
https://trac.sagemath.org/ticket/16500#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
EDIT: deleted comment as I messed up ticket numbers...
</p>
TicketvdelecroixThu, 19 Jun 2014 21:29:43 GMT
https://trac.sagemath.org/ticket/16500#comment:5
https://trac.sagemath.org/ticket/16500#comment:5
<p>
(Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16500#comment:4" title="Comment 4">comment:4</a>) sorry, this comment was for <a class="closed ticket" href="https://trac.sagemath.org/ticket/16430" title="enhancement: Small speedup for OA(None,p^c) (closed: fixed)">#16430</a>. Not this one!!
</p>
TicketvdelecroixThu, 19 Jun 2014 21:29:58 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:6
https://trac.sagemath.org/ticket/16500#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenWed, 25 Jun 2014 13:58:18 GMT
https://trac.sagemath.org/ticket/16500#comment:7
https://trac.sagemath.org/ticket/16500#comment:7
<p>
Rebased on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/16499" title="enhancement: Cheap speedup in the OA recursive constructions (closed: fixed)">#16499</a>. But....
</p>
<pre class="wiki">sage -t --long latin_squares.py
[40 tests, 35.08 s]
</pre><p>
<code>T_T</code>
</p>
<p>
Nathann
</p>
TicketgitWed, 25 Jun 2014 13:58:34 GMTcommit changed
https://trac.sagemath.org/ticket/16500#comment:8
https://trac.sagemath.org/ticket/16500#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>70f7046fea49d3ae47cfd3670a9c53f34791e462</em> to <em>770a28da24236a2b13f905eab3d827e0fbfe34d8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0fa89d548f431a8929c76f3205bdb6c3779cf432"><span class="icon"></span>0fa89d5</a></td><td><code>trac #16347: Wilson's construction with two truncated groups</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=828ff220b83ce8427025bebe42bbc3aaa21ac28b"><span class="icon"></span>828ff22</a></td><td><code>trac #16437: cut the branches in W. dec. with two trunc. blocks</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8ebd21be12c81b751a7f09067221bef01014b705"><span class="icon"></span>8ebd21b</a></td><td><code>trac #16347: use is_sum_of_squares_pyx instead of two_squares</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0175134767948882f3d8c2ea0a612161ed3d4154"><span class="icon"></span>0175134</a></td><td><code>trac #16347: doc + simplifications</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9ff5062f8d005f19bcdfabf1f9ea65a11856da0b"><span class="icon"></span>9ff5062</a></td><td><code>trac #16423: Table of MOLS from the handbook and comparison with Sage</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e64be9845ccf9a763bc6b89dcb6530e9962bbe92"><span class="icon"></span>e64be98</a></td><td><code>trac #16423: tiny code improvement and alignment</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e948cf64a435f48206b3f46ff9693201c5675ed5"><span class="icon"></span>e948cf6</a></td><td><code>trac #16423: Aligning the alignment</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0a7d853bf758ac7abce1acfe54e18c5ea784d21f"><span class="icon"></span>0a7d853</a></td><td><code>trac #16423: Broken doctests</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b3293519d314c2bd98c8074a4bd24f1535d92247"><span class="icon"></span>b329351</a></td><td><code>trac #16499: Cheap speedup in the OA recursive constructions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=770a28da24236a2b13f905eab3d827e0fbfe34d8"><span class="icon"></span>770a28d</a></td><td><code>trac #16500: New recursive constructions of Orthogonal Arrays</code>
</td></tr></table>
TicketvdelecroixWed, 25 Jun 2014 14:40:45 GMT
https://trac.sagemath.org/ticket/16500#comment:9
https://trac.sagemath.org/ticket/16500#comment:9
<p>
Hi Nathann,
</p>
<p>
Stupid questions to start:
</p>
<ul><li>It would be nice to have references! You provide <code>[AC07]_</code> for <code>construction_3_4</code> but that's all.
</li><li>Why you did not move <code>product</code>, <code>one_truncated_group</code> and <code>two_trucated_group</code> in the recursive construction?
</li><li>Why not put the cache only for <code>find_recursive_construction</code>? (less cached function and less function calls)
</li></ul><p>
Vicent
</p>
TicketncohenWed, 25 Jun 2014 14:49:15 GMT
https://trac.sagemath.org/ticket/16500#comment:10
https://trac.sagemath.org/ticket/16500#comment:10
<p>
Yo !
</p>
<p>
I updated the "find" functions a bit. Nothing smart, just common sense, and the <code>MOLS_table</code> function is fast again. Yeepeeeeeeeeee !!! <code>:-P</code>
</p>
<blockquote class="citation">
<ul><li>It would be nice to have references! You provide <code>[AC07]_</code> for <code>construction_3_4</code> but that's all.
</li></ul></blockquote>
<p>
Ahahahah. I had nothing else <code>:-P</code>
</p>
<p>
I tried to reverse-engineer the construction from the theorem's claim, and when I was not able too I asked Julian R. Abel for a hint. This being said, the explanations I give in the docstring are more or less like a proof.
</p>
<blockquote class="citation">
<ul><li>Why you did not move <code>product</code>, <code>one_truncated_group</code> and <code>two_trucated_group</code> in the recursive construction?
</li></ul></blockquote>
<p>
Because I thought that it would be abusing your kindness. I waste my health implementing those things, but I still try to makes patches somehow readable so that reviewing them will not be hell for you. I can add a commit for that if you don't mind. As I told you by email, "this is in the plan" <code>:-P</code>
</p>
<blockquote class="citation">
<ul><li>Why not put the cache only for <code>find_recursive_construction</code>? (less cached function and less function calls)
</li></ul></blockquote>
<p>
Because this function returns both OA and True/False answers. The <code>find_*</code> functions I cached only return immutable stuff.
</p>
<p>
Nathann
</p>
TicketgitWed, 25 Jun 2014 14:51:22 GMTcommit changed
https://trac.sagemath.org/ticket/16500#comment:11
https://trac.sagemath.org/ticket/16500#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>770a28da24236a2b13f905eab3d827e0fbfe34d8</em> to <em>a67c04f13bd0aa2b46e6998d2b996437f342470c</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=a67c04f13bd0aa2b46e6998d2b996437f342470c"><span class="icon"></span>a67c04f</a></td><td><code>trac #16500: New recursive constructions of Orthogonal Arrays</code>
</td></tr></table>
TicketvdelecroixWed, 25 Jun 2014 15:13:22 GMT
https://trac.sagemath.org/ticket/16500#comment:12
https://trac.sagemath.org/ticket/16500#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16500#comment:10" title="Comment 10">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>Why you did not move <code>product</code>, <code>one_truncated_group</code> and <code>two_trucated_group</code> in the recursive construction?
</li></ul></blockquote>
<p>
Because I thought that it would be abusing your kindness. I waste my health implementing those things, but I still try to makes patches somehow readable so that reviewing them will not be hell for you. I can add a commit for that if you don't mind. As I told you by email, "this is in the plan" <code>:-P</code>
</p>
</blockquote>
<p>
Ok. Will see that later. I postponed to <a class="closed ticket" href="https://trac.sagemath.org/ticket/16535" title="enhancement: get rid of who_asked parameter in combinatorial design and move Wilson ... (closed: fixed)">#16535</a> if you agree.
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>Why not put the cache only for <code>find_recursive_construction</code>? (less cached function and less function calls)
</li></ul></blockquote>
<p>
Because this function returns both OA and True/False answers. The <code>find_*</code> functions I cached only return immutable stuff.
</p>
</blockquote>
<p>
But why not having <code>orthogonal_array</code> implements the three lines that are right now in <code>find_recursive_construction</code>? My main concern is about readability. I would prefer
</p>
<pre class="wiki">@cached_method
def find_recursive_construction(k,n):
for find_c in [find_construction_3_3,
find_construction_3_4,
find_construction_3_5,
find_construction_3_6]:
res = find_c(k,n)
if res: return res
</pre><p>
That way:
</p>
<ul><li>you still have the freedom to update <code>find_recursive_construction</code> without touching <code>orthogonal_array</code>
</li><li>you keep an eye on who did what with the cache
</li><li>you perform the work of adapting your answer only in <code>orthogonal_array</code>
</li><li>if you changed your mind about the syntax <code>existence=True</code> and such you will not have to touch to <code>find_recursive_construction</code>
</li><li>the file <code>orthogonal_array_recursive.py</code> will look like a "dynamical" database in the very same way that <code>database.py</code> is a static one
</li></ul><p>
Vincent
</p>
TicketncohenWed, 25 Jun 2014 15:25:17 GMT
https://trac.sagemath.org/ticket/16500#comment:13
https://trac.sagemath.org/ticket/16500#comment:13
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Ok. Will see that later. I postponed to <a class="closed ticket" href="https://trac.sagemath.org/ticket/16535" title="enhancement: get rid of who_asked parameter in combinatorial design and move Wilson ... (closed: fixed)">#16535</a> if you agree.
</p>
</blockquote>
<p>
I will have to rebase what is currently above this patch, then.
</p>
<p>
Well.... does not matter...
</p>
<blockquote class="citation">
<p>
But why not having <code>orthogonal_array</code> implements the three lines that are right now in <code>find_recursive_construction</code>?
</p>
</blockquote>
<p>
Oh, you mean only the part that actually creates the design ? Yeah, why not !...
</p>
<p>
I will add a commit for that in a second.
</p>
<p>
Nathann
</p>
TicketgitWed, 25 Jun 2014 15:32:52 GMTcommit changed
https://trac.sagemath.org/ticket/16500#comment:14
https://trac.sagemath.org/ticket/16500#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>a67c04f13bd0aa2b46e6998d2b996437f342470c</em> to <em>41c50d5a256d9e746d8acfb33a4ff7c58e05789b</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=41c50d5a256d9e746d8acfb33a4ff7c58e05789b"><span class="icon"></span>41c50d5</a></td><td><code>trac #16500: Simplified find_recursive_construction</code>
</td></tr></table>
TicketvdelecroixThu, 26 Jun 2014 09:31:17 GMT
https://trac.sagemath.org/ticket/16500#comment:15
https://trac.sagemath.org/ticket/16500#comment:15
<p>
Hi,
</p>
<p>
small commit at <code>u/vdelecroix/16500</code>
</p>
<p>
Be careful that a truncated OA is <strong>not</strong> an incomplete OA. In truncated OA you removed points in columns whereas in incomplete OA you have less blocks than an OA (but columns are not changed)... it is very confusing to read your doc. And moreover you use block or column indifferently but it would be better to have a unique name for that.
</p>
<p>
In the doc of the construction 3.4 there is
</p>
<pre class="wiki">- If there exists an `OA(k,m+r+1)` the column of size `s` is truncated in
order to intersect `B_0`.
- If there exists an `OA(k,m+r+1)`, the last column must not intersect `B_0`
</pre><p>
which is contradictory!
</p>
<p>
The rest is fine except that there is no need to use linear programming to build an oval, see <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/16552" title="enhancement: oval in finite projective plane (needs_work)">#16552</a>.
</p>
<p>
Vincent
</p>
TicketvdelecroixThu, 26 Jun 2014 09:32:29 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:16
https://trac.sagemath.org/ticket/16500#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketncohenThu, 26 Jun 2014 09:58:34 GMT
https://trac.sagemath.org/ticket/16500#comment:17
https://trac.sagemath.org/ticket/16500#comment:17
<p>
Yo !
</p>
<blockquote class="citation">
<p>
small commit at <code>u/vdelecroix/16500</code>
</p>
</blockquote>
<p>
Looks good !
</p>
<blockquote class="citation">
<p>
Be careful that a truncated OA is <strong>not</strong> an incomplete OA.
</p>
</blockquote>
<p>
Arg yes yes, I always mix the two words <code>^^;</code>
</p>
<p>
And moreover you use block or column indifferently but it would be better to have a unique name for that.
</p>
<p>
Do you mean "column or group" ? There are <code>n^2</code> blocks in an <code>OA(k,n)</code> but <code>k</code> columns.
</p>
<blockquote class="citation">
<p>
In the doc of the construction 3.4 there is
</p>
<pre class="wiki">- If there exists an `OA(k,m+r+1)` the column of size `s` is truncated in
order to intersect `B_0`.
- If there exists an `OA(k,m+r+1)`, the last column must not intersect `B_0`
</pre><p>
which is contradictory!
</p>
</blockquote>
<p>
I don't se how <code>O_o</code>
</p>
<blockquote class="citation">
<p>
The rest is fine except that there is no need to use linear programming to build an oval, see <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/16552" title="enhancement: oval in finite projective plane (needs_work)">#16552</a>.
</p>
</blockquote>
<p>
Oh ? Cool. Free ovals ! <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketgitThu, 26 Jun 2014 09:59:07 GMTcommit changed
https://trac.sagemath.org/ticket/16500#comment:18
https://trac.sagemath.org/ticket/16500#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>41c50d5a256d9e746d8acfb33a4ff7c58e05789b</em> to <em>e1992ce4c0a145ce8fd61fae0abe0809cd6ff173</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=e1992ce4c0a145ce8fd61fae0abe0809cd6ff173"><span class="icon"></span>e1992ce</a></td><td><code>trac #16500: doc + speedup</code>
</td></tr></table>
TicketncohenThu, 26 Jun 2014 09:59:23 GMT
https://trac.sagemath.org/ticket/16500#comment:19
https://trac.sagemath.org/ticket/16500#comment:19
<p>
What exactly needs work ?
</p>
<p>
Nathann
</p>
TicketvdelecroixThu, 26 Jun 2014 10:03:03 GMT
https://trac.sagemath.org/ticket/16500#comment:20
https://trac.sagemath.org/ticket/16500#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16500#comment:19" title="Comment 19">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What exactly needs work ?
</p>
</blockquote>
<p>
the doc of construction 3.4
</p>
TicketncohenThu, 26 Jun 2014 10:04:50 GMT
https://trac.sagemath.org/ticket/16500#comment:21
https://trac.sagemath.org/ticket/16500#comment:21
<p>
Then please answer my question above : what is wrong in those sentences ?
</p>
<p>
Nathann
</p>
TicketncohenThu, 26 Jun 2014 10:05:25 GMT
https://trac.sagemath.org/ticket/16500#comment:22
https://trac.sagemath.org/ticket/16500#comment:22
<p>
Oh. Right.
</p>
TicketgitThu, 26 Jun 2014 10:08:09 GMTcommit changed
https://trac.sagemath.org/ticket/16500#comment:23
https://trac.sagemath.org/ticket/16500#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>e1992ce4c0a145ce8fd61fae0abe0809cd6ff173</em> to <em>697dd0ca8284485897b051015af74b385c345fb4</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=697dd0ca8284485897b051015af74b385c345fb4"><span class="icon"></span>697dd0c</a></td><td><code>trac #16500: Typoes in the doc</code>
</td></tr></table>
TicketncohenThu, 26 Jun 2014 10:11:49 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:24
https://trac.sagemath.org/ticket/16500#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixThu, 26 Jun 2014 10:21:56 GMTstatus changed
https://trac.sagemath.org/ticket/16500#comment:25
https://trac.sagemath.org/ticket/16500#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
This one was much easier once the Wilson construction is understood!
</p>
<p>
Do you already did the even more general construction from Brouwer-Rees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?
</p>
<p>
Vincent
</p>
TicketvdelecroixThu, 26 Jun 2014 10:22:12 GMTreviewer set
https://trac.sagemath.org/ticket/16500#comment:26
https://trac.sagemath.org/ticket/16500#comment:26
<ul>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
TicketncohenThu, 26 Jun 2014 10:24:28 GMT
https://trac.sagemath.org/ticket/16500#comment:27
https://trac.sagemath.org/ticket/16500#comment:27
<p>
Yo !
</p>
<blockquote class="citation">
<p>
This one was much easier once the Wilson construction is understood!
</p>
</blockquote>
<p>
Yep yep. That's what I will remember of design theory. Deadly scary stuff that becomes totally straightforward once you pay attention to it.
</p>
<p>
Still, a lot of stuff remains deadly scary in the field <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Do you already did the even more general construction from Brouwer-Rees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?
</p>
</blockquote>
<p>
Now yet, but I will have to. What scares me is not the implementation of the construction, but how to properly write the input part of the function <code>T_T</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 26 Jun 2014 10:30:52 GMT
https://trac.sagemath.org/ticket/16500#comment:28
https://trac.sagemath.org/ticket/16500#comment:28
<blockquote class="citation">
<blockquote class="citation">
<p>
This one was much easier once the Wilson construction is understood!
</p>
</blockquote>
</blockquote>
<p>
Some smarter comment: I believe that it is thanks to work like the one we do that we can get to understand such things. That's how it happened to me with LP : I had to implement very basic things 1000 times for Sage, and in the end I find myself understanding the basics properly, which would have NEVER happened if I had just had a book in front of me. Or even if it was in Sage's code.
</p>
<p>
When you implement Sage stuff you are forced to spend time on things you would quickly look at otherwise.
</p>
<p>
Nathann
</p>
TicketvbraunThu, 26 Jun 2014 19:37:07 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16500#comment:29
https://trac.sagemath.org/ticket/16500#comment:29
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/16500</em> to <em>697dd0ca8284485897b051015af74b385c345fb4</em>
</li>
</ul>
Ticket