Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#19463 closed enhancement (fixed)

A coding/two_weight_db module

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.10
Component: coding theory Keywords:
Cc: jsrn, dlucas, dimpase Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: a865eb3 (Commits) Commit:
Dependencies: #19624 Stopgaps:

Description (last modified by ncohen)

This ticket creates a new coding/two_weight_db module.

In it are stored all codes that were stored in graphs/strongly_regular_db.pyx. I expect that this file will change heavily, if we end up enriching our list of two weight codes for their own sake.

A first commit moves out of the strongly_regular_graph function the code that builds the database of small strongly regular graphs. Which turned out to be a good idea later, as building this list actually takes some time in order to guess the parameters of the SRG from the 2-weight code.

Nathann

Change History (46)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/19463
  • Commit set to 9d9894a361f22299a6162ea3b4b3f74a4e225085
  • Status changed from new to needs_review

What the hell. I made a mistake and was dead sure I had deleted that branch that took me hours. Praise the Lord for 'git reflog' [1] O_o

Nathann

[1] http://stackoverflow.com/questions/3640764/can-i-recover-branch-after-its-deletion-in-git


New commits:

6e37891trac #19463: A function to build the db of small srgs
9d9894atrac #19463: A coding/two_weight_db module

comment:2 Changed 4 years ago by dimpase

in [BJ03], you get name wrong; it is Iliya Bouyukliev, Juriaan Simonis, i.e. the 1st names are Iliya and Juriaan. (Juriaan is not so uncommon given Dutch name, Simonis is a relatively rare Dutch/Flemish surname).

comment:3 Changed 4 years ago by dimpase

The code should be capable of telling whether an SRG with such and such parameters can be constructed merely from knowledge of parameters of two-weight codes available in the DB. Currently this is not implemented, partly due to an error in the formulas on http://moodle.tec.hkr.se/~chen/research/2-weight-codes/index.htm

comment:4 follow-up: Changed 4 years ago by vdelecroix

Isn't there a simpler way of getting the set of weights than

_,w1,w2 = sorted(set([x.hamming_weight() for x in LinearCode(M)]))

You are going through the whole set of vectors! But I admit that the module is not imported on sage startup.

One possibility: hard code the values + add a (long) doctest that checks that these values are indeed correct?

comment:5 Changed 4 years ago by vdelecroix

... and note that there is WeightDistribution in the guava GAP package (very efficiently written in C).

comment:6 Changed 4 years ago by git

  • Commit changed from 9d9894a361f22299a6162ea3b4b3f74a4e225085 to 6c8ea206c058bf7fb92523abee99d8d3fa91b332

Branch pushed to git repo; I updated commit sha1. New commits:

6c8ea20trac #19463: Review

comment:7 Changed 4 years ago by ncohen

in [BJ03], you get name wrong

Fixed.

Isn't there a simpler way of getting the set of weights than

I now call LinearCode.weight_distribution.

One possibility: hard code the values + add a (long) doctest that checks that these values are indeed correct?

That was done in an early version of this patch. I removed it to not see data repeated. I guess that it cannot hurt... All this code may eventually be wiped out however, if we start adding generic code constructions instead of fixed-size examples. That will probably change all the design, but well. We'll see.

Nathann

comment:8 Changed 4 years ago by git

  • Commit changed from 6c8ea206c058bf7fb92523abee99d8d3fa91b332 to 73930f28c0d15ac1cbe1b6fd2741817608dec0ec

Branch pushed to git repo; I updated commit sha1. New commits:

73930f2trac #19463: Hardcode more data

comment:9 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by jsrn

Replying to vdelecroix:

Isn't there a simpler way of getting the set of weights than

_,w1,w2 = sorted(set([x.hamming_weight() for x in LinearCode(M)]))

You are going through the whole set of vectors! But I admit that the module is not imported on sage startup.

One possibility: hard code the values + add a (long) doctest that checks that these values are indeed correct?

I was thinking that it would be nice to refactor the DB by creating a class TwoWeightCode; a two-weight code has, after all, rather special properties and certain properties could be computed much faster for it.

I would give this class a flag at construction time verify = True. When this is true, it computes the weight distribution and verifies the code is two-weight. When it is false, the code is assumed two-weight: the two weights could either be given to the constructor, or they could be inferred very easily by running through the code until two distinct weights had been encountered. This can be expected to happen very quickly. A long test could then run a verify_is_two_weight in the codes or something.

Johan

comment:10 in reply to: ↑ 9 Changed 4 years ago by ncohen

I was thinking that it would be nice to refactor the DB by creating a class TwoWeightCode; a two-weight code has, after all, rather special properties and certain properties could be computed much faster for it.

I have no objection to that if you plan to do it yourself.

Nathann

comment:11 Changed 4 years ago by ncohen

To be more precise: this is a trac ticket. What is going here is a review, and I read anything that is written here as a comment about my code. When somebody says here that "it would be cool if your code did this/that" I read it as a comment from a reviewer. Could you make it clear whether you were asking me to implement it, or is it a random idea you were throwing here?

Nathann

comment:12 follow-up: Changed 4 years ago by jsrn

I wrote it as a "random idea". I am somewhat motivated to do it myself, but realistically, I might well not find time to do it. I have no objections to your code if no one else wants to implement my suggestion.

It was also a comment to Vincent's suggestion. Something like: what he suggests opens up a few questions IMHO, and to properly cater all that, one needs a more invasive restructuring of your code. In that sense it was a defence of your code as it's currently written.

Johan

comment:13 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by ncohen

It was also a comment to Vincent's suggestion. Something like: what he suggests opens up a few questions IMHO, and to properly cater all that, one needs a more invasive restructuring of your code. In that sense it was a defence of your code as it's currently written.

I expect all this code to be totally wiped out and rewritten in the future.

As you saw in the emails I sent about 2-weight codes the plan is to make it the 'new database' for those objects, and from what Eric Chen was saying it seems that all these codes belong to known families that we will be able to generate easily later.

I do not know what this code will look like, if it will totally replace what we have or only replace it partially, and how soon this will be implemented.

What I did here is extract the codes from the strongly regular graph module, in what will eventually become an independent database. Which, for the moment, is nothing but a dictionary with a bit of doc.

Nathann

comment:14 in reply to: ↑ 13 ; follow-up: Changed 4 years ago by jsrn

As you saw in the emails I sent about 2-weight codes the plan is to make it the 'new database' for those objects, and from what Eric Chen was saying it seems that all these codes belong to known families that we will be able to generate easily later.

My suggestion would make even more sense in this case, almost no matter how the future code will be written. Encapsulating the two-weight code properties and algorithms in a class is much more tidy and more easily supports computing things on demand.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by ncohen

My suggestion would make even more sense in this case, almost no matter how the future code will be written. Encapsulating the two-weight code properties and algorithms in a class is much more tidy and more easily supports computing things on demand.

Which properties and algorithms are you talking about?

Nathann

comment:16 in reply to: ↑ 15 Changed 4 years ago by dimpase

Replying to ncohen:

My suggestion would make even more sense in this case, almost no matter how the future code will be written. Encapsulating the two-weight code properties and algorithms in a class is much more tidy and more easily supports computing things on demand.

Which properties and algorithms are you talking about?

see the examples in http://pages.uoregon.edu/kantor/PAPERS/2-WeightCodes.pdf Most of them are infinite series. It's 30 years old paper, one should check if there is a newer survey...

comment:17 follow-up: Changed 4 years ago by ncohen

I just love conversing with you guys. I ask one person what properties/algorithms he would expect to see in a TwoWeightCode class and I am answered with a survey on those codes.

If you have any question about the code under review here, I will be glad to help.

Nathann

comment:18 in reply to: ↑ 17 ; follow-up: Changed 4 years ago by dimpase

Replying to ncohen:

I just love conversing with you guys. I ask one person what properties/algorithms he would expect to see in a TwoWeightCode class and I am answered with a survey on those codes.

well, I meant algorithms to build all these... One further bunch of algorithms would be constructing these complementary and projective duals...

Disclaimer: I am not a coding theorist and I know almost nothing about all these marvellous practical things about decoding/encoding, etc...

comment:19 in reply to: ↑ 18 ; follow-up: Changed 4 years ago by ncohen

well, I meant algorithms to build all these...

Oh. Well, that was not the topic. As you can read, we were discussing the usefulness of a specific class for two weight codes. While I hold nothing against it, I wondered why Johan thought that it would be useful: I personally just need the codes to build strongly regular graphs. I don't know which properties/methods we would attach to them if we had such a class.

Nathann

comment:20 Changed 4 years ago by dimpase

Probably it makes sense to make a sub-class for projective codes, for a q-ary [n,k]-projective code naturally corresponds to a set in PG(k-1, q), to which one can do things not possible with general codes. But 2-distance? Well, I don't know.

comment:21 in reply to: ↑ 19 Changed 4 years ago by jsrn

Replying to ncohen:

well, I meant algorithms to build all these...

While I hold nothing against it, I wondered why Johan thought that it would be useful: I personally just need the codes to build strongly regular graphs. I don't know which properties/methods we would attach to them if we had such a class.

A class is just a dictionary with code attached to it :-) Two-weight codes are special codes that allow certain properties to be calculated much faster than the general exponential bounds. Such as, obviously, minimum distance and which hamming weights are in the code, but there's surely more. Since such codes are apparently interesting in graph theory and combinatorics, it seems likely that someone might want to play around with them as codes, before you build graphs. "playing around" would then be computing stuff on them. Making them a class would give a natural place to put this code. By just making them LinearCodes, we miss out on the opportunity of putting these fast algorithms in a natural place. I'm not really talking about encoding/decoding, since I don't know that anyone should be interested in that.

One concrete example in your use where a class might be useful is in lazy computation of the two weights, using the faster, probabilistic algorithm.

The constructions of families that Dima talks about could be either functions that instantiate TwoWeightCode or subclasses, depending on whether the first would be overkill or not.

I concede that it might look like over-engineering from your point of view, however. From my point of view, this is a very special class of codes that is seemingly useful and (now) used in Sage. Therefore its natural that it should have a class :-)

Last edited 4 years ago by jsrn (previous) (diff)

comment:22 Changed 4 years ago by git

  • Commit changed from 73930f28c0d15ac1cbe1b6fd2741817608dec0ec to ddcb9e33d277f1fe16512bc8933f47e3b22f17c0

Branch pushed to git repo; I updated commit sha1. New commits:

ddcb9e3trac #19463: Merged with 6.10.beta2

comment:23 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:24 Changed 4 years ago by git

  • Commit changed from ddcb9e33d277f1fe16512bc8933f47e3b22f17c0 to 5d40cac98e50cbd0c12c50829a798d85dcd584e4

Branch pushed to git repo; I updated commit sha1. New commits:

5d40cactrac #19463: Merged with 6.10.beta5

comment:25 Changed 4 years ago by ncohen

Just merged this branch with the latest beta, as it was in conflict. This branch moves a long list of constructors, and there is a need to double-check everything every time this list gets modified by another patch.

Nathann

comment:26 Changed 4 years ago by git

  • Commit changed from 5d40cac98e50cbd0c12c50829a798d85dcd584e4 to 114e59cb65de52be8cc35c4d5022b092ee544a69

Branch pushed to git repo; I updated commit sha1. New commits:

114e59ctrac #19463: Bugfix with d['q'] -> d['K'].cardinality()

comment:27 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:28 Changed 4 years ago by git

  • Commit changed from 114e59cb65de52be8cc35c4d5022b092ee544a69 to 390af081d1639cf15d282ea7d44763eff56fc8e5

Branch pushed to git repo; I updated commit sha1. New commits:

8fc9e97v=176
65cd4d8GS14 -> GS70
4c57626and v=630
390af08trac #19463: Merged with #19624

comment:29 Changed 4 years ago by ncohen

  • Dependencies set to #19624

comment:30 Changed 4 years ago by dimpase

take the last commit from public/19463 to avoid the following:

$ sage -btp src/sage/coding/two_weight_db.py
python -u setup.py install
Updating Cython code....
Enabling Cython debugging support
Compiling sage/graphs/strongly_regular_db.pyx because it changed.
[1/1] Cythonizing sage/graphs/strongly_regular_db.pyx

Error compiling Cython file:
------------------------------------------------------------
...
        sage: G = SRG_630_85_20_10()                    # long time
        sage: G.is_strongly_regular(parameters=True)    # long time
        (630, 85, 20, 10)
    """
    from sage.graphs.generators.intersection import IntersectionGraph
    hs = HoffmanSingletonGraph()
                             ^
------------------------------------------------------------

sage/graphs/strongly_regular_db.pyx:2340:30: undeclared name not builtin: HoffmanSingletonGraph
...

comment:31 Changed 4 years ago by git

  • Commit changed from 390af081d1639cf15d282ea7d44763eff56fc8e5 to a3220e2fa1a5f32c3e74c17bcf081dd1898c03ea

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

287f49eMerge branch 'develop' of trac.sagemath.org:sage into develop
32931b0Merge branch 'develop' of trac.sagemath.org:sage into develop
7a2872aMerge branch 'develop' of trac.sagemath.org:sage into develop
ecfc955Merge branch 'develop' of trac.sagemath.org:sage into develop
2b442c1Merge branch 'develop' of trac.sagemath.org:sage into develop
3c860d2Merge branch 'develop' of trac.sagemath.org:sage into develop
a5536bbMerge branch 'develop' of trac.sagemath.org:sage into develop
a1b0953Merge branch 'develop' of trac.sagemath.org:sage into develop
ee61fa5Merge branch 'u/ncohen/19463' of trac.sagemath.org:sage into 2wtdb
a3220e2trac #19463: pay ye import duty

comment:32 follow-up: Changed 4 years ago by ncohen

......................................

NEVER use one of Dima's branches.

comment:33 Changed 4 years ago by git

  • Commit changed from a3220e2fa1a5f32c3e74c17bcf081dd1898c03ea to 6c396655ba346f59e8b8e4e0b662ff53726d9c25

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6c39665trac #19463: pay ye import duty

comment:34 Changed 4 years ago by ncohen

Fixed. Thanks,

Nathann

comment:35 in reply to: ↑ 32 Changed 4 years ago by dimpase

Replying to ncohen:

......................................

NEVER use one of Dima's branches.

I told you - take the last commit :-)

comment:36 Changed 4 years ago by dimpase

  • Status changed from needs_review to positive_review

I don't quite understand the new design, but it seems to work.

comment:37 Changed 4 years ago by ncohen

  • Reviewers set to Dima Pasechnik

comment:38 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:39 Changed 4 years ago by dimpase

  • Branch changed from u/ncohen/19463 to public/19463
  • Commit changed from 6c396655ba346f59e8b8e4e0b662ff53726d9c25 to d161122e70766cae707df83f8bdb686fc5443be9

comment:40 Changed 4 years ago by dimpase

  • Status changed from needs_work to needs_review

the merge conflict was in the .rst file, trivial to resolve. I hope I didn't screw up the branch I propose...

comment:41 Changed 4 years ago by ncohen

  • Branch changed from public/19463 to u/ncohen/19463
  • Commit changed from d161122e70766cae707df83f8bdb686fc5443be9 to 6c396655ba346f59e8b8e4e0b662ff53726d9c25

comment:42 Changed 4 years ago by git

  • Commit changed from 6c396655ba346f59e8b8e4e0b662ff53726d9c25 to a865eb3e2214740394570e6977ac606ebeb2df28

Branch pushed to git repo; I updated commit sha1. New commits:

a865eb3trac #19463: Merged with 6.10.beta6

comment:43 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

This new commit only merges it with beta6, and not with anything else.

comment:44 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/19463 to a865eb3e2214740394570e6977ac606ebeb2df28
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:45 Changed 4 years ago by dimpase

  • Commit a865eb3e2214740394570e6977ac606ebeb2df28 deleted

There is still a two-weight code left in graphs/strongly_regular_graphs_db, namely, in SRG_729_336_153_156 there is matrix L, which gives

sage: [w for w,f in enumerate(LinearCode(L.T).weight_distribution()) if w and f]
[108, 117]
sage: LinearCode(L.T)
Linear code of length 168, dimension 6 over Finite Field of size 3

comment:46 Changed 4 years ago by dimpase

I didn't know that commenting on closed tickets looks like it nukes commits. I think it's actually just a wrong message, as I can still see this commit just fine.

Note: See TracTickets for help on using tickets.