Opened 5 years ago

Closed 4 years ago

#16559 closed enhancement (fixed)

Brouwer-Van Rees version of Wilson's decomposition

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: vdelecroix, knsam, dimpase, brett Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 9bbd1f2 (Commits) Commit: 9bbd1f24e0689368b338777363ae2199c79e5c17
Dependencies: #16884 Stopgaps:

Description (last modified by ncohen)

Heeeeeere it is !

Nathann

Change History (34)

comment:1 Changed 5 years ago by ncohen

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

comment:2 Changed 5 years ago by git

  • Commit set to 30370573b908d3f1f132f1fa87ced73326e1b9b4

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

9ff5062trac #16423: Table of MOLS from the handbook and comparison with Sage
e64be98trac #16423: tiny code improvement and alignment
e948cf6trac #16423: Aligning the alignment
0a7d853trac #16423: Broken doctests
b329351trac #16499: Cheap speedup in the OA recursive constructions
a67c04ftrac #16500: New recursive constructions of Orthogonal Arrays
41c50d5trac #16500: Simplified find_recursive_construction
e1992cetrac #16500: doc + speedup
697dd0ctrac #16500: Typoes in the doc
3037057trac #16559: Brouwer-Van Rees version of Wilson's decomposition

comment:3 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Hi Nathann,

  • Could we get rid of simple_wilson_construction from #16535 in this ticket or should I open a new one?
  • You should provide at least a possibly stupid but non-trivial example of the new construction.

Vincent

comment:4 in reply to: ↑ 3 ; follow-up: Changed 5 years ago by ncohen

Yo !

  • Could we get rid of simple_wilson_construction from #16535 in this ticket or should I open a new one?

Be careful, this ticket only depends on #16500 as it was meant to be very local. If you want to touch other parts of the file you should base the changes higher in the patch stack.

  • You should provide at least a possibly stupid but non-trivial example of the new construction.

Are all applications of Wilson's theorem that we have in Sage at the moment "trivial" ? Because that function handles them all :-P

The thing is that it is not possible to use this construction for as long as incomplete_orthogonal_arrays does not handle holes of size >1.

Nathann

comment:5 Changed 5 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:6 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by vdelecroix

Replying to ncohen:

  • You should provide at least a possibly stupid but non-trivial example of the new construction.

Are all applications of Wilson's theorem that we have in Sage at the moment "trivial" ? Because that function handles them all :-P

The thing is that it is not possible to use this construction for as long as incomplete_orthogonal_arrays does not handle holes of size >1.

You can provide the OA explicitly. I mean: as it is, the function gives nothing new! Or more precisely, it does but only in principle... the only current positive effect is to slow down the Wilson construction!

I really think that it is a good thing to have. But with no application in mind it is a bit premature. I will try to build a non-already existing example from the Brouwer-Van Rees paper.

Vincent

comment:7 in reply to: ↑ 6 Changed 5 years ago by ncohen

You can provide the OA explicitly.

I can provide the OA to wilson_decomposition, but it will require a OA with holes of size >1 and for this the code will call incomplete_orthogonal_array.

I mean: as it is, the function gives nothing new! Or more precisely, it does but only in principle... the only current positive effect is to slow down the Wilson construction!

Right now it cannot help us compute new designs, indeed. Later, when we will have ways to compute holes of size >1, we will be able to use it. I don't work miracles, man. I can just implement constructions. And you can help me by making the incomplete_orthogonal_arrays function return OA with bigger holes.

I really think that it is a good thing to have. But with no application in mind it is a bit premature.

And so what ?... You refuse the patch because of that ?... What do we earn by doing that ?..

Nathann

comment:8 Changed 5 years ago by vdelecroix

You do not need a function to build an incomplete array. Here is the OA(4,6)-OA(4,2) from Horton

OA = [
[1,1,5,1],[1,2,6,2],[1,3,3,5],[1,4,4,6],[1,5,1,3],[1,6,2,4],
[2,1,2,6],[2,2,1,5],[2,3,6,1],[2,4,5,2],[2,5,3,4],[2,6,4,3],
[3,1,6,4],[3,2,5,3],[3,3,1,6],[3,4,2,5],[3,5,4,1],[3,6,3,2],
[4,1,4,5],[4,2,3,6],[4,3,5,4],[4,4,6,3],[4,5,2,2],[4,6,1,1],
[5,1,1,2],[5,2,4,4],[5,3,2,3],[5,4,3,1],
[6,1,3,3],[6,2,2,1],[6,3,4,2],[6,4,1,4]]

comment:9 Changed 5 years ago by ncohen

This is not sufficient, the holed OA must be returned by the incomplete_orthogonal_array function.

Nathann

comment:10 Changed 5 years ago by vdelecroix

Hi Nathann,

The feature is cool, the doc is especially nice but I am not comfortable by letting it goes before having more IOA. Could we try adding few examples of IOA and put this one on top?

Vincent

comment:11 Changed 5 years ago by ncohen

Let's do that, then ...

Nathann

comment:12 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:13 Changed 4 years ago by ncohen

And noooooowwwwwww that's hell to rebase -_-

comment:14 Changed 4 years ago by git

  • Commit changed from 30370573b908d3f1f132f1fa87ced73326e1b9b4 to 9afa21da1388480a4aaa78c8187a398e440680e2

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

5031aeetrac #16879: Fix the import statements
0c1893ftrac #16879: Fix the doc
6a3869dtrac #16879: speed up
d7129d6trac #16879: Trivial stuff
1979486trac #16884: Remove OA constructors (they will be turned into QDM constructors)
f23e0cftrac #16884: A database entry for Quasi-difference matrices. +doc and stuff
f074c38trac #16884: Convert OA(9,514) into a Vmt
781b168trac #16884: is_quasi_difference_matrix
15c78batrac #16884: A V(12,185) that yields a OA(11,2406)
9afa21dtrac #16559: Brouwer-Van Rees version of Wilson's decomposition

comment:15 Changed 4 years ago by ncohen

  • Dependencies changed from #16500 to #16884

Now with a real example. It is an OA that Sage cannot build yet, but I will need to do a couple of things before it is made automatic. And I am a bit scared of the performances of the future find_wilson function that will also handle the Brouwer-van Rees generalization.

Nathann

comment:16 Changed 4 years ago by git

  • Commit changed from 9afa21da1388480a4aaa78c8187a398e440680e2 to 8916046ca141a64b8c50fee198f852b812216a82

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

8916046trac #16559: Brouwer-Van Rees version of Wilson's decomposition

comment:17 Changed 4 years ago by ncohen

Here is an additional commit that gives a correct error message when incomplete_orthogonal_array cannot build what we need.

I also changed the example for the Brouwer-van Rees construction. While it works, it is a bit sad that it only gives an OA(5,256) :-PPPP

Anyway...

Nathann

comment:18 Changed 4 years ago by git

  • Commit changed from 8916046ca141a64b8c50fee198f852b812216a82 to cf1145783cc67664986ced298e0f31d4e6c1d3b4

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

cf11457trac #16559: Fixed error message for large holes and smaller example

comment:19 Changed 4 years ago by git

  • Commit changed from cf1145783cc67664986ced298e0f31d4e6c1d3b4 to 9b8ba79c4956a5962a2fc3d7491cc7ae58907511

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

9b8ba79trac #16559: Fixes reported by Julian R. Abel

comment:20 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:21 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

I got doctest failure with the development version

File "orthogonal_arrays.py", line 565, in sage.combinat.designs.orthogonal_arrays.wilson_construction
Failed example:
    OA = designs.orthogonal_array(6,11)
Expected nothing
Got:
    doctest:1: DeprecationWarning: This function will soon be removed. Use the designs.orthogonal_arrays.* functions instead
    See http://trac.sagemath.org/17034 for details.

and

File "orthogonal_arrays.py", line 567, in sage.combinat.designs.orthogonal_arrays.wilson_construction
Failed example:
    OAb = wilson_construction(OA,5,11,21,[[(5,5)]])
Exception raised:
    Traceback (most recent call last):
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 488, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 851, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.designs.orthogonal_arrays.wilson_construction[10]>", line 1, in <module>
        OAb = wilson_construction(OA,Integer(5),Integer(11),Integer(21),[[(Integer(5),Integer(5))]])
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/combinat/designs/orthogonal_arrays.py", line 615, in wilson_construction
        profile) for profile in block_profiles}
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/combinat/designs/orthogonal_arrays.py", line 615, in <dictcomp>
        profile) for profile in block_profiles}
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/combinat/designs/orthogonal_arrays.py", line 1240, in incomplete_orthogonal_array
        elif x==1 and any(uu==y and mu<=1 and lmbda==1 and k<=kk+1 for (nn,kk,lmbda,mu,uu) in QDM.get((n,1),[])):
      File "/opt/sage_flatsurf/local/lib/python2.7/site-packages/sage/combinat/designs/orthogonal_arrays.py", line 1240, in <genexpr>
        elif x==1 and any(uu==y and mu<=1 and lmbda==1 and k<=kk+1 for (nn,kk,lmbda,mu,uu) in QDM.get((n,1),[])):
    ValueError: need more than 4 values to unpack

Vincent

comment:22 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

Sorry about that. I just fixed it.

Nathann

comment:23 Changed 4 years ago by git

  • Commit changed from 9b8ba79c4956a5962a2fc3d7491cc7ae58907511 to fe62ae45eb1ce7642aa35380c8e4fc6033405f9f

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

b0419b8trac #16559: Merged with 6.4.beta6
fe62ae4trac #16559: Bugfix

comment:24 follow-up: Changed 4 years ago by vdelecroix

  • Branch changed from u/ncohen/16559 to u/vdelecroix/16559
  • Commit changed from fe62ae45eb1ce7642aa35380c8e4fc6033405f9f to 12177d8c1dd4802baa2608ae4736d805932bca5c
  • Status changed from needs_review to needs_info

Hi Nathann,

Stupid bugfix for the doc in my commit.

Do you mind if I allow to have OA=None in wilson construction and move the code from simple_wilson_construction (in find_orthogonal_array_build.py) to wilson_construction (in orthogonal_array.py). It should be fine with your next tickets, but in the future we should get rid of simple_wilson_construction.

Vincent


New commits:

12177d8trac #16559: fix documentation

comment:25 in reply to: ↑ 24 Changed 4 years ago by ncohen

Yo !

Do you mind if I allow to have OA=None in wilson construction and move the code from simple_wilson_construction (in find_orthogonal_array_build.py) to wilson_construction (in orthogonal_array.py). It should be fine with your next tickets, but in the future we should get rid of simple_wilson_construction.

No problem, this function is not very complicated at the moment anyway !

Nathann

comment:26 Changed 4 years ago by git

  • Commit changed from 12177d8c1dd4802baa2608ae4736d805932bca5c to bdd5f8b57891adf75e85c59c817669b1038172b7

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

bdd5f8btrac #16559: remove simple_wilson_construction

comment:27 Changed 4 years ago by vdelecroix

Hi Nathann,

I moved the code of simple_wilson_construction to wilson_construction. I had not enough energy to make the explanations for the Brouwer van Rees construction... so it is currently a NotImplementedError.

I am happy with the current version, but it would be better to add one line for the explanations.

Vincent

comment:28 Changed 4 years ago by vdelecroix

  • Status changed from needs_info to needs_review

comment:29 Changed 4 years ago by ncohen

Hello,

You do not have to deprecate this function, it can be removed. It is only internal stuff, not really meant to be called directly.

Nathann

comment:30 Changed 4 years ago by git

  • Commit changed from bdd5f8b57891adf75e85c59c817669b1038172b7 to 3eaf73f7cf8ba3b62710a1b1435352e746b5b33f

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

3eaf73ftrac #16559: really remove simple_wilson_construction

comment:31 Changed 4 years ago by ncohen

  • Branch changed from u/vdelecroix/16559 to public/16559
  • Commit 3eaf73f7cf8ba3b62710a1b1435352e746b5b33f deleted

I merged your two commits into one and added one with the description. If that's okay for you, ...

Nathann

comment:32 Changed 4 years ago by git

  • Commit set to 9bbd1f24e0689368b338777363ae2199c79e5c17

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

8916046trac #16559: Brouwer-Van Rees version of Wilson's decomposition
cf11457trac #16559: Fixed error message for large holes and smaller example
9b8ba79trac #16559: Fixes reported by Julian R. Abel
b0419b8trac #16559: Merged with 6.4.beta6
fe62ae4trac #16559: Bugfix
12177d8trac #16559: fix documentation
3825155trac #16559: remove simple_wilson_construction
9bbd1f2trac #16559: A description for the Brouwer-van Rees construction

comment:33 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Good to go!

Vincent

comment:34 Changed 4 years ago by vbraun

  • Branch changed from public/16559 to 9bbd1f24e0689368b338777363ae2199c79e5c17
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.