Opened 6 years ago

Closed 5 years ago

Last modified 5 years ago

#15310 closed enhancement (fixed)

Wilson's construction of Transversal Designs/Orthogonal Arrays/MOLS

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords:
Cc: wdj, rbeezer, brett, dimpase, vdelecroix Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: e86d26c (Commits) Commit:
Dependencies: #15287, #15431 Stopgaps:

Description (last modified by ncohen)

This ticket implements Wilson's construction of transversal designs (which are equivalent to OA and MOLS) as found in Douglas Stinson's book.

The implementation of the construction is not a very technical problem though it requires several parameters that are not obvious when the user asks for a transversal design of parameters k,n. A function find_wilson_decomposition thus tries to guess those parameters, and needs for that to know the values of k,n for which Sage knows how to build a transversal design.

It can then try all possibilities, and use Wilson's construction as efficiently as possible !

Nathann

Change History (60)

comment:1 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/15310
  • Commit set to 21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8

New commits:

[changeset:21ca843]Wilson's construction of Transversal Designs/Orthogonal? Arrays/MOLS
[changeset:7c1b651]Orthogonal arrays
[changeset:d93abcd]Latin Squares
[changeset:2ec76c7]Bug in AffineGeometryDesign?
[changeset:cf71d58]Rebase on 5.13.beta0
[changeset:9fcfb13]Rename the method from ProjectivePlaneDesign? to DesarguesianProjectivePlaneDesign?
[changeset:363badb]trac 15107 -- reviewer's comments
[changeset:ee6d412]Projective Plane designs constructor

comment:2 Changed 6 years ago by git

  • Commit changed from 21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8 to 7487b62fe657ef04722f06fa5c1e7647855e4f89

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

[changeset:7487b62]Wilson's construction -- find_wilson_decomposition and test of availability
[changeset:847c7b6]Wilson's construction -- rebase on bugfix from 15287
[changeset:59f340b]Orthogonal arrays -- doctest
[changeset:e32c6de]Orthogonal arrays -- bugfix

comment:3 Changed 6 years ago by ncohen

  • Dependencies set to #15287
  • Status changed from new to needs_review

comment:4 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by git

  • Commit changed from 7487b62fe657ef04722f06fa5c1e7647855e4f89 to 6abda3c9eb7fedd8b63ad135a9b04f6469ae570d

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

6abda3ctrac #15310: Wilson's construction of Transversal Designs

comment:7 Changed 5 years ago by ncohen

Rebased (and ready for a review :-P)

Nathann

comment:8 Changed 5 years ago by ncohen

  • Cc wdj rbeezer brett dimpase added

comment:9 Changed 5 years ago by git

  • Commit changed from 6abda3c9eb7fedd8b63ad135a9b04f6469ae570d to effb0ac5dc265553a6c4fb7ce9a1337262f4d549

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

effb0actrac #15310: Wilson's construction of Transversal Designs

comment:10 Changed 5 years ago by git

  • Commit changed from effb0ac5dc265553a6c4fb7ce9a1337262f4d549 to 03f896c363e23a00fabf0b38b87a277354f07327

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

03f896ctrac #15310: Wilson's construction of Transversal Designs

comment:11 Changed 5 years ago by ncohen

  • Cc vdelecroix added
  • Dependencies changed from #15287 to #15287, #15431

comment:12 Changed 5 years ago by git

  • Commit changed from 03f896c363e23a00fabf0b38b87a277354f07327 to 6357236d82dd6714eb59a7e63bb22a7f02c18e88

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

79ea502trac #15431: depends on #15287
ec6c09etrac #15431: depends on #15368
6fbef0ctrac #15431 : Construction of TD(6,12)
c87cac5trac #15431: rebase on updated #15287
ba232b6trac #15431: rebase on 6.2.beta6
a02aa52trac #15431: Reviewer's remarks
4adf6b5trac #15431: Reviewer's remark II
47ffd91trac #15431: remove old todo
a537755trac #15431: Back to the standard definition of TD
6357236trac #15310: Rebase on updated #15431

comment:13 Changed 5 years ago by git

  • Commit changed from 6357236d82dd6714eb59a7e63bb22a7f02c18e88 to 25f5959ec5fe7ccd1479fdbdcd489cf550933c7e

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

25f5959trac #15310: Merged into 6.2.rc0

comment:14 Changed 5 years ago by git

  • Commit changed from 25f5959ec5fe7ccd1479fdbdcd489cf550933c7e to f23fa885ee5a080f2a8051f23f7fc9f130541849

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

f23fa88trac #15310: useless checks

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

Hi Nathann,

I am not sure I would be able to do the full review. Nevertheless, you can can speed up a lot the function find_wilson_decomposition using the fact that if a TD(k,n) exists then we have the inequality k <= n+1. Here is a sample version of what can be done:

def find_wilson_decomposition(k,n):
    # we can start from k-1 since we need a TD(k+1,t)
    for t in range(max(1,k-1),n-1):
        u = n%t
        # We ensure that 1<=u and
        # u <= k-2 since we need a TD(k,u)
        if u == 0 or u <= k-2:
            continue

        m = n//t

        # k < m+2 since we need a TD(k,m)
        if k >= m+2:
            break

        if (transversal_design(k  ,m  , availability=True) and
            transversal_design(k  ,m+1, availability=True) and
            transversal_design(k+1,t  , availability=True) and
            transversal_design(k  ,u  , availability=True)):
            return k,m,t,u

    return False

You can check that there is no stupid call to find_wilson_decomposition with the following

sage: from sage.combinat.designs.orthogonal_arrays import find_wilson_decomposition
sage: find_wilson_decomposition(7,71)
(7, 8, 8, 7)
sage: find_wilson_decomposition.get_cache() # get the list of cached values
...

comment:16 in reply to: ↑ 15 Changed 5 years ago by ncohen

Yoooooooooooo !!

I am not sure I would be able to do the full review.

PLeaaaaaaaaaaase.. I swear, all the results are checked before being returned ! And the algorithms are so weird that the slightest typo would make all results wrong :-P

Nevertheless, you can can speed up a lot the function find_wilson_decomposition using the fact that if a TD(k,n) exists then we have the inequality k <= n+1.

Oh ?

Here is a sample version of what can be done:

What does it change exactly ? That the TD(k,u) is not called when the answer is obviously no ? Wouldn't we get the very same result by moving the check of TD(k,u) to the top of the 4 tests ?

Nathann

comment:17 Changed 5 years ago by ncohen

Yeah, you are right, let's add those tests before the big if. I will do it in a second.

Nathann

comment:18 Changed 5 years ago by ncohen

What about this ?

	if ( k < m+2 and k < t+3 and k < u+2 and
            transversal_design(k  ,m  , availability=True) and
            transversal_design(k  ,m+1, availability=True) and
            transversal_design(k+1,t  , availability=True) and
            transversal_design(k  ,u  , availability=True)):
            return k,m,t,u

comment:19 Changed 5 years ago by ncohen

Oh I see, you tested all of them by changing the bounds of the loops. Right. I'll change that.

Nathann

comment:20 follow-up: Changed 5 years ago by ncohen

Why isn't it for t in range(max(1,k),n-1): in the first loop ?

comment:21 Changed 5 years ago by git

  • Commit changed from f23fa885ee5a080f2a8051f23f7fc9f130541849 to 62f0158c281c55523a532d5ef21c666ba9c7dc3d

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

62f0158trac #15310: cutting some branches of the exploration

comment:22 in reply to: ↑ 20 Changed 5 years ago by vdelecroix

Replying to ncohen:

Why isn't it for t in range(max(1,k),n-1): in the first loop ?

My mistake. This is why I did not write a branch for that... I wanted you to check carefully!!

comment:23 Changed 5 years ago by ncohen

Well, in this direction it is not a problem :-P

Nathann

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

Hi Nathann,

Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.

1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?

2) The programming design with TD calling OA is very bad. In OA there is a nice EmptySetError which has an important mathematical meaning. But if you ask for a transversal design you get instead a NotImplementedError which is much less informative

sage: designs.orthogonal_array(6,3)   # this is great
Traceback (most recent call last)
...
EmptySetError: No Orthogonal Array exists when k>=n+t
sage: designs.transversal_design(6,3)  # this is bad
Traceback (most recent call last)
...
NotImplementedError: I don't know how to build this Transversal Design!

In the ideal world, Sage would only return a design or raise an EmptySetError with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. When availability=True it would be nice to get a troolean: True (means yes), False (means no), Unknown in sage.misc.unknown (means I do not know). And then, you might change the name availability to existence.

3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a # long time.

4) Could you mention the following reference as a todo

  • AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
  • TITLE = Making the MOLS table
  • BOOKTITLE = Computational and constructive design theory
  • SERIES = Math. Appl.
  • VOLUME = 368
  • PAGES = 67--134
  • PUBLISHER = Kluwer Acad. Publ., Dordrecht
  • YEAR = 1996

They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.

Cheers, Vincent

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

Yo !

Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.

Ahahaha. Well you must have more background that I have then, I am jealous :-P

1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?

I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.

I also got word from Julian Abel that the Wilson Decomposition I implemented was not the best one, and that some variants may be useful. I copy/paste what he told me here (he probably will not mind)

I note from  your list of  known MOLS that you've used Wilson's theorem with 1 truncated group, but not more.  The next most important variants are
where there are (1) 2 truncated groups (2) 1 spike block or 1 truncated group and a spike. These variants are as follows:

Theorem 1: If  there are k+2 MOLS(t),    and k MOLS(s) for s=g, g+1, g+2, u_1, u_2,  where 0 \leq u_1, u_2 \leq t, then there are k MOLS(gt + u_1 + u_2).
Theorem 2: If  there are k+x MOLS(t),     and k MOLS(s) for s=g, g+1, g+x,  g+x,  where 0  \leq u_1,   u_2 \leq t, x> 0 then there are k MOLS(gt +  x).
Theorem 3: If  there are k+x+1 MOLS(t),  and k MOLS(s) for s=g, g+1, g+2, g+x, u_1,  where 0 \ leq  u_1  \leq t, x > 0, then there are k MOLS(gt + x + u_1).

For instance, Th. 1 gives 6 MOLS for v=106 = 7. 13 + 7 + 8.  Theorem 2 gives 7 MOLS(v) for v=155 = 8.19 + 3. And Theorem 3 gives 6 MOLS(v) for v=148= 7.19 + 6 + 9.

He also pointed me toward references where I can read those constructions, but I have not begun this step yet and he told me it would be hard to read. Still, it has to be done.

2) The programming design with TD calling OA is very bad. In OA there is a nice EmptySetError which has an important mathematical meaning. But if you ask for a transversal design you get instead a NotImplementedError which is much less informative

How is that a result of TD calling OA ?

In the ideal world, Sage would only return a design or raise an EmptySetError with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. When availability=True it would be nice to get a troolean: True (means yes), False (means no), Unknown in sage.misc.unknown (means I do not know).

Well. No problem if "if Unknown" is equivalent to "if False".

And then, you might change the name availability to existence.

Could we do that on top of #12267 ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.

3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a # long time.

Well, I usually set #long even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.

4) Could you mention the following reference as a todo

  • AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
  • TITLE = Making the MOLS table
  • BOOKTITLE = Computational and constructive design theory
  • SERIES = Math. Appl.
  • VOLUME = 368
  • PAGES = 67--134
  • PUBLISHER = Kluwer Acad. Publ., Dordrecht
  • YEAR = 1996

They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.

okayokay, good idea ! I will add a commit in a second.

Nathann

comment:26 Changed 5 years ago by git

  • Commit changed from 62f0158c281c55523a532d5ef21c666ba9c7dc3d to d74341411288315f13da3d4383e515b884ba7440

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

d743414trac #15310: reviewer's remarks

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

Replying to ncohen:

1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?

I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.

Actually, the product construction is what you are doing in #16227. You can see it as a particular case of Wilson construction.

2) The programming design with TD calling OA is very bad. In OA there is a nice EmptySetError which has an important mathematical meaning. But if you ask for a transversal design you get instead a NotImplementedError which is much less informative

How is that a result of TD calling OA ?

I would better say not calling OA appropriately. line 79

    elif orthogonal_array(k,n, check = False, availability = True):
       ...

I still found that having half of the implementation in TD and half of the implementation in OA is very confusing.

Well. No problem if "if Unknown" is equivalent to "if False".

It is. You do not know your troolean algebra !?

And then, you might change the name availability to existence.

Could we do that on top of #12267 ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.

Make sense. I will open a ticket for that.

3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a # long time.

Well, I usually set #long even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.

No do not worry about this.

4) Could you mention the following reference as a todo

  • AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
  • TITLE = Making the MOLS table
  • BOOKTITLE = Computational and constructive design theory
  • SERIES = Math. Appl.
  • VOLUME = 368
  • PAGES = 67--134
  • PUBLISHER = Kluwer Acad. Publ., Dordrecht
  • YEAR = 1996

They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.

okayokay, good idea ! I will add a commit in a second.

and please, add also the references you got from Julian Abel. I guess that they are pretty similar.

Vincent

comment:28 in reply to: ↑ 27 Changed 5 years ago by ncohen

Yo !

Actually, the product construction is what you are doing in #16227. You can see it as a particular case of Wilson construction.

Oh. Cool, then. Must prove I am on the right path :-D

I would better say not calling OA appropriately. line 79

    elif orthogonal_array(k,n, check = False, availability = True):
       ...

Oh. And you want to transfer the "False" answer which means "that stuff does not exist" as an exception ? Then do you mind if we do that in the ticket which will change "availability" to "existence" ? It would be easier to not fix many conflicts in many patches. But it is a good idea and it will be implemented, be sure I don't say this because I don't want to do it. It *is* a good idea.

Well. No problem if "if Unknown" is equivalent to "if False".

It is. You do not know your troolean algebra !?

To me it should raise an Exception. You just cannot trust these things to do what they should.

Make sense. I will open a ticket for that.

Thanks. Add me in Cc when you do, of course :-)

No do not worry about this.

Too late :-P

and please, add also the references you got from Julian Abel. I guess that they are pretty similar.

Hmmm... Not now please, I will probably have more questions to ask him and right now we are exchanging email about a construction of MOLS that I cannot reproduce. I implemented quite a lot of specific constructions of MOLS/OA during the last days. Besides #16241 #16236 and #16235 I have the following ready :

~$ grep "^def " qd.py 
def OA_from_quasi_difference_matrix(M,G,add_col=True):
def OA_from_wider_OA(OA,k):
def OA_6_20(k,n,availability=False):
def OA_7_21(k,n,availability=False):
def OA_5_22(k,n,availability=False):
def OA_7_60(k,n,availability=False):
def OA_9_24(k,n,availability=False):
def OA_6_26(k,n,availability=False):
def OA_7_28(k,n,availability=False):
def OA_6_30(k,n,availability=False):
def OA_7_33(k,n,availability=False):
def OA_6_34(k,n,availability=False):
def OA_7_35(k,n,availability=False):
def OA_10_36(k,n,availability=False):
def OA_6_38(k,n,availability=False):
def OA_7_39(k,n,availability=False):
def OA_9_40(k,n,availability=False):
def OA_10_48(k,n,availability=False):
def OA_9_40b(k,n,availability=False):

Well. Except the last 3. Those are the ones we are fighting against at the moment :-)

Nathann

comment:29 follow-up: Changed 5 years ago by brett

I will jump in here. Julian Able's other versions of Wilson's construction are the ones discussed in the Colbourn and Dinitz reference. I was wrong about the details when I chatted with Vincent: I said they simplified when $u$ was a nice value, but your posted email from Julian reminds me that these are multiple truncations. I do not think these need to go into a first round. I would advocate getting the basic Wilson's theorem into the official Sage release and then adding more intricate variations

With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops

I am waiting for sage to compile, then I will get the new commit and look more closely at the code.

Here are some additional thoughts that apply to the whole TD/OA enterprise rather than just this patch (If I should be discussing these things somewhere else because they are more general comments then please let me know and point me to where to have this discussion)

  • (anticipating ticket #16231) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.
  • There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the non-existence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the non-existence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first

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

Replying to brett:

With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops

Yes. It is possible to have that in #16227: we can replace the two functions with one. But I am not sure it would be faster/clearer.

  • (anticipating ticket #16231) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.

This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.

  • There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the non-existence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the non-existence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first

Cool: look at ticket #16272. I will add those references to the description. If you have other non-existence theorems please post them on #16272.

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

Yo !

With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops

I implemented it this way because I followed Douglas Stinson's book, which defines this construction explicitly for 1<=u.

This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.

I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like #14562 and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.

Anyway, right now I don't think that it is really a problem... There is a lot of work needing to be done, and this work is implementing constructions, any kind of constructions, in any formalism you like. We can merge everything later if we need. But really what we need right now are constructions, and nothing else.

Cool: look at ticket #16272. I will add those references to the description. If you have other non-existence theorems please post them on #16272.

Yep, non-existence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.

I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that :-)

But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about :-P

Nathann

comment:32 Changed 5 years ago by ncohen

By the way, all designs constructions in the list I gave above now work. I will implement some more before sending the patch, but they do work. Plus I will need stuff like #16261 and #16269 before.

comment:33 Changed 5 years ago by ncohen

By the way will you be in Bordeaux during July/August? ? I have no plans yet :-D

Nathann

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

Hello,

Replying to ncohen:

This is an important issue I started to discuss with Nathann in #15431... and I am in favour of implementing all the code with OA conventions.

I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like #14562 and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.

True. But on the other hand

  • it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input
  • the EmptySetError raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks

look at ticket #16272. I will add those references to the description. If you have other non-existence theorems please post them on #16272.

Yep, non-existence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.

I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that :-)

I like it. But I agree that it can be implemented later on.

But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about :-P

Nice challenge! You want it to be ready for next week?

comment:35 in reply to: ↑ 34 Changed 5 years ago by ncohen

Yo !

True. But on the other hand

  • it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input

Well... Just read the constructors of each class, you will see :-P

  • the EmptySetError raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks

Yeah, probably ... But that's a very bad reason for changing the data structure :-P

I like it. But I agree that it can be implemented later on.

Never implement something you don't need. And I am already breaking this rule by implementing designs. I don't have anything to do with designs. I just love them :-P

Nice challenge! You want it to be ready for next week?

Ahahahahahah. Well, you have some reviews ahead of you, don't you ? :-P

Nathann

comment:36 follow-up: Changed 5 years ago by brett

I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure. For example incidence structures (and by extension, designs) are stored as their sets of sets. The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows

  • a single place to check all known non-existence results
  • future ease in making this a class

In principle I do not mind if the constructions that you have implemented for TDs stay as they are but are wrapped by OA->TD translation TD construction followed by TD-OA translation. It can be left as a possible future task to clean this up.

Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his Covering Array tables, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?

brett

p.s. how do I format the link correctly

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

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

  • Status changed from needs_review to positive_review

Hi,

everybody: please, in a given ticket, only discuss the ticket! There is the sage-devel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.

Nathann: you have to rebase #16227 above the last commit in here.

Vincent

comment:38 in reply to: ↑ 36 Changed 5 years ago by ncohen

Yo !

I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure.

For the moment I did not see the need to turn it into a class. Especially since making it a class will require many useless copies of stuff, each time you ask the class to give you its data or when you build an instance from the data (copy in each direction, for nothing).

For example incidence structures (and by extension, designs) are stored as their sets of sets.

And I like to work with list of sets indeed :-P

The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows

  • a single place to check all known non-existence results
  • future ease in making this a class

It is true, but if it means that implementing constructions becomes harder, this is too much to pay. Really, give it a try. Today is a holiday, and I have been implementing constructions since I woke up. It is *HARD* and painful.

Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his http://www.public.asu.edu/~ccolbou/src/tabby/catable.htmCovering Array tables, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?

I don't think so .... Designs are particularly messy in this respect :-P

Nathann P.S. : Vincent is right, let's discuss this somewhere else. On the otherhand, if you can review this ticket we can use it as a forum afterwards :-D

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

everybody: please, in a given ticket, only discuss the ticket! There is the sage-devel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.

Why are the comments lost ? The ticket still exists long afterwards !

Nathann: you have to rebase #16227 above the last commit in here.

It creates a conflict ? O_o

I thought git would handle this by itself...

Nathann

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

Replying to ncohen:

everybody: please, in a given ticket, only discuss the ticket! There is the sage-devel mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.

Why are the comments lost ? The ticket still exists long afterwards !

Nathann: you have to rebase #16227 above the last commit in here.

It creates a conflict ? O_o

I thought git would handle this by itself...

git is not god

Auto-merging src/sage/combinat/designs/orthogonal_arrays.py
CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py
Automatic merge failed; fix conflicts and then commit the result.

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

git is not god

Then we should write a patch to change that.

More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.

Nathann

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

  • Status changed from positive_review to needs_review

Replying to ncohen:

git is not god

Then we should write a patch to change that.

More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.

It was! But on the other hand there is a serious issue in #16227. The function Wilson construction and TD_product should be similar but they are not. Wilson call the transversal_design to start the construction but you have to feed TD_product with the designs! Why is that?

I think it would make more sense to merge the two tickets simultaneously. Would you mind if we move the changes you introduced in #16227 in this one (I can even do that by myself).

comment:43 in reply to: ↑ 42 Changed 5 years ago by ncohen

It was! But on the other hand there is a serious issue in #16227. The function Wilson construction and TD_product should be similar but they are not.

Since when are such things called serious ? :-P

Besides I implemented one months after the other, so if you do not mind... :-P

Wilson call the transversal_design to start the construction but you have to feed TD_product with the designs! Why is that?

Because I suspect that TD_product may be useful to the users later to compute products of their own designs (not the one Sage knows) and I did not think this would happen with wilson decompsition.... If we make TD_product call the designs itself, it makes it less useful, that's all. I saw one as "internal stuff" while the other one could eventually become useful for users.

I think it would make more sense to merge the two tickets simultaneously.

Why ?

Would you mind if we move the changes you introduced in #16227 in this one (I can even do that by myself).

Well, stuff is based on the TD ticket, and I will have to deal with the conflicts later if any, so if I can avoid it ....

Nathann

comment:44 follow-up: Changed 5 years ago by brett

What if both functions could be called in two ways:

1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them

2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.

Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.

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

comment:45 in reply to: ↑ 44 Changed 5 years ago by ncohen

Yo !

1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them

This is already done, as Sage will automatically use the product construction to see if such a design exists. When you call designs.orthogonal_array(...) the TD product construction will be called from time to time.

2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.

Yepyep, we can make the designs be optional parameters indeed ...

Really I don't mind but I am writing construction code and there is a lot of work to do. If you want features like that, would you mind implementing them ? It is not a lot of work, you just have to add optional parameters in Wilson's construction equal to None, and if they are set to None Sage will find the designs itself otherwise it will use those that are provided.

Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.

Indeed indeed. But it is not like anybody will know that Sage can produce MOLS/OA/TD already, so we have time before the crowd complains about the missing features.. Right now I am just trying to implement what I need to create more TD/OA/MOLS, and we will have all the time in the world to create fancy features when it will be in :-P

I am two constructions away from having implemented all explicit construction of length <= 80 that the Handbook provides, but they are tricky ones. Then this step will be done too, and we will have to implement the variants of Wilson's theorem.

Nathann

Vincent : is there anything I should do on this ticket ?

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

I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the TD_product. Do not think about other users, they can think by themselves :-P. I will copy/paste that on #16227.

Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.

My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.

comment:47 in reply to: ↑ 46 Changed 5 years ago by ncohen

Yo !

I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the TD_product. Do not think about other users, they can think by themselves :-P. I will copy/paste that on #16227.

Why on earth would you want me to remove features, really ?... If this function is not meant for the users it makes no difference, and if users see it they can use it. Why do you want me to remove features ?... "for the greater good of having uniform functions that nobody sees" ?... Really guys ...

Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.

We already deal with OA. All this is being built without an OA class .... My current file contains 1735 lines of code/doc to generate OA, and all that is needed are lists of lists of integers.

My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.

Okay.

Nathann

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

Do you mind if we change wilson_construction to TD_wilson_construction... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!

comment:49 in reply to: ↑ 48 Changed 5 years ago by ncohen

Do you mind if we change wilson_construction to TD_wilson_construction... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!

I am pretty sure a lot of people who find wilson_construction in orthogonal_array.py will wonder what it actually does :-P

If you must absolutely change something potentially deadly that will force me to fix conflicts everywhere above, what about wilson_construction_of_TD instead ?

Nathann

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

comment:50 Changed 5 years ago by ncohen

By the way I have this in my file, though two entries still do not work :-/

def OA_from_quasi_difference_matrix(M,G,add_col=True):
def OA_from_Vmt(m,t,V):
def OA_from_wider_OA(OA,k):
def _feasible_set_parameters(k,n,fk,fn,availability):
def OA_6_20(k,n,availability=False):
def OA_7_21(k,n,availability=False):
def OA_5_22(k,n,availability=False):
def OA_7_60(k,n,availability=False):
def OA_9_24(k,n,availability=False):
def OA_6_26(k,n,availability=False):
def OA_7_28(k,n,availability=False):
def OA_6_30(k,n,availability=False):
def OA_7_33(k,n,availability=False):
def OA_6_34(k,n,availability=False):
def OA_7_35(k,n,availability=False):
def OA_10_36(k,n,availability=False):
def OA_6_38(k,n,availability=False):
def OA_7_39(k,n,availability=False):
def OA_9_40(k,n,availability=False):
def OA_7_42(k,n,availability=False):
def OA_7_44(k,n,availability=False):
def OA_8_45(k,n,availability=False): # Broken
def OA_6_46(k,n,availability=False):
def OA_10_48(k,n,availability=False):
def OA_8_50(k,n,availability=False):
def OA_7_51(k,n,availability=False):
def OA_7_52(k,n,availability=False): # Broken
def OA_7_54(k,n,availability=False):
def OA_8_55(k,n,availability=False):
def OA_9_56(k,n,availability=False):
def OA_7_62(k,n,availability=False):
def OA_9_75(k,n,availability=False):
def OA_11_80(k,n,availability=False):
def OA_10_82(k,n,availability=False):
def OA_10_100(k,n,availability=False):
def OA_12_144(k,n,availability=False):
def OA_12_210(k,n,availability=False):

comment:51 Changed 5 years ago by git

  • Commit changed from d74341411288315f13da3d4383e515b884ba7440 to 3fc79ba5be0b99e99593ff54bfa075a52cc5937c

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

3fc79batrac #15310: Merged into 6.2.rc1

comment:52 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

All tests pass. I am happy with this.

comment:53 Changed 5 years ago by ncohen

Thanks !

comment:54 Changed 5 years ago by git

  • Commit changed from 3fc79ba5be0b99e99593ff54bfa075a52cc5937c to e86d26cb8126f3e557cc6a27b1727e2055f67321
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

e86d26ctrac #15310: Merged with 6.2.rc2

comment:55 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

Straightforward merge conflict.

comment:56 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:57 Changed 5 years ago by vbraun

Reviewer name

comment:58 Changed 5 years ago by ncohen

  • Reviewers set to Vincent Delecroix

comment:59 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/15310 to e86d26cb8126f3e557cc6a27b1727e2055f67321
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:60 Changed 5 years ago by kcrisman

  • Commit e86d26cb8126f3e557cc6a27b1727e2055f67321 deleted

I'm not so sure about the availability argument. I know this is late to the game - see here for some comments. I don't see why one couldn't factor out the actual part that checks whether things are available...

Note: See TracTickets for help on using tickets.