Opened 7 years ago

Closed 6 years ago

# find_brouwer_van_rees_with_one_truncated_column

Reported by: Owned by: ncohen major sage-6.4 combinatorial designs vdelecroix Nathann Cohen Vincent Delecroix N/A 955b67f 955b67f0cf7f5f0e584a8f7fb0d3520c675fc37e #16920

### Description

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

### comment:1 Changed 7 years ago by ncohen

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

### comment:2 Changed 7 years ago by git

• Commit set to 822f174b04d1fbea062e4431bbba4a95215c4071

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

 ​f23e0cf trac #16884: A database entry for Quasi-difference 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) ​8916046 trac #16559: Brouwer-Van Rees version of Wilson's decomposition ​cf11457 trac #16559: Fixed error message for large holes and smaller example ​4ecf942 trac #16920: New V(m,t) vectors ​b06bc3b trac #16920: Make the V(m,t) database more compact ​c26542b trac #16920: Even more MOLS ​822f174 trac #16922: find_brouwer_van_rees_with_one_truncated_column

### comment:3 Changed 6 years ago by vdelecroix

• Status changed from needs_review to needs_work

Hi Nathann,

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

Vincent

### comment:4 Changed 6 years ago by ncohen

• Status changed from needs_work to needs_review

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

### comment:5 Changed 6 years ago by git

• Commit changed from 822f174b04d1fbea062e4431bbba4a95215c4071 to 0d26d101552d5c279f849f17fbc7186a421d709e

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

 ​9b8ba79 trac #16559: Fixes reported by Julian R. Abel ​b0419b8 trac #16559: Merged with 6.4.beta6 ​fe62ae4 trac #16559: Bugfix ​12177d8 trac #16559: fix documentation ​3825155 trac #16559: remove simple_wilson_construction ​9bbd1f2 trac #16559: A description for the Brouwer-van Rees construction ​cf90906 trac #16920: Correct bibliographical references ​cf378ab trac #16920: Merged with updated #16559 ​0d26d10 trac #16922: find_brouwer_van_rees_with_one_truncated_column

### comment:6 Changed 6 years ago by git

• Commit changed from 0d26d101552d5c279f849f17fbc7186a421d709e to b71013a5ffb081f77fc8a0a75338c8a39c3a378c

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

 ​b71013a trac #16922: big optim. + small optim. + doctest

### comment:7 follow-ups: ↓ 8 ↓ 9 Changed 6 years ago by vdelecroix

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

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

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

Nathann

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

Vincent

Version 0, edited 6 years ago by ncohen (next)

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

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

### comment:10 Changed 6 years ago by git

• Commit changed from b71013a5ffb081f77fc8a0a75338c8a39c3a378c to 955b67f0cf7f5f0e584a8f7fb0d3520c675fc37e

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

 ​955b67f trac #16922: rewrite multiple (new name int_as_sum)

### comment:11 Changed 6 years ago by vdelecroix

All right. Done.

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

Vincent

### comment:12 follow-up: ↓ 13 Changed 6 years ago by ncohen

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

Last edited 6 years ago by ncohen (previous) (diff)

### comment:13 in reply to: ↑ 12 Changed 6 years ago by vdelecroix

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

### comment:14 Changed 6 years ago by ncohen

This code is awful.

Anyway, I will rewrite it soon.

Nathann

### comment:15 Changed 6 years ago by ncohen

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

### comment:16 Changed 6 years ago by vbraun

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