search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.35k stars 462 forks source link

find_brouwer_van_rees_with_one_truncated_column #16922

Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 9 years ago

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

Here is what we have been waiting for. Removes a lot of '-', but in parts of the table that we do not see :-P

Depends on #16920

CC: @videlec

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 955b67f

Reviewer: Vincent Delecroix

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

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

Branch: public/16922

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

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

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)
8916046trac #16559: Brouwer-Van Rees version of Wilson's decomposition
cf11457trac #16559: Fixed error message for large holes and smaller example
4ecf942trac #16920: New V(m,t) vectors
b06bc3btrac #16920: Make the V(m,t) database more compact
c26542btrac #16920: Even more MOLS
822f174trac #16922: find_brouwer_van_rees_with_one_truncated_column
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 822f174

videlec commented 9 years ago
comment:3

Hi Nathann,

I got a lot of segmentation error while running the tests with this branch! Do you know what happen?

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:4

Sorry about that. Don't know where the segfaults came from, but when I solved the bug about the "more than 4 values needed to unpack" there was none left.

Also, I rewrote history to move this last commit above its dependencies (in which commits had been added in the meantime).

This should be better now.

By the way: the current implementation may look a bit "hacky". The thing is that it is 'a bit too early' to implement this construction, because at the moment there are no 'nice' functions to query the database of incomplete orthogonal arrays, and there is none yet because caching incomplete orthogonal arrays is much harder than caching orthogonal arrays (more parameters, mainly !). In the future we may even have find functions for incomplete orthogonal arrays and stuff.

Well, I have to write that and because it is not exactly straightforward to get a good design (and because it requires a lot of 'administrative' code) I implemented that first.

Still, it works and it is not so bad.

Well, just know that I am not intending to leave that code in the current state. Though I tried to not make it too awful either, and of course the review is there to fix anything you will not like.

Branch updated.

Nathann

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

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

9b8ba79trac #16559: Fixes reported by Julian R. Abel
b0419b8trac #16559: Merged with 6.4.beta6
fe62ae4trac #16559: Bugfix
12177d8trac #16559: fix documentation
3825155trac #16559: remove simple_wilson_construction
9bbd1f2trac #16559: A description for the Brouwer-van Rees construction
cf90906trac #16920: Correct bibliographical references
cf378abtrac #16920: Merged with updated #16559
0d26d10trac #16922: find_brouwer_van_rees_with_one_truncated_column
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 822f174 to 0d26d10

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

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

b71013atrac #16922: big optim. + small optim. + doctest
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 0d26d10 to b71013a

videlec commented 9 years ago
comment:7

Hi Nathann,

I changed the complexity of multiple by one order. And we can win more by cutting some of the branches (if I got the value v in m steps then I can not be bigger than v + (k-m) max_value at the end).

Have a look and tell me if it is worth it to add this cut.

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:8

I changed the complexity of multiple by one order.

True, True. Well done O_o

And we can win more by cutting some of the branches (if I got the value v in m steps then I can not be bigger than v + (k-m) max_value at the end).

Well, technically can't we do it with log(k) iterations instead of k ?

I mean, if you call S^n={x_1+...+x_n: x_i \in S} then you can use the log algorithm to compute the power of a matrix, can't you ? And you can do even faster is you initialize D with D = {r*x:tuple([x]*r) for x in S for r in tuple(range(cutoff/x+1))}.

Keep in mind that this function will change, somehow. I mean... If we want to be able to do the same for the Brouwer-van Rees decomposition with 2 truncated columns, the problem is very different: in each column you can have any combinations of 'allowed value', but you cannot have a multiplier x in column 1 and a multiplier y in column 2 unless you have an OA(k,m+x+y)-OA(k,x)-OA(k,y).

I still don't know how to write that nicely T_T

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:9

Yo !

Have a look and tell me if it is worth it to add this cut.

It is up to you. I am not sure that it is necessary at the moment: I hope that this will all be rewritten in not so long to handle two columns.

Nathann

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

Changed commit from b71013a to 955b67f

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

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

955b67ftrac #16922: rewrite multiple (new name int_as_sum)
videlec commented 9 years ago
comment:11

All right. Done.

I find it much clearer. Perhaps less nicer to make it works for two columns...

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:12

What is the point of making it decrease toward zero ? O_o

To have more meaningful comments like if (vv > 0 and # The new integer i is too big ?

Honestly I do not care, this will be rewritten soon anyway. But why would you do something like that ?

You even do for j in range(k-1,-1,-1) which is totally equivalent to for j in range(k) given that you do not use j. Only to make it more complicated ?...

Nathann

videlec commented 9 years ago
comment:13

Replying to @nathanncohen:

What is the point of making it decrease toward zero ? O_o

To have more meaningful comments like if (vv > 0 and # The new integer i is too big ?

Honestly I do not care, this will be rewritten soon anyway. But why would you do something like that ?

You even do for j in range(k-1,-1,-1) which is totally equivalent to for j in range(k) given that you do not use j. Only to make it more complicated ?...

Hum. j is useful as it is the remaining number of steps and allow to cut branches when the maximum number of steps allowed (i.e. k_max) is relatively small.

+ if (vv > 0 and            # The new integer i is too big
+     vv <= j*max_value and # The new integer i is too small
+     vv not in D and       # We had it in D already
+     vv not in new_D):     # We had it in new_D already

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:14

This code is awful.

Anyway, I will rewrite it soon.

Nathann

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

Reviewer: Vincent Delecroix

vbraun commented 9 years ago

Changed branch from public/16922 to 955b67f