Opened 10 years ago
Last modified 9 years ago
#12418 closed enhancement
adding Delsarte bound for codes — at Version 22
Reported by: | dimpase | Owned by: | wdj |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | coding theory | Keywords: | |
Cc: | jpang, kini, wdj, ncohen, ppurka, ptrrsn_1 | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12533, #13650 | Stopgaps: |
Description (last modified by )
Delsarte bound for codes, aka Linear Programming bound, is easy to implement in Sage.
To work well in big dimensions, one needs an arbitrary precision LP solver. We use an LP backend to PPL, which is available in Sage since #12533.
Change History (24)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Cc kini added
comment:3 Changed 10 years ago by
- Cc wdj added
comment:4 Changed 10 years ago by
- Cc ncohen added
- Description modified (diff)
comment:5 Changed 10 years ago by
comment:6 Changed 10 years ago by
- Cc ppurka added
comment:7 Changed 10 years ago by
The function named delsarte_bound
should be renamed to something like delsarte_bound_hamming_space
. This is so that in future other functions like delsarte_bound_johnson_space
, delsarte_bound_permutation_space
, etc can be added easily, without having inconsistencies in naming.
comment:8 Changed 10 years ago by
- Cc ptrrsn_1 added
comment:9 Changed 10 years ago by
- Description modified (diff)
comment:10 Changed 10 years ago by
- Dependencies set to #12533
- Description modified (diff)
comment:11 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:12 follow-ups: ↓ 14 ↓ 20 Changed 10 years ago by
I think the Krawtchouk
polynomial could be computed explicitly by not making repeated calls to binomial
. This should speed it up. I have something like this in mind:
def Krawtchouk2(n,q,l,i): # Use the expression in equation (55) of MacWilliams & Sloane, pg 151 # We write jth term = some_factor * (j-1)th term kraw = jth_term = (q-1)**l * binomial(n, l) # j=0 for j in range(1,l+1): jth_term *= -q*(l-j+1)*(i-j+1)/((q-1)*j*(n-j+1)) kraw += jth_term return kraw n,q,l,i = 10,8,7,5 timeit('Krawtchouk2(n,q,l,i)') timeit('Krawtchouk (n,q,l,i)') print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i) 625 loops, best of 3: 53.3 µs per loop 625 loops, best of 3: 205 µs per loop True
I noticed that sage handles nonintegral components in the binomial, so the expression for the Krawtchouk
already works with nonintegral n
and x
.
n,q,l,i = 10.6,8,7,5.4 #timeit('Krawtchouk3(n,q,l,i)') timeit('Krawtchouk2(n,q,l,i)') timeit('Krawtchouk (n,q,l,i)') print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i) print Krawtchouk2(n,q,l,i), Krawtchouk(n,q,l,i) 625 loops, best of 3: 382 µs per loop 125 loops, best of 3: 4.74 ms per loop False 93582.0160001147 93582.0159999999
comment:13 Changed 10 years ago by
Can you mention when it guarantees a weight spectrum? Would doing an ILP
make it a proper weight spectrum?
- ``return_data`` -- if ``True``, return a weights vector, which actually need not be a proper weight enumerator, or even have integer entries, and the LP.
Also, I think the term weight enumerator
refers to the weight enumerator polynomial
. Perhaps using weight distribution
or distance distribution
is more appropriate here.
comment:14 in reply to: ↑ 12 ; follow-up: ↓ 16 Changed 10 years ago by
Replying to ppurka:
I think the
Krawtchouk
polynomial could be computed explicitly by not making repeated calls tobinomial
. This should speed it up.
It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden set of distances, rather than just [1..d] ? It's a trivial add-on. I did this in a prototype code for Johnson schemes, here.
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
comment:15 Changed 10 years ago by
- Dependencies changed from #12533 to #12533, #13650
- Description modified (diff)
- Milestone changed from sage-5.4 to sage-5.5
comment:16 in reply to: ↑ 14 ; follow-up: ↓ 18 Changed 10 years ago by
Replying to dimpase:
Replying to ppurka:
I think the
Krawtchouk
polynomial could be computed explicitly by not making repeated calls tobinomial
. This should speed it up.It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
The point is that someone might try to use these polynomials more generally in a separate context. They are not defined anywhere else in Sage, so anyone who tries to use them will use this one.
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden set of distances, rather than just [1..d] ? It's a trivial add-on. I did this in a prototype code for Johnson schemes, here.
Wow! You have the Johnson scheme too?! Sure, add them all in!! Do you use the polynomials used by Aaltonen?
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
LP for permutation codes would be interesting. There are not too many good results known there. IIRC, it uses Charlier polynomials.
EDIT: FWIW, it is Charlier polynomials.
comment:17 Changed 10 years ago by
Oh, I forgot to add. Forbidden distances will be nice as well. I think only some special cases achieve the closed form solutions. In general, still not much is known. It looks like you only need to drop distances d_1,...,d_m
instead of 1,...,d
, right?
How about introducing an extra keyword called forbidden_distances
or exclude_distances
, which defaults to 1,...,d
?
comment:18 in reply to: ↑ 16 ; follow-up: ↓ 19 Changed 10 years ago by
Replying to ppurka:
Replying to dimpase:
Replying to ppurka:
I think the
Krawtchouk
polynomial could be computed explicitly by not making repeated calls tobinomial
. This should speed it up.It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
The point is that someone might try to use these polynomials more generally in a separate context. They are not defined anywhere else in Sage, so anyone who tries to use them will use this one.
Actually, I have most discrete orthogonal polynomials arising in the classical P- and Q- polynomial schemes implemented, although it's neither polished nor optimized.
[
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden set of distances, rather than just [1..d] ? It's a trivial add-on. I did this in a prototype code for Johnson schemes, here.
Wow! You have the Johnson scheme too?! Sure, add them all in!! Do you use the polynomials used by Aaltonen?
I use the descriptions in the book "Algebraic Combinatorics I" by E.Bannai and T.Ito. Something known as Eberlein polynomials.
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
LP for permutation codes would be interesting. There are not too many good results known there. IIRC, it uses Chebychev polynomials(?).
yes, this should be perfectly doable.
comment:19 in reply to: ↑ 18 Changed 10 years ago by
Replying to dimpase:
I use the descriptions in the book "Algebraic Combinatorics I" by E.Bannai and T.Ito. Something known as Eberlein polynomials.
That's for the binary case. For the q-ary case it is a product of Krawtchouk and Hahn, if I recall properly. Let me fish out the paper; I will send it to you.
comment:20 in reply to: ↑ 12 ; follow-up: ↓ 21 Changed 9 years ago by
Replying to ppurka:
I think the
Krawtchouk
polynomial could be computed explicitly by not making repeated calls tobinomial
. This should speed it up. I have something like this in mind:
This can be further optimized by using Horner's rule. I'll do this, and leave the rest (other schemes) for another ticket, OK?
comment:21 in reply to: ↑ 20 Changed 9 years ago by
Replying to dimpase:
This can be further optimized by using Horner's rule. I'll do this, and leave the rest (other schemes) for another ticket, OK?
Yes, yes. One space/polynomial at a time. Just Hamming space in this ticket is OK.
comment:22 Changed 9 years ago by
- Description modified (diff)
Please review. I added a Kravchouck speedup, and cleaned up docstrings as requested.
(GLPK can solve non-integer rational LP. It is not exposed, but may not be too hard either)