GSoC 2019: Ideas Page
Introduction
Welcome to Sagemath's Ideas Page for GSoC 2019! (Last year 2018)
SageMath's GSoC organization homepage  the hub for submitting applications and where the everything on Google's side is organized.
Please subscribe to the sagegsoc mailing list and the GAP developer list for discussion on possible GAP GSoC projects. Also, make sure you have gone through the information regarding application procedures, requirements and general advice. The Application Template is also available on that wiki page. Archives of past GSoC project ideas can be found here.
All projects will start with an introduction phase to learn about Sagemath’s (or sister projects') internal organization and to get used to their established development process. We also require you to show us that you are able to execute actual development by submitting a relevant patch and/or reviewing a ticket via Trac of the project you are interested in applying to. The developer guide is a great comprehensive resource that can guide you through your first steps in contributing to Sagemath.
Apart from the project ideas listed below, 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!
Contents
 GSoC 2019: Ideas Page

Project Ideas
 Improve support of representation theory (multiple projects)
 Implement Lie superalgebras
 Refactor RSK and implement new insertion rules
 Enumeration of paths
 Diameter, radius, eccentricities, and distances
 Improvements of the graph module
 Polynomial optimisation and sums of squares (multiple projects)
 Sagemath distributions on OSX (multiple projects)
 Sagemath distributions on *BSDs (multiple projects)
 Integration of Kenzo with SimplicialSets
 Extensions of padic fields
Project Ideas
Here is a list of project proposals with identified mentors. Other wellmotivated proposals from students involving Sagemath in a substantial way will be gladly considered, as well.
Improve support of representation theory (multiple projects)
Mentor 
Travis Scrimshaw 
Area 
Algebra, Representation Theory, possibly Combinatorics 
Skills 
Understanding of linear algebra, preferably representation theory and algebra, associated combinatorics desirable, Cython experience is good 
Representation theory is the study of symmetries and is an important part of modern mathematics with applications to other fields, such as physics and chemistry. GAP supports doing computations using the characters of representations, but it often does not contain constructions nor manipulations of the modules. There is currently some limited support within Sage for representations as a proofofconcept, but this needs to be expanded and refined. Things that can be added are tensor products (for bialgebras), dual representations (for Hopf algebras), induction and restriction functors, methods to construct representations of groups (e.g., symmetric group), Lie algebra representations, etc.
Implement Lie superalgebras
Mentor 
Travis Scrimshaw 
Area 
Algebra, Representation Theory 
Skills 
Foundations in algebra and combinatorics, experience reading research papers 
Lie superalgebras were introduced by Kac in order to unify bosons and fermions and are currently an active topic of research. Lie algebras have been implemented in Sage and the that framework has been tested and is mostly stable. The next step is to extend this framework to Lie superalgebras and provide implementations of the basic and finitedimensional Lie superalgebras. This project could also aim to cover some of their representation theory or quantum groups.
Refactor RSK and implement new insertion rules
Mentor 
Travis Scrimshaw 
Area 
Combinatorics 
Skills 
Understanding of RSK and combinatorics, experience in Cython, data structures, and algorithms preferable 
The RobinsonSchenstedKnuth (RSK) bijection is a core part of modern day combinatorics involving tableaux and symmetric functions. The current implementation includes the classical RSK insertion and two generalizations called EdelmanGreene and Hecke insertion. However, the current design does not scale well as new insertion algorithms are implemented in Sage (e.g., super RSK 24894 and dual/coRSK 25070). The goal of this project is to refactor the code to use the same design patterns as the growth diagrams. This project would also include writing new insertion rules.
Enumeration of paths
Mentor 
David Coudert 
Area 
Graph theory 
Skills 
Knowledge of graph algorithms, Python, C/C++, git. 
In the graph module of Sagemath, we currently have a method in Python for enumerating all paths from a source to a destination in an undirected graph by increasing length (number of edges). We also have methods for enumerating all (simple) paths and cycles in a directed graph by increasing length (number of edges). The following tasks are intended to speed up these methods and offer more functionalities:
 Implement Cython versions of these algorithms and ensure that we can have the same functionalities for directed and undirected graphs;
 Extend these methods to weighted (directed) graphs;
 Implement an iterator over the shortests st paths using improved versions of Yen’s algorithm for simple paths and Eppstein’s algorithm for nonsimple paths.
Diameter, radius, eccentricities, and distances
Mentor 
David Coudert 
Area 
Graph theory 
Skills 
Knowledge of graph algorithms, Python, C/C++, git 
The graph module of Sagemath already provides some smart algorithms for computing the diameter and eccentricity of unweighted undirected graphs, and a large variety of methods for computing paths and distances.
 The first goal of this project is to implement best known methods for computing diameter, radius, centers, eccentricities of (weighted) (un)directed graphs, so we could get the complete collection. See for instance [d1] [d2] [d3].
The second objective is to clean and improve methods for computing shortest paths and distances (single source and all pairs). In particular, implement the method proposed in https://ask.sagemath.org/question/44823/sagefloydalgorithmincython/.
References:
[d1] Feodor Dragan, Michel Habib, Laurent Viennot. Revisiting Radius, Diameter, and all Eccentricity Computation in Graphs through Certificates. http://arxiv.org/abs/1803.04660
[d2] Takuya Akiba, Yoichi Iwata, Yuki Kawata: An Exact Algorithm for Diameters of Large Real Directed Graphs. SEA 2015: 5667 https://doi.org/10.1007/9783319200866_5
[d3] Borassi, Michele (2016) Algorithms for metric properties of large realworld networks from theory to practice and back. Advisor: Crescenzi, Prof. Pierluigi. Coadvisor: De Nicola, Prof. Rocco . pp. 262. http://etheses.imtlucca.it/198/
Improvements of the graph module
Mentor 
David Coudert 
Area 
Graph theory 
Skills 
Knowledge of graph algorithms, Python, C/C++, git 
The goal of this project is to contribute the improvement of the graph module of Sagemath by, for instance:
 Clean the (di)graph constructors, in particular to enable loading a graph from a file. This requires to write methods for loading / saving a graph from/to a file in different graph formats. NetworkX has plenty of methods for reading graphs from file, but we should avoid the conversion from networkx graphs to Sage graphs. This has been initiated long time ago but not finalized.
 Cythonize methods that are obviously too slow in Python.
 Improve graph traversals like LexBFS and add other traversals like LexM (can be used to get approximation of tree length), LexDFS, etc.
Polynomial optimisation and sums of squares (multiple projects)
Mentor 
Dima Pasechnik, Marcelo Forets 
Area 
Nonlinear optimisation, real algebraic geometry 
Skills 
algebra, Python, C/C++, Cython, linear/nonlinear optimisation, numerical analysis (MSc/PhD level) 
Optimisation problems with polynomial constraints are efficiently, in practice, solved by building an increasingly tight sequence of semidefinite programming (SDP) relaxations, one of them known as Lasserre hierarchy [1].
While Sagemath already has an ability to solve SDPs, more work has to be done in particular to implement moment matrices for polynomials and sums of squares approximations of nonnegative polynomials, and a frontend allowing to define systems of polynomial inequalities using natural syntax, similar to what already can be done with systems of linear inequalities. Another related topic would be to interface to Sagemath more SDP solvers (currently only CVXOPT is available), and possibly prototype an arbitrary precision SDP solver to avoid typical numerical difficulties arising in sums of squaresbased SDP relaxations, e.g. implementing a version of the algorithm from [2].
Sagemath distributions on OSX (multiple projects)
Mentor 
Dima Pasechnik, Isuru Fernando, ... 
Area 
Software packaging and distribution, modularization, OSX, Homebrew, MacPorts, Conda 
Skills 
UNIX skills, OSX skills, experience with software distribution systems on OSX, such as Homebrew and MacPorts 
Currently Sagemath is distributed either as semicomplete source/binary blob, with exception of few Linux distributions, in particular Debian https://wiki.debian.org/DebianScience/Sage, and Gentoo, which make an effort of stripping out components already provided, and modularize the rest. Building on this experience, we would like to see Sagemath available on OSX distribution systems, such as Homebrew, Mac Ports, and Conda. The task of improving the installation of a "native" prebuilt Sagemath on OSX is also open.
Sagemath distributions on *BSDs (multiple projects)
Mentor 
Dima Pasechnik, LiWen Hsu, ... 
Area 
Software packaging and distribution, modularization, FreeBSD, OpenBSD, Conda 
Skills 
UNIX skills, *BSD skills, experience with software distribution systems on *BSD platforms such as FreeBSD ports 
Currently Sagemath is distributed either as semicomplete source/binary blob, with exception of few Linux distributions, in particular Debian https://wiki.debian.org/DebianScience/Sage, and Gentoo, which make an effort of stripping out components already provided, and modularize the rest. Building on this experience, we would like to see Sagemath available "natively" on *BSD systems and distributions, such as FreeBSD (ports), OpenBSD, and possibly others. The work of porting the source of Sagemath to FreeBSD is close to being completed, save tracking down one or two bugs, see https://trac.sagemath.org/ticket/26249. One can also explore a possibility of porting Conda to FreeBSD (or other *BSD) and provide Sage via Conda.
Integration of Kenzo with SimplicialSets
Mentor 
Miguel Marco 
Area 
Algebraic topology 
Skills 
Algebraic topology and some of its algorithms, Python, some Lisp experience 
Sage includes a module for simplicial sets. Kenzo is a lisp program that also provides related functionalities, but extends what Sage can do. Recently we have started adding an interface to Kenzo from Sage. The goal of this project would be to integrate it inside the SimplicalSets module.
That would require some redesign on the SimplicialSets classes, and maybe some patches to Kenzo, so the corresponding data types match correctly.
Extensions of padic fields
Mentor 
Xavier Caruso, David Roe, Julian Rüth 
Area 
Algebra, Number Theory 
Skills 
Basics of Algebraic Number Theory, Python, Cython 
Currently Sage has support for the field of padic numbers (\mathbf Q_p) and its extensions when they are presented as a compositum of a totally ramified extension on top of a unramified extension of \mathbf Q_p. The goal of this project is: (1) to add support for unramified and totally extensions of arbitrary padic fields and (2) to implement algorithms for decomposing any extension as a compositum of an unramified extension and a totally ramified extension, in order to have support for arbitrary extensions of padic fields

TEMPLATE
Project Title
Mentor
Name(s)
Area
Mathematical and/or technical scope ...
Skills
What the student should bring ...
...