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

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

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

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

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

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).

7. Better plotting: Rank-3 matroids can be plotted, but the algorithm that positions the points can be improved. In particular, right now points are placed so that false collinearities appear.

8. Trac tickets: Any of the issues on the SageMath Trac server. http://trac.sagemath.org/query?status=!closed&component=matroid+theory

Rank-metric codes

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.

Generic Dispatcher

In Sage there are many places where we can choose between several algorithms or underlying softwares to solve a problem. This is often related to the presence of the keyword algorithm or method in functions. The aim of this task is to build a generic dispatcher that would choose depending on the parameters the fastest solution available. The solution must be very light and not affect performance. The dispatch threshold must be static and computed through a dedicated command (like sage -recompute-thresholds). We could also have default threshold that depend on architectures. This generic dispatcher could also be used to check coherency between the various implementations.

Note that it is different from what is called multimethods where the dispatch depends only on the input type. Here we consider a dispatcher that might also depend on the input values.

Steps:

1. identify some Sage functions/methods that could benefit from the dispatcher
2. write a simple prototype of generic dispatcher adapted to 1 and intensively test it
3. release a first candidate for the dispatcher
4. more Sage functions coverage (this can be hard since some threshold might be extremly complicated to determine. In order to do that you are advised to ask for help on the mailing-list)

Regression test framework

Sage currently does not provide tests for speed regression. In the past, we had some critical regressions and it would be natural to implement a general framework to deal with this. The project should be implemented in Python and not be Sage specific. It might serve other purposes in the future.

Steps:

1. Implement a Python program that runs some python code and stores the corresponding timing.
2. Design a large set of Sage tests (possibly asking for contribution on sage-devel)
3. Set up a server whose object would be to check for speed regression (or progression) of Sage code samples

Moduli space of dynamical systems

There is functionality for working with dynamical systems over projective space in Sage. However, one of the areas lacking in functionality is the moduli space. We say two self-maps of projective space are equivalent if there is an element of PGL that conjugates one to the other. The following two algorithms should be implemented.

1. Given two endomorphisms of projective space determine if they are conjugate. In other words, determine if they are in the same class in the moduli space. If they are, also return the PGL element that conjugates one to the other. [Xander Faber, Michelle Manes, and Bianca Viray. Computing conjugating sets and automorphism groups of rational functions. Journal of Algebra 423 (2014), 1161–1190]
2. Not all representations of a given moduli space class are equally 'nice'. There is already an algorithm implemented to return the minimal model (in terms of resultant), but the coefficients can be non-optimal. Given an endomorphism of projective space compute a reduced form, i.e., a conjugation that makes the coefficients small. The simplest approach would be to "reduce" the binary form describing the fixed points or (if that's too degenerate) the points of period n for some small n. [Stoll, Michael; Cremona, John E., On the reduction theory of binary forms. J. Reine Angew. Math. 565 (2003), 79–99.]

If there is still time leftover, you can examine some applications of these two algorithms such as the concept of potential good reduction or an iterator of reduced minimal moduli elements of bounded height.

Other

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