Opened 5 years ago

Closed 5 years ago

#16503 closed enhancement (fixed)

q-x construction of Orthogonal Arrays

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: vdelecroix Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 8da2c73 (Commits) Commit: 8da2c73aeb5a5ca2e1561131fb3218b3c451b33c
Dependencies: #16500 Stopgaps:

Description

Another construction of orthogonal arrays. New OA for n=158, 329, 334, 355, 517, 574, 745, 979, 1926.

Thanks to Julian R. Abel's pointers, as usual :-)

Nathann

Change History (18)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16503
  • Dependencies set to #16500
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 9128badc12a22a2fed2b78f4e08e9bb349d1ecaa

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

004833atrac #16347: Wilson's construction with two truncated groups
f5069f0trac #16347: Merged with 6.3.beta4
f182d36trac #16499: Cheap speedup in the OA recursive constructions
70f7046trac #16500: New recursive constructions of Orthogonal Arrays
9128badtrac #16503: q-x construction of Orthogonal Arrays

comment:3 Changed 5 years ago by git

  • Commit changed from 9128badc12a22a2fed2b78f4e08e9bb349d1ecaa to 6087843eba8aac6bf74b4ef69ea72762ce47cacf

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 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
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
6087843trac #16503: q-x construction of Orthogonal Arrays

comment:4 Changed 5 years ago by ncohen

Updated on top of #16500 !

Nathann

comment:5 Changed 5 years ago by git

  • Commit changed from 6087843eba8aac6bf74b4ef69ea72762ce47cacf to 71dad5d46b3fe7b343962974a75a9c199e0904a6

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

41c50d5trac #16500: Simplified find_recursive_construction
e1992cetrac #16500: doc + speedup
697dd0ctrac #16500: Typoes in the doc
71dad5dtrac #16503: q-x construction of Orthogonal Arrays

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

Hi Nathann,

1) One lines 656-659 you have an import followed by a commented check!!

from sage.combinat.designs.bibd import _check_pbd
PBD = [[relabel[xx] for xx in B if not xx in points_to_delete] for B in TD]

# _check_pbd(PBD,n,[q,q-x-1,q-x+1,x+2])

why is that?

2) This is wrong (lines 730-731)

# The next is always True, because q is a prime power
# orthogonal_array(k+1,q,existence=True) and

if k+1 > q... instead we can start the loop at k+1 instead of 3.

3) I bounced into something bad: I wanted to change in find_recursive_construction the

assert k >= 3

into a

assert k > 3, "you do not need recursion for k<4"

since it is trivial to build one latin square. But it appears that the recursive constructions is called with k=3 many times! so bad! This has to be corrected... but hopefully, not here. I guess that #16535 would be the good place.

Vincent

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

Hello !

1) One lines 656-659 you have an import followed by a commented check!!

from sage.combinat.designs.bibd import _check_pbd
PBD = [[relabel[xx] for xx in B if not xx in points_to_delete] for B in TD]

# _check_pbd(PBD,n,[q,q-x-1,q-x+1,x+2])

why is that?

It is something I used while implementing the construction and as it said something about the PBD I left it. I updated that comment as that troubled you.

2) This is wrong (lines 730-731)

# The next is always True, because q is a prime power
# orthogonal_array(k+1,q,existence=True) and

The line before that one is

            orthogonal_array(k+1,q-x+1,existence=True) and

3) I bounced into something bad: I wanted to change in find_recursive_construction the

assert k >= 3

into a

assert k > 3, "you do not need recursion for k<4"

since it is trivial to build one latin square. But it appears that the recursive constructions is called with k=3 many times! so bad! This has to be corrected... but hopefully, not here. I guess that #16535 would be the good place.

Why in #16535 ? What we need to do is add a case for k=3 in the orthogonal_array constructor.

I fixed the things above, plus an apparently incorrect 1<x.

Nathann

comment:8 Changed 5 years ago by git

  • Commit changed from 71dad5d46b3fe7b343962974a75a9c199e0904a6 to 91eb3d2d16fa8a4576d6b5d6e2686af6f8593def

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

91eb3d2trac #16503: Review

comment:9 Changed 5 years ago by vdelecroix

Hi Nathann,

You can actually cut the loop if x >= q as x is increasing along the loop. It is done at public/16503 (it does not matter too much right now, but it will if you want to compute a big MOLS table).

Beyond that, you can set to positive review.

Vincent

comment:10 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

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

HMmmmm... I don't like much to differentiate over integer divisions.. Do you mind if we keep it like that ?

Nathann

comment:12 in reply to: ↑ 11 Changed 5 years ago by vdelecroix

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

Replying to ncohen:

HMmmmm... I don't like much to differentiate over integer divisions.. Do you mind if we keep it like that ?

Me neither, but the floor function is increasing... so it is fine (as the composition of increasing functions is increasing)! But we can keep it as it is, since we cut very little with that: (q^2-n)/(q-2) ~ q + cte for large q.

Vincent

comment:13 Changed 5 years ago by vdelecroix

  • Status changed from positive_review to needs_work

As reported in #16524 there is a problem building the doc. Solution (line 622)

-    REFERENCES::
+    REFERENCES:

comment:14 Changed 5 years ago by git

  • Commit changed from 91eb3d2d16fa8a4576d6b5d6e2686af6f8593def to 8da2c73aeb5a5ca2e1561131fb3218b3c451b33c

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

8da2c73trac #16503: Broken doc

comment:15 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:16 Changed 5 years ago by vdelecroix

... building the doc...

comment:17 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:18 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16503 to 8da2c73aeb5a5ca2e1561131fb3218b3c451b33c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.