Opened 7 years ago
Closed 6 years ago
#16347 closed enhancement (fixed)
Wilson's constructions of OA with 2 truncated groups
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorial designs  Keywords:  
Cc:  vdelecroix, knsam, dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  0175134 (Commits)  Commit:  0175134767948882f3d8c2ea0a612161ed3d4154 
Dependencies:  #16373  Stopgaps: 
Description (last modified by )
Heeeeeeeere it is ! The new construction !
As a result, the MOLS table really took a lifetime to fill. This is fixed by caching the OA that Sage can build, a new feature from #16460.
Nathann
Change History (51)
comment:1 Changed 7 years ago by
 Branch set to u/ncohen/16347
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit set to 9fefb55ae381228affcfa085d6814fef6e8dd1bf
comment:3 Changed 7 years ago by
 Commit changed from 9fefb55ae381228affcfa085d6814fef6e8dd1bf to 00ee241a234506c6dfade78b97ce445c0d3b87b1
comment:4 Changed 7 years ago by
 Component changed from combinatorics to combinatorial designs
comment:5 Changed 7 years ago by
 Dependencies changed from #16295 to #16295, #16391
With this updated patch, we only have one version of wilson_construction
which can handle 0,1 or 2 truncated columns. It can actually handle much more situations that will appear in new constructions I am writing these days. I think that it is a much cleaner code :)
The two function which look for decomposition of integers are left as they are, they are still useful : they find sets of parameters with which the new wilson_construction
function is to be fed.
Nathann
comment:6 Changed 7 years ago by
 Commit changed from 00ee241a234506c6dfade78b97ce445c0d3b87b1 to a4554f5c90ea6a4fee0a170b2fb8a862b21df724
Branch pushed to git repo; I updated commit sha1. New commits:
90a72bd  trac #16370: OA(k,n) strongly regular graphs

395458f  trac #16391: Helper functions for OA constructions

0ed318e  trac #16391: Merged with 6.3.beta2

f86d187  trac #16391: small improvement

d954b93  trac #16391: Independent Set problem with a LP

c1bb903  trac #16347: Merged with #16391

a4554f5  trac #16347: Genelarized Wilson construction

comment:7 Changed 7 years ago by
 Description modified (diff)
comment:8 Changed 7 years ago by
 Dependencies changed from #16295, #16391 to #16295, #16391, #16373
comment:9 Changed 7 years ago by
 Dependencies changed from #16295, #16391, #16373 to #16391, #16373
comment:10 Changed 7 years ago by
 Commit changed from a4554f5c90ea6a4fee0a170b2fb8a862b21df724 to 2e463514ceb2fb48d3c6fdc2a3391055bfafe373
comment:11 Changed 7 years ago by
 Description modified (diff)
comment:12 followup: ↓ 13 Changed 7 years ago by
 Status changed from needs_review to needs_info
Hi Nathann,
I do not like the fact that we would have to cache everything. Could we instead cache the construction? In other words, have a function
@cached_function def orthogonal_array_construction(n): r""" Return a triple `(k,f,args)` such that `k` is the maximum value such that Sage knows how to build a `OA(k,n)` and `f(*args)` actually return this `OA(k,n)`. """
Advantages:
 that function can be use to speed up both boolean and designs answers of
orthogonal_array
.  we can remove the current cache from
find_wilson_decomposition*
andTD_find_product_decomposition
 it might be used later on to draw the tree of constructions.
I am not sure it is feasible, but without thinking too much, it looks like a good solution.
Vincent
comment:13 in reply to: ↑ 12 Changed 7 years ago by
Yo !
I do not like the fact that we would have to cache everything.
Could you have missed the 10 000 posts about a new flag for the @cached_method decorator ?
Could we instead cache the construction? In other words, have a function
@cached_function def orthogonal_array_construction(n): r""" Return a triple `(k,f,args)` such that `k` is the maximum value such that Sage knows how to build a `OA(k,n)` and `f(*args)` actually return this `OA(k,n)`. """
You should not compute the largest k if you do not need to. If your function takes both k and n as an argument then it is Volker's idea.
It actually isn't a bad idea, if not for the fact that there is no reason why we should go that far to implement a caching mechanism in combinat.designs while the caching mechanism has nothing to do with designs.
The "clean/proper" solution is to implement a real caching mechanism for designs which takes k,n as input and answer accordingly, by only storing for each n the largest k that has been built so far, and the smallest k such that it has been proved that no OA(k,n) could built so far.
This is what I want to do eventually, but I first wanted to get the actual constructions in ..... This is not a definitive solution but it is not the moment to implement a caching mechanism either... There are features to get in, really ...
Nathann
P.S. : When I say eventually I do not say "in two years". I say > as soon as all the current patches are merged into Sage, along with the 4 constructions I have been keeping on my hard drive waiting for all these patches to be reviewed.
comment:14 Changed 7 years ago by
 Status changed from needs_info to needs_review
comment:15 Changed 7 years ago by
Oh, I forgot something : the other solution is of course to implement a @cached_method_with_conditions decorator which can filter the input.
Nathann
comment:16 Changed 7 years ago by
It is now implemented in #16353 but Volker introduced a notion of morality in computer science and it seems that one is not allowed to write a function that could be used for possibly dark deeds.
Nathann
comment:17 followup: ↓ 18 Changed 7 years ago by
I actually developed the same idea as yours while thinking a bit more about it. What we want to cache is something like n > (k1,OA,k2)
where OA
is a OA(k1,n) and k2
is such that Sage does not know how to compute OA(k2,n). And this feature looks very specific to design and I do not see how a decorator can handle that nicely.
So, if you are willing to use these @cached_method everywhere or even the one you wrote in #16353, there is a need for a big TODO saying that it is here for quickanddirty speedup.
So let's not talk to much about caching right now, I will look at the construction.
Vincent
comment:18 in reply to: ↑ 17 Changed 7 years ago by
Yo !
I actually developed the same idea as yours while thinking a bit more about it. What we want to cache is something like
n > (k1,OA,k2)
whereOA
is a OA(k1,n) andk2
is such that Sage does not know how to compute OA(k2,n). And this feature looks very specific to design and I do not see how a decorator can handle that nicely.
Yes of course, this would be designspecific.
So, if you are willing to use these @cached_method everywhere or even the one you wrote in #16353, there is a need for a big TODO saying that it is here for quickanddirty speedup.
What was done here is quick but not dirty. We cache too much, but that's much better than not caching anything at all because all functions would become useless. What I implemented in #16353 is NOT quick and dirty, it is the most generic way to solve our problem here. Anything more would be designspecific and that's where it would actually become to be ugly, because it would just be "for our own purposes" with global variabls everywhere ....
So let's not talk to much about caching right now, I will look at the construction.
Yes, please do. But remember that there are many dependencies to this patch that have to be reviewed first.
Nathann
comment:19 Changed 6 years ago by
 Dependencies changed from #16391, #16373 to #16391, #16373, #16460
comment:20 Changed 6 years ago by
 Description modified (diff)
comment:21 Changed 6 years ago by
 Dependencies changed from #16391, #16373, #16460 to #16373
Rebased on top of #16373, all in one commit !
Nathann
comment:22 Changed 6 years ago by
 Commit changed from 2e463514ceb2fb48d3c6fdc2a3391055bfafe373 to 004833af803033e08e71011d4e69462de8909283
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
8704b9c  trac #16361: merge updated #16461

767e091  trac #16388: Specify the values of k,n in the exceptions

a460169  merge Sage version 6.3.beta3

c365a39  trac #16388: use format for OA + specify (k,n) for BIBD

ec26ca2  trac #16388: a missing one in BIBD_from_TD

79178b6  trac #16388: (v,k,1)BIBD instead of BIBD(v,k,1)

02ecf51  trac #16361: Merged with #16388

5d4607a  trac #16361: Don't reraise the exceptions

541269b  trac #16373: merge #16361

004833a  trac #16347: Wilson's construction with two truncated groups

comment:23 Changed 6 years ago by
 Description modified (diff)
comment:24 Changed 6 years ago by
 Commit changed from 004833af803033e08e71011d4e69462de8909283 to f5069f0dd30bd698489fa047b6fdabd7b8cdaf03
Branch pushed to git repo; I updated commit sha1. New commits:
f5069f0  trac #16347: Merged with 6.3.beta4

comment:25 followup: ↓ 26 Changed 6 years ago by
 Status changed from needs_review to needs_info
Hi Nathann,
I did several things at public/16347
. But I still need to understand more the Wilson construction.
The only construction that does not belong to orthogonal_array
is the product construction (which can be seen as a particular case of wilson construction). What do you think if we move it to orthogonal_array
and remove the who_asked
stuff? It would be much more readable.
Vincent
comment:26 in reply to: ↑ 25 Changed 6 years ago by
 Branch changed from u/ncohen/16347 to public/16347
 Commit changed from f5069f0dd30bd698489fa047b6fdabd7b8cdaf03 to 1d1a476fe12b2cca3e7249b092582e2a16005380
 Status changed from needs_info to needs_review
Yo !
I did several things at
public/16347
. But I still need to understand more the Wilson construction.
I took a picture of a drawing I made, hoping that it helps.
http://www.steinertriples.fr/ncohen/tmp/photo1.jpg
The only construction that does not belong to
orthogonal_array
is the product construction (which can be seen as a particular case of wilson construction). What do you think if we move it toorthogonal_array
and remove thewho_asked
stuff? It would be much more readable.
I agree, I agree. I intended to do this at some point, but.. Well... When the current patches will be reviewed, etc etc ...
Actually, tickets #16500 and #16503 create a file named orthogonal_arrays_recursive.py
which contain many pairs construction/find_parameters. I intended to move the "find decompositions" that we already have in other files there (e.g. the one implemented here, and the find_product_decomposition
), and indeed to rewrite this last TD construction for OA.
It will be done. For everty patch that you review I will write another one that does one of these things :P
Nathann
New commits:
03c1f45  trac #16430: Small speedup for OA(None,p^c)

8e8a9f3  trac #16430: Merged with 6.3.beta4

162b83c  trac #16430: Many bugfixes

3e01acb  trac #16430: micro improvements

81b9448  trac #16430: put back the seealso

d3f9702  trac #16347: merge #16430

8bcbe6f  trac #16437: fix MOLS table doctest

49169d5  trac #16437: use is_sum_of_two_squares and fix error msg

1d1a476  trac #16347: optimize find_wilson_decomposition

comment:27 Changed 6 years ago by
 Commit changed from 1d1a476fe12b2cca3e7249b092582e2a16005380 to d93a97c5abb48f3f5067c516ca0b133b52146da4
Branch pushed to git repo; I updated commit sha1. New commits:
d93a97c  trac #16347: more docs + simplifications

comment:28 followup: ↓ 29 Changed 6 years ago by
More changes on public if you agree...
Questions:
 I do not understand why you output
n
infind_wilson_decomposition_with_one_truncated_group
 I do not understand why you output
k
infind_wilson_decomposition_with_two_truncated_groups
I would rather output (r,m,(r1,))
and (r,m,(r1,r2))
. That way the call would be uniform in orthogonal_array
... and you should decide between r1,r2
and u1,u2
.
Vincent
PS: right now I am going to teach ctypes and cython, so I will not look at it again until tonight.
comment:29 in reply to: ↑ 28 Changed 6 years ago by
Yo !
More changes on public if you agree...
They look good ! Except for tho things :
Finds a wilson decomposition to build an `OA(k,n)` with one truncated column
Here one can understand that the purpose of the function is to build a truncated OA....
+ Then there exists an `OA(k,rm+\sum u_i)`. This construction is a + straightforward generalization of Lemma 3.16 of [HananiBIBD]_.
It is only straightforward when one tells you what there is to find :P
 I do not understand why you output
n
infind_wilson_decomposition_with_one_truncated_group
 I do not understand why you output
k
infind_wilson_decomposition_with_two_truncated_groups
Historical resons I would say. You just changed the inputs used by Wilson's construction, I did it too before, and I did not think necessary to update the related functions ...
I would rather output
(r,m,(r1,))
and(r,m,(r1,r2))
. That way the call would be uniform inorthogonal_array
... and you should decide betweenr1,r2
andu1,u2
.
If you sleep better this way you can update them. Really it is only internal stuff, I thought that we could make them private functions at some point.. I do not care as long as the designs are produced :P
By the way, #16500 defines a find_recursive_construction
is orthogonal_array_recursive.py
which calls all recursive constructions. The plan was to move the two find_wilson_decomposition*
to this file later, and this will require to change their output again.
PS: right now I am going to teach ctypes and cython, so I will not look at it again until tonight.
Good luck ! And show them
sage cython a my_file.pyx # produces a html file whose lines are clickable
that's really cool !
Nathann
comment:30 Changed 6 years ago by
 Commit changed from d93a97c5abb48f3f5067c516ca0b133b52146da4 to 80bbb95e063a1105007ecb6fb61d1b08b34d6ca5
comment:31 Changed 6 years ago by
 Commit changed from 80bbb95e063a1105007ecb6fb61d1b08b34d6ca5 to cb67ae69db6ed23971e2ba8eceeebe1e72f714db
Branch pushed to git repo; I updated commit sha1. New commits:
cb67ae6  trac #16347: fix doctest and speedup find_wilson

comment:32 followup: ↓ 33 Changed 6 years ago by
Hi Nathann,
It is much clearer now without the who_asked
. I did a bit of speedup in find_wilson_*
and the test in latin_squares
run in 11sec instead of 17sec. Not yet marvelous but not bad. It would be nice to spend some time there as most of the time is clearly spent in looking for decompositions.
(I messed up the case of k=1
in the intermediate commit... so they are not relevant)
Vincent
comment:33 in reply to: ↑ 32 Changed 6 years ago by
Yo.
It is much clearer now without the
who_asked
. I did a bit of speedup infind_wilson_*
and the test inlatin_squares
run in 11sec instead of 17sec. Not yet marvelous but not bad. It would be nice to spend some time there as most of the time is clearly spent in looking for decompositions.(I messed up the case of
k=1
in the intermediate commit... so they are not relevant)
Several values decreased in the table of mols.
Btw, you should have opened another ticket to remove who_asked
and move functions around.
Nathann
comment:34 Changed 6 years ago by
What the hell is this find_wilson_decomposition
function ? I told you that I had already written the very same thing in #16500 !!
Nathann
comment:35 Changed 6 years ago by
Okay, could you move the last two commits to a different patch, *above* those that are aready in needs_review
?
Nathann
comment:36 Changed 6 years ago by
All right...
comment:37 followup: ↓ 38 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hi Nathann,
There is something that I do not understand. After the merge of #16430 the MOLS table gets better... but it is fake
sage: designs.orthogonal_array(8,66,existence=True) True sage: designs.orthogonal_array(8,66) Traceback (most recent call last): ... AssertionError
So please do the merge yourself from f5069f0. I will adapt the review from there.
Vincent
comment:38 in reply to: ↑ 37 ; followup: ↓ 39 Changed 6 years ago by
Yo !
So please do the merge yourself from f5069f0.
....
Now I have to fix the bugs you meet when you do a merge ?...
Nathann
comment:39 in reply to: ↑ 38 Changed 6 years ago by
Replying to ncohen:
Yo !
So please do the merge yourself from f5069f0.
....
Now I have to fix the bugs you meet when you do a merge ?...
Nope. The merge with #16430 just fails. f5069f0 is your commit before I started the review. I can dig to find what is the problem here but you should be able to find better than me what is the problem...
comment:40 Changed 6 years ago by
 Branch changed from public/16347 to u/ncohen/16347
 Commit changed from cb67ae69db6ed23971e2ba8eceeebe1e72f714db to f5069f0dd30bd698489fa047b6fdabd7b8cdaf03
 Status changed from needs_work to needs_review
Okay, here it is. There was a problem in find_wilson_decomposition_with_two_truncated_groups
, a variable was being assigned negative values.
Fixed in the updated branch which rebases history. I will also need to rewrite the branches above this one.
Nathann
P.S. : I pushed the changes on u/ncohen/16347 because pushing on the public one may have deleted commits, though you probably have them on your computer.
comment:41 Changed 6 years ago by
 Commit changed from f5069f0dd30bd698489fa047b6fdabd7b8cdaf03 to 0fa89d548f431a8929c76f3205bdb6c3779cf432
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
03c1f45  trac #16430: Small speedup for OA(None,p^c)

8e8a9f3  trac #16430: Merged with 6.3.beta4

162b83c  trac #16430: Many bugfixes

3e01acb  trac #16430: micro improvements

81b9448  trac #16430: put back the seealso

0fa89d5  trac #16347: Wilson's construction with two truncated groups

comment:42 Changed 6 years ago by
Thank you!
comment:43 followup: ↓ 44 Changed 6 years ago by
More reasonable review at public/16347bis
. If you like it enough, set to positive review.
Vincent
comment:44 in reply to: ↑ 43 ; followup: ↓ 46 Changed 6 years ago by
Yo !
More reasonable review at
public/16347bis
. If you like it enough, set to positive review.
I agree with the latest two commits but when it comes to the modifications made in find_wilson_decomposition_with_two_truncated_groups
I believe that you are really making the code harder to read for almost no improvement. You add 6 lines to replace one, and this only to avoid calling orthogonal_arrays
several times, knowing that all calls would answer instantly (they do the check that "n<=1 or k<n+1" each time).
When n
is not a prime power, I expect that orthogonal_array(n+1,n,existence=True)
is much more costly than all orthogonal_array(n+1,n_prime,existence=True)
for n_prime<n
combined (all straightforward 'no').
Really, that's not where the performance is hidden. The next patch improves things a lot, and the next patch on recursive constructions make things a lot worse. There will be profiling to do there, but really that's not where performance is to be found.
Nathann
comment:45 Changed 6 years ago by
(There are broken doctests in block_design.py
)
comment:46 in reply to: ↑ 44 Changed 6 years ago by
Replying to ncohen:
Yo !
More reasonable review at
public/16347bis
. If you like it enough, set to positive review.I agree with the latest two commits but when it comes to the modifications made in
find_wilson_decomposition_with_two_truncated_groups
I believe that you are really making the code harder to read for almost no improvement. You add 6 lines to replace one, and this only to avoid callingorthogonal_arrays
several times, knowing that all calls would answer instantly (they do the check that "n<=1 or k<n+1" each time).When
n
is not a prime power, I expect thatorthogonal_array(n+1,n,existence=True)
is much more costly than allorthogonal_array(n+1,n_prime,existence=True)
forn_prime<n
combined (all straightforward 'no').Really, that's not where the performance is hidden. The next patch improves things a lot, and the next patch on recursive constructions make things a lot worse. There will be profiling to do there, but really that's not where performance is to be found.
Then, why after the commit is it 30% faster to construct the MOLS table?
EDIT: and I have no doctest error.
Vincent
comment:47 Changed 6 years ago by
Here are the timings I got
old timing before the branch cut (at 0fa89d5)
sage t long latin_squares.py [36 tests, 17.83 s]
new timings after the branch cut (at 828ff22)
sage t long latin_squares.py [36 tests, 15.00 s]
comment:48 Changed 6 years ago by
Right right it's faster this way, sorry for what I said. I find it weird, but still, it is faster O_o
Nathann
comment:49 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
Sorry, it was my fault again for the doctests too. Positive review then, thank you for your help !
Nathann
comment:50 Changed 6 years ago by
 Branch changed from u/ncohen/16347 to public/16347bis
 Commit changed from 0fa89d548f431a8929c76f3205bdb6c3779cf432 to 0175134767948882f3d8c2ea0a612161ed3d4154
comment:51 Changed 6 years ago by
 Branch changed from public/16347bis to 0175134767948882f3d8c2ea0a612161ed3d4154
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
trac #16241: useless if condition in MOLS constructor
trac #16241: Merged with updated #16235
trac #16236: Five mutually orthogonal latin squares of order 12
trac #16236: Merged with updated #16241
trac #16236: Broken doctests
trac #16236: Merged with updated #16241
trac #16236: Merged with #16272
trac #16295 : Faster is_orthogonal_array
trac #16295: Doctests and review
trac #16347: Wilson's constructions of OA with 2 truncated groups