Opened 6 years ago
Closed 6 years ago
#16604 closed enhancement (fixed)
new OA for n=112,160,176,208,224,352,416,514,544,640,796,896
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorial designs  Keywords:  
Cc:  vdelecroix  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  24c4f7f (Commits)  Commit:  24c4f7fc4cf619fca8cceb5707b74b935de880c2 
Dependencies:  #16582,#16797  Stopgaps: 
Description
As the title says.
Because this method also needs to shorten a matrix in the middle of OA_from_Vmt
, it is split into QDM_from_Vmt
and OA_from_quasi_difference_matrix
(which was already called).
Nathann
Change History (59)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/16604
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 00654fb8dbffe2134dc0b55ead5cea52dadf1654
comment:3 followup: ↓ 4 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hey Nathann,
In OA_14_124
, it is not safe to ask for a finite field of size 2^{5} and hope that, by chance, its generator satisfies w^5 + w^2 + 1 = 0
. You would rather give the constructor an explicit polynomial:
sage: R = PolynomialRing(GF(2),'x') sage: x = R.gen() sage: GF(2**5, 'w', modulus=x**5+x**2+1) Finite Field in w of size 2^5
and I got a docbuild error
OSError: [combinat ] None:5: WARNING: citation not found: BvR514
Vincent
comment:4 in reply to: ↑ 3 Changed 6 years ago by
 Status changed from needs_work to needs_review
 Summary changed from new OA for n=112,160,224,514,796 to new OA for n=112,160,224,514,640,796
Yo !
In
OA_14_124
, it is not safe to ask for a finite field of size 2^{5} and hope that, by chance, its generator satisfiesw^5 + w^2 + 1 = 0
.
Yeah... And "by chance" it always works ?
Given that you are the one to complain about this, I will use the first's trick against you : conway=True
:P
and I got a docbuild error
OSError: [combinat ] None:5: WARNING: citation not found: BvR514
Ahahahah. I must have replaced 82 with 514 at some point :D
I had also "made a small mistake" in the implementation. I had forgotten to set some flag from "False" to "True", which means that the new OA have a longer width. I didn't like to notice that I had implemented so many new OA and that they did not even reach the Handbook's bound.... Now all is good :P
I also added an OA for 640, freshly debugged.
Nathann
comment:5 Changed 6 years ago by
 Commit changed from 00654fb8dbffe2134dc0b55ead5cea52dadf1654 to ee7ac60c2dbd59374d95bb86b66587c6a6e47321
Branch pushed to git repo; I updated commit sha1. New commits:
ee7ac60  trac #16604: OA for n=640, reviewer's remarks and silly mistake

comment:6 Changed 6 years ago by
 Commit changed from ee7ac60c2dbd59374d95bb86b66587c6a6e47321 to ba6609df5508dd25035203e9e53ce9e4d1ca1ee7
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ba6609d  trac #16604: OA for n=640, reviewer's remarks and silly mistake

comment:7 Changed 6 years ago by
(I had forgotten a "Found by Julian R. Abel" line)
Nathann
comment:8 Changed 6 years ago by
 Summary changed from new OA for n=112,160,224,514,640,796 to new OA for n=112,160,224,514,640,796,896
added a OA(15,896)
.
comment:9 Changed 6 years ago by
 Commit changed from ba6609df5508dd25035203e9e53ce9e4d1ca1ee7 to c218148c1f076c08ad5a448754421e82c78b5509
Branch pushed to git repo; I updated commit sha1. New commits:
c218148  trac #16604: OA(15,896)

comment:10 Changed 6 years ago by
 Commit changed from c218148c1f076c08ad5a448754421e82c78b5509 to 03c2ca3a0668b773ecf79c4c222fc802040053dd
Branch pushed to git repo; I updated commit sha1. New commits:
03c2ca3  trac #16604: OA(16,208)

comment:11 Changed 6 years ago by
 Summary changed from new OA for n=112,160,224,514,640,796,896 to new OA for n=112,160,208,224,514,640,796,896
comment:12 Changed 6 years ago by
 Commit changed from 03c2ca3a0668b773ecf79c4c222fc802040053dd to 6074f4b7fcfcbb18b60726954adfa78e68716384
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6074f4b  trac #16604: OA(16,208)

comment:13 Changed 6 years ago by
 Summary changed from new OA for n=112,160,208,224,514,640,796,896 to new OA for n=112,160,176,208,224,514,640,796,896
comment:14 Changed 6 years ago by
 Commit changed from 6074f4b7fcfcbb18b60726954adfa78e68716384 to 35cbadc1fe6d60fe52b86ec19a6ad337ddb201d2
Branch pushed to git repo; I updated commit sha1. New commits:
35cbadc  trac #16604: OA(16,176)

comment:15 Changed 6 years ago by
 Commit changed from 35cbadc1fe6d60fe52b86ec19a6ad337ddb201d2 to bfcc6f5e263fa92bf04424dfabe825314c6b225d
Branch pushed to git repo; I updated commit sha1. New commits:
bfcc6f5  trac #16604: Now without copy and paste

comment:16 Changed 6 years ago by
 Commit changed from bfcc6f5e263fa92bf04424dfabe825314c6b225d to 226599fa239e84272d441e0bc29e4b9a2fbdf8f1
Branch pushed to git repo; I updated commit sha1. New commits:
226599f  trac #16604: OA(20,352)

comment:17 Changed 6 years ago by
 Commit changed from 226599fa239e84272d441e0bc29e4b9a2fbdf8f1 to 326ece4053b973beef506e427f5bc29846cfa8ed
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
326ece4  trac #16604: OA(20,352)

comment:18 Changed 6 years ago by
 Summary changed from new OA for n=112,160,176,208,224,514,640,796,896 to new OA for n=112,160,176,208,224,352,514,640,796,896
comment:19 Changed 6 years ago by
 Commit changed from 326ece4053b973beef506e427f5bc29846cfa8ed to a6212204674050c40fca7a7c41d4f25c6c2c066c
Branch pushed to git repo; I updated commit sha1. New commits:
a621220  trac #16604: OA(20,416)

comment:20 Changed 6 years ago by
 Summary changed from new OA for n=112,160,176,208,224,352,514,640,796,896 to new OA for n=112,160,176,208,224,352,416,514,640,796,896
comment:21 Changed 6 years ago by
 Commit changed from a6212204674050c40fca7a7c41d4f25c6c2c066c to 0232b73b42b1460f05622dbfc81f8d3f51b9a50b
Branch pushed to git repo; I updated commit sha1. New commits:
0232b73  trac #16604: OA(20,544)

comment:22 Changed 6 years ago by
 Summary changed from new OA for n=112,160,176,208,224,352,416,514,640,796,896 to new OA for n=112,160,176,208,224,352,416,514,544,640,796,896
comment:23 Changed 6 years ago by
Is this the end of commit?
comment:24 Changed 6 years ago by
Yes it i! All MOLS from Julian R. Abel's thesis have been fixed and implemented ! :D
Nathann
comment:25 Changed 6 years ago by
 Commit changed from 0232b73b42b1460f05622dbfc81f8d3f51b9a50b to e5f428d75ade25f0524abbb61c71a67039ed754a
Branch pushed to git repo; I updated commit sha1. New commits:
e5f428d  trac #16604: Merged with 6.3.beta6

comment:26 followup: ↓ 27 Changed 6 years ago by
 Status changed from needs_review to needs_info
Hi Nathann,
I simplified the helper function at u/vdelecroix/16604 and update the branch over 6.3.rc1.
I would be really happy if:
 the helper function would return a quasidifference matrix instead
 it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?
(I can handle the merge with your documentation ticket #16766)
Vincent
comment:27 in reply to: ↑ 26 ; followup: ↓ 29 Changed 6 years ago by
 Status changed from needs_info to needs_review
Yo !
I would be really happy if:
 the helper function would return a quasidifference matrix instead
 it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?
I made it a private function exactly because I have no idea how to write a proper documentation for it. It is just a kind of construction that Julian R. Abel uses for many OA, and as I found I had been doing copy/pastes for it many many times I figured out that it would be better to simplify the code by making it one function. What it does exactly was not more documented before than it is now.
You can find examples of this construction in the Handbook, like on page 171 about theorem 3.76 for n=80.
(I can handle the merge with your documentation ticket #16766)
Hmmmm... I know that we will have to pay for this patch :/
Nathann
comment:28 followup: ↓ 31 Changed 6 years ago by
(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)
comment:29 in reply to: ↑ 27 ; followup: ↓ 30 Changed 6 years ago by
Replying to ncohen:
Yo !
I would be really happy if:
 the helper function would return a quasidifference matrix instead
 it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?
I made it a private function exactly because I have no idea how to write a proper documentation for it. It is just a kind of construction that Julian R. Abel uses for many OA, and as I found I had been doing copy/pastes for it many many times I figured out that it would be better to simplify the code by making it one function. What it does exactly was not more documented before than it is now.
You can find examples of this construction in the Handbook, like on page 171 about theorem 3.76 for n=80.
It is not an explanation... I would like something like "If A and Y are matrices of size XX and properties YY then applying construction ZZ you obtain a quasidifference matrix".
comment:30 in reply to: ↑ 29 Changed 6 years ago by
It is not an explanation... I would like something like "If A and Y are matrices of size XX and properties YY then applying construction ZZ you obtain a quasidifference matrix".
I understand what you want, I am just telling you that this is all I have.
Nathann
comment:31 in reply to: ↑ 28 ; followup: ↓ 32 Changed 6 years ago by
(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)
to change your last two commits I would do that :
1) git reset HEAD~1 # this "cancels" your last commit, and its code will become "staged differences". As if you had not typed "git commit"
2) git commit amend author <whatever you want> # change the author of the merge commit
3) git commit a author <whatever you want> # do your last commit again
Nathann
comment:32 in reply to: ↑ 31 Changed 6 years ago by
Replying to ncohen:
(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)
to change your last two commits I would do that :
1) git reset HEAD~1 # this "cancels" your last commit, and its code will become "staged differences". As if you had not typed "git commit"
2) git commit amend author <whatever you want> # change the author of the merge commit
3) git commit a author <whatever you want> # do your last commit again
Great. It worked... but this method works only if there is at most one commit after the merge. If you have a look at the branch u/vdelecroix/16604 the helper function is much simpler (and the code run a bit faster).
Vincent
comment:33 Changed 6 years ago by
 Branch changed from u/ncohen/16604 to u/vdelecroix/16604
 Commit changed from e5f428d75ade25f0524abbb61c71a67039ed754a to de1dafd330dcf9b07899f677b26bcab6d0ba7297
comment:34 Changed 6 years ago by
Yooooooooo !
I just read your new version of the code. Thanks, it's much better than this ! I will add a small commit for a sentence I had some trouble understanding at first.
And if you do not mind I will also reverse your 2**n>1<<n
. That's zero improvement on speed for less redability.
Nathann
comment:35 Changed 6 years ago by
 Branch changed from u/vdelecroix/16604 to public/16604
 Commit changed from de1dafd330dcf9b07899f677b26bcab6d0ba7297 to 976013cf69d2bdfab7772c047fdee6094292dc9c
Here it is ! And I agree with your commits of course, thank you again !
By the way : the improvement at #16720 is made by not using addition on the group/field objects from Sage, because it is too slow. So we have to keep that in mind if we ever meet speed problems again with these operations.
Nathann
New commits:
976013c  trac #16604: review of the reviewer's patch

comment:36 Changed 6 years ago by
 Commit changed from 976013cf69d2bdfab7772c047fdee6094292dc9c to 3d1482926f8621b2fc509aec9e6e4281244524af
Branch pushed to git repo; I updated commit sha1. New commits:
3d14829  trac #16604: the helper as a standalone function

comment:37 followup: ↓ 38 Changed 6 years ago by
Hi again,
I read the AbelCheng paper of 1994 (written during Julian Abel's thesis I guess) where the explanation was clear enough to write a complete documentation. The function has moved to orthogonal_array.py...
Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.
Vincent
PS: there are two mysteries that I will ask Julian about
 it is not clear to me why we need w^{c} = w + 1
 we do not care very much of the fact that the part different from
2^c
is a prime number
comment:38 in reply to: ↑ 37 ; followup: ↓ 39 Changed 6 years ago by
Yooooo !!!
I read the AbelCheng paper of 1994 (written during Julian Abel's thesis I guess) where the explanation was clear enough to write a complete documentation. The function has moved to orthogonal_array.py...
Great ! It is cool to have a good doc for this construction. But the function's name makes one think "Okay, this function takes c as an input and return an OA with n=2^c
".
Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.
Well. Did you read it three times yourself ? :P
 Most of the function's one line description defines what n is, and at this level we do not care much. What about
Returns an OA(k,G_12^c) from a constrained (G_1,k1,2)difference matrix
? It is a bit more meaningful and also indicates that the function's input is not as simple as a pair of integers...
 Why
G_1
and notG
?
 Shouldn't we use
F_p
rather thanGF(2)
in the doc ?
that belong t
 B and C : why not name them
A_{G_1}
andA_{GF(2)}
?
For any pair `i` and `j` of distinct integers in `{1,...,k1}` and `g` an element of `G_1`
>for any i\neq j and g\in G_1
?
C_{i,k_1}  C_{i,k_1}
is zero:P
 the array whose rowS
About the function's name here's my attempt: OA_p_times_2_pow_c_from_matrix
? With your name one can believe that it is just about powers of two. And the "from matrix" indicated that "if you are looking for something standard, pass your way".
Nathann
comment:39 in reply to: ↑ 38 ; followup: ↓ 43 Changed 6 years ago by
Hello,
Thanks for your careful reading.
Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.
Well. Did you read it three times yourself ?
:P
No. I wrote it three times ;?
 Most of the function's one line description defines what n is, and at this level we do not care much. What about
Returns an OA(k,G_12^c) from a constrained (G_1,k1,2)difference matrix
? It is a bit more meaningful and also indicates that the function's input is not as simple as a pair of integers...
done
 Why
G_1
and notG
?
Because G was the cartesian product. Now changed.
 Shouldn't we use
F_p
rather thanGF(2)
in the doc ?
You meant F_2
? And then use F_{2^c}
for GF(2^c)
. In non compiled version of the doc I found my version more readable. Moreover, it conincides with what you use in Sage to get your finite field. And it is pretty much standard (wikipedia entry for GF(2)).
that belong t
t > to (done)
 B and C : why not name them
A_{G_1}
andA_{GF(2)}
?
B and C is the notation from AbelCheng 1994. And it is much shorter when you have to write B_{i,k_1}
instead of (A_{GF(2)})_{i,k_1}
.
For any pair `i` and `j` of distinct integers in `{1,...,k1}` and `g` an element of `G_1`
>for any i\neq j and g\in G_1
?
done
C_{i,k_1}  C_{i,k_1}
is zero:P
you are right! It is now C_{i,k_1}  C_{j,k_1}
.
 the array whose rowS
done
About the function's name here's my attempt:
OA_p_times_2_pow_c_from_matrix
? With your name one can believe that it is just about powers of two. And the "from matrix" indicated that "if you are looking for something standard, pass your way".
As I mentioned it is not p_times_2_pow_c
but n_times_2_pow_c
. G
needs not be a cyclic group of prime order. Changed for OA_n_times_2_pow_c_from_matrix
.
Vincent
comment:40 Changed 6 years ago by
 Commit changed from 3d1482926f8621b2fc509aec9e6e4281244524af to 7b392539e555ec0796a9d4b76f885920c48616ac
Branch pushed to git repo; I updated commit sha1. New commits:
7b39253  trac #16604: updated documentation + name changed

comment:41 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:42 Changed 6 years ago by
 Commit changed from 7b392539e555ec0796a9d4b76f885920c48616ac to 3cf39835a05cafffa1406c0ace944f9f4b7e3042
comment:43 in reply to: ↑ 39 Changed 6 years ago by
Helloooooooooo !!
Thanks for your modifications. I added a small commit to fix a couple of things
 add the function in the new index
 Move the explanation on how elements of
GF(2^c)
should be encoded to the input section
I also tried to rephrase the last sentence of the explanation but I still don't get it. I replaced an occurrence of G_1
with G
(and I think that was not a mistake), plus I changed the bound 1<=i<= G
to 1<= i <= 2G
, and now it seems that you indexed Y
with i,j
while it should be indexed on k
. Especially since now that i
goes to 2G
the vector Y
has the wrong length. Plus you define Y
as being of length k1
. Could you check that again ?
You also defined k
as ranging from 1
to k1
which was a bit hard to read, so I "found a way around".
Tell me what you think !
Nathann
comment:44 Changed 6 years ago by
Hi,
I was a bit stupid: there is a k
in the parameter but I used it as a variable... so it is definitely confusing. Moreover in the AbelCheng articles they use transposed matrix so I was confused with rows and columns. I will add a commit about that in a minute.
Vincent
comment:45 Changed 6 years ago by
 Commit changed from 3cf39835a05cafffa1406c0ace944f9f4b7e3042 to d612056869f25d94835570fca45572bfd2f5ccc8
Branch pushed to git repo; I updated commit sha1. New commits:
d612056  trac #16604: on the doc again

comment:46 Changed 6 years ago by
The matrix A
has as many rows as the length of Y
and has 2G
columns...
Vincent
comment:47 Changed 6 years ago by
Cool ! This time I got it ! :D
It really is hell with everybody using the matrix or its transpose T_T
By the wayyyyyy... As this function is now public... Would you feel like writing some code to check that all constraints are satisfied ? ^^;
You see all these things better than I, that's why I ask... ^^;
Nathann
comment:48 Changed 6 years ago by
 Commit changed from d612056869f25d94835570fca45572bfd2f5ccc8 to bff470ee5b4bb561cae7f01cf08ed7dfe126fa94
Branch pushed to git repo; I updated commit sha1. New commits:
bff470e  trac #16604: small check of dimensions

comment:49 followup: ↓ 50 Changed 6 years ago by
Good idea. I did the dimension check... if we want more, we need is_difference_matrix
.
I would go for a positive review at this stage... what do you think?
Vincent
comment:50 in reply to: ↑ 49 Changed 6 years ago by
Yo !
Good idea. I did the dimension check... if we want more, we need
is_difference_matrix
.
We don't have is_difference_matrix
? O_o
Okay then I will write this today. You may like difference families but I like difference matrices.
We need a is_difference_matrix
. Then we'll finish this ticket.
Nathann
comment:51 Changed 6 years ago by
 Dependencies changed from #16582 to #16582,#16797
Ticket for is_difference_matrix: #16797
Nathann
comment:52 Changed 6 years ago by
 Commit changed from bff470ee5b4bb561cae7f01cf08ed7dfe126fa94 to 579e75bd1c2a355082d5cf04b7f0ecc95d6c092a
Branch pushed to git repo; I updated commit sha1. New commits:
8f10d94  trac #16797: is_difference_matrix

aa097f6  trac #16797: Fit with the current definition until we can change everything at once

5d21b8c  trac #16797: int * and ** instead of Python list

8f29bd1  trac #16797: change int to int * in a malloc

811e3e9  trac #16797: better malloc + better error msg

1b8c2e3  trac #16797: More compact mallocs

b78c347  trac #16797: Reorder the arguments to copy is_orthogonal_array

6c21904  trac #16797: correct a row/column inversion

48b6902  trac #16604: merge #16797

579e75b  trac #16604: input check + doctest

comment:53 Changed 6 years ago by
Needs review.
Vincent
comment:54 Changed 6 years ago by
 Commit changed from 579e75bd1c2a355082d5cf04b7f0ecc95d6c092a to 05c691500eb1131cb71303ed759ddf2cbc13b46f
comment:55 Changed 6 years ago by
Your turn !
Nathann
comment:56 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
I am happy with the current version.
Vincent
comment:57 Changed 6 years ago by
 Commit changed from 05c691500eb1131cb71303ed759ddf2cbc13b46f to 24c4f7fc4cf619fca8cceb5707b74b935de880c2
 Status changed from positive_review to needs_review
comment:58 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:59 Changed 6 years ago by
 Branch changed from public/16604 to 24c4f7fc4cf619fca8cceb5707b74b935de880c2
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16582: MOLS: Table with n<600 and updated syntax
trac #16582: Merged with beta5
trac #16604: new OA for n=112,160,224,514,796