GSoC 1st - 8th September

This week a new optimization for the FGLM adapted algorithm has been added.
As expected, this new algoritm is faster for computing the grobner basis of the ideal associated to the linear code in the way we need it for the decoding algorithm.
Here is part of the comparisson of the groebner basis computation.

sage: C = RandomLinearCode(9,3,GF(4,'a'))                                                                                                                    

sage: I = C.create_ideal()                                                                                                                                   

sage: %time gB = I.groebner_basis('libsingular:stdfglm')                                                                                                     

CPU times: user 370.84 s, sys: 2.36 s, total: 373.19 s                                                                                                       

Wall time: 375.74 s                                                                                                                                       

sage: %time gb=C.groebner_basis_fglm()  #FGLM adapted algorithm                                                                                                                           

CPU times: user 16.36 s, sys: 0.10 s, total: 16.45 s                                                                                                         

Wall time: 16.78 s                                                                                                                                           

   

sage: C = RandomLinearCode(10,3,GF(5))

sage: %time gb = C.groebner_basis_fglm()#FGLM adapted algorithm

CPU times: user 581.37 s, sys: 2.21 s, total: 583.58 s

Wall time: 590.37 s

sage: I = C.create_ideal()

sage: %time gB = I.groebner_basis()

CPU times: user 1331.38 s, sys: 1.14 s, total: 1332.53 s

Wall time: 1336.74 s

In order to make this comparisson was necessary implement the function for creating the ideal associated to the code.  Code

Documentation of the FGLM adapted algorithm for linear codes over finite field in the general case and all other functions, including the new decoding algorithm has been documented a tested. The link to the repository:
https://bitbucket.org/vsuaste/coding-theory/commits/e3dc1a07f7d304700053981596493646ca06428f

Here some examples in which the new decoding algorithm is faster than syndrome decoding of sage:

sage: C = HammingCode(2,GF(7))

sage: C

Linear code of length 8, dimension 6 over Finite Field of size 7

sage: v = random_vector(GF(7),C.length())

sage: %time C.decode(v)    #syndrome algorithm

CPU times: user 2.10 s, sys: 0.03 s, total: 2.13 s

Wall time: 2.19 s

(0, 4, 5, 4, 1, 2, 5, 4)

sage: %time C.decode_fq(v)  #new decoding algorithm

CPU times: user 0.81 s, sys: 0.02 s, total: 0.83 s

Wall time: 0.87 s

(0, 5, 5, 1, 4, 1, 4, 6)

sage: C = HammingCode(2,GF(11))

sage: v = random_vector(GF(11), C.length())

sage: v

(0, 10, 0, 8, 10, 0, 2, 5, 2, 10, 10, 4)

sage: %time C.decode_fq(v) # new decoding algorithm

CPU times: user 53.32 s, sys: 1.45 s, total: 54.76 s

Wall time: 56.19 s

(0, 1, 0, 10, 8, 0, 0, 2, 3, 8, 8, 5)

sage: %time C.decode(v) ###syndrome algorithm still running after hours.....

sage: C = HammingCode(3,GF(4,'a'))

sage: v = random_vector(GF(4,'a'),C.length())

sage: v

(a + 1, a + 1, 0, a + 1, 0, 1, a + 1, a + 1, a + 1, a + 1, 0, 1, a, 1, a, 0, a + 1, 0, a, a + 1, 0)

sage: %time C.decode_fq(v) #new decoding algorithm

CPU times: user 81.18 s, sys: 1.36 s, total: 82.55 s

Wall time: 84.30 s

(0, 0, 0, a + 1, 0, 1, 0, 0, 0, 0, 0, 0, a, 1, 1, 0, a + 1, 0, a, a + 1, 1)

sage: %time C.decode(v) ###syndrome algorithm still running after hours.....