#15310 closed enhancement (fixed)
Wilson's construction of Transversal Designs/Orthogonal Arrays/MOLS
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  
Cc:  wdj, rbeezer, brett, dimpase, vdelecroix  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  e86d26c (Commits)  Commit:  
Dependencies:  #15287, #15431  Stopgaps: 
Description (last modified by )
This ticket implements Wilson's construction of transversal designs (which are equivalent to OA and MOLS) as found in Douglas Stinson's book.
The implementation of the construction is not a very technical problem though it requires several parameters that are not obvious when the user asks for a transversal design of parameters k,n
. A function find_wilson_decomposition
thus tries to guess those parameters, and needs for that to know the values of k,n
for which Sage knows how to build a transversal design.
It can then try all possibilities, and use Wilson's construction as efficiently as possible !
Nathann
Change History (60)
comment:1 Changed 7 years ago by
 Branch set to u/ncohen/15310
 Commit set to 21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8
comment:2 Changed 7 years ago by
 Commit changed from 21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8 to 7487b62fe657ef04722f06fa5c1e7647855e4f89
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:7487b62]  Wilson's construction  find_wilson_decomposition and test of availability 
[changeset:847c7b6]  Wilson's construction  rebase on bugfix from 15287 
[changeset:59f340b]  Orthogonal arrays  doctest 
[changeset:e32c6de]  Orthogonal arrays  bugfix 
comment:3 Changed 7 years ago by
 Dependencies set to #15287
 Status changed from new to needs_review
comment:4 Changed 7 years ago by
 Description modified (diff)
comment:5 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 7 years ago by
 Commit changed from 7487b62fe657ef04722f06fa5c1e7647855e4f89 to 6abda3c9eb7fedd8b63ad135a9b04f6469ae570d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6abda3c  trac #15310: Wilson's construction of Transversal Designs

comment:7 Changed 7 years ago by
Rebased (and ready for a review :P
)
Nathann
comment:8 Changed 7 years ago by
 Cc wdj rbeezer brett dimpase added
comment:9 Changed 7 years ago by
 Commit changed from 6abda3c9eb7fedd8b63ad135a9b04f6469ae570d to effb0ac5dc265553a6c4fb7ce9a1337262f4d549
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
effb0ac  trac #15310: Wilson's construction of Transversal Designs

comment:10 Changed 7 years ago by
 Commit changed from effb0ac5dc265553a6c4fb7ce9a1337262f4d549 to 03f896c363e23a00fabf0b38b87a277354f07327
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
03f896c  trac #15310: Wilson's construction of Transversal Designs

comment:11 Changed 7 years ago by
 Cc vdelecroix added
 Dependencies changed from #15287 to #15287, #15431
comment:12 Changed 7 years ago by
 Commit changed from 03f896c363e23a00fabf0b38b87a277354f07327 to 6357236d82dd6714eb59a7e63bb22a7f02c18e88
Branch pushed to git repo; I updated commit sha1. New commits:
79ea502  trac #15431: depends on #15287

ec6c09e  trac #15431: depends on #15368

6fbef0c  trac #15431 : Construction of TD(6,12)

c87cac5  trac #15431: rebase on updated #15287

ba232b6  trac #15431: rebase on 6.2.beta6

a02aa52  trac #15431: Reviewer's remarks

4adf6b5  trac #15431: Reviewer's remark II

47ffd91  trac #15431: remove old todo

a537755  trac #15431: Back to the standard definition of TD

6357236  trac #15310: Rebase on updated #15431

comment:13 Changed 7 years ago by
 Commit changed from 6357236d82dd6714eb59a7e63bb22a7f02c18e88 to 25f5959ec5fe7ccd1479fdbdcd489cf550933c7e
Branch pushed to git repo; I updated commit sha1. New commits:
25f5959  trac #15310: Merged into 6.2.rc0

comment:14 Changed 7 years ago by
 Commit changed from 25f5959ec5fe7ccd1479fdbdcd489cf550933c7e to f23fa885ee5a080f2a8051f23f7fc9f130541849
Branch pushed to git repo; I updated commit sha1. New commits:
f23fa88  trac #15310: useless checks

comment:15 followup: ↓ 16 Changed 7 years ago by
Hi Nathann,
I am not sure I would be able to do the full review. Nevertheless, you can can speed up a lot the function find_wilson_decomposition
using the fact that if a TD(k,n) exists then we have the inequality k <= n+1
. Here is a sample version of what can be done:
def find_wilson_decomposition(k,n): # we can start from k1 since we need a TD(k+1,t) for t in range(max(1,k1),n1): u = n%t # We ensure that 1<=u and # u <= k2 since we need a TD(k,u) if u == 0 or u <= k2: continue m = n//t # k < m+2 since we need a TD(k,m) if k >= m+2: break if (transversal_design(k ,m , availability=True) and transversal_design(k ,m+1, availability=True) and transversal_design(k+1,t , availability=True) and transversal_design(k ,u , availability=True)): return k,m,t,u return False
You can check that there is no stupid call to find_wilson_decomposition
with the following
sage: from sage.combinat.designs.orthogonal_arrays import find_wilson_decomposition sage: find_wilson_decomposition(7,71) (7, 8, 8, 7) sage: find_wilson_decomposition.get_cache() # get the list of cached values ...
comment:16 in reply to: ↑ 15 Changed 7 years ago by
Yoooooooooooo !!
I am not sure I would be able to do the full review.
PLeaaaaaaaaaaase.. I swear, all the results are checked before being returned ! And the algorithms are so weird that the slightest typo would make all results wrong :P
Nevertheless, you can can speed up a lot the function
find_wilson_decomposition
using the fact that if a TD(k,n) exists then we have the inequalityk <= n+1
.
Oh ?
Here is a sample version of what can be done:
What does it change exactly ? That the TD(k,u)
is not called when the answer is obviously no ? Wouldn't we get the very same result by moving the check of TD(k,u)
to the top of the 4 tests ?
Nathann
comment:17 Changed 7 years ago by
Yeah, you are right, let's add those tests before the big if. I will do it in a second.
Nathann
comment:18 Changed 7 years ago by
What about this ?
if ( k < m+2 and k < t+3 and k < u+2 and transversal_design(k ,m , availability=True) and transversal_design(k ,m+1, availability=True) and transversal_design(k+1,t , availability=True) and transversal_design(k ,u , availability=True)): return k,m,t,u
comment:19 Changed 7 years ago by
Oh I see, you tested all of them by changing the bounds of the loops. Right. I'll change that.
Nathann
comment:20 followup: ↓ 22 Changed 7 years ago by
Why isn't it for t in range(max(1,k),n1):
in the first loop ?
comment:21 Changed 7 years ago by
 Commit changed from f23fa885ee5a080f2a8051f23f7fc9f130541849 to 62f0158c281c55523a532d5ef21c666ba9c7dc3d
Branch pushed to git repo; I updated commit sha1. New commits:
62f0158  trac #15310: cutting some branches of the exploration

comment:22 in reply to: ↑ 20 Changed 7 years ago by
Replying to ncohen:
Why isn't it
for t in range(max(1,k),n1):
in the first loop ?
My mistake. This is why I did not write a branch for that... I wanted you to check carefully!!
comment:23 Changed 7 years ago by
Well, in this direction it is not a problem :P
Nathann
comment:24 followup: ↓ 25 Changed 7 years ago by
Hi Nathann,
Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
2) The programming design with TD calling OA is very bad. In OA there is a nice EmptySetError
which has an important mathematical meaning. But if you ask for a transversal design you get instead a NotImplementedError
which is much less informative
sage: designs.orthogonal_array(6,3) # this is great Traceback (most recent call last) ... EmptySetError: No Orthogonal Array exists when k>=n+t sage: designs.transversal_design(6,3) # this is bad Traceback (most recent call last) ... NotImplementedError: I don't know how to build this Transversal Design!
In the ideal world, Sage would only return a design or raise an EmptySetError
with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. When availability=True
it would be nice to get a troolean: True (means yes), False (means no), Unknown in sage.misc.unknown
(means I do not know). And then, you might change the name availability
to existence
.
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a # long time
.
4) Could you mention the following reference as a todo
 AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
 TITLE = Making the MOLS table
 BOOKTITLE = Computational and constructive design theory
 SERIES = Math. Appl.
 VOLUME = 368
 PAGES = 67134
 PUBLISHER = Kluwer Acad. Publ., Dordrecht
 YEAR = 1996
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
Cheers, Vincent
comment:25 in reply to: ↑ 24 Changed 7 years ago by
Yo !
Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.
Ahahaha. Well you must have more background that I have then, I am jealous :P
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.
I also got word from Julian Abel that the Wilson Decomposition I implemented was not the best one, and that some variants may be useful. I copy/paste what he told me here (he probably will not mind)
I note from your list of known MOLS that you've used Wilson's theorem with 1 truncated group, but not more. The next most important variants are where there are (1) 2 truncated groups (2) 1 spike block or 1 truncated group and a spike. These variants are as follows: Theorem 1: If there are k+2 MOLS(t), and k MOLS(s) for s=g, g+1, g+2, u_1, u_2, where 0 \leq u_1, u_2 \leq t, then there are k MOLS(gt + u_1 + u_2). Theorem 2: If there are k+x MOLS(t), and k MOLS(s) for s=g, g+1, g+x, g+x, where 0 \leq u_1, u_2 \leq t, x> 0 then there are k MOLS(gt + x). Theorem 3: If there are k+x+1 MOLS(t), and k MOLS(s) for s=g, g+1, g+2, g+x, u_1, where 0 \ leq u_1 \leq t, x > 0, then there are k MOLS(gt + x + u_1). For instance, Th. 1 gives 6 MOLS for v=106 = 7. 13 + 7 + 8. Theorem 2 gives 7 MOLS(v) for v=155 = 8.19 + 3. And Theorem 3 gives 6 MOLS(v) for v=148= 7.19 + 6 + 9.
He also pointed me toward references where I can read those constructions, but I have not begun this step yet and he told me it would be hard to read. Still, it has to be done.
2) The programming design with TD calling OA is very bad. In OA there is a nice
EmptySetError
which has an important mathematical meaning. But if you ask for a transversal design you get instead aNotImplementedError
which is much less informative
How is that a result of TD calling OA ?
In the ideal world, Sage would only return a design or raise an
EmptySetError
with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. Whenavailability=True
it would be nice to get a troolean: True (means yes), False (means no), Unknown insage.misc.unknown
(means I do not know).
Well. No problem if "if Unknown" is equivalent to "if False".
And then, you might change the name
availability
toexistence
.
Could we do that on top of #12267 ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a
# long time
.
Well, I usually set #long
even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.
4) Could you mention the following reference as a todo
 AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
 TITLE = Making the MOLS table
 BOOKTITLE = Computational and constructive design theory
 SERIES = Math. Appl.
 VOLUME = 368
 PAGES = 67134
 PUBLISHER = Kluwer Acad. Publ., Dordrecht
 YEAR = 1996
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
okayokay, good idea ! I will add a commit in a second.
Nathann
comment:26 Changed 7 years ago by
 Commit changed from 62f0158c281c55523a532d5ef21c666ba9c7dc3d to d74341411288315f13da3d4383e515b884ba7440
Branch pushed to git repo; I updated commit sha1. New commits:
d743414  trac #15310: reviewer's remarks

comment:27 followup: ↓ 28 Changed 7 years ago by
Replying to ncohen:
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.
Actually, the product construction is what you are doing in #16227. You can see it as a particular case of Wilson construction.
2) The programming design with TD calling OA is very bad. In OA there is a nice
EmptySetError
which has an important mathematical meaning. But if you ask for a transversal design you get instead aNotImplementedError
which is much less informativeHow is that a result of TD calling OA ?
I would better say not calling OA appropriately. line 79
elif orthogonal_array(k,n, check = False, availability = True): ...
I still found that having half of the implementation in TD and half of the implementation in OA is very confusing.
Well. No problem if "if Unknown" is equivalent to "if False".
It is. You do not know your troolean algebra !?
And then, you might change the name
availability
toexistence
.Could we do that on top of #12267 ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.
Make sense. I will open a ticket for that.
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a
# long time
.Well, I usually set
#long
even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.
No do not worry about this.
4) Could you mention the following reference as a todo
 AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
 TITLE = Making the MOLS table
 BOOKTITLE = Computational and constructive design theory
 SERIES = Math. Appl.
 VOLUME = 368
 PAGES = 67134
 PUBLISHER = Kluwer Acad. Publ., Dordrecht
 YEAR = 1996
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
okayokay, good idea ! I will add a commit in a second.
and please, add also the references you got from Julian Abel. I guess that they are pretty similar.
Vincent
comment:28 in reply to: ↑ 27 Changed 7 years ago by
Yo !
Actually, the product construction is what you are doing in #16227. You can see it as a particular case of Wilson construction.
Oh. Cool, then. Must prove I am on the right path :D
I would better say not calling OA appropriately. line 79
elif orthogonal_array(k,n, check = False, availability = True): ...
Oh. And you want to transfer the "False" answer which means "that stuff does not exist" as an exception ? Then do you mind if we do that in the ticket which will change "availability" to "existence" ? It would be easier to not fix many conflicts in many patches. But it is a good idea and it will be implemented, be sure I don't say this because I don't want to do it. It *is* a good idea.
Well. No problem if "if Unknown" is equivalent to "if False".
It is. You do not know your troolean algebra !?
To me it should raise an Exception. You just cannot trust these things to do what they should.
Make sense. I will open a ticket for that.
Thanks. Add me in Cc when you do, of course :)
No do not worry about this.
Too late :P
and please, add also the references you got from Julian Abel. I guess that they are pretty similar.
Hmmm... Not now please, I will probably have more questions to ask him and right now we are exchanging email about a construction of MOLS that I cannot reproduce. I implemented quite a lot of specific constructions of MOLS/OA during the last days. Besides #16241 #16236 and #16235 I have the following ready :
~$ grep "^def " qd.py def OA_from_quasi_difference_matrix(M,G,add_col=True): def OA_from_wider_OA(OA,k): def OA_6_20(k,n,availability=False): def OA_7_21(k,n,availability=False): def OA_5_22(k,n,availability=False): def OA_7_60(k,n,availability=False): def OA_9_24(k,n,availability=False): def OA_6_26(k,n,availability=False): def OA_7_28(k,n,availability=False): def OA_6_30(k,n,availability=False): def OA_7_33(k,n,availability=False): def OA_6_34(k,n,availability=False): def OA_7_35(k,n,availability=False): def OA_10_36(k,n,availability=False): def OA_6_38(k,n,availability=False): def OA_7_39(k,n,availability=False): def OA_9_40(k,n,availability=False): def OA_10_48(k,n,availability=False): def OA_9_40b(k,n,availability=False):
Well. Except the last 3. Those are the ones we are fighting against at the moment :)
Nathann
comment:29 followup: ↓ 30 Changed 7 years ago by
I will jump in here. Julian Able's other versions of Wilson's construction are the ones discussed in the Colbourn and Dinitz reference. I was wrong about the details when I chatted with Vincent: I said they simplified when $u$ was a nice value, but your posted email from Julian reminds me that these are multiple truncations. I do not think these need to go into a first round. I would advocate getting the basic Wilson's theorem into the official Sage release and then adding more intricate variations
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
I am waiting for sage to compile, then I will get the new commit and look more closely at the code.
Here are some additional thoughts that apply to the whole TD/OA enterprise rather than just this patch (If I should be discussing these things somewhere else because they are more general comments then please let me know and point me to where to have this discussion)
 (anticipating ticket #16231) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.
 There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the nonexistence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the nonexistence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first
comment:30 in reply to: ↑ 29 ; followup: ↓ 31 Changed 7 years ago by
Replying to brett:
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
Yes. It is possible to have that in #16227: we can replace the two functions with one. But I am not sure it would be faster/clearer.
 (anticipating ticket #16231) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.
This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.
 There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the nonexistence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the nonexistence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first
Cool: look at ticket #16272. I will add those references to the description. If you have other nonexistence theorems please post them on #16272.
comment:31 in reply to: ↑ 30 ; followup: ↓ 34 Changed 7 years ago by
Yo !
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
I implemented it this way because I followed Douglas Stinson's book, which defines this construction explicitly for 1<=u.
This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.
I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like #14562 and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.
Anyway, right now I don't think that it is really a problem... There is a lot of work needing to be done, and this work is implementing constructions, any kind of constructions, in any formalism you like. We can merge everything later if we need. But really what we need right now are constructions, and nothing else.
Cool: look at ticket #16272. I will add those references to the description. If you have other nonexistence theorems please post them on #16272.
Yep, nonexistence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.
I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that :)
But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about :P
Nathann
comment:32 Changed 7 years ago by
comment:33 Changed 7 years ago by
By the way will you be in Bordeaux during July/August? ? I have no plans yet :D
Nathann
comment:34 in reply to: ↑ 31 ; followup: ↓ 35 Changed 7 years ago by
Hello,
Replying to ncohen:
This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.
I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like #14562 and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.
True. But on the other hand
 it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input
 the
EmptySetError
raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks
look at ticket #16272. I will add those references to the description. If you have other nonexistence theorems please post them on #16272.
Yep, nonexistence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.
I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that
:)
I like it. But I agree that it can be implemented later on.
But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about
:P
Nice challenge! You want it to be ready for next week?
comment:35 in reply to: ↑ 34 Changed 7 years ago by
Yo !
True. But on the other hand
 it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input
Well... Just read the constructors of each class, you will see :P
 the
EmptySetError
raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks
Yeah, probably ... But that's a very bad reason for changing the data structure :P
I like it. But I agree that it can be implemented later on.
Never implement something you don't need. And I am already breaking this rule by implementing designs. I don't have anything to do with designs. I just love them :P
Nice challenge! You want it to be ready for next week?
Ahahahahahah. Well, you have some reviews ahead of you, don't you ? :P
Nathann
comment:36 followup: ↓ 38 Changed 7 years ago by
I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure. For example incidence structures (and by extension, designs) are stored as their sets of sets. The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows
 a single place to check all known nonexistence results
 future ease in making this a class
In principle I do not mind if the constructions that you have implemented for TDs stay as they are but are wrapped by OA>TD translation TD construction followed by TDOA translation. It can be left as a possible future task to clean this up.
Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his Covering Array tables, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?
brett
p.s. how do I format the link correctly
comment:37 followup: ↓ 39 Changed 7 years ago by
 Status changed from needs_review to positive_review
Hi,
everybody: please, in a given ticket, only discuss the ticket! There is the sagedevel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
Nathann: you have to rebase #16227 above the last commit in here.
Vincent
comment:38 in reply to: ↑ 36 Changed 7 years ago by
Yo !
I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure.
For the moment I did not see the need to turn it into a class. Especially since making it a class will require many useless copies of stuff, each time you ask the class to give you its data or when you build an instance from the data (copy in each direction, for nothing).
For example incidence structures (and by extension, designs) are stored as their sets of sets.
And I like to work with list of sets indeed :P
The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows
 a single place to check all known nonexistence results
 future ease in making this a class
It is true, but if it means that implementing constructions becomes harder, this is too much to pay. Really, give it a try. Today is a holiday, and I have been implementing constructions since I woke up. It is *HARD* and painful.
Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his http://www.public.asu.edu/~ccolbou/src/tabby/catable.htmCovering Array tables, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?
I don't think so .... Designs are particularly messy in this respect :P
Nathann
P.S. : Vincent is right, let's discuss this somewhere else. On the otherhand, if you can review this ticket we can use it as a forum afterwards :D
comment:39 in reply to: ↑ 37 ; followup: ↓ 40 Changed 7 years ago by
everybody: please, in a given ticket, only discuss the ticket! There is the sagedevel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
Why are the comments lost ? The ticket still exists long afterwards !
Nathann: you have to rebase #16227 above the last commit in here.
It creates a conflict ? O_o
I thought git would handle this by itself...
Nathann
comment:40 in reply to: ↑ 39 ; followup: ↓ 41 Changed 7 years ago by
Replying to ncohen:
everybody: please, in a given ticket, only discuss the ticket! There is the sagedevel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
Why are the comments lost ? The ticket still exists long afterwards !
Nathann: you have to rebase #16227 above the last commit in here.
It creates a conflict ?
O_o
I thought git would handle this by itself...
git is not god
Automerging src/sage/combinat/designs/orthogonal_arrays.py CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py Automatic merge failed; fix conflicts and then commit the result.
comment:41 in reply to: ↑ 40 ; followup: ↓ 42 Changed 7 years ago by
git is not god
Then we should write a patch to change that.
More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.
Nathann
comment:42 in reply to: ↑ 41 ; followup: ↓ 43 Changed 7 years ago by
 Status changed from positive_review to needs_review
Replying to ncohen:
git is not god
Then we should write a patch to change that.
More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.
It was! But on the other hand there is a serious issue in #16227. The function Wilson construction and TD_product should be similar but they are not. Wilson call the transversal_design
to start the construction but you have to feed TD_product
with the designs! Why is that?
I think it would make more sense to merge the two tickets simultaneously. Would you mind if we move the changes you introduced in #16227 in this one (I can even do that by myself).
comment:43 in reply to: ↑ 42 Changed 7 years ago by
It was! But on the other hand there is a serious issue in #16227. The function Wilson construction and TD_product should be similar but they are not.
Since when are such things called serious ? :P
Besides I implemented one months after the other, so if you do not mind... :P
Wilson call the
transversal_design
to start the construction but you have to feedTD_product
with the designs! Why is that?
Because I suspect that TD_product may be useful to the users later to compute products of their own designs (not the one Sage knows) and I did not think this would happen with wilson decompsition.... If we make TD_product call the designs itself, it makes it less useful, that's all. I saw one as "internal stuff" while the other one could eventually become useful for users.
I think it would make more sense to merge the two tickets simultaneously.
Why ?
Would you mind if we move the changes you introduced in #16227 in this one (I can even do that by myself).
Well, stuff is based on the TD ticket, and I will have to deal with the conflicts later if any, so if I can avoid it ....
Nathann
comment:44 followup: ↓ 45 Changed 7 years ago by
What if both functions could be called in two ways:
1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them
2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.
Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.
comment:45 in reply to: ↑ 44 Changed 7 years ago by
Yo !
1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them
This is already done, as Sage will automatically use the product construction to see if such a design exists. When you call designs.orthogonal_array(...)
the TD product construction will be called from time to time.
2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.
Yepyep, we can make the designs be optional parameters indeed ...
Really I don't mind but I am writing construction code and there is a lot of work to do. If you want features like that, would you mind implementing them ? It is not a lot of work, you just have to add optional parameters in Wilson's construction equal to None, and if they are set to None Sage will find the designs itself otherwise it will use those that are provided.
Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.
Indeed indeed. But it is not like anybody will know that Sage can produce MOLS/OA/TD already, so we have time before the crowd complains about the missing features.. Right now I am just trying to implement what I need to create more TD/OA/MOLS, and we will have all the time in the world to create fancy features when it will be in :P
I am two constructions away from having implemented all explicit construction of length <= 80 that the Handbook provides, but they are tricky ones. Then this step will be done too, and we will have to implement the variants of Wilson's theorem.
Nathann
Vincent : is there anything I should do on this ticket ?
comment:46 followup: ↓ 47 Changed 7 years ago by
I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the TD_product
. Do not think about other users, they can think by themselves :P. I will copy/paste that on #16227.
Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.
My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.
comment:47 in reply to: ↑ 46 Changed 7 years ago by
Yo !
I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the
TD_product
. Do not think about other users, they can think by themselves :P. I will copy/paste that on #16227.
Why on earth would you want me to remove features, really ?... If this function is not meant for the users it makes no difference, and if users see it they can use it. Why do you want me to remove features ?... "for the greater good of having uniform functions that nobody sees" ?... Really guys ...
Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.
We already deal with OA. All this is being built without an OA class .... My current file contains 1735 lines of code/doc to generate OA, and all that is needed are lists of lists of integers.
My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.
Okay.
Nathann
comment:48 followup: ↓ 49 Changed 7 years ago by
Do you mind if we change wilson_construction
to TD_wilson_construction
... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!
comment:49 in reply to: ↑ 48 Changed 7 years ago by
Do you mind if we change
wilson_construction
toTD_wilson_construction
... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!
I am pretty sure a lot of people who find wilson_construction
in orthogonal_array.py
will wonder what it actually does :P
If you must absolutely change something potentially deadly that will force me to fix conflicts everywhere above, what about wilson_construction_of_TD
instead ?
Nathann
comment:50 Changed 7 years ago by
By the way I have this in my file, though two entries still do not work :/
def OA_from_quasi_difference_matrix(M,G,add_col=True): def OA_from_Vmt(m,t,V): def OA_from_wider_OA(OA,k): def _feasible_set_parameters(k,n,fk,fn,availability): def OA_6_20(k,n,availability=False): def OA_7_21(k,n,availability=False): def OA_5_22(k,n,availability=False): def OA_7_60(k,n,availability=False): def OA_9_24(k,n,availability=False): def OA_6_26(k,n,availability=False): def OA_7_28(k,n,availability=False): def OA_6_30(k,n,availability=False): def OA_7_33(k,n,availability=False): def OA_6_34(k,n,availability=False): def OA_7_35(k,n,availability=False): def OA_10_36(k,n,availability=False): def OA_6_38(k,n,availability=False): def OA_7_39(k,n,availability=False): def OA_9_40(k,n,availability=False): def OA_7_42(k,n,availability=False): def OA_7_44(k,n,availability=False): def OA_8_45(k,n,availability=False): # Broken def OA_6_46(k,n,availability=False): def OA_10_48(k,n,availability=False): def OA_8_50(k,n,availability=False): def OA_7_51(k,n,availability=False): def OA_7_52(k,n,availability=False): # Broken def OA_7_54(k,n,availability=False): def OA_8_55(k,n,availability=False): def OA_9_56(k,n,availability=False): def OA_7_62(k,n,availability=False): def OA_9_75(k,n,availability=False): def OA_11_80(k,n,availability=False): def OA_10_82(k,n,availability=False): def OA_10_100(k,n,availability=False): def OA_12_144(k,n,availability=False): def OA_12_210(k,n,availability=False):
comment:51 Changed 7 years ago by
 Commit changed from d74341411288315f13da3d4383e515b884ba7440 to 3fc79ba5be0b99e99593ff54bfa075a52cc5937c
Branch pushed to git repo; I updated commit sha1. New commits:
3fc79ba  trac #15310: Merged into 6.2.rc1

comment:52 Changed 7 years ago by
 Status changed from needs_review to positive_review
All tests pass. I am happy with this.
comment:53 Changed 7 years ago by
Thanks !
comment:54 Changed 7 years ago by
 Commit changed from 3fc79ba5be0b99e99593ff54bfa075a52cc5937c to e86d26cb8126f3e557cc6a27b1727e2055f67321
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
e86d26c  trac #15310: Merged with 6.2.rc2

comment:55 Changed 7 years ago by
 Status changed from needs_review to positive_review
Straightforward merge conflict.
comment:56 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:57 Changed 7 years ago by
Reviewer name
comment:58 Changed 7 years ago by
 Reviewers set to Vincent Delecroix
comment:59 Changed 7 years ago by
 Branch changed from u/ncohen/15310 to e86d26cb8126f3e557cc6a27b1727e2055f67321
 Resolution set to fixed
 Status changed from positive_review to closed
comment:60 Changed 6 years ago by
 Commit e86d26cb8126f3e557cc6a27b1727e2055f67321 deleted
I'm not so sure about the availability
argument. I know this is late to the game  see here for some comments. I don't see why one couldn't factor out the actual part that checks whether things are available...
New commits: