15081
Comment:

← Revision 30 as of 20180220 00:32:41 ⇥
15097

Deletions are marked like this.  Additions are marked like this. 
Line 137:  Line 137: 
 Mentor  Travis Scrimshaw    Mentor  Travis Scrimshaw, Michael Walter  
GSoC 2018: Ideas Page
Introduction
Welcome to Sagemath's Ideas Page for GSoC 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 2018: Ideas Page

Project Ideas
 Addition of SPQRtree to graph module
 Matroid Theory (several projects)
 Redesigning the polynomial class hierarchy and linking with libraries
 Polynomial optimisation and sums of squares (multiple projects)
 Databases of and bounds of codes (multiple projects)
 Implement Aspects Of Representation Theory (multiple projects)
 Implement Lie superalgebras
 Improve Root/Coxeter Systems
 Implement Quantum Cluster (Super)Algebras
 Rational Points on Varieties
 Arithmetic and Complex Dynamics
Project Ideas
Addition of SPQRtree to graph module
Mentor 
David Coudert 
Area 
Graph theory 
Objective:
The goal of this project is to contribute the graph theory module of SageMath with the addition of the linear time algorithm for partitioning a graph into 3connected components [1] and the construction of the corresponding SPQRtree [2]. Then, we will use these algorithms as preprocessing for several graph problems such as Hamiltonian Cycle, TSP, etc.
The preferred approach will be to create an interface for the OGDF library [3] that contains an efficient C++ implementation of the construction of SPQRtrees.
[1] J. E. Hopcroft, R. E. Tarjan: Dividing a Graph into Triconnected Components. SIAM J. Comput. 2(3): 135158 (1973) [2] C. Gutwenger, P. Mutzel: A Linear Time Implementation of SPQRTrees. Graph Drawing 2000: 7790 [3] http://www.ogdf.net/

Matroid Theory (several projects)
Mentor 
Stefan van Zwam 
Area 
Matroid Theory, Graph Theory, Combinatorics 
Skills 
Strong foundation in (discrete) mathematics (PhD student level), strong programming skills, experience reading research papers 
Matroid theory in SageMath can be improved in many ways. Some potential topics, of varying difficulty, are:
 Support for signedgraphic [5], gaingraphic, frame matroids [6] (showing the graph, resigning across cuts, Whitney switching, etc.)
 Tangles and branch decompositions [4]
 Faster minor testing (finish ticket 16545 [3], and extend the ideas to nonbinary matroids)
 A framework for dealing with minorclosed classes: like a set data structure, but with some support for minors.
 linear extensions/coextensions that keep track of allowed vectors.
 Bracket rings [2] /Tutte groups/universal partial fields [1] (needs: strong knowledge of algebra and Groebner bases)
[1] http://matroidunion.org/?p=2103
[2] https://en.wikipedia.org/wiki/Bracket_ring
[3] https://trac.sagemath.org/ticket/16545
[4] https://www.sciencedirect.com/science/article/pii/S0095895609000082
[5] https://arxiv.org/abs/1405.1313
[6] https://arxiv.org/abs/1609.05574
Redesigning the polynomial class hierarchy and linking with libraries
Mentor 
JeanPierre Flori 
Area 
Basic algebra, C/C++, Cython 
Skills 
Strong programming skills, familiarity with polynomial algebra 
Sagemath supports univariate and multivariate polynomial arithmetic over general rings with many features. For efficiency, it is crucial that Sagemath links to lowlevel implementations for polynomials over certain rings, such as finite fields or integers. These things have been in Sagemath for a long time, and e.g. much of the linking code was written in early versions of Cython when it was much less powerful than it is now.
It is time to rethink and redesign the class hierarchy and the linking code for polynomials in Sagemath. The task in this project is to get an overview of the current features Sagemath supports, what we would like to do forward, and then come up with a better, cleaner design and implementation for doing this. This will entail relinking to the many projects Sagemath already talks to, and perhaps find projects that have appeared on the OSS scene since.
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].
[1] https://en.wikipedia.org/wiki/Sumofsquares_optimization
[2] https://arxiv.org/abs/1507.03549

Databases of and bounds of codes (multiple projects)
Mentor 
Dima Pasechnik (with extra support by Johan Rosenkilde) 
Area 
Coding theory 
Skills 
Basic programming skills, knowledge of algebra and discrete mathematics (BSc/MSc level or better) 
Sagemath already has a considerable coding theory component. We will aim to extend it to allow constructions of optimal linear (and perhaps more general) codes, akin to a nonopensource [1]. In particular, while Sagemath is capable to compute bounds on code sizes, in many cases matching bounds of [1] (or even better than these), there is no systematic way to organise these bounds available.
The main task here will be to construct optimal (or best known) codes for given sets of parameters, in many cases combining constructions already available in Sagemath to build codes inductively. This is similar in technique to what is already done in Sagemath for Hadamard matrices and other combinatorial objects such as strongly regular graphs. Smaller tasks would be to implement linear programming bounds for constant weight codes, as well as semidefinite optimisationbased bounds due to A.Schrijver et al., see e.g. [2].
[2] https://www.math.ubordeaux.fr/~cbachocb/articles/handbook.pdf
Implement Aspects Of Representation Theory (multiple projects)
Mentor 
Travis Scrimshaw, Michael Walter 
Area 
Representation theory, algebra, combinatorics 
Skills 
Understanding of algebra and representation theory, experience with Cython preferred, knowledge of combinatorics desirable 
Representation theory is a broad area of mathematics that has deep connections with many applications in other fields, such as physics and chemistry. GAP provides support for (typically finite) groups, and usually through their character theory. However, it does not contain support for standard constructions nor representations of algebras. Sagemath provides access to GAP and is currently the only software that provides systematic support for crystals, combinatorial realizations of KacMoody algebra representations. Sagemath also currently provides some very limited support for representation theory, but it has the framework in place to both significantly improve and increase the aspects of representation.
Some of the potential projects include:
 Implement induction and restriction functors.
 Implement methods and framework for constructing representations.
 Implement representations for Hecke algebras.
 Implement various bases for the symmetric group algebra.
 Implement group representations as modules.
Algorithm to find invariant subspaces #11285.
Finalize implementations of Fock space#15508, Lie algebras #14901, cellular algebras #19506, etc.
Implement Lie superalgebras
Mentor 
Travis Scrimshaw 
Area 
Algebra, representation theory 
Skills 
Knowledge of algebra, experience with Cython preferred 
Lie superalgebras were introduced by Kac in order to unify bosons and fermions and are currently an active topic of research. The goal of this project is to extend the Lie algebra framework in Sagemath to Lie superalgebras and provide a basic implementation of the standard finitedimensional Lie superalgebras and their representations.
Improve Root/Coxeter Systems
Mentor 
Travis Scrimshaw 
Area 
Representation theory, combinatorics, geometry 
Skills 
Understanding of linear algebra, knowledge of root systems or Coxeter groups preferred 
This project is above improving the implementation of root systems and Coxeter systems in Sagemath. It is divided into 3 main areas:
Root systems
We currently have an implementation of root systems with special inputs for finite and affine types, but there has been interest to implement an easy system for obtaining hyperbolic types. One aspect of this project is to implement such a system. Another aspect is to make the current implementation of Dynkin diagrams, Cartan matrices, and root systems more robust and generalize to, e.g., Lie superalgebras, complex reflection groups, and DAHAs.
Coxeter systems
The currently implementation of Coxeter systems currently uses the root system code and needs to be improved. In particular, this removing any ambiguity between dual types of root systems, such as types B and C.
Complex reflection groups
One last aspect is that the root system code could be used to describe a permutation representation of finite complex reflection groups, but currently this relies on the (experimental) GAP3 package. This is not strictly necessary, and we should remove this as a dependency by doing a direct implementation.
Implement Quantum Cluster (Super)Algebras
Mentor 
Travis Scrimshaw 
Area 
Combinatorics, algebra 
Skills 
Solid foundation of algebra, experience reading research papers preferable 
Cluster algebras and their generalizations are important algebraic objects that contain deep connections with areas such as algebraic geometry and representation theory. They have been implemented in Sagemath (see, e.g., ClusterSeed and #21254). One of the next steps is to implement the quantum version, where the variables now skew commute. (Quantum) Cluster superalgebras are a super version of (quantum) cluster algebras that are in the process of being mathematically developed, but there are currently some proposed structures. The primary goal of this project is to provide a basic implementation of known structures to help advance the field.
Rational Points on Varieties
Mentor 
Benjamin Hutz 
Area 
number theory, algebraic geometry 
Skills 
number theory, algebraic number theory, and algebraic geometry at a basic level 
The rational point finding on varieties/schemes is rudimentary at best in Sagemath. There are a couple simple improvements to do (such as sieving modulo primes) and some more advanced algorithms (such as Turner's thesis) for point searching to implement. Finishing #22771 for point enumeration over number fields could also be done. In all cases, these are published algorithms that need implementation in Sage.
Someone experienced with classes/inheritance could also work on aspects of the schemes code to fix issues like those in #23807. There is an issue with whether or not schemes should have a unique representation in memory which is currently inconsistently applied.
Arithmetic and Complex Dynamics
Mentor 
Benjamin Hutz 
Area 
number theory, dynamical systems 
Skills 
number theory, cython 
There are a number of areas that the dynamical systems code could be improved. A few specific possibilities are the following. The algorithm to determine the set of rational preperiodic points could use the following improvements:
 use the dynatomic polynomial for small periods
 allow the ambient space to be a subscheme
 allow the ambient space to be a product of projective spaces.
There are a number of other basic functionality missing from products of projective space.
It is possible some improvements to the Mandelbrot and Julia set functionality could be done. A basic implementation was done for GSoC last year so now, some other applications and/or optimizations could be done. In particular, a faster implementation through something like a divideandconquer approach could greatly speed up some of the slower more general functions.
There are also a number of open issues at dynamicswiki.