Open 909be1dd-d710-47b0-8f51-48d1bdcdb816 opened 7 years ago
Branch: u/imarquez/groebner-decoder
Commit: 0fa5896
Changed branch from u/imarquez/groebner-decoder to u/danielaugot/groebner-decoder
Hi Irene,
there was a very minor conflict (traling whitespace) in merging with develop.
Daniel
New commits:
de27033 | merge solved, by removing a trailing whitespace |
Changed branch from u/danielaugot/groebner-decoder to u/imarquez/groebner-decoder
Branch pushed to git repo; I updated commit sha1. New commits:
8f4bb7a | Eliminate the rest of the conflict marks |
I will continue working in the documentation and extra functions in the following days.
Changed branch from u/imarquez/groebner-decoder to u/mmarco/groebner-decoder
Changed branch from u/mmarco/groebner-decoder to u/imarquez/groebner-decoder
Branch pushed to git repo; I updated commit sha1. New commits:
76b83d7 | Documentation correct |
New functions have been added: coset_leaders, coset_weight_distribution, covering_radius(without Magma), newton_radius and unique_decoding_radius().
Documentation now is correct
Sorry before is covering_radius (without the optional package of GUAVA)
Hello Irene,
I actually implemented a version of covering_radius
which does not use GUAVA in
very slow Python algorithm instead of using GUAVA.
We should benchmark your implementation and mine, and keep the fastest one. BTW, I did some benchmarking GUAVA vs. naive Python implementation, and GUAVA was always faster (which is why I automatically use GUAVA calls if the user has GUAVA installed).
David
In the _insert_next_fq method, you treat these two different cases:
if List:
for i in s:
new = v.__copy__()
for q in Fqstar:
new[i]=q
if new not in List:
List.append(new.__copy__())
else:
for i in s:
new = v.__copy__()
for q in Fqstar:
new[i]=q
List.append(new.__copy__())
is it really what you want to do? wouldn't it make sense to just use the first case everywhere?
That whole helper-method can be simplified into an almost-one-liner: all error-vectors of weight 1 can be created as:
I = identity_matrix(F, n)
single_errs = ( a * I.row(i) for a in F for i in range(n) )
Now you want to extend List
with the elements [ v + e for e in single_errs ]
.
But you want to avoid duplicating the elements already in List
. Therefore you should use a set
for List
. This causes a small snag since set
s only work for immutable vectors.
Assuming single_errs
was computed outside at the beginning of the method, then the update of List
in the loop of coset_leaders
could look like
shifts = [ v + e for e in single_errs ]
for w in shifts: w.set_immutable()
List.union(shifts)
List
breaks the convention of starting variables with minuscule. What about the name worklist
?
Best, Johan
The keyword algorithm
for the "one"/"all" of coset_leaders
is not good: algorithm
is reserved for different methods with which to compute the result. What about representative = True
, where representative = False
means to output all of them.
Replying to @miguelmarco:
In the _insert_next_fq method, you treat these two different cases: is it really what you want to do? wouldn't it make sense to just use the first case everywhere?
I think the if
condition should be kept. It makes a difference and avoids a linear search inside a for
loop in the case List
is empty.
This causes a small snag since sets only work for immutable vectors.
I think we should not return immutable vectors from coset leaders. The output might be used for further computations by the user and then it will create strange issues, which will be hard to debug. The less surprises we have for the user, the better it is.
List
breaks the convention of starting variables with minuscule. What about the nameworklist
?
This can be done I suppose, just for consistency.
The keyword algorithm for the "one"/"all" of coset_leaders is not good
I agree. This is not really a different algorithm.
If you care about the coset_leaders
method I see many improvements possibles:
deque
instead of list
for the worklist;1
).Just as a quick model you might want to look at this:
import collections
def coset_leaders_one(C):
H = C.parity_check_matrix().transpose()
K = C.base_ring()
q = K.cardinality()
def my_generator(v):
t = list(v)
for i, vi in enumerate(v):
if vi: break
for a in K:
if a:
t[i] = a
yield vector(t)
t[i] = 0
def normalize(s):
for si in s:
if si:
return tuple(s / si)
return tuple(s)
z = vector(K, C.length())
sz = normalize(C.syndrome(z))
S = {sz: z}
generators = collections.deque([my_generator(z)])
target_size = (q ** H.ncols() - 1) // (q - 1) + 1
while generators:
g = generators.popleft()
for v in g:
syndrome = normalize(v*H)
if syndrome not in S:
S[syndrome] = v
if len(S) == target_size:
r = [S.pop(sz)]
for s in S.values():
r.extend(a * s for a in K if a)
return r
if not v[0]:
generators.append(my_generator(v))
You can adapt this for the case where you want them all.
You might also look at this implementation: u/ylchapuy/coset_leaders
@sagetrac-ylchapuy Thank you for this implementation. If you have this implementation in a Ticket somewhere please try to get it in first, and make this ticket a dependency of the other one. Your implementation is several hundred times faster than this one.
Meanwhile, I have been checking whether the coset leaders returned in your function "match" with the coset leaders returned by the implementation in this ticket. I haven't looked into it in detail, but there is a discrepancy. The discrepancy is not present for all codes though.
sage: from coset_1 import coset_leaders_one
sage: from coset_2 import coset_leaders
sage: C = codes.ReedSolomonCode(7,5,GF(8,'a'))
/mnt/usb/Installations/sage/src/bin/sage-ipython:1: DeprecationWarning: codes.Re
edSolomonCode is now deprecated. Please use codes.GeneralizedReedSolomonCode ins
tead.
See http://trac.sagemath.org/18928 for details.
#!/usr/bin/env python
sage: L1 = coset_leaders_one(C)
sage: L2 = coset_leaders(C, "one")
sage: L2_2 = flatten(L2)
sage: L1bool = [False]*len(L1)
sage: L2bool = [False]*len(L2)
sage: Fqstar = C.base_ring().list()[1:]
sage: for i,w in enumerate(L1):
....: wlist = [_*w for _ in Fqstar]
....: for _w in wlist:
....: if _w in L2_2:
....: L1bool[i] = True
....: break
....: for i,v in enumerate(L2_2):
....: vlist = [_*v for _ in Fqstar]
....: for _v in vlist:
....: if _v in L1:
....: L2bool[i] = True
....: break
....:
sage: all(L1bool)
True
sage: all(L2bool)
False
sage: %time L1 = coset_leaders_one(C)
CPU times: user 6.67 ms, sys: 0 ns, total: 6.67 ms
Wall time: 6.02 ms
sage: %time L2 = coset_leaders(C)
CPU times: user 8.43 s, sys: 3.33 ms, total: 8.44 s
Wall time: 8.39 s
sage: len(L1)
64
sage: len(L2)
64
sage: len(L2_2)
64
Replying to @ppurka:
@sagetrac-ylchapuy Thank you for this implementation. If you have this implementation in a Ticket somewhere please try to get it in first, and make this ticket a dependency of the other one. Your implementation is several hundred times faster than this one.
The ticket where this should be done is #19913 .
Sadly I won't have time to do more on this in the foreseeable future, but would be pleased if someone else is motivated enough to integrate this on his own.
And as a side remark, the code in the branch from comment:19 is even much better.
6 time faster on your example code:
sage: C
[7, 5, 3] Generalized Reed-Solomon Code over Finite Field in a of size 2^3
sage: %timeit coset_leaders_one(C)
100 loops, best of 3: 3.03 ms per loop
sage: %timeit _coset_leaders(C)
1000 loops, best of 3: 477 µs per loop
and on a some bigger examples
sage: C = codes.random_linear_code(GF(7), 32, 27)
sage: %timeit coset_leaders_one(C)
1 loop, best of 3: 1.35 s per loop
sage: %timeit _coset_leaders(C)
10 loops, best of 3: 78.2 ms per loop
sage: C = codes.random_linear_code(GF(3), 32, 22)
sage: %timeit coset_leaders_one(C)
1 loop, best of 3: 23.8 s per loop
sage: %timeit _coset_leaders(C)
1 loop, best of 3: 1.18 s per loop
I didn't try with the implementation from here...
A new version of the ticket #14973 adapted to the new coding Theory framework
CC: @johanrosenkilde @sagetrac-dlucas @sagetrac-danielaugot
Component: coding theory
Keywords: sd75
Author: Irene Márquez-Corbella, Miguel Marco
Branch/Commit: u/imarquez/groebner-decoder @
76b83d7
Issue created by migration from https://trac.sagemath.org/ticket/21339