= GSoC 2022: Ideas Page = == Introduction == Welcome to SageMath's Ideas Page for GSoC 2022! ([[https://wiki.sagemath.org/GSoC/2021 | Last year 2021]]) '''[[https://summerofcode.withgoogle.com/programs/2022/organizations/sagemath | SageMath's GSoC organization homepage]]''' -- the hub for submitting applications and where the everything on Google's side is organized. ([[https://summerofcode.withgoogle.com/how-it-works/#timeline | Timeline]]) Please subscribe to the [[https://groups.google.com/forum/#!forum/sage-gsoc|sage-gsoc]] mailing list and the GAP developer list for discussion on possible GAP GSoC projects. Also, make sure you have gone through the '''[[https://wiki.sagemath.org/GSoC/Students | 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 [[https://wiki.sagemath.org/GSoC | here]]. All projects will start with an introduction phase to learn about Sage``Math’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 [[https://trac.sagemath.org/ | Trac]] of the project you are interested in applying to. The [[http://doc.sagemath.org/html/en/developer/index.html|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 [[http://trac.sagemath.org/query?status=needs_info&status=needs_work&status=new&milestone=sage-wishlist&or&milestone=sage-feature&col=id&col=summary&col=status&col=type&col=priority&col=component&order=priority|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. {{{#!wiki comment/dashed --- TEMPLATE == Project Title == || Mentor || Name(s) || || Area || Mathematical and/or technical scope ... || || Skills || What the student should bring ... || || Length || Medium-term or long-term || || Difficulty || Easy, medium, hard, etc. || ... * ... * ... }}} == Improve (free) module implementations == || Mentor || Travis Scrimshaw || || Area || Linear Algebra, Performance, Refactoring || || Skills || Understanding of linear algebra and object-oriented programming. Cython experience is highly recommended. || || Length || 175 hours || || Difficulty || Medium-easy || SageMath has multiple implementations of free modules: 1. Finite dimensional coordinate representations in the "standard" basis using `FreeModule` that provides both a dense and sparse implementation. 2. Using `CombinatorialFreeModule` (CFM) as (possibly infinite dimensional) sparse vectors. There are various benefits to each implementation. However, they are largely disjoint and would mutually benefit from having a common base classes. In particular, having a dense implementation for CFM elements for applications that require heavier use of (dense) linear algebra. The goal of this project is to refactor these classes to bring them closer together (although they will likely remain separate as they are likely not fully compatible implementations for the parents). == Rewrite exterior algebra and implement Gröbner bases == || Mentor || Travis Scrimshaw, Vic Reiner || || Area || Algebra, Performance || || Skills || Understanding of abstract algebra and Cython. Knowledge of Gröbner basis is recommended. || || Length || 175 hour and 350 hour variants || || Difficulty || Medium-hard || The exterior (or Grassmann) algebra is a fundamental object in mathematics, in particular with applications to physics and geometry. It could be considered as the closest non-commutative analog of polynomials where the variables skew-commute with each other. The current implementation uses a basis indexed by subsets (as tuples), but a more efficient version would be indexed by integers encoding membership by the binary string. The first goal is to do this change ([[https://github.com/sagemath/sage/issues/32369|#32369]]). The second goal of this project would be to implement an algorithm for Gröbner basis for their ideals in order to construct quotient algebras. A variation of this project would be to improve the implementation of commutative graded algebras to not rely on the more generic [[https://www.singular.uni-kl.de/Manual/4-0-2/sing_469.htm|plural]] for computations (except perhaps those involving ideals). For the ambitious, these computations would be extracted to an independent C++ library for many common rings (implemented using other libraries). == Implement Schubert and Grothendieck polynomials == || Mentor || Travis Scrimshaw || || Area || Algebra, Combinatorics, Schubert Calculus || || Skills || Foundations in combinatorics, experience reading research papers. || || Length || 175 hours || || Difficulty || Medium-hard || 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 [[https://github.com/sagemath/sage/issues/6629|#6629]], as well as implement the symmetric Grothendieck polynomials and their duals in symmetric functions. == Tensor operations in Sage using Python libraries as backends == || Mentor || Matthias Koeppe || || Area || Linear/multilinear algebra || || Skills || Solid knowledge of linear algebra, Python experience, ideally experience with numpy, !PyTorch, JAX, or !TensorFlow || || Length || 350 hours || || Difficulty || Hard || In this project, we develop new backends for the [[https://sagemanifolds.obspm.fr/tensor_modules.html|tensor modules from the SageManifolds project]]. Amongst the goals of the project are such elements as a [[https://github.com/sagemath/sage/issues/30308|fast implementation of tensor operations using numpy]] and [[https://github.com/sagemath/sage/issues/30096|using TensorFlow Core and PyTorch]]. == Enhanced optimization solver interfaces for Sage == || Mentor || Matthias Koeppe || || Area || Optimization || || Skills || Solid knowledge of linear optimization, Python experience, ideally experience with Python optimization interfaces || || Length || 350 hours || || Difficulty || Hard || See [[https://github.com/sagemath/sage/issues/26511|Meta-ticket #26511: Use Python optimization interfaces: cvxpy, PuLP, Pyomo, cylp...]] == Fast evaluation of symbolic expressions == || Mentor || Vincent Delecroix and Isuru Fernando || || Area || Symbolic expression || || Skills || Basic math background in algebra and analysis. Fluent in Python and C/C++. Knowledge of compilers, Cython, or parallelization (openmp) would be useful. || || Length || 350 hours || || Difficulty || Medium || 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 }}} The objective of this project is to rewrite the code for fast callable using the more modern project [[https://github.com/symengine/symengine|symengine]]. Doing so the applicant is likely to contribute to both symengine and SageMath projects. Here is a potential list of subtasks 0. '''make sage code compatible with symengine''' Some algorithms in sage do use `fast_callable` (such as integration routine, numerical differential equations solver, computation of geodesics on manifolds, ...). For each of them, one need to check whether the `symengine` functions can be used as a drop-in replacement and possibly adapt the sage code. Documentation and tests should be adapted accordingly. 1. '''add support for more data types in symengine''' (in order to support more sage types) * Making numpy arrays support more types such as * integers ([[https://gmplib.org/|GMP]] `mpz_t` and [[http://www.flintlib.org/|flint]] `fmpz_t`) * rationals ([[https://gmplib.org/|GMP]] `mpq_t` and [[http://www.flintlib.org/|flint]] `fmpq_t`) * real numbers ([[https://www.mpfr.org/|MPFR]] `mpfr_t`) * intervals ([[https://gforge.inria.fr/projects/mpfi/|MPFI]] `mpfi_t`) and balls ([[http://arblib.org/|arb]] `arb_t` and `acb_t`) An example of such implementation are the [[https://github.com/moble/quaternion|quaternions]]. 2. '''optimization''' * Time benchmark `fast_callable` against `symengine` * Analyzing and optimizing accuracy (for floating points numbers). For example the order of operations do matter for accuracy. * 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. * Generate code for multiple input arrays so that compiler can optimize it better. 3. '''parallelization''' Related projects * [[https://docs.sympy.org/latest/modules/codegen.html|sympy codegen]]. * The (now abandoned) project [[http://deeplearning.net/software/theano/|Theano]] might be of interest for optimization. == Edge connectivity and edge disjoint spanning trees in digraphs == || Mentor || David Coudert || || Area || Graph theory || || Skills || Solid knowledge of graph theory and graph algorithms, Python and C/C++ experience || || Length || 350 hours || || Difficulty || Hard || The current method used for finding edge disjoint spanning trees in directed graphs (digraphs) relies on mixed integer linear programming and it may fail on some instances (see [[https://github.com/sagemath/sage/issues/32169|ticket #32169]]). The problem has been fixed for undirected graphs, implementing a combinatorial algorithm (see [[https://github.com/sagemath/sage/issues/32911|ticket #32911]]). The goal of this project is to implement combinatorial algorithms for finding edge disjoint spanning trees in digraphs. We will particularly consider the following algorithms: * Harold N. Gabow: A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. J. Comput. Syst. Sci. 50(2): 259-273 (1995) ​[[https://doi.org/10.1006/jcss.1995.1022]] * Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha and Debmalya Panigrahi: Fast edge splitting and Edmonds' arborescence construction for unweighted graphs. ACM-SIAM symposium on Discrete algorithms (SODA), pp 455-464, 2008 [[https://users.cs.duke.edu/~debmalya/papers/soda08-splitting.pdf]] == Improve Height Functionality == || Mentor || Ben Hutz and Alex Galarraga|| || Area || Algebraic Geometry || || Skills || Python experience, abstract algebra, basic algebraic geometry, number theory || || Length || 175 hours || || Difficulty || Medium Hard || There are some issues with the current implementations of heights in Sage * [[https://github.com/sagemath/sage/issues/32687|#32687]] error in height difference bound * [[https://github.com/sagemath/sage/issues/32686|#32686]] points_of_bounded_height for projective space is incorrect * A very advanced student could also finish [[https://github.com/sagemath/sage/issues/21129|#21129]] Arakelov-Zhang pairing of rational maps Related to [[https://github.com/sagemath/sage/issues/32687|#32687]] is implementing the more efficient algorithm from Krumm from the paper mentioned in that ticket. == Implementation of generalizations of RSK algorithm == || Mentor || Tomohiro Sasamoto || || Area || Combinatorics, Probability Theory || || Skills || Python experience, understand combinatorial algorithms, experience reading research papers || || Length || 175 hours || || Difficulty || Medium Hard || In Sage, the classical RSK algorithm is implemented. Such algorithm admits extensions as Sagan and Stanley's version, which puts in bijection pairs of skew tableaux with matrices of sequences. Another extension of the RSK is given by a recent algorithm by Imamura, Mucciconi and Sasamoto. As these generalizations of the RSK are not yet available in Sage we aim to implement them. The project will include creating new combinatorial operations on tableaux and new realization of Kashiwara operators. We also aim at creating Sage functions with which one can visualize such new operations. == Implement piecewise functions of one or several variables == || Mentor || Yuan Zhou || || Area || Geometry || || Skills || Knowledge of linear algebra and polyhedral geometry, Python experience. || || Length || 175 hour and 350 hour variants || || Difficulty || Medium || See [[https://github.com/sagemath/sage/issues/20877|Meta-ticket #20877: Piecewise functions, polyhedral complexes, piecewise functions of several variables, periodic piecewise functions]] == Make polyhedral algorithms verifiable == || Mentor || Yuan Zhou || || Area || Geometry || || Skills || Knowledge of polyhedral geometry and linear programming, Python experience. || || Length || 350 hour || || Difficulty || Medium-hard || See [[https://github.com/sagemath/sage/issues/31343|Meta-ticket #31343: Certified polyhedral computation]]