New recursive constructions of Orthogonal Arrays

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Here they are ! They have been sitting on my HD for a long time :-P

Nathann

Depends on #16499

CC: @videlec @KPanComputes

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 697dd0c

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/16500

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Branch: u/ncohen/16500

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

`004833a`	`trac #16347: Wilson's construction with two truncated groups`
`f5069f0`	`trac #16347: Merged with 6.3.beta4`
`f182d36`	`trac #16499: Cheap speedup in the OA recursive constructions`
`70f7046`	`trac #16500: New recursive constructions of Orthogonal Arrays`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 70f7046

videlec commented 10 years ago

comment:4

EDIT: deleted comment as I messed up ticket numbers...

videlec commented 10 years ago

comment:5

(Replying to comment:4) sorry, this comment was for #16430. Not this one!!

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:7

Rebased on top of #16499. But....

sage -t --long latin_squares.py
    [40 tests, 35.08 s]

T_T

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

`0fa89d5`	`trac #16347: Wilson's construction with two truncated groups`
`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`
`9ff5062`	`trac #16423: Table of MOLS from the handbook and comparison with Sage`
`e64be98`	`trac #16423: tiny code improvement and alignment`
`e948cf6`	`trac #16423: Aligning the alignment`
`0a7d853`	`trac #16423: Broken doctests`
`b329351`	`trac #16499: Cheap speedup in the OA recursive constructions`
`770a28d`	`trac #16500: New recursive constructions of Orthogonal Arrays`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 70f7046 to 770a28d

videlec commented 10 years ago

comment:9

Hi Nathann,

Stupid questions to start:

It would be nice to have references! You provide [AC07]_ for construction_3_4 but that's all.
Why you did not move product, one_truncated_group and two_trucated_group in the recursive construction?
Why not put the cache only for find_recursive_construction? (less cached function and less function calls)

Vicent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:10

Yo !

I updated the "find" functions a bit. Nothing smart, just common sense, and the MOLS_table function is fast again. Yeepeeeeeeeeee !!! :-P

It would be nice to have references! You provide [AC07]_ for construction_3_4 but that's all.

Ahahahah. I had nothing else :-P

I tried to reverse-engineer the construction from the theorem's claim, and when I was not able too I asked Julian R. Abel for a hint. This being said, the explanations I give in the docstring are more or less like a proof.

Why you did not move product, one_truncated_group and two_trucated_group in the recursive construction?

Because I thought that it would be abusing your kindness. I waste my health implementing those things, but I still try to makes patches somehow readable so that reviewing them will not be hell for you. I can add a commit for that if you don't mind. As I told you by email, "this is in the plan" :-P

Why not put the cache only for find_recursive_construction? (less cached function and less function calls)

Because this function returns both OA and !True/False answers. The find_* functions I cached only return immutable stuff.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

a67c04f trac #16500: New recursive constructions of Orthogonal Arrays

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 770a28d to a67c04f

videlec commented 10 years ago

comment:12

Replying to @nathanncohen:

Why you did not move product, one_truncated_group and two_trucated_group in the recursive construction?

Because I thought that it would be abusing your kindness. I waste my health implementing those things, but I still try to makes patches somehow readable so that reviewing them will not be hell for you. I can add a commit for that if you don't mind. As I told you by email, "this is in the plan" :-P

Ok. Will see that later. I postponed to #16535 if you agree.

Why not put the cache only for find_recursive_construction? (less cached function and less function calls)

Because this function returns both OA and !True/False answers. The find_* functions I cached only return immutable stuff.

But why not having orthogonal_array implements the three lines that are right now in find_recursive_construction? My main concern is about readability. I would prefer

@cached_method
def find_recursive_construction(k,n):
    for find_c in [find_construction_3_3,
                   find_construction_3_4,
                   find_construction_3_5,
                   find_construction_3_6]:
        res = find_c(k,n)
        if res: return res

That way:

you still have the freedom to update find_recursive_construction without touching orthogonal_array
you keep an eye on who did what with the cache
you perform the work of adapting your answer only in orthogonal_array
if you changed your mind about the syntax existence=True and such you will not have to touch to find_recursive_construction
the file orthogonal_array_recursive.py will look like a "dynamical" database in the very same way that database.py is a static one

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:13

Yo !

Ok. Will see that later. I postponed to #16535 if you agree.

I will have to rebase what is currently above this patch, then.

Well.... does not matter...

But why not having orthogonal_array implements the three lines that are right now in find_recursive_construction?

Oh, you mean only the part that actually creates the design ? Yeah, why not !...

I will add a commit for that in a second.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a67c04f to 41c50d5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

41c50d5 trac #16500: Simplified find_recursive_construction

videlec commented 10 years ago

comment:15

Hi,

small commit at u/vdelecroix/16500

Be careful that a truncated OA is not an incomplete OA. In truncated OA you removed points in columns whereas in incomplete OA you have less blocks than an OA (but columns are not changed)... it is very confusing to read your doc. And moreover you use block or column indifferently but it would be better to have a unique name for that.

In the doc of the construction 3.4 there is

- If there exists an `OA(k,m+r+1)` the column of size `s` is truncated in
  order to intersect `B_0`.

- If there exists an `OA(k,m+r+1)`, the last column must not intersect `B_0`

which is contradictory!

The rest is fine except that there is no need to use linear programming to build an oval, see #16552.

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:17

Yo !

small commit at u/vdelecroix/16500

Looks good !

Be careful that a truncated OA is not an incomplete OA.

Arg yes yes, I always mix the two words ^^;

And moreover you use block or column indifferently but it would be better to have a unique name for that.

Do you mean "column or group" ? There are n^2 blocks in an OA(k,n) but k columns.

In the doc of the construction 3.4 there is

- If there exists an `OA(k,m+r+1)` the column of size `s` is truncated in
  order to intersect `B_0`.

- If there exists an `OA(k,m+r+1)`, the last column must not intersect `B_0`

which is contradictory!

I don't se how O_o

The rest is fine except that there is no need to use linear programming to build an oval, see #16552.

Oh ? Cool. Free ovals ! :-D

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

e1992ce trac #16500: doc + speedup

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 41c50d5 to e1992ce

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:19

What exactly needs work ?

Nathann

videlec commented 10 years ago

comment:20

Replying to @nathanncohen:

What exactly needs work ?

the doc of construction 3.4

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:21

Then please answer my question above : what is wrong in those sentences ?

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:22

Oh. Right.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

697dd0c trac #16500: Typoes in the doc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from e1992ce to 697dd0c

videlec commented 10 years ago

comment:25

This one was much easier once the Wilson construction is understood!

Do you already did the even more general construction from Brouwer-Rees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?

Vincent

videlec commented 10 years ago

Reviewer: Vincent Delecroix

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:27

Yo !

This one was much easier once the Wilson construction is understood!

Yep yep. That's what I will remember of design theory. Deadly scary stuff that becomes totally straightforward once you pay attention to it.

Still, a lot of stuff remains deadly scary in the field :-P

Do you already did the even more general construction from Brouwer-Rees 1982 (they consider generalization of truncated OA where the extra columns are partitioned in possibly more than two parts)?

Now yet, but I will have to. What scares me is not the implementation of the construction, but how to properly write the input part of the function T_T

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:28

This one was much easier once the Wilson construction is understood!

Some smarter comment: I believe that it is thanks to work like the one we do that we can get to understand such things. That's how it happened to me with LP : I had to implement very basic things 1000 times for Sage, and in the end I find myself understanding the basics properly, which would have NEVER happened if I had just had a book in front of me. Or even if it was in Sage's code.

When you implement Sage stuff you are forced to spend time on things you would quickly look at otherwise.

Nathann

vbraun commented 10 years ago

Changed branch from u/ncohen/16500 to 697dd0c

sagemath / sage

New recursive constructions of Orthogonal Arrays #16500