19777
Comment:

19154

Deletions are marked like this.  Additions are marked like this. 
Line 48:  Line 48: 
In Sage there are many places where we can choose between several algorithms or underlying softwares to solve a problem. This is often related to the presence of the keyword ''algorithm'' or ''method'' in functions. The aim of this task is to build a generic dispatcher that would choose depending on the parameters the fastest solution available. The solution must be very light and not affect performance. The dispatch threshold must be static and computed through a dedicated command (like ''sage recomputethresholds''). This generic dispatcher could also be used to check coherency between the various implementations.   Mentor  Vincent Delecroix   Difficulty  Medium to very Hard   Skills  good knowledge of Python and notions of Cython and C  In Sage there are many places where we can choose between several algorithms or underlying softwares to solve a problem. This is often related to the presence of the keyword ''algorithm'' or ''method'' in functions. The aim of this task is to build a generic dispatcher that would choose depending on the parameters the fastest solution available. The solution must be very light and not affect performance. The dispatch threshold must be static and computed through a dedicated command (like ''sage recomputethresholds''). We could also have default threshold that depend on architectures. This generic dispatcher could also be used to check coherency between the various implementations. 
Line 52:  Line 56: 
* (draft) timeline:  Steps: 
Line 56:  Line 61: 
4. more Sage functions coverage  Mentor  Vincent Delecroix   Difficulty  Medium to very Hard   Skills  good knowledge of Python and notions of Cython and C  William Stein: This makes me pretty nervous: "The dispatch threshold must be static and decided at build time." This is basically what ATLAS (automatically tuned linera algebra software does). There's so many ways in which this can go wrong, and it can be extremely time consuming figure out what good thresholds are. To do this project, the student could (1) identify numerous specific cases of code in the Sage library that have thresholds hardcoded (or otherwise) right now, then (2) try to abstract out something that would allow implementation of all those cases. One major difficulty is that the mathematics in (1) could be very deep and difficult for any one human to understand, so posting to mailing lists for feedback is important. Vincent Delecroix: I adapted the description according to your remarks. Thanks! 
4. more Sage functions coverage (this can be hard since some threshold might be extremly complicated to determine. In order to do that you are advised to ask for help on the mailinglist) 
GSoC 2015
Introduction
Google Summer of Code is a highly enjoyable and rewarding way to spend a summer.
Sage is a GPL opensource 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 opensource software tools and libraries and ties them together via Python. Python is also the primary interface language for the user and its objectoriented 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 website 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.
Feel free to introduce yourself and your project idea in our mailing list.
To get a better feeling how Sage works, please check out the developer guide.
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!
Shoot Simon Spicer ([email protected]) an email if you want more details from a recent GSoC student on the actual logistics of doing a GSoC project.
Contents
 GSoC 2015

Project Ideas
 Generic Dispatcher
 Android App
 iOS App
 Computation of qexpansions of modular forms attached to elliptic curves at all cusps.
 Hermite Normal Forms for modules over the ring of integers of number fields.
 Multivariate Asymptotic Expressions
 SageMathCloud
 Extending Game Theory in Sage
 Add support for systems of rational inequalities
 Extending Matroid Theory functionality
 Projects with no mentor
Application Template
Please use this application template, in particular answer the questions thoroughly enough to convince us to pick you!
Personal:
 Name
 Contact Information (email, instant messaging, …)
 Location/Timezone
 University
Background:
 What are your technical skills, education, experience, etc. Especially make sure to explain with what level of mathematics you are comfortable with and on what level you would like to program.
 Who are you? What makes you the best person to work on this particular project? Special motivation?
 What platform and operatingsystem are you using on your computer? (Sage development is done best on Linux and OSX)
 Are you or have you been engaged in other opensource projects?
 Do you code on your own pet projects?
 Are you a Sage user, how long do you know Sage?
Project:
 Title, Project Synopsis: a short description and summary of its aim and scope.
 What is your personal involvement or relationship with your proposed project?
 Details: describe all the details and explain modules or parts of your whole project. Break down the whole project into individual tasks  as good as possible  and describe deliverable and quantifiable results for each of them. It also helps if you have already discussed this with a possible mentor.
 Schedule: A timetable, including special circumstances like exams or holidays, for the individual tasks.
 Risk Management: Try to anticipate potential problems and explain, how to mitigate them. Propose alternative scenarios, if a particular milestone isn't reached, to still successfully complete the project.
Project Ideas
Generic Dispatcher
Mentor 
Vincent Delecroix 
Difficulty 
Medium to very Hard 
Skills 
good knowledge of Python and notions of Cython and C 
In Sage there are many places where we can choose between several algorithms or underlying softwares to solve a problem. This is often related to the presence of the keyword algorithm or method in functions. The aim of this task is to build a generic dispatcher that would choose depending on the parameters the fastest solution available. The solution must be very light and not affect performance. The dispatch threshold must be static and computed through a dedicated command (like sage recomputethresholds). We could also have default threshold that depend on architectures. This generic dispatcher could also be used to check coherency between the various implementations.
Note that it is different from what is called multimethods where the dispatch depends only on the input type. Here we consider a dispatcher that might also depend on the input values.
Steps:
 identify some simple Sage functions/methods that could benefit from the dispatcher
 write a simple prototype of generic dispatcher adapted to 1 and intensively test it
 release a first candidate for the dispatcher
 more Sage functions coverage (this can be hard since some threshold might be extremly complicated to determine. In order to do that you are advised to ask for help on the mailinglist)
Android App
iOS App
Computation of qexpansions of modular forms attached to elliptic curves at all cusps.
Mentor 
William Stein 
Difficulty 
Extreme 
Skills 
Good knowledge of Python, Sage, and researchlevel knowledge of number theory 
There is a wellknown and easy to implement algorithm to compute the qexpansions at all cusps of X_0(N) of the newform attached to an elliptic curve, when N is squarefree, but no such algorithm is known explicitly in general. Being able to compute these qexpansions at all cusps in general has many very interesting applications, including determining the ramification of modular parametrizations of elliptic curves at cusps, and numerical computation of constants in the functional equation of the twists of a newform. A graduate student, Hao Chen (of University of Washington), has new ideas to carry out these computations. The project is to fully implement his algorithm, get it included in Sage, and also implement some of the interesting applications of the algorithm.
Hermite Normal Forms for modules over the ring of integers of number fields.
Mentor 
William Stein 
Difficulty 
Extreme 
Skills 
Good knowledge of Python, Sage, and graduatelevel knowledge of abstract algebra and algebraic number theory 
A Hermite Normal Form (HNF) algorithm for modules over general Dedekind domains was introduced in Cohen's book 'Advanced topics in computational number theory'. The algorithm is currently not implemented directly in Sage,
 except in the special case when the ring is a principal ideal domain.
Much research in computational number theory would benefit from an efficient implementation of this (very tricky and subtle) algorithm. For example, this algorithm is needed to get anywhere with quaternion algebras and associated Brandt modules over totally real fields. As a GSoC project, it would be reasonable to at least expose this HNF algorithm (from PARI) over the ring of integers of number fields, then use it to implement basic functionality for working with finitely generated modules over Dedekind domains.
Pari has much new interesting functionality, e.g., for computing Hermite normal forms among other things. This project would involve making that functionality usable in Sage, with one application being to computation with modules over the ring of integers of a number field.
NOTE: Whether to use the PARI functionality or write something new will depend on the student, the quality of what is in PARI, etc. We did some tests of this functionality from PARI last summer at the Quaternion Algebras sage days and the results were mixed. Magma has this functionality, and speed/quality comparisons with its implementation would be critical to keep in mind.
Multivariate Asymptotic Expressions
Mentor 
Daniel Krenn; comentor: Clemens Heuberger 
Difficulty 
Hard 
Skills 
good knowledge of Python and Sage; graduatelevel knowledge of mathematics is useful 
An asymptotic expression typically contains exact terms and Oterms (wikipedia: Big O notation ), for example, n^{3} + 2*n^{2} + O(n). In the multivariate setting this notion is extended to several variables, e.g., n^{2}*t + n*t^{2} + O(n) + O(t). The basic framework for this asymptotic ring is currently under development (see trac meta ticket #17601). The main aim of this summer of code project is to extend its functionality to fully support the multivariate case. This includes the following parts:
Advanced operations with asymptotic expressions: As a first step in this project operations like exponentiation, taking powers and logarithms should be implemented. This happens on a high level using the existing addition and multiplication, and thereby, get to know the existing framework.
Implement mutlivariate growth groups: This would explore the full potential of the existing framework, which is already prepared for partially ordered growth groups. The conrete growth groups, in the case of lexicographic orders (e.g., terms with n*log(n)) as well as in the case of dependent variables (such as t <= n^{(1/2)}), have to be written.
Interplay with existing SageObjects ("UserInterface"): In order to comfortably create asymptotic expressions, a conversion from, for example (but not limited to), Sage's symbolic ring to the asymptotic ring should be established.
SageMathCloud
Create a personal GPLlicensed version of SageMathCloud (https://cloud.sagemath.com) that is included with every copy of Sage. The current source code of SageMathCloud is here: https://github.com/sagemath/cloud SageMathCloud (SMC) consists of:
 BROWSER: a single page application that runs in the web browser, which implements sage worksheets, code editing, latex editing, todo lists, markdown editing, a terminal, etc.
 HTML/PROXY/SSL: a static html server (nginx), a proxy server (haproxy), and ssl encryption (stunnel)
 DATABASE: a big distributed Cassandra database
 COMPUTE: compute virtual machines that run user code (Sage worksheets, IPthon notebooks, terminal sessions)
 HUB: a node.js process the does authentication, talks with the database, and generally coordinates traffic between web browsers and compute virtual machines.
The point of this project would be to make a singleproject version of SMC for personal use that involves only the BROWSER and COMPUTE components listed above. The compute component would also serve html and have a small sqlite database to store images and other configuration information. The filesystem and files would just be the user's current account. In particular, this would involve completely cutting the HUB/PROXY/SSL and CASSANDRA components out of the picture. The benefit is that the sagews version of worksheets would be easily editable offline by anybody (not true now) and there would be a new offline latex editing tool.
Mentor 
William Stein (and Harald Schilly) 
Difficulty 
MediumHard 
Skills 
CoffeeScript, Node.js, Python, SQLite; little mathematical knowledge is needed 
Other
There are many issues at https://github.com/sagemath/cloud/issues and other possible SMC projects. Let use know ([email protected]) if you're interested in something else involving SMC. I like the above for a Sage GSoC project, since it would result in a code being included in Sage.
For example, a good project could be a dynamic formula editor to manipulate symbolic expressions  very likely based on http://mathquill.com/ (as it is used at desmos.com)
Another project idea is to create a UI frontend for entering and editing structured tabular data with realtime synchronization.
Extending Game Theory in Sage
Mentor 
Vincent Knight (additional help KarlDieter Crisman) 
Difficulty 
Medium 
Skills 
Good knowledge of Python, Sage, and some knowledge of Game Theory would be advantageous 
Recent contributions to Sage have developed Game Theoretic tools. The main aim of this summer of code project is to extend this functionality. This includes the following potential directions:
Further integration with gambit: One implementation of the solution of normal form games is done through the gambit python api. This currently implements a single two player algorithm, work would be undertaken to expand this to the various algorithms available in gambit (multiple players etc...).
Tests for degeneracy of normal form games: A degenerate game is a game where the Nash equilibria does not correspond to an isolated point of the strategy space. This work would involve researching, designing annd implementing algorithms to tests for degeneracy of normal form games.
Designing of educational materials making use of SageMathCloud: Having Sage and solution concepts for games readily available to all in SageMathCloud make this an excellent teaching tool. A variety of teaching materials could be designed making use of screencasts, interacts and other web technologies. Furthermore, this could also involve the enhancement of the game theoretic library in Sage to include example games.
Add support for systems of rational inequalities
Enable Sage users to solve systems of rational inequalities like
abs(2*x3)/(3*x)>(x+1)/(x2) and (4*x+5)^2/(x3)<x+3.
For this, the way to go seems to package QEPCAD in such a quality that it can become an "optional package". One could then use:
sage: maxima_calculus("domain: real") #14229 sage: dnf1 = solve(abs(2*x3)/(3*x)>(x+1)/(x2),x) sage: qf1 = apply(qepcad_formula.or_, map(qepcad_formula.and_, dnf1)) sage: dnf2 = solve((4*x+5)^2/(x3)<x+3,x) sage: qf2 = apply(qepcad_formula.or_, map(qepcad_formula.and_, dnf2)) sage: qepcad(qepcad_formula.and_(qf1, qf2), vars='(x)')
to get the solution "0 < x < 2".
A further topic would be to introduce shorter syntax (infix boolean operators, inequality chains) for the above, to do something like the following:
sage: dnf1 _and_ dnf2 0 < x < 2
Note that 0 < x < 2 would not be a string here, but a Sage object. Also, dnf1 and dnf2 should be in the new syntax, instead of the current "list of lists" DNF.
Finally, also the something like the following should work:
sage: solve(0 < x < 2 _or_ x > 1, x) x > 0
Motivation: Rational inequalities are a topic of our institute's 1st year classes, and Mathematica is currently used there.
(I cannot really offer to be a mentor here, because I did not do any Sage development yet jondo)
Mentor 
... 
Difficulty 
... 
Skills 
C programming, Sage packaging, cross platform testing 
Extending Matroid Theory functionality
Mentor 
Stefan van Zwam; comentor: Michael Welsh 
Difficulty 
Medium 
Skills 
Good knowledge of Python, Sage, and some knowledge of Matroid Theory would be advantageous 
The basic code for dealing with matroids in Sage is fairly mature, but many enhancements are still desirable. Among those:
Connectivity algorithms: Implement efficient tests for the connectivity of a matroid. In particular the (r(M))^2 E algorithm for 3connectivity by Bixby and Cunningham (1979), and generic algorithms based on either Tutte's Linking Theorem or Matroid Intersection.
An improved catalog: This could be a warmup task for the first two weeks. Enhance the matroid catalog with some options, such as adding options to prescribe the field of a representation.
Automorphisms and certificates: Many matroid test methods are currently True/False. In many cases, it makes sense to return a certificate of the claim, such as an isomorphism in case two matroids are determined to be isomorphic.
Representability tests: Test if a given abstract matroid is binary, ternary, quaternary, regular, ...
Framework for classes of representable matroids: This can take two directions. First, a parentlike class such as BinaryMatroids, which symbolically represents all binary matroids, and has methods for extending, membership tests, etc. Second, a finite collection of matroids (such as all binary matroids without a P7minor up to 9 elements), where each matroid stores information about its allowed extensions and coextensions for faster generation and membership testing.
Projects with no mentor
If you are a candidate extremly motivated by one of the topic below, send an email to mailing list.
Notebook mode with execution from top to bottom
In the current notebook (both Sage notebook and IPython notebook) the cells can be executed in any order. From a teaching point of view this is terrible and from a scientific point of view this leads to highly non reproducible computations.
The purpose of this task is to have a new mode for the IPython notebook that would force computations from top to bottom. If a cell is executed, then the state in which it is executed must be the one you obtain by executing all the cells above it. In order to make it work, one needs to save the Python state after each cell.
Note: This is not completely Sage oriented... (see with IPython people)
Mentor 
... 
Difficulty 
... 
Skills 
... 
William Stein: I don't get the point of this as a real project. Who proposed this? For example, regarding "one needs to save the Python state after each cell", I don't think that is even possible. Another relevant remark is that right now IPython records the order in which cells are evaluated with numbers.
Vincent Delecroix: This is my proposition. It pops out during pari days that a notebook that acts like console should be available. I will not be so sure that it is not feasible. You can basically deepcopy globals() after each cell. Such top to bottom mode is what is implemented in coqide (for the theorem prover coq).
Native GUI
Adapt Spyder to work with Sage.
See also this thread on sagedevel.
Mentor 
... 
Difficulty 
... 
Skills 
... 