Differences between revisions 9 and 10
Revision 9 as of 2018-01-23 11:36:56
Size: 6368
Editor: dimpase
Comment:
Revision 10 as of 2018-01-23 11:37:52
Size: 6369
Editor: dimpase
Comment:
Deletions are marked like this. Additions are marked like this.
Line 76: Line 76:
== Polynomial optimisation and sums of squares (multiple projects)== == Polynomial optimisation and sums of squares (multiple projects) ==

GSoC 2018: Ideas Page

Introduction

Welcome to Sage'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 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 Sage’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 Sage.

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

Addition of SPQR-tree 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 3-connected components [1] and the construction of the corresponding SPQR-tree [2]. Then, we will use these algorithms as pre-processing 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 SPQR-trees.

[1] J. E. Hopcroft, R. E. Tarjan: Dividing a Graph into Triconnected Components. SIAM J. Comput. 2(3): 135-158 (1973) [2] C. Gutwenger, P. Mutzel: A Linear Time Implementation of SPQR-Trees. Graph Drawing 2000: 77-90 [3] http://www.ogdf.net/

---

Matroid Theory (several topics)

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 signed-graphic, gain-graphic, frame matroids (showing the graph, resigning across cuts, Whitney switching, etc.)
  • Tangles and branch decompositions.
  • Faster minor testing (finish ticket 16545, and extend the ideas to non-binary matroids)
  • A framework for dealing with minor-closed classes: like a set data structure, but with some support for minors.
  • linear extensions/coextensions that keep track of allowed vectors.
  • Bracket rings/Tutte groups/universal partial fields (needs: strong knowledge of algebra and Groebner bases)

Redesigning the polynomial class hierarchy and linking with libraries

Mentor

Jean-Pierre Flori

Area

Basic algebra, C/C++, Cython

Skills

Strong programming skills, familiarity with polynomial algebra

Sage supports univariate and multivariate polynomial arithmetic over general rings with many features. For efficiency, it is crucial that Sage links to low-level implementations for polynomials over certain rings, such as finite fields or integers. These things have been in Sage 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 Sage. The task in this project is to get an overview of the current features Sage 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 re-linking to the many projects Sage 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

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 squares-based SDP relaxations, e.g. implementing a version of the algorithm from [2].

[1] https://en.wikipedia.org/wiki/Sum-of-squares_optimization [2] https://arxiv.org/abs/1507.03549

---

TEMPLATE

Project Title

Mentor

Name(s)

Area

Mathematical and/or technical scope ...

Skills

What the student should bring ...

...

  • ...
  • ...

GSoC/2018 (last edited 2018-02-20 00:32:41 by tscrim)