Opened 6 years ago
Closed 6 years ago
#16500 closed enhancement (fixed)
New recursive constructions of Orthogonal Arrays
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorial designs  Keywords:  
Cc:  vdelecroix, knsam  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  697dd0c (Commits)  Commit:  697dd0ca8284485897b051015af74b385c345fb4 
Dependencies:  #16499  Stopgaps: 
Description
Here they are ! They have been sitting on my HD for a long time :P
Nathann
Change History (29)
comment:1 Changed 6 years ago by
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Branch set to u/ncohen/16500
comment:3 Changed 6 years ago by
 Commit set to 70f7046fea49d3ae47cfd3670a9c53f34791e462
comment:4 followup: ↓ 5 Changed 6 years ago by
 Status changed from needs_review to needs_info
EDIT: deleted comment as I messed up ticket numbers...
comment:5 in reply to: ↑ 4 Changed 6 years ago by
comment:6 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:7 Changed 6 years ago by
comment:8 Changed 6 years ago by
 Commit changed from 70f7046fea49d3ae47cfd3670a9c53f34791e462 to 770a28da24236a2b13f905eab3d827e0fbfe34d8
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
0fa89d5  trac #16347: Wilson's construction with two truncated groups

828ff22  trac #16437: cut the branches in W. dec. with two trunc. blocks

8ebd21b  trac #16347: use is_sum_of_squares_pyx instead of two_squares

0175134  trac #16347: doc + simplifications

9ff5062  trac #16423: Table of MOLS from the handbook and comparison with Sage

e64be98  trac #16423: tiny code improvement and alignment

e948cf6  trac #16423: Aligning the alignment

0a7d853  trac #16423: Broken doctests

b329351  trac #16499: Cheap speedup in the OA recursive constructions

770a28d  trac #16500: New recursive constructions of Orthogonal Arrays

comment:9 followup: ↓ 10 Changed 6 years ago by
Hi Nathann,
Stupid questions to start:
 It would be nice to have references! You provide
[AC07]_
forconstruction_3_4
but that's all.  Why you did not move
product
,one_truncated_group
andtwo_trucated_group
in the recursive construction?  Why not put the cache only for
find_recursive_construction
? (less cached function and less function calls)
Vicent
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 6 years ago by
Yo !
I updated the "find" functions a bit. Nothing smart, just common sense, and the MOLS_table
function is fast again. Yeepeeeeeeeeee !!! :P
 It would be nice to have references! You provide
[AC07]_
forconstruction_3_4
but that's all.
Ahahahah. I had nothing else :P
I tried to reverseengineer 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.
 Why you did not move
product
,one_truncated_group
andtwo_trucated_group
in the recursive construction?
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" :P
 Why not put the cache only for
find_recursive_construction
? (less cached function and less function calls)
Because this function returns both OA and True/False answers. The find_*
functions I cached only return immutable stuff.
Nathann
comment:11 Changed 6 years ago by
 Commit changed from 770a28da24236a2b13f905eab3d827e0fbfe34d8 to a67c04f13bd0aa2b46e6998d2b996437f342470c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a67c04f  trac #16500: New recursive constructions of Orthogonal Arrays

comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 6 years ago by
Replying to ncohen:
 Why you did not move
product
,one_truncated_group
andtwo_trucated_group
in the recursive construction?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"
:P
Ok. Will see that later. I postponed to #16535 if you agree.
 Why not put the cache only for
find_recursive_construction
? (less cached function and less function calls)Because this function returns both OA and True/False answers. The
find_*
functions I cached only return immutable stuff.
But why not having orthogonal_array
implements the three lines that are right now in find_recursive_construction
? My main concern is about readability. I would prefer
@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
That way:
 you still have the freedom to update
find_recursive_construction
without touchingorthogonal_array
 you keep an eye on who did what with the cache
 you perform the work of adapting your answer only in
orthogonal_array
 if you changed your mind about the syntax
existence=True
and such you will not have to touch tofind_recursive_construction
 the file
orthogonal_array_recursive.py
will look like a "dynamical" database in the very same way thatdatabase.py
is a static one
Vincent
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Yo !
Ok. Will see that later. I postponed to #16535 if you agree.
I will have to rebase what is currently above this patch, then.
Well.... does not matter...
But why not having
orthogonal_array
implements the three lines that are right now infind_recursive_construction
?
Oh, you mean only the part that actually creates the design ? Yeah, why not !...
I will add a commit for that in a second.
Nathann
comment:14 Changed 6 years ago by
 Commit changed from a67c04f13bd0aa2b46e6998d2b996437f342470c to 41c50d5a256d9e746d8acfb33a4ff7c58e05789b
Branch pushed to git repo; I updated commit sha1. New commits:
41c50d5  trac #16500: Simplified find_recursive_construction

comment:15 followup: ↓ 17 Changed 6 years ago by
Hi,
small commit at u/vdelecroix/16500
Be careful that a truncated OA is not 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.
In the doc of the construction 3.4 there is
 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`
which is contradictory!
The rest is fine except that there is no need to use linear programming to build an oval, see #16552.
Vincent
comment:16 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:17 in reply to: ↑ 15 Changed 6 years ago by
Yo !
small commit at
u/vdelecroix/16500
Looks good !
Be careful that a truncated OA is not an incomplete OA.
Arg yes yes, I always mix the two words ^^;
And moreover you use block or column indifferently but it would be better to have a unique name for that.
Do you mean "column or group" ? There are n^2
blocks in an OA(k,n)
but k
columns.
In the doc of the construction 3.4 there is
 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`which is contradictory!
I don't se how O_o
The rest is fine except that there is no need to use linear programming to build an oval, see #16552.
Oh ? Cool. Free ovals ! :D
Nathann
comment:18 Changed 6 years ago by
 Commit changed from 41c50d5a256d9e746d8acfb33a4ff7c58e05789b to e1992ce4c0a145ce8fd61fae0abe0809cd6ff173
Branch pushed to git repo; I updated commit sha1. New commits:
e1992ce  trac #16500: doc + speedup

comment:19 followup: ↓ 20 Changed 6 years ago by
What exactly needs work ?
Nathann
comment:20 in reply to: ↑ 19 Changed 6 years ago by
comment:21 Changed 6 years ago by
Then please answer my question above : what is wrong in those sentences ?
Nathann
comment:22 Changed 6 years ago by
Oh. Right.
comment:23 Changed 6 years ago by
 Commit changed from e1992ce4c0a145ce8fd61fae0abe0809cd6ff173 to 697dd0ca8284485897b051015af74b385c345fb4
Branch pushed to git repo; I updated commit sha1. New commits:
697dd0c  trac #16500: Typoes in the doc

comment:24 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:25 followup: ↓ 27 Changed 6 years ago by
 Status changed from needs_review to positive_review
This one was much easier once the Wilson construction is understood!
Do you already did the even more general construction from BrouwerRees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?
Vincent
comment:26 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
comment:27 in reply to: ↑ 25 ; followup: ↓ 28 Changed 6 years ago by
Yo !
This one was much easier once the Wilson construction is understood!
Yep yep. That's what I will remember of design theory. Deadly scary stuff that becomes totally straightforward once you pay attention to it.
Still, a lot of stuff remains deadly scary in the field :P
Do you already did the even more general construction from BrouwerRees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?
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 T_T
Nathann
comment:28 in reply to: ↑ 27 Changed 6 years ago by
This one was much easier once the Wilson construction is understood!
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.
When you implement Sage stuff you are forced to spend time on things you would quickly look at otherwise.
Nathann
comment:29 Changed 6 years ago by
 Branch changed from u/ncohen/16500 to 697dd0ca8284485897b051015af74b385c345fb4
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16347: Wilson's construction with two truncated groups
trac #16347: Merged with 6.3.beta4
trac #16499: Cheap speedup in the OA recursive constructions
trac #16500: New recursive constructions of Orthogonal Arrays