Opened 12 years ago
Closed 10 years ago
#10153 closed enhancement (invalid)
Canonical generator matrices for linear codes and their automorphism groups
Reported by: | Thomas Feulner | Owned by: | David Joyner |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | coding theory | Keywords: | Automorpism group, canonical representative |
Cc: | Robert Miller, Burcin Erocal | Merged in: | |
Authors: | Reviewers: | Thomas Feulner | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Let R be a finite ring (up to now: a finite field or Z_{4}). A submodule of R^{n} is called a linear code of length n. Two linear codes C, C' over R of length n are equivalent, if there is
- a permutation pi in S_{n}
- a multiplication vector phi in R*^{n} (R* the set of invertible elements)
- an automorphism alpha of R
with C' = (phi, pi, alpha) C and the action is defined via
(phi, pi, alpha) (c_{0}, ..., c_{n-1}) = ( phi_{0} alpha( c_{pi-1(0)}) , ... , phi_{n-1} alpha( c_{pi-1(n-1)}) )
This patch adds an algorithm for calculating a unique representative within the equivalence class of a given linear code (returning some unique generator matrix). The algorithm calculates the automorphism group of the code as a byproduct.
Attachments (2)
Change History (15)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
I think this is fixed with the new patch. I am now using GMP, it was a 32-bit error and
5922201600
is the correct order.
comment:3 Changed 12 years ago by
Cc: | Robert Miller added |
---|
comment:4 follow-up: 5 Changed 12 years ago by
Status: | new → needs_work |
---|
This applied fine to sage 4.6.1.a2 on a 10.6.5 mac, however there were some compiler warnings of the form "warning: command line option "-Wstrict-prototypes" is valid for C/ObjC but not for C++". I don't know if these are important. The patch passes sage -testall.
The patch is huge. I have the following questions:
1) Do you have any tests which compare your output to the output of Robert Miller's automorphism groups in the case of binary linear codes? For example, does your program yield the same result that sage: C = HammingCode?(3, GF(2)) sage: C.automorphism_group_binary_code() does?
2) Do you have any tests which compare your output to the output of the permutation automorphism groups in the case of non-binary linear codes? For example, does your program yield the same result that sage: C = HammingCode?(2, GF(3)) sage: C.permutation_automorphism_group() Permutation Group with generators [(1,2,3)] does?
It seems not. If that is true, it would be great to add them to the tests.
Also, it is great that you linked your documentation into the manual. However, most of it is too vague - for example
get_transporter() Returns the transporter element. ...
Could this be improved?
I'm going to mark this as "needs work".
comment:5 Changed 12 years ago by
Cc: | Burcin Erocal added |
---|
Replying to wdj:
This applied fine to sage 4.6.1.a2 on a 10.6.5 mac, however there were some compiler warnings of the form "warning: command line option "-Wstrict-prototypes" is valid for C/ObjC but not for C++". I don't know if these are important. The patch passes sage -testall.
This was discussed in ticket:425. They decided to accept this minor annoyance.
The patch is huge. I have the following questions: 1) Do you have any tests which compare your output to the output of Robert Miller's automorphism groups in the case of binary linear codes? For example, does your program yield the same result that sage: C = HammingCode?(3, GF(2)) sage: C.automorphism_group_binary_code() does?
Now, there is a test which compares the result of both algorithms showing that the groups are equal.
2) Do you have any tests which compare your output to the output of the permutation automorphism groups in the case of non-binary linear codes? For example, does your program yield the same result that sage: C = HammingCode?(2, GF(3)) sage: C.permutation_automorphism_group() Permutation Group with generators [(1,2,3)] does? It seems not. If that is true, it would be great to add them to the tests.
The new examples also try to show the differences in this case. Furthermore, I had some problems in constructing the automorphism group in the case of a finite field of order p^{r} as a semidirect product. Maybe someone can give me a hint for improving the following example.
sage: GammaGF4 = HammingCode(3, GF(4, 'a') ).check_mat() sage: canonizer.start_matrix(GammaGF4) sage: gens = canonizer.get_automorphism_generators() sage: V = VectorSpace(GF(4, 'a'), GammaGF4.nrows() ) # long time sage: elts = V.list() # long time sage: A_correct = PermutationGroup([ PermutationGroupElement( [elts.index( x.apply_map(g[2])*g[0].transpose())+1 for x in elts]) for g in gens ]) # long time sage: A_correct.order() == canonizer.get_autom_order() # long time True
Also, it is great that you linked your documentation into the manual. However, most of it is too vague - for example
get_transporter() Returns the transporter element. ...
Could this be improved? I'm going to mark this as "needs work".
Is this more precise? Maybe we can also discuss the natural way of returning the group elements. Mathematically correct via B^{-1} or user-friendly without inversion. I have implemented the second way, but I am not sure if the warning sections are sufficient.
comment:6 Changed 12 years ago by
Installed fine on a 10.6.6 mac running 4.7.a1. However, there was the following doctest failure:
sage -t -force_lib "devel/sage/sage/coding/code_can.pyx" ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 495: sage: canonizer._latex_() Expected: '\\textnormal{Canonization object for linear codes over finite fields or } `\\ZZ_4`\\textnormal{. The actual code is generated by}\\\\\\left(\\begin{array}{rrrrrrr}\n1 & 0 & 0 & 1 & 0 & 1 & 0 \\\\\n0 & 1 & 0 & 1 & 0 & 1 & 1 \\\\\n0 & 0 & 1 & 1 & 0 & 0 & 1 \\\\\n0 & 0 & 0 & 0 & 1 & 1 & 1\n\\end{array}\\right)' Got: '\\textnormal{Canonization object for linear codes over finite fields or } `\\ZZ_4`\\textnormal{. The actual code is generated by}\\\\\\left(\\begin{array}{rrrrrrr}\n1 & 0 & 0 & 0 & 0 & 1 & 1 \\\\\n0 & 1 & 0 & 0 & 1 & 0 & 1 \\\\\n0 & 0 & 1 & 0 & 1 & 1 & 0 \\\\\n0 & 0 & 0 & 1 & 1 & 1 & 1\n\\end{array}\\right)' ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 358: sage: [a[0] * Gamma.apply_morphism(a[2]) * a[1] == Gamma for a in gens] Expected: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True] Got: [True, True, True, True, True, True, True, True, True, True, True, True, True, True] ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/code_can.pyx", line 476: sage: repr(canonizer) Expected: 'Canonization object for linear codes over finite fields or `\\ZZ_4`. The actual code is generated by\n[1 0 0 1 0 1 0]\n[0 1 0 1 0 1 1]\n[0 0 1 1 0 0 1]\n[0 0 0 0 1 1 1]' Got: 'Canonization object for linear codes over finite fields or `\\ZZ_4`. The actual code is generated by\n[1 0 0 0 0 1 1]\n[0 1 0 0 1 0 1]\n[0 0 1 0 1 1 0]\n[0 0 0 1 1 1 1]' ********************************************************************** 3 items had failures: 1 of 7 in __main__.example_10 1 of 44 in __main__.example_6 1 of 7 in __main__.example_9 ***Test Failed*** 3 failures. For whitespace errors, see the file /Users/davidjoyner/.sage//tmp/.doctest_code_can.py [43.1 s] ---------------------------------------------------------------------- The following tests failed: sage -t -force_lib "devel/sage/sage/coding/code_can.pyx" Total time for all tests: 43.2 seconds
Honestly, I'm not sure the best way of returning the component of the automorphism group which corresponds to field automorohisms. Sage does not seem to have the Galois action on a vector space such as GF(4,"a")^{3 implemented. You can try to return an element of this component as a tuple of integers which give the exponents of a Frobenius action. You might also just return it as a separate abelian group. There are probably other ideas out there too. How does Magma do it? }
comment:7 follow-up: 8 Changed 12 years ago by
Just a few minor comments on the documentation, which is much better.
"Canonization of linear codes over finite rings (we are only supporting finite fields and \ZZ_4)" The first sentence becomes the title. It would be nicer to simply have "Canonization of linear codes over finite rings" and add the parenthetical remark later.
"elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise."
You say "Warning: The program ..." a few times. What program? get_automorphism_generators
?
You say "See sage.coding.code_can for the interpretation of the group elements." a few times. What does this mean exactly? I am looking at the documentation of that module. Do you mean read the source code?
Changed 12 years ago by
Attachment: | trac_10153_canonical_generator_matrices.patch added |
---|
better documentation, now using templates for wrapping the C++ code
comment:8 Changed 12 years ago by
Status: | needs_work → needs_review |
---|
The new patch fixes the doctest failures. They were forced by different generator matrices of the Hamming Code on different platforms.
Replying to wdj:
Just a few minor comments on the documentation, which is much better. "Canonization of linear codes over finite rings (we are only supporting finite fields and \ZZ_4)" The first sentence becomes the title. It would be nicer to simply have "Canonization of linear codes over finite rings" and add the parenthetical remark later.
"elments [A, B] and [A', B'] are multiplied componentwisely." --> "elements [A, B] and [A', B'] are multiplied componentwise."
Changed.
You say "Warning: The program ..." a few times. What program?
get_automorphism_generators
?
Changed. Now, the warning is linking to the corresponding functions.
You say "See sage.coding.code_can for the interpretation of the group elements." a few times. What does this mean exactly? I am looking at the documentation of that module. Do you mean read the source code?
I tried to link the documentation of this method to the documentation of the module via :mod:!`sage.coding.code_can. But this didn
t work. I have removed this sentences in the warnings since the OUTPUT sections of the methods will explain the group elements, too.
comment:9 follow-up: 10 Changed 12 years ago by
I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1):
she:sage-4.7.alpha1 davidjoyner$ ./sage -t -force_lib "devel/sage/sage/coding/linear_code.py" sage -t -force_lib "devel/sage/sage/coding/linear_code.py" ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1860: sage: G = C.permutation_automorphism_group() # this should take < 5 seconds Exception raised: Traceback (most recent call last): File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_42[11]>", line 1, in <module> G = C.permutation_automorphism_group() # this should take < 5 seconds###line 1860: sage: G = C.permutation_automorphism_group() # this should take < 5 seconds File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper return func(*args, **kwds) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group MS = MatrixSpace(F,len(Cwt),n) NameError: global name 'Cwt' is not defined ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1861: sage: G.is_isomorphic(M11) # this should take < 5 seconds Expected: True Got: False ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1875: sage: C.permutation_automorphism_group(algorithm="partition") Exception raised: Traceback (most recent call last): File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_42[17]>", line 1, in <module> C.permutation_automorphism_group(algorithm="partition")###line 1875: sage: C.permutation_automorphism_group(algorithm="partition") File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper return func(*args, **kwds) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group MS = MatrixSpace(F,len(Cwt),n) NameError: global name 'Cwt' is not defined ********************************************************************** File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/devel/sage/sage/coding/linear_code.py", line 1879: sage: C.permutation_automorphism_group(algorithm="partition") Exception raised: Traceback (most recent call last): File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_42[19]>", line 1, in <module> C.permutation_automorphism_group(algorithm="partition")###line 1879: sage: C.permutation_automorphism_group(algorithm="partition") File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/misc/decorators.py", line 573, in wrapper return func(*args, **kwds) File "/Volumes/Bay2/sagefiles2/sage-4.7.alpha1/local/lib/python/site-packages/sage/coding/linear_code.py", line 1949, in permutation_automorphism_group MS = MatrixSpace(F,len(Cwt),n) NameError: global name 'Cwt' is not defined ********************************************************************** 1 items had failures: 4 of 22 in __main__.example_42 ***Test Failed*** 4 failures. For whitespace errors, see the file /Users/davidjoyner/.sage//tmp/.doctest_linear_code.py [17.4 s] ---------------------------------------------------------------------- The following tests failed: sage -t -force_lib "devel/sage/sage/coding/linear_code.py" Total time for all tests: 17.4 seconds
comment:10 Changed 12 years ago by
Replying to wdj:
I now get the following test failure (on a 10.6.6 mac running sage-4.7.a1)
Sorry, the patch changed a single line linear_code.py, which was not my intention.
Changed 12 years ago by
Attachment: | trac_10153_canonical_generator_matrices.2.patch added |
---|
comment:11 Changed 12 years ago by
IMHO, it would be good to represent the resulting group generators as sparse matrices. (Or, perhaps, a new Sage type "MonomialMatrix?" ?)
Did you check that parts of Boost you are using are not in Sage? (It would be more consistent to add them there, if needed, rather than to keep them here).
Would it be possible to factor out the code by Ralf Gugisch into a separate package/patch? (well, that's certainly a lot of work, I know, so just wondering... I noticed he had some stuff on oriented matroids implemented, is this a part of it?)
I also noticed that the patch mixes up Unix/Windows? encoded files. Can this be streamlined?
comment:12 Changed 10 years ago by
Milestone: | sage-5.3 → sage-duplicate/invalid/wontfix |
---|---|
Status: | needs_review → positive_review |
The approach of adding a large C++ library is wrong. I started a new attempt written in cython, which uses Robert Millers partition refinement code. This will hopefully become an optional package soon.
comment:13 Changed 10 years ago by
Authors: | Thomas Feulner |
---|---|
Resolution: | → invalid |
Reviewers: | → Thomas Feulner |
Status: | positive_review → closed |
Thanks for creating this!
Haven't had time to look at this closely but I did test it out to see if it would apply okay. On a 10.6.4 mac, I got this failure: