Opened 6 years ago
Closed 6 years ago
#1258 closed enhancement (fixed)
[with bundle, with positive review] additions and changes to linear_codes
Reported by: | wdj | Owned by: | wdj |
---|---|---|---|
Priority: | minor | Milestone: | sage-2.9 |
Component: | coding theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The patch http://sage.math.washington.edu/home/wdj/patches/linear_codes20071124.hg contains a new functions zeta_polynomial, weight_enumerator, chinen_polynomial, is_equivalent (for binary codes); an improved best_known_code; many pythonic revisions (suggested by William Stein long ago). Also, there are some minor docstring improvements. None of these are major improvements but I have a student working on Duursma zeta functions of self-dual codes and these will be useful for her.
Attachments (2)
Change History (10)
comment:1 Changed 6 years ago by mabshoff
- Summary changed from additions and changes to linear_codes to [with bundle] additions and changes to linear_codes
comment:2 Changed 6 years ago by rlm
- Summary changed from [with bundle] additions and changes to linear_codes to [with bundle, with negative review] additions and changes to linear_codes
comment:3 Changed 6 years ago by rlm
The first doctest failure seems to be an error in the way GAP is calling Leon's code. The directory mentioned in the documentation is SAGEHOME/local/lib/gap*/guava* but the guava code is installed in SAGEHOME/local/lib/gap*/pkg/guava*
comment:4 Changed 6 years ago by wdj
- Milestone changed from sage-2.9 to sage-2.9.1
- To the best of my knowledge, the doctest failures are not the result of bad programming in this patch. They are because Leon's code, included with guava, is not compiled. It used to be that one could modify the spkg install file in SAGE's standard GAP package to try to fix this problem. Now the mechanism is different and I don't know why Leon's code is not compiled.
The docstring typo mentioned above has been fixed.
- "There are several places in the code where you are calling several gap.eval's within an inner loop." Agreed. I spent even more time trying to remove these calls. I did modify several two functions along these lines but don't know if they are any faster.
(a) I don't see how to without rewriting the GAP code. (b) Except for the example above, there were only one or 2 other places where gap.eval occurred in a loop. In those two cases, I tried to rewrite the code (I've tried before as well) but possibly not entirely successful. I don't see a tremendous savings anyway, since the loops are usually over the dimension and the computation inside the loop is growing exponentially with the dimension anyway... (c) For the example above, I see not point in trying to speed it up since (a) I think it is buggy, (b) Robert Miller's code is hundreds of times faster and will be replacing it very soon. It is good to have for testing purposes though.
- There was a mistake in the patch with the implementation of Chinen zeta polynomials. That has been fixed.
The patch is at http://sage.math.washington.edu/home/wdj/patches/linear-codes20071210.hg and modified file at http://sage.math.washington.edu/home/wdj/patches/linear_code.py
Changed 6 years ago by rlm
comment:5 Changed 6 years ago by rlm
- Summary changed from [with bundle, with negative review] additions and changes to linear_codes to [with bundle, with positive review] additions and changes to linear_codes
The bundle at http://sage.math.washington.edu/home/rlmill/sage-2.9.alpha5/codes.hg should apply cleanly to sage-2.9.alpha5
comment:6 Changed 6 years ago by rlm
- Milestone changed from sage-2.9.1 to sage-2.9
Changed 6 years ago by was
comment:7 Changed 6 years ago by rlm
From IRC:
[2:48pm] was-1258: rlm -- after applying 1258 the doctests for linear_code.py take 93 seconds on sage.math! [2:48pm] was-1258: unacceptable. ... [2:48pm] was-1258: line 1062 takes a long time. ... [2:49pm] was-1258: line 1280 [2:49pm] was-1258: line 1333 [2:49pm] was-1258: 1757 [2:49pm] was-1258: 352 takes very long.
Computations taking longer than about 10 seconds or so should be marked # long time, so that the doctester knows to skip them unless you do ./sage -t -long. Also, computations taking longer than a minute or two are probably not suitable for doctesting.
comment:8 Changed 6 years ago by mabshoff
- Resolution set to fixed
- Status changed from new to closed
Merged in 2.9.rc2.
Feedback: The changes all seem good, but I have a suggestion for further improvement. As you are probably well aware, any call like gap.eval(blablahblah) takes a lot of time, because of pseudo-tty. There are several places in the code where you are calling several gap.eval's within an inner loop. It seems like a much better idea to form one large string of GAP code, which includes the loop, and calling gap.eval on the large string exactly once. One example is the loop starting on line 963, linear_codes.py. (I know this will soon be replaced anyway, but it's a good example of unnecessary pseudo-tty lag.)
Also, there are some doctest issues, resulting in a negative review for now.