Differences between revisions 10 and 11
Revision 10 as of 2016-02-01 23:25:58
Size: 9444
Editor: Stefan
Comment:
Revision 11 as of 2016-02-02 15:43:51
Size: 10697
Editor: dlucas
Comment:
Deletions are marked like this. Additions are marked like this.
Line 102: Line 102:
== Rank-metric codes ==

|| Mentor || Johan S. R. Nielsen, David Lucas||
|| Difficulty || Medium ||
|| Skills || Knowledge of abstract algebra (finite fields, field extensions, polynomial rings). Standard knowledge of Python. Familiarity with coding theory a plus. ||

Coding theory studies the encoding of data in ways that have certain auxiliary properties, such as error-correction capabilities. Rank-metric codes are a hot research topic, with applications in packet-based network communication.
Essentially, a rank metric code is a set of matrices, usually over a finite field, such that the difference of any
two of them has high rank. By far the most important construction is the Gabidulin code, which arise from the
evaluation of skew polynomials.

This project is to implement Rank-metric codes in Sage, including Gabidulin codes and their decoding.
Sage has good (and quickly expanding) support for linear codes using the Hamming metric, the most
common object in error-correcting code theory. The framework there should serve as inspiration.
Implementing Gabidulin codes will also require support for skew polynomial rings, for which some work has
already been done in Sage and this should be followed through.

GSoC 2016

Introduction

Google Summer of Code is a highly enjoyable and rewarding way to spend a summer.

SageMath (or Sage for short) is a GPL open-source mathematical software system. It is designed to be not just a computer algebra system, but more like a complete environment for doing mathematics and related calculations. It is based on a vast collection of existing open-source software tools and libraries and ties them together via Python. Python is also the primary interface language for the user and its object-oriented way of expressing concepts is used to express calculations - of course, there are also many “normal” functions :-) Behind the scenes, the Sage library executes the commands and calculations by its own algorithms or by accessing appropriate routines from the included software packages. On top of that, there are various ways how users can interact with Sage, most notably a dynamic web-site called “Notebook”.

Sage works hand-in-hand with other computational mathematics software systems, such as SymPy, GAP, etc, and can serve as an umbrella organization for GSOC projects for those sister projects.

All projects will start with an introduction phase to learn about Sage’s (or sister projects') internal organization and to get used to their established development process.

For Sage, this is documented in the developers' manual and all students will be instructed by the mentors on how to get their hands dirty. Sage uses Git (accessible at http://git.sagemath.org/) for revision control and trac (accessible at http://trac.sagemath.org) for organizing development and code review. Our license is GPLv2+. Feel free to contact Mentors before you send us project proposals.

/!\ We also require you to show us that you are able to execute actual development by submitting a patch via Sage's trac (i.e. see tickets marked for beginners) or a similar development tool of the respective project.

For Sage, feel free to introduce yourself and your project idea in Sage's GSOC mailing list.

For GAP, feel free to introduce yourself to GAP's developer list. Some discussion of possible GAP GSOC projects is happening at the joint GAP Sage days in St Andrews, see the agenda.

To get a better feeling of how Sage works, please check out the developer guide.

There is also a comprehensive list of future feature wishes in our trac issue tracker. They might contain the perfect project idea for you we didn't even think about!

Application Template

Please use this application template, in particular answer the questions thoroughly enough to convince us to pick you!

Personal:

  • Name
  • Contact Information (email, instant messaging, …)
  • Location/Timezone
  • University

Background:

  • What are your technical skills, education, experience, etc. Especially make sure to explain with what level of mathematics you are comfortable with and on what level you would like to program.
  • Who are you? What makes you the best person to work on this particular project? Your personal motivation?
  • What platform and operating-system are you using on your computer? (Sage development is done best on Linux and OSX)
  • Are you or have you been engaged in other open-source projects?
  • Do you code on your own pet projects?
  • Are you a Sage user, how long do you know Sage?

Project:

  • Title, Project Synopsis: a short description and summary of its aim and scope.
  • What is your personal involvement or relationship with your proposed project?
  • Details: describe all the details and explain modules or parts of your whole project. Break down the whole project into individual tasks - as good as possible - and describe deliverable and quantifiable results for each of them. It also helps if you have already discussed this with a possible mentor.
  • Schedule: A timetable, including special circumstances like exams or holidays, for the individual tasks.
  • Risk Management: Try to anticipate potential problems and explain, how to mitigate them. Propose alternative scenarios, if a particular milestone isn't reached, to still successfully complete the project.

Project Ideas

Hyperplane arrangements

Mentor

Miguel Marco / Volker Braun

Difficulty

Medium

Skills

standard Python knowledge, good mathematical knowledge about hyperplane arrangements

Sage already has a module for hyperplane arrangements, but it only admits arrangements over the rationals and finite fields. Since there is a rich theory about complex arrangements, it would be interesting to extend this to other fields. It would probably require to redesign the classes, having one common base class and further classes for field-specific methods. In this setting, it would also make sense to implement invariants as the Orlik-Solomon/Orlik-Terao algebras, resonance varieties, fundamental group of complements, logarithmic derivation modules (with the corresponding Betti numbers)...

Wrap/Expose more functionalities from Singular

Mentor

Miguel Marco / Travis Scrimshaw

Difficulty

Medium

Skills

Ability to work with the category/parent/element framework, some basic understanding of commutative algebra objects

We ship Singular, which is used mainly for computations with multivariate polynomial rings and their ideals (mostly Gröbner basis). We could also take advantage of its capabilities to deal with modules, resolutions... In order to do so, we would need to write some wrapping classes for these objects and interface the corresponding Singular calls.

Implement a framework for non-free modules

Mentor

Travis Scrimshaw

Difficulty

Medium

Skills

Ability to work with the category/parent/element framework, some linear algebra or understanding of modules

There is very little capacity in Sage for non-free modules. We should implement generic functionality and base classes for non-free modules. This will likely have some overlap with the project to expose more from Singular.

Combine common functionality between CombinatorialFreeModule and Sage's free module code

Mentor

Travis Scrimshaw

Difficulty

Medium--Hard

Skills

Good understanding of OOP and adapter classes and basic linear algebra

Currently, there is some overlap between the implementation of CombinatorialFreeModule (CFM) and (sparse) FreeModule. In particular, a CFM is roughly a special indexing set on top of a sparse free module. The goal of this project would be to combine features between these two class hierarchies in an attempt to ease the burden of code maintenance and improve the features of both.

Extending Matroid Theory functionality

Mentor

Stefan van Zwam

Difficulty

Medium

Skills

Good knowledge of Python, SageMath, and some knowledge of Matroid Theory would be advantageous

The basic code for dealing with matroids in SageMath is fairly mature, but many enhancements are still desirable. Among those:

  1. An improved catalog: This could be a warm-up task for the first two weeks. Enhance the matroid catalog with some options, such as adding options to prescribe the field of a representation.

  2. Automorphisms: Very basic to implement (construct a graph out of the matroid, use the automorphism group code from graphs) but still missing.

  3. Certificates: Many matroid test methods are currently True/False. In many cases, it makes sense to return a certificate of the claim, such as an isomorphism in case two matroids are determined to be isomorphic.

  4. Representability tests: Test if a given abstract matroid is binary, ternary, quaternary, regular, ...

  5. Framework for classes of representable matroids: This can take two directions. First, a parent-like class such as BinaryMatroids, which symbolically represents all binary matroids, and has methods for extending, membership tests, etc. Second, a finite collection of matroids (such as all binary matroids without a P7-minor up to 9 elements), where each matroid stores information about its allowed extensions and coextensions for faster generation and membership testing.

  6. Faster minor testing: Testing whether a matroid has a specified minor is an important yet computationally expensive task. It is desirable to increase SageMath's ability for this. For binary matroids, Jayant Apte's ticket is a good start, but needs to be brought up to standards of documentation. For other classes, ideas from Hlineny's Macek software can be used (pattern matching of 2x2 subdeterminants in the representable case).

Rank-metric codes

Mentor

Johan S. R. Nielsen, David Lucas

Difficulty

Medium

Skills

Knowledge of abstract algebra (finite fields, field extensions, polynomial rings). Standard knowledge of Python. Familiarity with coding theory a plus.

Coding theory studies the encoding of data in ways that have certain auxiliary properties, such as error-correction capabilities. Rank-metric codes are a hot research topic, with applications in packet-based network communication. Essentially, a rank metric code is a set of matrices, usually over a finite field, such that the difference of any two of them has high rank. By far the most important construction is the Gabidulin code, which arise from the evaluation of skew polynomials.

This project is to implement Rank-metric codes in Sage, including Gabidulin codes and their decoding. Sage has good (and quickly expanding) support for linear codes using the Hamming metric, the most common object in error-correcting code theory. The framework there should serve as inspiration. Implementing Gabidulin codes will also require support for skew polynomial rings, for which some work has already been done in Sage and this should be followed through.

Please feel free to add ideas (or copy-paste them from last year's Sage GSOC wiki page).

GSoC/2016 (last edited 2016-03-22 09:18:34 by schilly)