GSoC 2012
Sage Project Proposals

Introduction

Links

Notebook

Sage Notebook on Google App Engine and Amazon EC2 (etc.)

3D Graphics via three.js JavaScript library and WebGL

UI Enhancements

Datasheets

Additional Notebook Ideas

Back-end

C library interface to GAP

Greatly improve the pseudo-tty interfaces between Sage and the big Ma's: Mathematica, Maple, and Matlab.

Improving Startup Time

Numeral Systems

Lattices

Piecewise Functions

Symbolic Expressions

Mathematical Function Library

Optimization

SAT-Solving

Mobile Applications

Android & Android Tablets

Apple iOS/iPad

Regression Testing Framework

External Projects

Maxima/Numerical Mathematics

Singular/Dynamic modules for Singular

Singular/Thread safe memory allocator for Groebner basis computation

Singular/Fast non-commutative multiplication and related data structures

PolyBoRi/Binary decision diagrams for Boolean polynomial rings

NTL/Univariate polynomials and factorization library

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 Mercurial 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.

 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.

Notebook

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 demo.sagenb.org, 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.

Sage Notebook on Google App Engine and Amazon EC2 (etc.)

Description

This is one strategy for making http://sagenb.org scale to millions of users.  Currently http://sagenb.org gets hammered (there are 84168 users and it is running on a single computer in the basement of the math building!).  Rewriting the notebook for GAE+EC2 may make Sage available to a much wider range of people.  This is a top priority project for me (William Stein) for April-July, with some personal NSF funding (for my salary), but I could use help!

https://github.com/williamstein/simplesage_gae

Mentor

William Stein

Backup: Jason Grout

Difficulty

Intermediate

Skills

  • Python, Jinja2 templates
  • Javascript, jQuery, web application programming
  • Google App Engine, Amazon EC2 (or other cloud hosting)
  • very basic use of Sage
  • No advanced mathematics knowledge is needed.

3D Graphics via three.js JavaScript library and WebGL

Description

Currently, Sage by default uses JMOL (http://jmol.sourceforge.net/) to display 3d graphics.  This is a weak link for Sage, because Jmol is a very complicated Java applet, so on many platforms it crashes web browsers, won't run at all, is unstable, etc. For example, Jmol doesn't work at all on iPhones and iPads, and probably never will. Moreover, selecting objects and manipulating them is very hard, as is evidenced by nobody ever having succeeded in doing so for Sage, despite much demand.  The future of 3d for the web is WebGL, which has some support by modern browsers and hardware.  The three.js is a Javascript library that allows one to describe a 3d scene and interact with it purely from Javascript.  Moreover, the scene can be rendered in any browser that supports HTML5's canvas2d, which is essentially all modern browsers, though it will render more quickly when WebGL is available.  The goal of this project is to do a complete reimplementation of 3d rendering for Sage using three.js, which fully replicates all functionality that Jmol offered, so that three.js can instead be the default.

http://trac.sagemath.org/sage_trac/ticket/12402

Mentor

William Stein

Backup: Jason Grout

Difficulty

Intermediate

Skills

  • Javascript
  • Python
  • Foundations of 3d computer graphics
  • familiarity with 3d plotting in Sage.  
  • Calculus.
  • No advanced mathematics knowledge is needed.

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.

Mentor

Jason Grout

backup: Dan Drake, William Stein

Difficulty

Easy

Skills

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

Datasheets

Description

Currently, the ways to include data from other sources than the notebook  itself is limited to the capabilities of Python (e.g. reading a CSV file via Python’s CSV module)

The goal of this project is to make it easier to import and edit data in the form of simple spreadsheets and databases from within worksheets in the notebook.

  1. The project starts by evaluating existing options for integrating spreadsheets (e.g. http://grridjs.org)
  2. Suitable front-end and back-end code needs to be written for an initial basic integration.
  3. The second part consists of adding more features, like typed columns, database access, creating new Sage specific types (e.g. a class “DataFrame”, interoperable with R’s data.frame objects), integrating Google Doc’s Spreadsheets, …

Mentor

Jason Grout

backup: Mike Hansen, William Stein

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

  • additional widgets, like a 2D locator.
  • flexible layout of controls, and interacts within interacts
  • 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.

Mentor

Jason Grout, Tomas Boothby, Mike Hansen, Dan Drake, William Stein

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.

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 corner-stones 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, William Stein

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

Description

Easy Server Deployment.

Setting up a Sage Notebook server “right” is complicated. Although it is easy to start one instance for personal use, it is getting more complicated if it is set up for a classroom setting or as a worldwide server. This involves questions about security, sandboxing and scalability. In conjunction with other improvements, this project aims to make it easy to deploy a server for various applications. This includes the following tasks:

  • Documentation and testing
  • Step-by-Step guides
  • Ready-to-use instances on a virtual image
  • Screen-casts
  • Create ways to backup & restore worksheets
  • Improve user-management
  • Improve administrative interface
  • Solve security-related questions
  • Test and explain various web-server configurations

Mentor

Dan Drake

backup: Jason Grout, William Stein

Difficulty

Intermediate

Skills

  • Python
  • Linux/Unix administration, Bash programming
  • Knowledge about web-servers

C library interface to GAP

Description

GAP (http://www.gap-system.org/) is a free open source system for computational discrete algebra, with extensive support for computational group theory.  It has its own command line interpreter interface.  It would be extremely valuable if GAP also had a C library interface.  Volker Braun and William Stein have written a proof of concept C library interface to GAP, but it is not ready for production use, since it does not behave well when certain errors occur, is based on an old version of GAP, etc.  The goal of this project would be to create a high quality complete C library interface to GAP, based on the existing work done in this direction. This would drastically speed up certain parts of Sage that currently communicate with GAP via a pseudo-tty interace.  The C library interface would also be contributed back to the GAP project, making GAP (independent of Sage) easier to embed in C programs, which would make it much more generally useful than it currently is.  (Martin Albrecht did something similar to this for Singular, and contributed it back; it is one of the most important improvements to Singular in years.)

http://trac.sagemath.org/sage_trac/ticket/6391

Mentor

William Stein

Backup: Volker Braun, Martin Albrecht

Difficulty

Intermediate

Skills

  • Expert knowledge of the C programming language, and a little bit of assembler.
  • Medium knowledge of Python and Cython.
  • Some background in how interpreted programming languages are implemented.
  • No advanced mathematics knowledge is needed.

 

Greatly improve the pseudo-tty interfaces between Sage and the big Ma's: Mathematica, Maple, and Matlab.

Description

A unique feature of Sage is that it is able to communicate with essentially every other math software system out there, and some of that communication is fairly sophisticated, optimized, and debugged.  However, the interfaces between Sage and the most popular commercial  mathematics software systems -- Mathematica, Maple, and Matlab -- could all benefit from substantial additional work.  They are buggy on certain platforms, don't deal well in some cases with large outputs, don't draw plots well, etc.  Currently, the interfaces are all pseudo-tty based, but it may be possible in some cases to create alternative interfaces (with exactly the same API) that use proprietary socket-based protocols, e.g., MathLink (http://www.wolfram.com/solutions/mathlink/) for Mathematica.  

Now that the API of the Sage interfaces is very stable (after 7 years!), the goal of this project is to investigate and implement the best possible ways of implementing this API for each commercial math software system.

Mentor

William Stein

Backup: Mike Hansen

Difficulty

Easy

Skills

Very good knowledge of Python.

Improving Startup Time

Description

When people type "sage" to start Sage, it often takes a long time for Sage to startup.  This is incredibly annoying.  The main reason for this is that Python uses the stat system call to get basic information about files well over 50,000 times every single time Sage starts.  This information is expensive to compute, and almost never changes.  Thus it should be cached.  Volker Braun has written a proof of concept patch that does such caching, but work remains.  The goal of this project would be to finish that patch and get it included in Sage.  

Moreover, the project should go further and look at how to make that caching approach generic so it could be used by other projects outside Sage. This could have the potential impact of making "Python + scientific library" startup time better for millions of people.

Make it so Python cache's module import locations on startup, thus

greatly improving startup time for large Python modules.

http://trac.sagemath.org/sage_trac/ticket/11729

Mentor

William Stein

Backup: Volker Braun

Difficulty

Intermediate

Skills

Very good knowledge of Python and C

Numeral Systems

Description

The term "numeral systems" mean representing numbers (e.g. integers) by digits and a base. Standard numeral systems such as binary and decimal are well known, but there are lots of others. There is no framework available which allows to work with numeral systems. Implementing this is the first goal.

Sage uses a standard double-and-add algorithm to build multiples of a

point of an elliptic curve. There are numeral systems (including  windowing techniques), which can be used for fast scalar-multiplication on elliptic curves.

Goal number two is to use the different numeral systems to speed up the mentioned scalar-multiplication.

Mentor

Daniel Krenn
Backup: Manfred Madritsch

Difficulty

Intermediate

Skills

  • Python / Cython
  • basic mathematical knowledge of numeral systems
  • some background in algebraic number theory might be useful, but not necessary
  • a broad mathematical knowledge also helps

Lattices

Description

Goal is to implement a lattice class, that can be populated with lattice algorithms available. Those include algorithms for

  • finding a good base,
  • finding all vectors with a given upper length,
  • calculating the successive minima,
  • calculating lattice invariants,
  • calculating the Voronoi cell of the lattice, solving closest vector problems.

Lattices arise in many different areas of mathematics, so it would be good to have the existing algorithms together in one place and a framework to implement new algorithms.

Mentor

Daniel Krenn
Backup: Volker Ziegler, Daniel Smertnig

Difficulty

Intermediate

Skills

  • Python / Cython
  • basic mathematical knowledge of lattices
  • some background in algebraic structures and graphs helps

Piecewise Functions

Piecewise functions are essential in approximation theory, numerical analysis, and throughout the classroom. Within a computer algebra system, they are invaluable for translating written mathematics in an understandable way to one’s domain-specific language.

Description

A full list of ideas (a work in progress) is available at the PiecewiseSymbolic SEP (Sage Enhancement Proposal)

  • Symbolic piecewise support from Ginac and/or Maxima.
  • For historical reasons, the current piecewise framework does not integrate well with the rest of symbolics.
  • Very well defined - make piecewise functions behave like all other symbolic functions in Sage.
  • Piecewise functions should support all of the methods that symbolic functions support, with exceptions only where there is a good reason.
  • They should additionally support a set of methods that are applied individually to the constituent functions. For example, it is possible to define a piecewise function, composed of differentiable pieces, that is not differentiable.

Mentor

Karl-Dieter Crisman

Difficulty

Intermediate

Skills

  • Python
  • C++ (Ginac)
  • Lisp (Maxima)

Symbolic Expressions

Part of a sophisticated mathematical software system is a way to represent symbolic expressions and fast methods to manipulate them.

Description

Pynac/GiNaC is designed for symbolic computations. This project is about enhancing and optimizing this crucial and important part of Sage.

Pynac replaces the numeric coefficients in GiNaC with python objects. The implementation should be extended to use machine longs and doubles as well as the GMP and MPFR libraries for multi precision integers, rationals and floating point numbers. This would provide a significant speed boost since using these types directly instead of the Python wrappers available in Sage is more efficient.

The stubs to use other types as numeric objects are available in the code. The task involves writing the required interfaces to machine types, GMP and MPFR, as well as profiling typical operations to see where the bottlenecks are.

Mentor

Burcin Erocal

backup: William Stein

Difficulty

Intermediate

Skills

  • C++
  • Python, Cython

Mathematical Function Library

Description

Sage exposes mathematical functions to the user by wrapping lower-level libraries and algorithms. They occur in symbolic expressions and can be evaluated for given arguments. Some of them are not efficient, some of them could be improved and even some are not even exposed at all.

  • Learn and assess the current state of exposed functions, create benchmarks (guided by the mentor) to track improvements.
  • Enhance, add or replace functions in the already existing framework - suitable core libraries already exist.
  • Expand existing range of arguments to new ones, like vector and matrix types.
  • Extensive testing, speed&feature comparisons, ...

Mentor

Burcin Erocal

backup: Martin Albrecht

Difficulty

Intermediate

Skills

  • Python, Cython
  • C++

Misc maths related project ideas

Mentor: William Stein

Difficulty: Hard

Skills: Python, Cython; fairly advanced algebra.

 

Numerical Mathematics

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.

Mentor

---

backup: Martin Albrecht

Difficulty

Intermediate

Skills

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

SAT-Solving

Description

CryptoMiniSat is a SAT-solver whose efficiency is witnessed by the fact that it won the SAT Race 2010. This project is about integrating CryptoMiniSat into Sage as an optional package by writing a C++/Cython wrapper.

As a second step the project will use this interface to use CryptoMiniSat as a solver for various problem domains covered by Sage, such as polynomial system solving (cf. for example http://www.math.umd.edu/~bardg/bard_thesis.pdf and http://bitbucket.org/malb/algebraic_attacks/src/anf2cnf.py), the sage.sage.logic module and any other application the applicant and perhaps the Sage community can come up with.

Mentor

Martin Albrecht

backup: Burcin Erocal

Difficulty

Intermediate

Skills

  • C++
  • Python, Cython

M1RI

Description

M1RI, that's the code Tom wrote for dense linear algebra over GF(3), GF(5) andGF(7), i.e., small finite prime fields.  This implementation is a collection of Sage worksheets at the moment, i.e. a proof of concept. From that we already know that this approach is very fast. Turning this into a proper library would be a hug benefit to the community. It requires C skills but most of the linear algebra business has been solved before, so the mathematics required is not that much.

Mentor

Martin Albrecht

backup: Burcin Erocal

Difficulty

Intermediate

Skills

  • C/C++
  • Python, Cython

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

http://code.google.com/p/sage-android/

Description

http://code.google.com/p/sage-android/

No hard mathematics involved :-)

Mentor

Volker Braun

backup: Harald Schilly

Difficulty

Easy

Skills

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

Apple iOS/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

Skills

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

Regression Testing Framework

Create a tool to check if there are any speed regressions between Sage releases.

Description

Sage uses the standard Python doctest framework to check for correctness. With more than 85% and increasing coverage these tests uncover many potential issues in new contributions.

However, there is no equivalent mechanism to check if changes introduced to the Sage library cause speed regressions.

There are standard solutions such as Codespeed to store timing information and display comparisons between different versions.

This task involves:

  • writing benchmarks for certain functions in Sage
  • adapting Codespeed or a different solution for use within Sage

Mentor

Burcin Erocal

backup: William Stein

Difficulty

Intermediate

Skills

  • Python
  • XML, JSON, Database
  • (interactive) Web-application

External Projects

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

Singular/Dynamic modules for Singular

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

The Singular computer algebra system allows users to extend it two ways (without recompiling Singular):

Most recent feature additions to the Singular kernel and Singular interpreter are essentially extensions needed by very few projects. Dynamic Modules were developed in order to prevent these from bloating the core. Unfortunately the Singular approach to dynamic loading does not work under MS-Windows due to its limitations concerning DLL linking/loading. It is possible to solve this problem as described on edll.sourceforge.net.

The task is to evaluate the proposed approaches and implement a dynamic loading mechanism which would work on Windows as well as on Unix'es.

skills/prerequisites: C/C++, experience with development under Windows, understanding of libraries and dynamic loading

mentors: Oleksandr Motsak, Hans Schoenemann

contact:  libsingular-devel@googlegroups.com, sage-gsoc discussion group 

Singular/Thread safe memory allocator for Groebner basis computation

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

The Singular computer algebra system uses a specialized memory allocation library named omalloc to boost its performance. This library contains optimized code to allocate/deallocate blocks of memory with a predefined size (monomials) and discards pages containing these blocks at once, without the need to deallocate each separately. Unfortunately, omalloc is not thread safe and thread safe malloc libraries such as TCMalloc cannot match its performance. See this presentation for some more info.

The task here is to either add functionality to an existing memory allocation library to support this special use case or to improve omalloc so that it is thread safe.

skills/prerequisites: real good understanding of C/C++, memory allocation, debugging

mentors: Christian Eder, Hans Schoenemann

contact: libsingular-devel@googlegroups.com, sage-gsoc discussion group 

Singular/Fast non-commutative multiplication and related data structures

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

The Singular computer algebra system contains a subsystem named Plural which implements a class of non-commutative algebras, which appear often in various applied problems. Its basic (and principal) feature is the non-commutative multiplication. Unfortunately it is not always fast enough. The existing implementation can be improved in many ways, including for instance:

The Plural internals are partially described by V. Levandovskyy and O. Motsak.

The task here is to evaluate existing multiplication implementations and either to implement DFFT or to improve existing designs (possibly by redesigning them).

skills/prerequisites: C/C++ (only basic Math. knowledge)

mentors: Oleksandr Motsak, Hans Schoenemann

contact: libsingular-devel@googlegroups.com, sage-gsoc discussion group 

PolyBoRi/Binary decision diagrams for Boolean polynomial rings

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

PolyBoRi uses (zero-suppressed) binary decision diagrams (ZDDs) to store Boolean polynomial data. Up to now it uses CUDD which is is not especially tuned for this application area.

The task is to construct a pure C++ class for the diagrams as well as a class for a decision diagram manager. The latter should handle pool allocation of diagram nodes and operation caching.

skills/prerequisites: C and C++, basic understanding of binary decision diagrams

mentors: Alexander Dreyer, Burcin Erocal

contact: polybori-discuss@lists.sourceforge.net, sage-gsoc discussion group 

NTL/Univariate polynomials and factorization library

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

With its speed and wide ranging functionality, the Number Theory Library (NTL) written by Victor Shoup served as the standard for univariate polynomial algorithms for a long time, similar to the way GNU Multiprecision Library (GMP) defines the standard for integer and rational arithmetic now. NTL has not been maintained since 2009. In the meantime, FLINT surpassed its speed and set a new standard in this area. However, FLINT only provides a C interface and does not support all the functionality provided by NTL such as polynomials over  where .

Many mathematical software packages rely on NTL for univariate polynomials and factorization. With its speed and C focus, FLINT is unlikely to support all functionality of NTL any time soon. This project proposes to build a module in FLINT and implement the missing functionality from NTL.

The algorithms implemented in NTL can be found in these papers. (Understanding these is not a requirement for the student, that's what the mentor is for.  ):

skills/prerequisites: C/C++, basic understanding of univariate polynomial factorization algorithms (as described in Modern Computer Algebra )

mentors: Martin Lee, Fredrik Johansson

contact: libsingular-devel@googlegroups.com, sage-gsoc discussion group 

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

William Stein
(BDFL)

Notebook, Back-end

 

Mentors

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

Karl-Dieter Crisman

kcrisman@gmail.com

Martin Albrecht

low-level Cython, crypto stuff, linear algebra

martinralbrecht@googlemail.com

Thomas Boothby

Notebook, Back-end

tomas.boothby@gmail.com

Mike Hansen

Notebook, general projects

mhansen@gmail.com

Volker Braun

Android, Python, low-level Cython

vbraun.name@gmail.com

Daniel Krenn

Numeral Systems, Lattices

krenn@aon.at

Volker Ziegler

Lattices

ziegler@math.tugraz.at

Manfred Madritsch

Numeral Systems

madritsch@math.tugraz.at

Daniel Smertnig

Lattices

daniel.smertnig@uni-graz.at

Ivan Andrus

iOS/iPhone App

darthandrus@gmail.com

Oleksandr Motsak

Singular

Christian Eder

Singular

Hans Schoenemann

Singular

Alexander Dreyer

PolyBoRi

alexander.dreyer@itwm.fraunhofer.de

Raymond Toy

Maxima

toy.raymond@gmail.com

Martin Lee

NTL

Fredrik Johansson

NTL

fredrik.johansson@gmail.com