Differences between revisions 1 and 19 (spanning 18 versions)
Revision 1 as of 2015-02-01 10:04:47
Size: 583
Editor: vdelecroix
Comment:
Revision 19 as of 2015-02-11 16:49:42
Size: 8103
Editor: was
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
= Projects and ideas for GSoC 2015 = = Project ideas for GSoC 2015 =
Line 3: Line 3:
 * new notebook modes that force execution from top to bottom for reproducible computations
 * native GUI ([[https://code.google.com/p/spyderlib/|Spyder]]
 * Generic framework to choose between different implementations of algorithms. In Sage there are various places where we have several possibilities to execute a task (e.g. calling pari or gap). It would be interesting to have a way of choosing the default parameters by performing benchmarkings at build time. That would also allow to check coherency between various implementations.
== 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.

Feel free to introduce yourself and your project idea in our [[https://groups.google.com/forum/#!forum/sage-gsoc|mailing list]].

To get a better feeling how Sage works, please check out the [[http://sagemath.org/doc/developer/index.html|developer guide]].

<<TableOfContents()>>

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

== Native GUI ==

Adapt [[https://code.google.com/p/spyderlib/|Spyder]] to work with Sage.

See also [[https://groups.google.com/forum/#!topic/sage-devel/87Rlenvcfrs|this thread on sage-devel]].

|| Mentor || ... ||
|| Difficulty || ... ||
|| Skills || ... ||

== Generic Dispatcher ==

In Sage there are various places where we can choose between several algorithms or underlying softwares to solve a problem. In Sage, this is often related to the presence of the keyword ''algorithm'' or ''method'' in methods and 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 decided at build time. 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.

 * (draft) timeline:
  1. write a simple prototype of generic dispatcher
  2. identify Sage functions/methods that could benefit from the dispatcher and test it
  3. release a first candidate for the dispatcher
  4. Sage integration

|| Mentor || ... ||
|| Difficulty || ... ||
|| Skills || good knowledge of Python and notions of Cython and C ||

== Android App ==

== iOS App ==

== Computation of q-expansions of modular forms attached to elliptic curves at all cusps. ==

|| Mentor || William Stein ||
|| Difficulty || Extreme ||
|| Skills || Good knowledge of Python, Sage, and research-level knowledge of number theory ||

There is a well-known and easy to implement algorithm to compute the $q$-expansions at all cusps of $X_0(N)$ of the newform attached to an elliptic curve, when N is square-free,
but no such algorithm is known explicitly in general.
Being able to compute these $q$-expansions 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.

== Wrap Functionality from PARI, e.g., 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 graduate-level knowledge of abstract algebra and algebraic number theory ||

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.

Motivation: 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 in Sage, except in
the special case when the ring is a principal ideal domain.
Much research projects 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 complete 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.

== Multivariate Asymptotic Expressions ==

|| Mentor || Daniel Krenn (backup: Clemens Heuberger) ||
|| Difficulty || Hard ||
|| Skills || good knowledge of Python and Sage; graduate-level knowledge of mathematics is useful ||

An asymptotic expression typically contains exact terms and O-terms ([[https://en.wikipedia.org/wiki/Big_O_notation|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 [[http://trac.sagemath.org/ticket/17601|#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:
    
 1. '''Advanved 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.
 2. '''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.
 3. '''Interplay with existing Sage-Objects ("User-Interface"):''' 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 ==

T.B.A.

Project ideas for GSoC 2015

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.

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.

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

...

Native GUI

Adapt Spyder to work with Sage.

See also this thread on sage-devel.

Mentor

...

Difficulty

...

Skills

...

Generic Dispatcher

In Sage there are various places where we can choose between several algorithms or underlying softwares to solve a problem. In Sage, this is often related to the presence of the keyword algorithm or method in methods and 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 decided at build time. 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.

  • (draft) timeline:
    1. write a simple prototype of generic dispatcher
    2. identify Sage functions/methods that could benefit from the dispatcher and test it
    3. release a first candidate for the dispatcher
    4. Sage integration

Mentor

...

Difficulty

...

Skills

good knowledge of Python and notions of Cython and C

Android App

iOS App

Computation of q-expansions of modular forms attached to elliptic curves at all cusps.

Mentor

William Stein

Difficulty

Extreme

Skills

Good knowledge of Python, Sage, and research-level knowledge of number theory

There is a well-known and easy to implement algorithm to compute the q-expansions at all cusps of X_0(N) of the newform attached to an elliptic curve, when N is square-free, but no such algorithm is known explicitly in general. Being able to compute these q-expansions 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.

Wrap Functionality from PARI, e.g., 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 graduate-level knowledge of abstract algebra and algebraic number theory

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.

Motivation: 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 in Sage, except in the special case when the ring is a principal ideal domain. Much research projects 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 complete 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.

Multivariate Asymptotic Expressions

Mentor

Daniel Krenn (backup: Clemens Heuberger)

Difficulty

Hard

Skills

good knowledge of Python and Sage; graduate-level knowledge of mathematics is useful

An asymptotic expression typically contains exact terms and O-terms (wikipedia: Big O notation ), for example, n3 + 2*n2 + O(n). In the multivariate setting this notion is extended to several variables, e.g., n2*t + n*t2 + 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:

  1. Advanved 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.

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

  3. Interplay with existing Sage-Objects ("User-Interface"): 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

T.B.A.

GSoC/2015 (last edited 2015-03-16 20:44:44 by schilly)