#14997: remove redundant lines from LinearCode.shortened() and speed up
LinearCode.punctured()
-----------------------------------------+-----------------------------
Reporter: ppurka | Owner:
Type: defect | Status: needs_review
Priority: minor | Milestone: sage-5.12
Component: coding theory | Resolution:
Keywords: | Merged in:
Authors: Punarbasu Purkayastha | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Dependencies:
Stopgaps: |
-----------------------------------------+-----------------------------
Description changed by ppurka:
Old description:
> Minor change, as mentioned in the title. The following two lines are not
> required since we already get a `LinearCode` instance from the
> `dual_code()` method.
>
> ----
> Apply [attachment:trac_14997.patch] to `devel/sage`
New description:
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 [attachment:trac_14997.patch] to `devel/sage`
--
--
Ticket URL: <http://trac.sagemath.org/ticket/14997#comment:2>
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/groups/opt_out.
