Opened 5 years ago

Closed 5 years ago

# Wilson's constructions of OA with 2 truncated groups

Reported by: Owned by: ncohen major sage-6.3 combinatorial designs vdelecroix, knsam, dimpase Nathann Cohen Vincent Delecroix N/A 0175134 (Commits) 0175134767948882f3d8c2ea0a612161ed3d4154 #16373

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

### comment:1 Changed 5 years ago by ncohen

• Branch set to u/ncohen/16347
• Status changed from new to needs_review

### comment:2 Changed 5 years ago by git

• Commit set to 9fefb55ae381228affcfa085d6814fef6e8dd1bf

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

 ​9fb0f62 trac #16241: useless if condition in MOLS constructor ​67ab2d2 trac #16241: Merged with updated #16235 ​e655b36 trac #16236: Five mutually orthogonal latin squares of order 12 ​b516266 trac #16236: Merged with updated #16241 ​f5339fa trac #16236: Broken doctests ​2d7da8a trac #16236: Merged with updated #16241 ​973b926 trac #16236: Merged with #16272 ​37681e2 trac #16295 : Faster is_orthogonal_array ​994324e trac #16295: Doctests and review ​9fefb55 trac #16347: Wilson's constructions of OA with 2 truncated groups

### comment:3 Changed 5 years ago by git

• Commit changed from 9fefb55ae381228affcfa085d6814fef6e8dd1bf to 00ee241a234506c6dfade78b97ce445c0d3b87b1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​fc6de73 trac #16295: Merged with 6.3.beta1 ​b9f8b03 trac #16295: bugfix in wilson's construction ​00ee241 trac #16347: Wilson's constructions of OA with 2 truncated groups

### comment:4 Changed 5 years ago by ncohen

• Component changed from combinatorics to combinatorial designs

### comment:5 Changed 5 years ago by ncohen

• 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 5 years ago by git

• 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 5 years ago by ncohen

• Description modified (diff)

### comment:8 Changed 5 years ago by ncohen

• Dependencies changed from #16295, #16391 to #16295, #16391, #16373

### comment:9 Changed 5 years ago by ncohen

• Dependencies changed from #16295, #16391, #16373 to #16391, #16373

### comment:10 Changed 5 years ago by git

• Commit changed from a4554f5c90ea6a4fee0a170b2fb8a862b21df724 to 2e463514ceb2fb48d3c6fdc2a3391055bfafe373

Branch pushed to git repo; I updated commit sha1. New commits:

 ​f969003 trac #16356: MOLS for n=18,57,154,276,298,342 ​20ef216 trac #16361: OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76) ​dcf5843 trac #16373: OA(18,273), OA(12,474), OA(33,993) ​2e46351 trac #16347: Merged with #16373

### comment:11 Changed 5 years ago by vdelecroix

• Description modified (diff)

### comment:12 follow-up: ↓ 13 Changed 5 years ago by vdelecroix

• 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).
"""


• 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* and TD_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 5 years ago by ncohen

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 5 years ago by ncohen

• Status changed from needs_info to needs_review

### comment:15 Changed 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by vdelecroix

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 5 years ago by ncohen

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) 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.

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 5 years ago by ncohen

• Dependencies changed from #16391, #16373 to #16391, #16373, #16460

### comment:20 Changed 5 years ago by ncohen

• Description modified (diff)

### comment:21 Changed 5 years ago by ncohen

• Dependencies changed from #16391, #16373, #16460 to #16373

Rebased on top of #16373, all in one commit !

Nathann

### comment:22 Changed 5 years ago by git

• 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 5 years ago by ncohen

• Description modified (diff)

### comment:24 Changed 5 years ago by git

• 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 5 years ago by vdelecroix

• 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

Last edited 5 years ago by vdelecroix (previous) (diff)

### comment:26 in reply to: ↑ 25 Changed 5 years ago by ncohen

• 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.

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.

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
Last edited 5 years ago by ncohen (previous) (diff)

### comment:27 Changed 5 years ago by git

• 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 5 years ago by vdelecroix

More changes on public if you agree...

Questions:

• I do not understand why you output n in find_wilson_decomposition_with_one_truncated_group
• I do not understand why you output k in find_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 5 years ago by ncohen

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 in find_wilson_decomposition_with_one_truncated_group
• I do not understand why you output k in find_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 in orthogonal_array... and you should decide between r1,r2 and u1,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 5 years ago by git

• Commit changed from d93a97c5abb48f3f5067c516ca0b133b52146da4 to 80bbb95e063a1105007ecb6fb61d1b08b34d6ca5

Branch pushed to git repo; I updated commit sha1. New commits:

 ​b83dd74 trac #16347: author comment ​80bbb95 trac #16347: get rid of who_asked

### comment:31 Changed 5 years ago by git

• 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 5 years ago by vdelecroix

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 5 years ago by ncohen

Yo.

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)

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 5 years ago by ncohen

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 5 years ago by ncohen

Okay, could you move the last two commits to a different patch, *above* those that are aready in needs_review ?

Nathann

All right...

### comment:37 follow-up: ↓ 38 Changed 5 years ago by vdelecroix

• 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 5 years ago by ncohen

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 5 years ago by vdelecroix

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 5 years ago by ncohen

• 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 5 years ago by git

• 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

Thank you!

### comment:43 follow-up: ↓ 44 Changed 5 years ago by vdelecroix

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 5 years ago by 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 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 5 years ago by ncohen

(There are broken doctests in block_design.py)

### comment:46 in reply to: ↑ 44 Changed 5 years ago by vdelecroix

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.

Then, why after the commit is it 30% faster to construct the MOLS table?

EDIT: and I have no doctest error.

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

### comment:47 Changed 5 years ago by vdelecroix

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 5 years ago by ncohen

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 5 years ago by ncohen

• 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 5 years ago by ncohen

• Branch changed from u/ncohen/16347 to public/16347-bis
• Commit changed from 0fa89d548f431a8929c76f3205bdb6c3779cf432 to 0175134767948882f3d8c2ea0a612161ed3d4154

New commits:

 ​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

### comment:51 Changed 5 years ago by vbraun

• Branch changed from public/16347-bis to 0175134767948882f3d8c2ea0a612161ed3d4154
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.