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:

Status badges

Description (last modified by ppurka)

  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

Attachments (1)

trac_14997.patch (1.2 KB) - added by ppurka 8 years ago.

Download all attachments as: .zip

Change History (7)

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()

Changed 8 years ago by ppurka

comment:3 Changed 8 years ago by ppurka

  • Cc dimpase added

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.