Opened 8 years ago

Closed 8 years ago

remove redundant lines from LinearCode.shortened() and speed up LinearCode.punctured()

Reported by: Owned by: ppurka minor sage-5.12 coding theory dimpase sage-5.12.beta3 Punarbasu Purkayastha Dmitrii Pasechnik N/A

1. Minor change in `LinearCode.shortened()`, as mentioned in the title. The following two lines are not required since we already get a `LinearCode` instance from the `dual_code()` method.
```         Cdpd = Cdp.dual_code()
-        Gs = Cdpd.gen_mat()
-        return LinearCode(Gs)
```
2. `LinearCode.punctured()` goes through the row space and then generates the basis vectors. This is very inefficient. Simply echelonizing the matrix speeds up the computations 4x for small generator matrices and over 18x for larger generator matrices.
```def puncture(C, coords):
G = C.gen_mat()
G = G.matrix_from_columns([i for i in range(G.ncols()) if i not in coords])
r = G.rank()
if r < G.nrows():
G.echelonize()
G = G[:r]
return LinearCode(G)

C = BinaryReedMullerCode(1, 3); C
Linear code of length 8, dimension 4 over Finite Field of size 2

timeit('C.punctured([0, 1, 2, 3, 7])'); C.punctured([0, 1, 2, 3, 7])
125 loops, best of 3: 946 µs per loop
Linear code of length 3, dimension 3 over Finite Field of size 2

timeit('puncture(C, [0, 1, 2, 3, 7])'); puncture(C, [0, 1, 2, 3, 7])
625 loops, best of 3: 221 µs per loop
Linear code of length 3, dimension 3 over Finite Field of size 2

C = BinaryReedMullerCode(3, 9); C
Linear code of length 512, dimension 130 over Finite Field of size 2

timeit('C.punctured([0, 1, 2, 3, 7])'); C.punctured([0, 1, 2, 3, 7])
5 loops, best of 3: 164 ms per loop
Linear code of length 507, dimension 130 over Finite Field of size 2

timeit('puncture(C, [0, 1, 2, 3, 7])'); puncture(C, [0, 1, 2, 3, 7])
25 loops, best of 3: 8.27 ms per loop
Linear code of length 507, dimension 130 over Finite Field of size 2
```

Apply trac_14997.patch to `devel/sage`

comment:1 Changed 8 years ago by ppurka

• Authors set to Punarbasu Purkayastha
• Description modified (diff)
• Status changed from new to needs_review

comment:2 Changed 8 years ago by ppurka

• Description modified (diff)
• Summary changed from remove redundant lines from LinearCode.shortened() to remove redundant lines from LinearCode.shortened() and speed up LinearCode.punctured()

comment:4 Changed 8 years ago by dimpase

• Status changed from needs_review to positive_review

comment:5 Changed 8 years ago by jdemeyer

• Reviewers set to Dmitrii Pasechnik

comment:6 Changed 8 years ago by jdemeyer

• Merged in set to sage-5.12.beta3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.