Wilson's constructions of OA with 2 truncated groups

[ncohen]

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

[git]

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

[git]

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

[ncohen]

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

[git]

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

[git]

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

[vdelecroix]

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* 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

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

[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

[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

[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

[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

[ncohen]

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

Nathann

[git]

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

[git]

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

​f5069f0

trac #16347: Merged with 6.3.beta4

[vdelecroix]

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

[ncohen]

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

[git]

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

​d93a97c

trac #16347: more docs + simplifications

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

[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

[git]

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

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

[git]

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

​cb67ae6

trac #16347: fix doctest and speedup find_wilson

[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

[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

[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

[ncohen]

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

Nathann

[vdelecroix]

All right...

[vdelecroix]

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

[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

[vdelecroix]

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

[ncohen]

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.

[git]

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

[vdelecroix]

Thank you!

[vdelecroix]

More reasonable review at public/16347-bis. If you like it enough, set to positive review.

Vincent

[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

[ncohen]

(There are broken doctests in block_design.py)

[vdelecroix]

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

[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]

[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

[ncohen]

Sorry, it was my fault again for the doctests too. Positive review then, thank you for your help !

Nathann

[ncohen]

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