GSoC 2014
Sage Project Proposals

Introduction

Links

UI: Web-Based

UI Enhancements

Interactive 2d plots

Sage Cell Server

Additional Notebook Ideas

Open-Sourcing SageMathCloud’s Notebook

Native GUI

UI: Mobile Applications

Android & Android Tablets

iOS App (iPhone & iPad)

Virtual Machine GUI

Back-end

Symbolics

Summation and integration routines using hypergeometric and Meijer G function representations

Pattern matching based symbolic integration

Numeric class wrappers in Pynac

Advanced Symbolic Expression Manipulation

Semidefinite Programming and sums of squares of real multivariate polynomials

Libs: Underlying Libraries

Maxima/Numerical Mathematics

Point Counting on curves over finite fields (Sage/FLINT/Pari)

This is related to elliptic curves:

Better point counting code on curves over finite fields.

Singular4 interface update

Combinatorics

Matroid theory

Knot theory

Student’s Proposal Template

Contact

Introduction

Sage is a GPLed open-source mathematical software system. It is designed to be not just a computer algebra system, but more like a complete environment for doing mathematics and related calculations. It is based on a vast collection of existing open-source software tools and libraries and ties them together via Python. This is also the primary interface language for the user and its object-oriented way of expressing concepts is used to express calculations - of course, there are also many “normal” functions :-) Behind the scenes, the Sage library executes the commands and calculations by its own algorithms or by accessing appropriate routines from the included software packages. On top of that, there are various ways how users can interact with Sage, most notably a dynamic web-site called “Notebook”.

All projects will start with an introduction phase to learn about Sage’s internal organization and to get used to its established development process. This is documented in the documentation for developers and all students will be instructed by the mentors on how to get their hands dirty. We use Git for revision control and trac for organizing development and code review. Our license is GPLv2+. Feel free to contact Mentors before you send us project proposals, contact details are at the bottom. Feel free to introduce yourself and your project idea in our mailing list. To get a better feeling of Sage’s features, please check out the documentation, especially the thematic tutorials.

 Student’s proposal template at the bottom.

Links


Project Proposals

This list of possible projects is organized into categories, starting with the web-based notebook interface.

UI: Web-Based

The Sage Notebook is the primary graphical interface for Sage. It consists of a Python-based server back-end evaluating the computations and a rich interactive Ajax-based website. It has a user management, each user has a list of worksheets and each worksheet consists of cells that are evaluated on the server and the output is sent back to the website. The following batch of notebook specific proposals outline projects for improving the notebook on different levels.

The core team behind the notebook consists of several people who very welcome new contributors. You can access a Sage Notebook at www.sagenb.org or cloud.sagemath.com, which has proven to be a very successful way of enabling average users to access an advanced mathematics suite online. Their dedicated mailing list is here.

UI Enhancements

Description

In the Sage Notebook, each user opens a worksheet to interact with Sage for doing mathematics. A worksheet is a list of alternating input/output cells. To actually do computations, one has to know about the commands and basic Python in order to do any calculations. Currently, a new user has to read the tutorial to get started, which needs time and is a barrier for new users.

The aim of this project is to make it easier for novice users to actually use the notebook and help them entering common calculations. This could be done via several independent enhancements:

  • Assessing commonly used functions by examining published notebooks and the written documentation.
  • A menu with entries and sub-entries, collecting common functions by topic - then providing:
  • Code-snippets with adequate descriptions.
  • Wizard dialogs that help accomplishing common calculations or plots.
  • e.g. along the ideas of: http://sagemath.org/eval.html
  • Enhancing the documentation, make it more accessible through the Notebook UI. Cross-Referencing.
  • Enhancing the auto-complete functionality, e.g. containing descriptions for the methods.
  • Interactive step-by-step tutorials to accomplish common calculations.
  • even more ideas ...

Code: https://github.com/sagemath/sagenb

In particular, check out the branch “newui”

Mentor

Jason Grout

backup: Dan Drake

Difficulty

Easy

Skills

  • HTML/CSS, Javascript (jQuery, AJAX), basic Python
  • UI-Design of online Applications

Interactive 2d plots

Description

Sage’s 3d plots are dynamic: the user can zoom in and out and rotate the image. By contrast, 2d plots are static: the user can see a picture, but cannot zoom in on features of interest, zoom out to obtain a more global perspective, trace along the curve, or pan the view. The goal of this project is to add features like this to 2d plots, at least in the notebook view, making the notebook more suitable for educational purposes.

Make sure to check out libraries like mpld3.

Mentor

John Perry

Difficulty

Intermediate

Skills

  • HTML/CSS, JavaScript
  • Python

Sage Cell Server

Description

The Sage Cell Server is basically a text box, where you can enter code and it is sent to a server for evaluation. This box can be embedded in any HTML website and for example, is in use for many online textbooks.

Besides basic calculations, it is able to present plots in 2D and 3D and also add html widgets for small interactive applications.

The goal of this project would be to extend the existing functionality, add better modes for plotting 2D or 3D, and/or work on server-side aspects.

Mentor

Jason Grout

Difficulty

Intermediate

Skills

  • HTML/CSS, JavaScript
  • Python

Additional Notebook Ideas

Apart from the ones above, other project ideas are also welcome. Here is a selected list of ideas for your inspiration. Contact the possible mentors for more details.:

Description

  • Improvements to @interact
  • Master-worksheet, a collection of other worksheets to build, for example, a book.
  • Permanent hyperlinks between worksheets, independent of worksheet numbering
  • Exporting worksheets to LaTeX, creating PDFs, export to ODF.
  • Slide-Show-Mode to make it possible to show interactive presentations.
  • Enhance revision history and snapshot capabilities.
  • Content-editable divs for the code cells, so we can support more complex ways for inputting code (e.g. a wysiwyg formula editor or colored syntax highlighting)
  • Support various types of text cells, so that, at the user's option, we could have a ReST text cell, an HTML (TinyMCE) text cell, a plain text cell, a latex text cell, etc.
  • Chat with exchange of text and code between users logged in on the same Sage server.
  • Wiki-like platform for editing and publishing mathematical, physical, statistical and other content.
  • Tagging support for worksheets, searching within tags
  • Efficiently exchange usage examples, tips and ideas.
  • even more ideas ...

Code: https://github.com/sagemath/sagenb

In particular, check out the branch “newui”

Mentor

Jason Grout, Dan Drake

discussion here: sage-gsoc

Difficulty

Easy to Intermediate, project could consist of one bigger project or several small and independent sub-projects.

Skills

  • HTML/CSS, Javascript (jQuery, Ajax, …)
  • basic Python.

Open-Sourcing SageMathCloud’s Notebook

Description

The “SageMathCloud” is a successor of the traditional web-based Sage Notebook. It’s an online web-service, re-designed from the ground up for scalability, reliability and fault-tolerance. On top of that infrastructure, it allows to collaboratively edit (mathematical) documents like the notebook and other text-based files. It uses the “Differential Synchronization” algorithm by Neil Fraser - the same used e.g. for Google’s Drive Documents.

The goal of this project is open-sourcing the relevant parts for the notebook interface, and to re-implement necessary parts of the underlying infrastructure to make them work.

Mentor

William Stein

Difficulty

Intermediate

Skills

  • HTML/CSS, Javascript (jQuery, Ajax, …)
  • Databases (NoSQL)
  • basic Python.

Native GUI

Description

Currently, Sage has several different user interfaces. There is a web-based notebook interface, various online services and the command-line. What’s missing is a native GUI. This mode of interaction with Sage has it’s own benefits, drawbacks and challenges.

So far, basic ingredients like an asynchronous remote procedure call service over plain TCP have been created. We have a MVC framework for the notebook with a Python Gtk3 interface an a proof-of-concept HTML/Websocket interface.

The goal of this project would be to make it viable and useful. Work out a plan for implementing features and assess which features are missing and how important they are.

Code:

Mentor

Volker Braun

Difficulty

Intermediate, and no hard mathematics involved :-)

Skills

  • Python
  • Gtk3 and gobject introspection
  • HTML/CSS, Javascript (jQuery, Ajax, …)

UI: Mobile Applications

The traditional way of running Sage is via a “full” personal computer workstation. There are other form factors and devices from where Sage should be accessible, most notably tablets and smartphones. This involves running Sage on a remote server and designing a new user interface for interacting with it.

Android & Android Tablets

Description

The current android app for Sage is here:

https://play.google.com/store/apps/details?id=org.sagemath.droid

It allows to run code remotely on a dedicated server and guides and assists the user with a helpful interface. Check it out, look at the list of open issues (bugs, stack trackes, new ideas) and make sure to also learn what “interacts” are. Besides just fixing bugs, there are many ways this application can be extended, improved and enhanced.

Code: https://github.com/sagemath/android

Mentor

Volker Braun

backup: Harald Schilly

Difficulty

Easy, and no hard mathematics involved :-)

Skills

  • Java
  • Android development
  • UI and interface design
  • Client/Server communication

iOS App (iPhone & iPad)

Description

https://bitbucket.org/gvol/sage-iphone-app/

  • Adding interactive widget support
  • Creating an iPad version
  • Enhancements for use in a classroom situation
  • Various other enhancements, particularly around text entry

Mentor

Ivan Andrus

Difficulty

Easy, and no hard mathematics involved :-)

Skills

  • iPhone/iPad development (Objective-C)
  • Possibly HTML, CSS, and JavaScript
  • UI Design skills would be a plus

Virtual Machine GUI

Right now Sage is installed on Windows machines as a VirtualBox virtual machine. This approach has some problems that makes some users desist in their intent to use Sage. We would need a simple GUI that deals with this issues. Namely, it should check the VirtualBox installation in the system, check the availability of connection ports, and handle the installed virtual machine status. In particular, it should run rhe virtual machine in headless mode if it is possible to connect from the local web browser.

See the discussion at https://groups.google.com/group/sage-devel/browse_thread/thread/a4808f2cf5b8b79f/03db2e576b21f42e?q=virtualbox&lnk=nl& about it.

Description

Write a GUI program to handle the VirtualBox VM. It should do something like the following:

  • download new Virtual Machines if necessary
  • let the user choose between different versions of the Sage VM
  • diagnose port / firewall issues
  • automatically export notebooks from the VM using a bundled ssh client
  • write the launcher in Python (which we also include) using some Python GUI toolkit (included, too)  

Mentor

Miguel Marco, Volker Braun

Difficulty

Medium

Skills

  • Python, some python GUI toolkit (Gtk3/pyQt/pyTclTk...)
  • VirtualBox VM’s administration

Back-end

Working with Sage is not restricted to a local machine. The web-interface can be made public to other computers over the Intranet/Internet. One very successful example is http://demo.sagenb.org - this is the site behind the Google Chrome Web app for the Sage Notebook. After a bit more than a month of availability in the Chrome Web Store it had more than 2,000 users. Another example is the main Notebook site with more than 40,000 registered users. Sage not only wants to be a comprehensive software suite for mathematics but also wants to be easily accessible.

Consequently, we have to improve the inner parts of Sage to be able to scale for a much broader audience and satisfy online Notebook users from High School and University students doing their homework up to employees of engineering companies sharing their calculations with co-workers. These proposed enhancement projects could have a truly global impact and will certainly drive Sage’s further growth.

Description

Web-server, session management and Notebook storage.

This project addresses the needs for a better scaling Notebook server. There are several layers to consider, each of them could be a project:

  • The served HTML/JavaScript front-end needs to be changed in order to correctly interact with the modified back-end. This would also include writing testing-code to ensure functionality and stress-testing the scalability of the back-end.
  • The server back-end needs to be able to scale across several machines, handle session management, retrieving and storing the data for each user’s Notebook and knowing how to interact with the database. Additionally, Sage-workers need to be orchestrated to modify each user’s session after each calculation is done. This probably would also include coding low-level networking interactions via libraries like ZeroMQ.
  • There needs to be programming logic to handle the storage, the interactions with the database and address their scaling issues. Again, with testing code to ensure functionality and scalability.

Those are just some of the cornerstones that need to be done to make the Sage Notebook more scalable.

Interested applicants are expected to contact Jason Grout, who is currently organizing a larger project dedicated solely to this task. There has already been good progress on this project.

Links: Notebook design

Mentor

Jason Grout

backup: Dan Drake

Difficulty

Hard

Skills

  • Python, Cython, maybe C++
  • maybe NoSQL DB MongoDB
  • maybe low-level networking via ZeroMQ
  • probably Linux/Unix administration, Bash programming
  • knowledge about web-servers
  • experience with heterogeneous distributed machines in a cluster or multiprocessor machine

Symbolics

Summation and integration routines using hypergeometric and Meijer G function representations

Description

We propose improving the summation and integration algorithms in Sage by introducing lookup tables and the usage of hypergeometric and Meijer G forms. The commercial computer algebra systems [1] as well as open source alternatives like Sympy [2] are also employing this technique.

Because of the complexity of the formulas involved in the Meijer G case, we suggest starting with hypergeometric function representations. However, both cases share the same steps as can be seen from the two ISSAC papers [3, 4] describing the algorithms. After setting up lookup tables which contain instances of hypergeometric and Meijer G functions with known values in terms of special functions, a suitable chain of consecutive transformations will convert a generic representation to the instances found in the tables. These transformations can be forward- and backward shift operators, contiguity relations or, in the Meijer G case, various integration theorems.

During the last part of the project, with these mechanisms set in place, we can focus on rewriting classes of sums and integrals in terms of hypergeometric and Meijer G functions, respectively. While transforming

sums into hypergeometric notation is straightforward (one has to check

whether the ratio of consecutive terms is a rational function), for the

integration case we will need to use for instance the convolution theorem

as in the example [4].

[1] http://www-m3.ma.tum.de/bornemann/Numerikstreifzug/Chapter9/MeijerG.pdf

[2] http://docs.sympy.org/dev/modules/integrals/g-functions.html

[3] http://www.planetquantum.com/Papers/Issac96.pdf

[4] http://www.cybertester.com/data/issac97.pdf

Mentor

Flavia Stan, Burcin Erocal

Difficulty

Intermediate

Skills

  • Python
  • background in special functions helps

Pattern matching based symbolic integration

Description

The goal of this project is to port Rubi (http://www.apmaths.uwo.ca/~arich/) to Sage.

Rubi is a collection of Mathematica rewrite rules for symbolic integration. Having a Sage version of this would be a great boost to our (yet nonexistent) integration engine, as well as a good test of the pattern matching and substitution capabilities of our symbolics backend.

Sage uses the C++ library Pynac (http://pynac.org) to represent symbolic expressions and perform basic arithmetic and manipulation with them. Pynac (which a fork of GiNaC (http://www.ginac.de)) supports rewrite rules (http://www.ginac.de/tutorial/Pattern-matching-and-advanced-substitutions.html), but probably not to the extent required by Rubi. Depending on the complexity of the rules in Rubi, improvements to the pattern matching capabilities in Pynac might be necessary.

Mentor

Burcin Erocal, Flavia Stan, ??

Difficulty

Intermediate / Hard

Skills

  • Python / Cython
  • C++

Numeric class wrappers in Pynac

Description

This would be a continuation of Titus Nicolae’s GSoC 2012 project. The goal is to speed up the symbolic expression library used in Sage by avoiding unnecessary creation of Python objects.

Pynac (http://pynac.org) is the C++ library that is used as the backend for symbolic expressions in Sage. In Pynac, numeric types are wrappers around Python objects. This allows using arbitrary Sage types in symbolic expressions at the cost of considerable overhead for creating Python objects around simple numerical types (arbitrary precision real numbers backed by MPFR, integers backed by MPIR, etc.).

In 2012, Titus restructured the numeric class in Pynac (https://bitbucket.org/pynac/pynac/src/b7fe62bfb3a682773a7157d965deea2b85e3719c/ginac/numeric.h) to allow implementing wrappers for various numeric types in subclasses. However, he ran out of time before he could provide useful wrappers that could speed up Pynac.

The task, if you chose to accept it, is to write wrappers in Pynac for

  • MPFR
  • FLINT (only for fmpz_t)
  • etc.

Mentor

Burcin Erocal, ??

Difficulty

Hard

Skills

  • C++, Python, Cython

Advanced Symbolic Expression Manipulation

Description

When working with symbolic expressions, manipulating them in a flexible way is essential. The goal of this project is to extend Sage's functionality of handling substitutions and patterns. This includes the following enhancements:

  • wildcards with restrictions: Such a wildcard matches a symbolic expression only if it is of given type (e.g. an integer, a polynomial) or given "outer function" (e.g. a sum of something), or if it fulfils a given condition (e.g. if it is a prime, if it has no occurrence of a symbol y).
  • default values of wildcards: E.g. if w0 has default value 1, then the pattern w0*w1 matches also x (as 1*x).
  • sequences of wildcards: Patterns can have a variable number of wildcards. Then, for example, it is possible implement the usual manipulation rules for logarithms with one substitution.
  • delayed substitutions: The evaluation of the right-hand side of the rule is hold until after the substitution. E.g. one can then replace each x separately by a random integer.
  • regular expression rules: Building substitution rules and patterns out of regular expressions.

Mentor

Daniel Krenn

Difficulty

Intermediate

Skills

  • Python
  • regular expressions
  • helpful is to know about substitutions and patterns in other computer algebra systems (especially Mathematica)

Numerical Optimization

Description

Sage has general purpose classes to express and solve linear and mixed-linear optimization problems. The first aim of this project is to enhance  the features of those classes and add more convenience for the user. Additionally, new classes for quadratic and continuous non-linear optimization should be created.

On the back-end side, those classes interface with various specific solvers. This requires code to wrap their functionality or the necessary linking to certain libraries (e.g. which already provide Python-bindings to solvers, and may have been already present in Sage, such as cvxopt). The second part of this project aims to add more clue-code for additional solvers. In this, it overlaps with the next topic, concerning semidefinite programming solvers and interfaces for them.

Specific examples of functionality which need wrapping would include GLPK’s (and other LP solvers, whenever available) abilities to warm-start the simplex algorithm. One problem-specific solver that might be added is the Skeleton implementation of the double-description method, though this may require some restructuring to turn into a library (though perhaps not, as much of the functionality is isolated into one filed, ddm.hpp).

Mentor

Dmitrii Pasechnik (for some parts), John Perry (other parts)

Difficulty

Intermediate

Skills

  • Python, Cython, maybe C/C++
  • background in Optimization/Operations Research helps

Semidefinite Programming and sums of squares of real multivariate polynomials

Description

Improving the integration of semidefinite programming (and, potentially, other convex conic programming, e.g. 2nd order cone programming) solvers in Sage, creating an interface similar to what we already have for linear programming, hooking up more backends (currently, only cvxopt is integrated into Sage), with an aim to have a M*-free environment for polynomial sums of squares modelling, such as done e.g. by MATLAB-based YALMIP (http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.WhatIsYALMIP). Potentially, it is a large project, as one can go quite far with developing modeling tools, adding symmetry treatment, etc.

Mentor

Dima Pasechnik, Mehdi Ghasemi

Difficulty

Intermediate to hard

Skills

  • Python, Cython, maybe C/C++
  • background in Optimization/Operations Research helps

Libs: Underlying Libraries

Maxima/Numerical Mathematics

This project is not directly related to Sage, but Maxima is an important component!

Description

Currently Maxima is exclusively meant for Symbolic computation with support lacking good Numerical facilities. The existing BLAS/LAPACK modules are based upon f2cl-ed code in Common lisp, and hence performance is not portable (SBCL is probably 10x faster than CLisp).

The goal of this project would be enhance Maxima's numerical capabilities by integrating parts of the Foreign-function-interface in Matlisp. One would then be able to interface with the compiled versions of BLAS/LAPACK, ODEPACK and also just about any other C/Fortran libraries.

This would enhance Maxima's ability to do Numerical computation, and will open up new avenues like, implementing Automatic-Differentiation, to be pursued later.

Mentor

Raymond Toy

Difficulty

Hard

Skills

  • Common Lisp
  • Fortran/C would help

Point Counting on curves over finite fields (Sage/FLINT/Pari)

Description

This is related to elliptic curves:

Better point counting code on curves over finite fields.

Mentor

Jean-Pierre Flori

Difficulty

Hard

Skills

  • C/Cython
  • Algebraic Computations

Singular4 interface update

Description

Currently Sage cannot use the latest revision (aka spielwiese) of Singular due to significant changes in it (see Singular 3 vs Singular 4 and Spielwiese Singular - cutting Singular into pieces). It will be necessary to change the Singular package building inside of Sage (which is almost trivial due to Singular build system improvement) and adapt the current Cython code to the newest Singular API (wherever it relies on Singular). As an improvement one may also write Sage Fields or Rings wrappers around Singular coefficient domains, which were newly introduced as a separate structure in the new Singular.

Mentor

Burcin Erocal, Oleksandr Motsak

Difficulty

Intermediate to easy

Skills

  • Cython, a bit of C/C++/Python
  • a bit of background in algebra

Combinatorics

Matroid theory

Description

Matroids are combinatorial abstractions of a number of mathematical objects, including graphs and matrices. This project aims to improve and extend Sage’s support for matroids. Some examples, where the first needs very little matroid theory knowledge, the second group a little more, and the third group a lot.

  • Visualization of rank-3 and rank-4 matroids. Does not require much matroid theory, experience with vector graphics (e.g. splines) might be helpful.

  • Testing if an arbitrary matroid is binary, ternary, quaternary.
  • Automorphism group computation
  • Build a framework for collections of matroids

  • Efficient routines for testing connectivity, and extending matroids while preserving connectivity
  • More efficient minor testing, especially in binary and representable matroids.

Mentor

Stefan van Zwam

co-mentor: Rudi Pendavingh

Difficulty

Easy to medium (programming), easy to hard (mathematics)

Skills

  • Python
  • Background in combinatorics, linear algebra, ideally matroid theory.
  • For the first task: experience with vector graphics is helpful.

Knot theory

Description

Knots and Links are mathematical objects that represent how one or several ropes are tied in the space. Currently sage has no support for them. Some goals of this project would be:

  • Design the data structure for the internal data representation: study different approaches (3d curve, plane diagram, Gauss code, braid…) and methods to translate from one to the others,
  • Write the corresponding class,
  • Methods to plot the knot/link, and, if possible, a javascript editor like the one existing for graphs.
  • Compute the immediate invariants (like connected components), and, if time permits, some of the non-trivial invariants (fundamental group, polynomial invariants, Seifert form…)

The javascript editor could be a project on its own. So a student could propose either to work on the backend or the editor (or two students could work on both lines of work).

Mentor

Miguel Marco, Volker Braun

Difficulty

Easy to medium.

Skills

  • Python/Sage
  • Background in topology/knot theory.
  • For the editor, experience with graphical javascript libraries.


Student’s Proposal Template

We recommend you to join our sage-gsoc mailing list and introduce yourself and ask to help you for your submission.

Contact

We suggest you to introduce yourself and discuss your project idea in our mailing list. Only contact the possible mentors below if you have really specific questions!

Name

Topics

E-Mail

Harald Schilly

(Oversight)

general questions

harald+gsoc@schil.ly

Mentors

William Stein

SageMathCloud only

wstein+gsoc@gmail.com

Dan Drake

general projects

drake@kaist.edu
dr.dan.drake@gmail.com

Burcin Erocal

Symbolics, low-level Cython

burcin@erocal.org

Jason Grout

Notebook, Back-end

jason-sage@creativetrax.com

Martin Albrecht

low-level Cython, crypto stuff, linear algebra

martinralbrecht@googlemail.com

Volker Braun

Android, Python, low-level Cython

vbraun.name@gmail.com

Ivan Andrus

iOS/iPhone App

darthandrus@gmail.com

Alexander Dreyer

PolyBoRi

alexander.dreyer@itwm.fraunhofer.de

Raymond Toy

Maxima

toy.raymond@gmail.com

Dmitrii Pasechnik

Optimization, semidefinite programming

dimpase@gmail.com

Julien Puydt

Debian

julien.puydt@laposte.net

John Palmieri

Debian

palmieri@math.washington.edu

John Perry

Linear programming, commutative algebra, general

john.perry@usm.edu

Miguel Marco

Algebra, Topology, PyQt,

mmarco@unizar.es

Stefan van Zwam

Matroid theory

svanzwam@math.princeton.edu

Rudi Pendavingh

Matroid theory

rudi@win.tue.nl

Flavia Stan

Symbolics

flavia.stan@gmail.com

Oleksandr Motsak

Singular

motsak@mathematik.uni-kl.de