Opened 6 years ago
Closed 6 years ago
#16884 closed enhancement (fixed)
Quasidifference matrices (database+is_QDM)
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:  f0b7bab (Commits)  Commit:  f0b7bab049e078a663702a935ea5f09facd396ed 
Dependencies:  #16879  Stopgaps: 
Description
A new database entry for quasidifference matrices. As a result:
 The Vmt vectors are added to the quasidifference matrices database entry, and not anymore to
OA_constructions
 The old OA constructions based on QDM are converted to QDM constructors.
 The OA constructor now queries the QDM database entry (and so it gets the QDM+Vmt)
Two notes:
 There is no
is_quasi_difference_matrix
right now, so the QDM are tested through the OA they generate.
 There is no
designs.quasi_difference_matrix
because I did not know how to write it in such a way that it would be easy to find a QDM that builds an OA. The problem is that a QDM is defined with 5 parameters(n,_,_,_,u)
and that then
of anOA(k,n)
is the sumn+u
. Consequently, if you want to build anOA(k,n)
from a QDM you must try all pairsn'+u = n
and that's a waste of time.
 Right now the DM are not added to the dictionary of QDM. I did not see the point, given that the DM are already queried by
orthogonal_arrays()
through their constructor (which will also contain additional constructions of DM).
Change History (19)
comment:1 Changed 6 years ago by
 Branch set to public/16884
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Commit set to fab7df1d9c61c974db44b80920f542f3ebdfbfd3
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
6fbe31b  trac #16879: orthogonal_array_recursive.py > pyx

5b1977d  trac #16879: a is_available function in orthogonal_arrays_recursive

613d30a  trac #16879: more speed up

4d927f2  trac #16879: rename orthogonal_arrays_recursive to orthogonal_arrays_find_recursive

3352371  trac #16879: Move constructions from orthogonal_arrays_find to orthogonal_arrays_build (this, and only this)

a42144d  trac #16879: Fix the import statements

3db376f  trac #16879: Fix the doc

a44247a  trac #16884: Remove OA constructors (they will be turned into QDM constructors)

b8f61a9  trac #16884: A database entry for Quasidifference matrices. +doc and stuff

fab7df1  trac #16884: Convert OA(9,514) into a Vmt

comment:4 Changed 6 years ago by
 Commit changed from fab7df1d9c61c974db44b80920f542f3ebdfbfd3 to 3fc2696ba6e20a6b01b913897e66b258759ddb45
Branch pushed to git repo; I updated commit sha1. New commits:
3fc2696  trac #16884: broken doctest

comment:5 Changed 6 years ago by
Except that there is a stupid test that ensures that something wrong holds, i.e. that all Vmt can be turned into full OA.
I will implement a is_quasi_difference_matrix
to change that test, but in the meantime I will just avoid the bad case.
Nathann
New commits:
3fc2696  trac #16884: broken doctest

comment:6 Changed 6 years ago by
 Summary changed from A database entry for Quasidifference matrices to Quasidifference matrices (database+is_QDM)
Here is a real fix.
Nathann
comment:7 Changed 6 years ago by
 Commit changed from 3fc2696ba6e20a6b01b913897e66b258759ddb45 to bc157e6e7837aeeccb080e17e1ab838506386df9
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
bc157e6  trac #16884: is_quasi_difference_matrix

comment:8 Changed 6 years ago by
 Commit changed from bc157e6e7837aeeccb080e17e1ab838506386df9 to a2922a439d868932a4b5a38dd9095941d83fc15a
Branch pushed to git repo; I updated commit sha1. New commits:
a2922a4  trac #16884: A V(12,185) that yields a OA(11,2406)

comment:9 Changed 6 years ago by
 Commit changed from a2922a439d868932a4b5a38dd9095941d83fc15a to 15c78ba967f5f15644a7eb83f2825de3ba5fd7fd
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
d9e0475  trac #16879: Move constructions from orthogonal_arrays_find to orthogonal_arrays_build (this, and only this)

5031aee  trac #16879: Fix the import statements

0c1893f  trac #16879: Fix the doc

6a3869d  trac #16879: speed up

d7129d6  trac #16879: Trivial stuff

1979486  trac #16884: Remove OA constructors (they will be turned into QDM constructors)

f23e0cf  trac #16884: A database entry for Quasidifference matrices. +doc and stuff

f074c38  trac #16884: Convert OA(9,514) into a Vmt

781b168  trac #16884: is_quasi_difference_matrix

15c78ba  trac #16884: A V(12,185) that yields a OA(11,2406)

comment:10 followup: ↓ 11 Changed 6 years ago by
 Status changed from needs_review to needs_info
Hello,
1) In the definition of quasi difference matrix, why do you require the group G to be Abelian? I saw that your definition coincides with the one from the handbook... but still. The question is just why. I don't mind the restriction since I do not know of any example on a noncommutative group.
2) You did not modify the doctests, is it on purpose
$ sage coverage database.py  SCORE database.py: 100.0% (68 of 68) Possibly wrong (function name doesn't occur in doctests): * line 1955: def QDM_19_6_1_0_1() * line 1987: def QDM_21_5_1_0_1() * line 2032: def QDM_21_6_1_0_5() * line 2070: def QDM_25_6_1_0_5() * line 2113: def QDM_33_6_1_0_1() * line 2154: def QDM_37_6_1_0_1() * line 2190: def QDM_35_7_1_0_7() * line 2225: def QDM_45_7_1_0_9() * line 2260: def QDM_54_7_1_0_8() * line 2295: def QDM_57_9_1_0_8() 
For the following see public/16884b
1') I got an error building the doc, because you used ::
instead of :
in is_quasi_difference_matrix
.
Vincent
comment:11 in reply to: ↑ 10 ; followup: ↓ 15 Changed 6 years ago by
Hello !
1) In the definition of quasi difference matrix, why do you require the group G to be Abelian? I saw that your definition coincides with the one from the handbook... but still. The question is just why. I don't mind the restriction since I do not know of any example on a noncommutative group.
No other reason, I just took the def from the Handbook.
2) You did not modify the doctests, is it on purpose
Nonono it is a mistake, I first wrote those functions when we had no is_quasi_difference_matrix
function and I had no other choice. It is fixed. Plus the '0' in the functions was actually a 1 and I had forgotten to update it.
I also changed the layout of the QDM dictionary: as for other dictionaries, the 'k' is a key. It is easier this way, I learned that by writing my update to the Brouwervan Rees construction (which I will update now).
And after the Brouwervan Rees construction is reviewed I will have to thing hard about a find_*
function. The good news is that it should make many  disappear :P
Nathann
comment:12 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:13 Changed 6 years ago by
 Commit changed from 15c78ba967f5f15644a7eb83f2825de3ba5fd7fd to f0b7bab049e078a663702a935ea5f09facd396ed
comment:14 Changed 6 years ago by
Here it is !
Nathann
comment:15 in reply to: ↑ 11 ; followup: ↓ 16 Changed 6 years ago by
 Status changed from needs_review to needs_info
Replying to ncohen:
2) You did not modify the doctests, is it on purpose
Nonono it is a mistake, I first wrote those functions when we had no
is_quasi_difference_matrix
function and I had no other choice. It is fixed. Plus the '0' in the functions was actually a 1 and I had forgotten to update it.I also changed the layout of the QDM dictionary: as for other dictionaries, the 'k' is a key.
You mean a value I gues. As the code is
for ((n,k,lmbda,mu,u),f) in [...]: if not (n+u,lmbda) in QDM: QDM[n+u,lmbda] = {} QDM[n+u,lmbda][n,lmbda,mu,u] = (k,f)
And after the Brouwervan Rees construction is reviewed I will have to thing hard about a
find_*
function. The good news is that it should make many  disappear:P
You can also set the values by hand (but still try hard to find more values).
More comments:
3) When there does exist a good QDM
to build an OA(k,n)
, could we use _OA_cache_set(kk,n,True)
instead of _OA_cache_set(k,n,True)
. We will win some few calls (especially when running MOLS_table
).
4) I wonder if such things as 3) above is doable with difference_matrix
as well. For example we could put a call to _OA_cache_set
inside difference_matrix
to set the existence to a potentially bigger k
. Alternatively, one can write _OA_cache_set(n,difference_matrix(n,None,existence=True))
in the core of orthogonal_array
but it might be slower.
Vincent
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 6 years ago by
Yo !
You mean a value I gues. As the code is
Indeed. And I may do the same for 'mu' in the future too. This variable is mostly useless.
You can also set the values by hand (but still try hard to find more values).
I began to write something which may more or less work. But today I had to clean the house in which I spent the week, tomorrow will be filled with travelling and sunday too. Adventure :P
3) When there does exist a good
QDM
to build anOA(k,n)
, could we use_OA_cache_set(kk,n,True)
instead of_OA_cache_set(k,n,True)
. We will win some few calls (especially when runningMOLS_table
).
I don't understand your sentence O_o
4) I wonder if such things as 3) above is doable with
difference_matrix
as well. For example we could put a call to_OA_cache_set
insidedifference_matrix
to set the existence to a potentially biggerk
. Alternatively, one can write_OA_cache_set(n,difference_matrix(n,None,existence=True))
in the core oforthogonal_array
but it might be slower.
Hmmmm.. I prefer that only the OA constructor plays with the OA_cache
. I thought once or twice while coding that it was a good thing but I forgot why.
Nathann
comment:17 in reply to: ↑ 16 Changed 6 years ago by
 Status changed from needs_info to positive_review
Replying to ncohen:
3) When there does exist a good
QDM
to build anOA(k,n)
, could we use_OA_cache_set(kk,n,True)
instead of_OA_cache_set(k,n,True)
. We will win some few calls (especially when runningMOLS_table
).I don't understand your sentence
O_o
Nevermind. I was wrong. My question should have been: if I ask for orthogonal_array(None,n,existence=True)
is there a better strategy to adopt when dealing with quasidifference matrix case. The answer is yes, but it is not nice to write down in your flow of if/elif/elif/...
.
Good to go!
Vincent
comment:18 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
comment:19 Changed 6 years ago by
 Branch changed from public/16884 to f0b7bab049e078a663702a935ea5f09facd396ed
 Resolution set to fixed
 Status changed from positive_review to closed
Oh, I forgot to say why this patch is useful:
There is a problem currently with the way Sage manages Vmt vectors. Indeed, from a Vmt ont can build a quasidifference matrix with
k=m+2
columns, and forOA(9,514)
(see last commit) the OA construction has to do a small change: 1) build the QDM from the Vmt; 2) Remove a column from the QDM; 3) Build the OA from the reduced QDM.Now, building the OA from the reduced QDM means filling a hole with an
OA(9,57)
(which exists). If the QDM is not reduced first, turning the QDM into an OA required anOA(10,57)
, which we don't have.For this reason the
OA(9,514)
was not included in the Vmt vectors, and this branch fixes it.The good thing is that with this branch everything is handled correctly (and the QDM automatically reduced if needed), which means that we can add to the Vmt database some Vmt that cannot be turned into complete OA.
Two good points:
1) I can not add another Vmt which had the same problem as this 514 thing and creates an OA that we do not have already
2) I can now add Vmt that will produce incomplete OA that can be used by
incomplete_orthogonal_array
to get OA with holes of size>1
, and that means perhaps being able to use the Brouwervan Rees version of Wilson's construction.Nathann