Pere Urbón Bayes wrote: > El dj 22 de 02 del 2007 a les 08:15 -0500, en/na David Joyner va > escriure: > >> Hi Pere, good to hear from you again. >> >> 1. Nick Alexander's suggestions (e.g., coding theory over rings) are good >> ones. >> >> 2. Another problem is to write code to compute the automorphism group of >> a linear code. It is surprisingly hard to write a fast algorithm to do >> this, even in the case of binary linear codes. I think this is an important >> problem though. >> > > This problem could be good, I don't know why but I like to work on hard > problems ... Where could I find some documentation about it? Could you > help me to start on it? >
1. Leon has several papers, referenced in the GUAVA manual http://cadigweb.ew.usna.edu/%7Ewdj/gap/GUAVA/htm/chapBib.html, which are hard to read but certainly detailed and relevant. If you download guava 2.7 (not version 2.8 included in SAGE) from http://cadigweb.ew.usna.edu/%7Ewdj/gap/GUAVA/ or from the GAP web page you'll see Leon's program in the subdirectory guava2.7/src/leon. The subdirectory doc has a manual of Leon's "backtracking" programs written in C. One direction to start is to read Leon's C code and re-write the entire thing (not just modify it and create a "derivative work"). There are several problems you'll have to solve (a) Leon's code is poorly documented and hard to read; the manual is very terse and provides little help in reading the code. (b) It is old C code and many commands are now different, leading to compiling problems (a few people have emailed me their hacks to get the code to compile - just email me if you have questions about this). (c) Leon creates his own finite field arithmetic (for GF9(q), q<256 I think) This must be replaced by SAGE's finite field structure. (d) Leon's programs are very general and require a non-trivial knowledge of combinatorics (blocks, designs, etc) even to figure out what he is doing. I hope I've made it clear that this would be very hard and probably require at least a year to finish, and more likely longer. I think this is an important problem in open-source mathematical software though. It has to be done in C or cleverly written SageX (about which I know little, but there are several experts on this email list). 2. I think at some point you will decide that you have to have a very efficient method for determining all the codewords of a given weight in a code. It is important that this be as fast as possible. I'm not convinced that the GAP code to do this is as efficient as possible. I think Leon's code has the ability to do this but I haven't figured out the command. If you decide not to pursue #1 above (and I wouldn't blame you) then implementing in C or SageX very efficient method for determining all the codewords of a given weight in a code would be very useful. If you can do this then by computing the matrix automorphism of the matrix of codewords of a given weight (GAP has a reasonably fast algorithm for doing this I think) you can sieve out the column permutations which can't belong to the automorphism group. This might also be a good place to start. > >> 3. At http://cadigweb.ew.usna.edu/%7Ewdj/gap/GUAVA/guava2do.html >> there is a list of projects for GUAVA, most or all of which are also >> possible SAGE projects. >> > > Work on LDPC Codes could be another good idea .... Could I work on this > two project for now with SAGE ... what do you think? > very efficient method for > > determining all the codewords of a given weight in a code. > Could you help me to start? > It is very easy to implement "bad" LDPC codes. By that I mean LDPC codes with bad parameters or poor error-correction ability. I have some experience in reading papers on LDPC codes, implementing a construction or two, and decoding algorithm or two, only to find out that the codes are terrible and the decoding algorithms are slow or only work in quirky situations. Based on my experience, the fact that Gallagher's famous MIT thesis from the 1960's was completely ignored for years doesn't surprise me in the least. The problem is that the "good" LDPC codes tend to be rather long, which makes them difficult to experiment with in GAP or Python (which are far too slow to be of any use for investigating them in most cases), or hard to implement. I think writing Python/SAGE "wrappers" for Radford's C code http://www.cs.toronto.edu/~radford/ldpc.software.html is potentially a very useful project. Although I haven't played with his program, is seems to be licensed under a BSD-style license. All I'm trying to say is that this is actually much harder than you might think - you can't just implement someone's cool construction and expect it to be useful. I think wrapping Radford's program would be a good start though and very useful. > >> 4. Two projects which I'm working on are >> (a) the zeta function of a linear code. There is an "experimental" >> version in the current SAGE distribution (look in linear_code.py) >> but I've completely rewritten it and no longer regard the code I have >> as experimental. If and when I get time I'll submit a patch (not >> until spring break at least). >> > > This sound interesting ..... > > >> (b) A complete description of the genus 0 AG codes. I'm not sure if SAGE's >> divisor classes even work in genus 0 so this may not be completed for >> quite awhile. >> > > > Thanks allot david!!! > Good luck Pere and let me know if there is anything else I can do. > Regards, > > >> If any of this sounds interesting, please let me know. >> >> - David >> >> > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
