#16922: find_brouwer_van_rees_with_one_truncated_column
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorial | Resolution:
designs | Merged in:
Keywords: | Reviewers:
Authors: Nathann Cohen | Work issues:
Report Upstream: N/A | Commit:
Branch: public/16922 | b71013a5ffb081f77fc8a0a75338c8a39c3a378c
Dependencies: #16920 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (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
--
Ticket URL: <http://trac.sagemath.org/ticket/16922#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
