GSoC 2020: Ideas Page
Introduction
Welcome to Sagemath's Ideas Page for GSoC 2020! (Last year 2019)
SageMath's GSoC organization homepage  the hub for submitting applications and where the everything on Google's side is organized. (Timeline)
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 2020: Ideas Page

Project Ideas
 Berkovich Projective Line
 Improve support of representation theory (multiple projects)
 Implement Schubert and Grothendieck polynomials
 Simplicial sets: complete the integration with Kenzo
 Diameter, radius, eccentricities, and distances
 Database of generators and of "sporadic" examples of distanceregular graphs
 Fast evaluation of symbolic expressions
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.
Berkovich Projective Line
Mentor 
Benjamin Hutz 
Area 
Schemes/Dynamical Systems 
Skills 
One semester of graduate algebra and analysis, Python, git 
Implement a basic framework for working with Berkovich space points and functions
 define a type I,II,III,IV point
 basic point operations, such as equality
 evaluate the induced map on Berkovich points from a projective morphism
 (as time allows) implement some of the dynamical systems algorithms that utilize Berkovich space (minimal model, etc).
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 Schubert and Grothendieck polynomials
Mentor 
Travis Scrimshaw 
Area 
Algebra, Combinatorics, Schubert Calculus 
Skills 
Foundations in combinatorics, experience reading research papers 
Schubert calculus can roughly be stated as the study of the intersections of lines, through which certain algebras arise that can be represented using Schubert polynomials and Grothendieck polynomials. The main goal of this project is to finish the implementation started in #6629, as well as implement the symmetric Grothendieck polynomials and their duals in symmetric functions.
Simplicial sets: complete the integration with Kenzo
Mentor 
Miguel Marco 
Area 
Algebraic topology 
Skills 
Mathematical background on simplicial sets. Experience with Lisp 
Kenzo is a Lisp program that is able to compute homology and homotopy groups of a big family of toopological spaces. Sage has an interface to it, but it is not tightly integrated with the existing modules for simplicial sets. This project would consist on iproving the existing interface and integrating it with the simplicial sets module, so we can use kenzo functionalities directly as methods of Sage objects.
It might imply patching Kenzo to support the input provided by Sage.
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/
Database of generators and of "sporadic" examples of distanceregular graphs
Mentor 
Dima Pasechnik 
Area 
Graph theory, algebraic combinatorics 
Skills 
Knowledge of graph algorithms, basic algebra and combinatorics, Python, git 
The graph module of Sagemath already provides a database of (generators and examples) of strongly regular graphs, and a numbers of generators for distanceregular graphs. This project will
implement more known constructions of distanceregular graphs, in particular covering the "classical parameters case" of P and Qpolynomial association schemes;
import and augment examples of small distanceregular graphs from https://www.distanceregular.org/
 implement methods to work with intersection arrays of distanceregular graphs
References:
 [BCN] A.E.Brouwer, A.M.Cohen, A.Neumaier; Distanceregular graphs. Springer 1989
[Sur16] Edwin R. van Dam, Jack H. Koolen, Hajime Tanaka; Distanceregular graphs (2014/16): https://arxiv.org/abs/1410.6294
Fast evaluation of symbolic expressions
Mentor 
Vincent Delecroix, Isuru Fernando 
Area 
Symbolic expression 
Skills 
Basic math background in algebra and analysis. Fluent in Python and C/C++. Kowledge of compilers, assembler, Cython, or parallelization (openmp) would be interesting. 
The simplest example of a function is given by univariate polynomials such as P(x) = x^3  2*x + 3. A more complex function is F: (x, y) > (cos(sqrt(x) + 1) * sin(y), tan(x^2 + 2) + y). For this project we are interested in making the evaluation of such expression at given concrete values fast and reliable. SageMath already has a "compiler" for symbolic expression that is used through fast_callable
sage: x, y = SR.var('x,y') sage: f = cos(sqrt(x) + 1) * sin(y) sage: g = fast_callable(f, vars=[x,y], domain=float) sage: g(2.3, 3.5) 0.2844686555174862
This project will consider
package symengine
Make sage optional packages for symengine and symengine.py
Analyze whether symengine can be used as a replacement for fast_callable
numpy compatibility
Making fast callable works with numpy arrays input (ie so that a fast callable behave as a universal numpy function)
Implementing arrays of fast callable, ie functions whose codomain has several components. Currently Sage has no support for making a fast callable for the 2variable function F: (x, y) > (cos(sqrt(x) + 1) * sin(y), tan(x^2 + 2) + y).
 Using the developed tools to improve overall Sage performance (numerical integration, numerical optimization, etc)
more data types
 Making numpy arrays support more types such as
real numbers (MPFR mpfr_t)
An example of such implementation are the quaternions.
 In parallel to the above task, implement interpreters for fast callable for these types.
 Making numpy arrays support more types such as
optimization
 Analyzing and optimizing accuracy (for floating points numbers).
Analyzing and optimizing the size of the evaluation tree: given an expression there are plenty of way to evaluate it. For example P(x, y) = x^4 + 2*x^2*y + 3*x^2 + 2*x*y + 2*y^2 + 2*y + 1 can be evaluated naively. But we can also rewrite it as P(x,y) = (x^2 + y + 1)^2 + (x + y)^2 and get another evaluation scheme. This problem of determining the optimal evaluation tree is known to be NPcomplete.
 Parallelization.
Related projects
The (now abandoned) project Theano might be of interest for optimization.

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