Opened 8 years ago
Closed 8 years ago
#14997 closed defect (fixed)
remove redundant lines from LinearCode.shortened() and speed up LinearCode.punctured()
Reported by: | ppurka | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.12 |
Component: | coding theory | Keywords: | |
Cc: | dimpase | Merged in: | sage-5.12.beta3 |
Authors: | Punarbasu Purkayastha | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
- Minor change in
LinearCode.shortened()
, as mentioned in the title. The following two lines are not required since we already get aLinearCode
instance from thedual_code()
method.Cdpd = Cdp.dual_code() - Gs = Cdpd.gen_mat() - return LinearCode(Gs)
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
Attachments (1)
Change History (7)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Description modified (diff)
- Summary changed from remove redundant lines from LinearCode.shortened() to remove redundant lines from LinearCode.shortened() and speed up LinearCode.punctured()
Changed 8 years ago by
comment:3 Changed 8 years ago by
- Cc dimpase added
comment:4 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:5 Changed 8 years ago by
- Reviewers set to Dmitrii Pasechnik
comment:6 Changed 8 years ago by
- 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.