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 sage-gsoc 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!

Project Ideas

Here is a list of project proposals with identified mentors. Other well-motivated proposals from students involving Sagemath in a substantial way will be gladly considered, as well.

Berkovich Projective Line

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)

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 proof-of-concept, 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

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

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

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/sage-floyd-algorithm-in-cython/.

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: 56-67 https://doi.org/10.1007/978-3-319-20086-6_5

• [d3] Borassi, Michele (2016) Algorithms for metric properties of large real-world networks from theory to practice and back. Advisor: Crescenzi, Prof. Pierluigi. Coadvisor: De Nicola, Prof. Rocco . pp. 262. http://e-theses.imtlucca.it/198/

Database of generators and of "sporadic" examples of distance-regular graphs

The graph module of Sagemath already provides a database of (generators and examples) of strongly regular graphs, and a numbers of generators for distance-regular graphs. This project will

• implement more known constructions of distance-regular graphs, in particular covering the "classical parameters case" of P- and Q-polynomial association schemes;

• import and augment examples of small distance-regular graphs from https://www.distanceregular.org/

• implement methods to work with intersection arrays of distance-regular graphs

References:

• [BCN] A.E.Brouwer, A.M.Cohen, A.Neumaier; Distance-regular graphs. Springer 1989

• [Sur16] Edwin R. van Dam, Jack H. Koolen, Hajime Tanaka; Distance-regular graphs (2014/16): https://arxiv.org/abs/1410.6294

Fast evaluation of symbolic expressions

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

1. package symengine

   • Make sage optional packages for symengine and symengine.py

   • Analyze whether symengine can be used as a replacement for fast_callable

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

3. more data types

   • Making numpy arrays support more types such as

     • integers (GMP mpz_t and flint fmpz_t)

     • rationals (GMP mpq_t and flint fmpq_t)

     • real numbers (MPFR mpfr_t)

     • intervals (MPFI mpfi_t) and balls (arb arb_t and acb_t)

     An example of such implementation are the quaternions.

   • In parallel to the above task, implement interpreters for fast callable for these types.

4. 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 NP-complete.

   • Parallelization.

Related projects

• sympy codegen.

• The (now abandoned) project Theano might be of interest for optimization.