Opened 4 years ago

Closed 4 years ago

#16884 closed enhancement (fixed)

Quasi-difference matrices (database+is_QDM)

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 quasi-difference matrices. As a result:

  • The Vmt vectors are added to the quasi-difference 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 the n of an OA(k,n) is the sum n+u. Consequently, if you want to build an OA(k,n) from a QDM you must try all pairs n'+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 4 years ago by ncohen

  • Branch set to public/16884
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by ncohen

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 quasi-difference matrix with k=m+2 columns, and for OA(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 an OA(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 Brouwer-van Rees version of Wilson's construction.

Nathann

comment:3 Changed 4 years ago by git

  • Commit set to fab7df1d9c61c974db44b80920f542f3ebdfbfd3

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

6fbe31btrac #16879: orthogonal_array_recursive.py -> pyx
5b1977dtrac #16879: a is_available function in orthogonal_arrays_recursive
613d30atrac #16879: more speed up
4d927f2trac #16879: rename orthogonal_arrays_recursive to orthogonal_arrays_find_recursive
3352371trac #16879: Move constructions from orthogonal_arrays_find to orthogonal_arrays_build (this, and only this)
a42144dtrac #16879: Fix the import statements
3db376ftrac #16879: Fix the doc
a44247atrac #16884: Remove OA constructors (they will be turned into QDM constructors)
b8f61a9trac #16884: A database entry for Quasi-difference matrices. +doc and stuff
fab7df1trac #16884: Convert OA(9,514) into a Vmt

comment:4 Changed 4 years ago by git

  • Commit changed from fab7df1d9c61c974db44b80920f542f3ebdfbfd3 to 3fc2696ba6e20a6b01b913897e66b258759ddb45

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

3fc2696trac #16884: broken doctest

comment:5 Changed 4 years ago by ncohen

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:

3fc2696trac #16884: broken doctest

comment:6 Changed 4 years ago by ncohen

  • Summary changed from A database entry for Quasi-difference matrices to Quasi-difference matrices (database+is_QDM)

Here is a real fix.

Nathann

comment:7 Changed 4 years ago by git

  • Commit changed from 3fc2696ba6e20a6b01b913897e66b258759ddb45 to bc157e6e7837aeeccb080e17e1ab838506386df9

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

bc157e6trac #16884: is_quasi_difference_matrix

comment:8 Changed 4 years ago by git

  • Commit changed from bc157e6e7837aeeccb080e17e1ab838506386df9 to a2922a439d868932a4b5a38dd9095941d83fc15a

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

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

comment:9 Changed 4 years ago by git

  • Commit changed from a2922a439d868932a4b5a38dd9095941d83fc15a to 15c78ba967f5f15644a7eb83f2825de3ba5fd7fd

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

d9e0475trac #16879: Move constructions from orthogonal_arrays_find to orthogonal_arrays_build (this, and only this)
5031aeetrac #16879: Fix the import statements
0c1893ftrac #16879: Fix the doc
6a3869dtrac #16879: speed up
d7129d6trac #16879: Trivial stuff
1979486trac #16884: Remove OA constructors (they will be turned into QDM constructors)
f23e0cftrac #16884: A database entry for Quasi-difference matrices. +doc and stuff
f074c38trac #16884: Convert OA(9,514) into a Vmt
781b168trac #16884: is_quasi_difference_matrix
15c78batrac #16884: A V(12,185) that yields a OA(11,2406)

comment:10 follow-up: Changed 4 years ago by vdelecroix

  • 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 non-commutative 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 ; follow-up: Changed 4 years ago by ncohen

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 non-commutative 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 Brouwer-van Rees construction (which I will update now).

And after the Brouwer-van 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 4 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:13 Changed 4 years ago by git

  • Commit changed from 15c78ba967f5f15644a7eb83f2825de3ba5fd7fd to f0b7bab049e078a663702a935ea5f09facd396ed

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

0be5b0btrac #16884: fix documentation
f0b7babtrac #16884: Doctest + a couple of fixes

comment:14 Changed 4 years ago by ncohen

Here it is !

Nathann

comment:15 in reply to: ↑ 11 ; follow-up: Changed 4 years ago by vdelecroix

  • 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 Brouwer-van 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 ; follow-up: Changed 4 years ago by ncohen

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 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).

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 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.

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 4 years ago by vdelecroix

  • Status changed from needs_info to positive_review

Replying to ncohen:

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).

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 quasi-difference 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 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:19 Changed 4 years ago by vbraun

  • Branch changed from public/16884 to f0b7bab049e078a663702a935ea5f09facd396ed
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.