Opened 6 years ago

Closed 5 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) Commit: 0175134767948882f3d8c2ea0a612161ed3d4154
Dependencies: #16373 Stopgaps:

Description (last modified by 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

Change History (51)

comment:1 Changed 6 years ago by ncohen

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

comment:2 Changed 6 years ago by git

  • Commit set to 9fefb55ae381228affcfa085d6814fef6e8dd1bf

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

9fb0f62trac #16241: useless if condition in MOLS constructor
67ab2d2trac #16241: Merged with updated #16235
e655b36trac #16236: Five mutually orthogonal latin squares of order 12
b516266trac #16236: Merged with updated #16241
f5339fatrac #16236: Broken doctests
2d7da8atrac #16236: Merged with updated #16241
973b926trac #16236: Merged with #16272
37681e2trac #16295 : Faster is_orthogonal_array
994324etrac #16295: Doctests and review
9fefb55trac #16347: Wilson's constructions of OA with 2 truncated groups

comment:3 Changed 6 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:

fc6de73trac #16295: Merged with 6.3.beta1
b9f8b03trac #16295: bugfix in wilson's construction
00ee241trac #16347: Wilson's constructions of OA with 2 truncated groups

comment:4 Changed 6 years ago by ncohen

  • Component changed from combinatorics to combinatorial designs

comment:5 Changed 6 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 6 years ago by git

  • Commit changed from 00ee241a234506c6dfade78b97ce445c0d3b87b1 to a4554f5c90ea6a4fee0a170b2fb8a862b21df724

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

90a72bdtrac #16370: OA(k,n) strongly regular graphs
395458ftrac #16391: Helper functions for OA constructions
0ed318etrac #16391: Merged with 6.3.beta2
f86d187trac #16391: small improvement
d954b93trac #16391: Independent Set problem with a LP
c1bb903trac #16347: Merged with #16391
a4554f5trac #16347: Genelarized Wilson construction

comment:7 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:8 Changed 6 years ago by ncohen

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

comment:9 Changed 6 years ago by ncohen

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

comment:10 Changed 6 years ago by git

  • Commit changed from a4554f5c90ea6a4fee0a170b2fb8a862b21df724 to 2e463514ceb2fb48d3c6fdc2a3391055bfafe373

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

f969003trac #16356: MOLS for n=18,57,154,276,298,342
20ef216trac #16361: OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76)
dcf5843trac #16373: OA(18,273), OA(12,474), OA(33,993)
2e46351trac #16347: Merged with #16373

comment:11 Changed 6 years ago by vdelecroix

  • Description modified (diff)

comment:12 follow-up: Changed 6 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)`.
    """

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

comment:13 in reply to: ↑ 12 Changed 6 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 6 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:15 Changed 6 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 6 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: Changed 6 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 6 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 6 years ago by ncohen

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

comment:20 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:21 Changed 6 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 6 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:

8704b9ctrac #16361: merge updated #16461
767e091trac #16388: Specify the values of k,n in the exceptions
a460169merge Sage version 6.3.beta3
c365a39trac #16388: use format for OA + specify (k,n) for BIBD
ec26ca2trac #16388: a missing one in BIBD_from_TD
79178b6trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)
02ecf51trac #16361: Merged with #16388
5d4607atrac #16361: Don't re-raise the exceptions
541269btrac #16373: merge #16361
004833atrac #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:

f5069f0trac #16347: Merged with 6.3.beta4

comment:25 follow-up: 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.

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:

03c1f45trac #16430: Small speedup for OA(None,p^c)
8e8a9f3trac #16430: Merged with 6.3.beta4
162b83ctrac #16430: Many bugfixes
3e01acbtrac #16430: micro improvements
81b9448trac #16430: put back the seealso
d3f9702trac #16347: merge #16430
8bcbe6ftrac #16437: fix MOLS table doctest
49169d5trac #16437: use is_sum_of_two_squares and fix error msg
1d1a476trac #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:

d93a97ctrac #16347: more docs + simplifications

comment:28 follow-up: 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:

b83dd74trac #16347: author comment
80bbb95trac #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:

cb67ae6trac #16347: fix doctest and speedup find_wilson

comment:32 follow-up: 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

comment:36 Changed 5 years ago by vdelecroix

All right...

comment:37 follow-up: 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: 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

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

03c1f45trac #16430: Small speedup for OA(None,p^c)
8e8a9f3trac #16430: Merged with 6.3.beta4
162b83ctrac #16430: Many bugfixes
3e01acbtrac #16430: micro improvements
81b9448trac #16430: put back the seealso
0fa89d5trac #16347: Wilson's construction with two truncated groups

comment:42 Changed 5 years ago by vdelecroix

Thank you!

comment:43 follow-up: 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: 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

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

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:

828ff22trac #16437: cut the branches in W. dec. with two trunc. blocks
8ebd21btrac #16347: use is_sum_of_squares_pyx instead of two_squares
0175134trac #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.