Opened 7 years ago
Closed 7 years ago
#16347 closed enhancement (fixed)
Wilson's constructions of OA with 2 truncated groups
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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, GitHub, GitLab) | 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 follow-up: ↓ 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 follow-up: ↓ 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 quick-and-dirty 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 design-specific.
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 quick-and-dirty 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 design-specific 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 7 years ago by
- Dependencies changed from #16391, #16373 to #16391, #16373, #16460
comment:20 Changed 7 years ago by
- Description modified (diff)
comment:21 Changed 7 years ago by
- Dependencies changed from #16391, #16373, #16460 to #16373
Rebased on top of #16373, all in one commit !
Nathann
comment:22 Changed 7 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 re-raise the exceptions
|
541269b | trac #16373: merge #16361
|
004833a | trac #16347: Wilson's construction with two truncated groups
|
comment:23 Changed 7 years ago by
- Description modified (diff)
comment:24 Changed 7 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 follow-up: ↓ 26 Changed 7 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.
EDIT: more precisely, all constructions in mutually_orthogonal_latin_squares
and transversal_design
comes from the database except the product construction. As your Wilson construction can be used for the product we can move all recursive constructions in orthogonal_array
and remove the who_asked
argument in all these functions.
Vincent
comment:26 in reply to: ↑ 25 Changed 7 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 7 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 follow-up: ↓ 29 Changed 7 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 7 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 7 years ago by
- Commit changed from d93a97c5abb48f3f5067c516ca0b133b52146da4 to 80bbb95e063a1105007ecb6fb61d1b08b34d6ca5
comment:31 Changed 7 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 follow-up: ↓ 33 Changed 7 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 7 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 7 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 7 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 7 years ago by
All right...
comment:37 follow-up: ↓ 38 Changed 7 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 ; follow-up: ↓ 39 Changed 7 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 7 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 7 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 7 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 7 years ago by
Thank you!
comment:43 follow-up: ↓ 44 Changed 7 years ago by
More reasonable review at public/16347-bis
. If you like it enough, set to positive review.
Vincent
comment:44 in reply to: ↑ 43 ; follow-up: ↓ 46 Changed 7 years ago by
Yo !
More reasonable review at
public/16347-bis
. 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 7 years ago by
(There are broken doctests in block_design.py
)
comment:46 in reply to: ↑ 44 Changed 7 years ago by
Replying to ncohen:
Yo !
More reasonable review at
public/16347-bis
. 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 7 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 7 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 7 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 7 years ago by
- Branch changed from u/ncohen/16347 to public/16347-bis
- Commit changed from 0fa89d548f431a8929c76f3205bdb6c3779cf432 to 0175134767948882f3d8c2ea0a612161ed3d4154
comment:51 Changed 7 years ago by
- Branch changed from public/16347-bis 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