Skip to content

GSoC 2012 Ideas

Jump to bottom Edit New page
asmeurer edited this page Apr 10, 2012 · 49 revisions

GSoC 2012 Project Ideas

This is the list of ideas for students wishing to apply for Google Summer of Code 2012. You can get inspired here, or come up with your own ideas. For more information on how to apply, see GSoC-2012-Application-Template.

Please always ask on our mailing list about these ideas to get the latest information about what is implemented and what exactly has to be done.

If you are a student interested in applying, please get in touch with us on our mailing list, so that we can help you with the application.

Ideas

Please add new ideas here. This is for inspiration, you can apply with something completely different if you like. The best project for you is one you are interested in, and are knowledgeable about. That way, you will be the most successful in your project and have the most fun doing it, while we will be the most confident in your commitment and your ability to complete it.

If you do want to suggest your own idea, please discuss it with us first, so we can determine if it's already been implemented, if it is enough work to constitute a Summer's worth of coding, if it's not too much work, and if it's within the scope of our project.

Even if you want to do an idea listed here, you should still contact us on our mailing list and discuss it with us. Also take a look at our application template.

The ideas are in no particular order. Checkout the current source or ask on the mailing list to see where things presently stand.

The second section contains more detailed projects that can be done.

  • Linear algebra

    • Rewrite the Matrices module to be more like the polys module, i.e., allow Matrix to use the polys ground types, and separate the internal data (sparse vs. dense) from the Matrix interface. The goal is to make the matrices in SymPy much faster and more modular than they are now. Note: this project has been partially completed by a past GSoC student
    • Implement a sparse matrix representation for Matrix, so we can efficiently manipulate large sparse matrices.** This is also related to the previous bullet point. Note: this project has been partially completed by a past GSoC student
    • There are some wacky grand ideas about the linear algebra module here

  • improve the integration algorithm, so that SymPy can integrate anything that can be integrated.

    • integration of functions on domains of maximum extent, etc.
    • Interesting idea: "SYMBOLIC COMPUTATION OF INTEGRALS BY RECURRENCE" by MICHAEL P. BARNETT

  • definite integration & integration on complex plane using residues. Note that we already have a strong algorithm that uses Meijer G-Functions implemented. So we need to first determine if such an algorithm would be worthwhile, or if it would be better to extend the current algorithm. Note that there are many integrals that are easy to compute using residues that cannot be computed by the current engine. Other possibilities: the ability to closed path integrals in the complex plane, which is not possible with the Meijer G algorithm.

  • Groebner bases and their applications in geometry, simplification and integration

    • improve Buchberger's algorithm and implement Faugere F4 (compare their speed) Note: This has already been implemented by a previous GSoC student. Please check with us to see the current state of Groebner bases in SymPy

  • improve polynomial algorithms (gcd, factorization) by allowing coefficients in algebraic extensions of the ground domain

  • implement efficient multivariate polynomials (arithmetics, gcd, factorization)

    • Implement a sparse representation for polynomials (see the dummy files in sympy/polys/ starting with "sparse" in the SymPy source code for a start to this project).
    • Figure out which representations to use where (sparse vs. dense).
    • implement efficient arithmetics (e.g. using geobuckets (Yan) or heaps (Monagan & Pearce))

  • improve SymPy's pattern matching abilities (efficiency and generality)

    • implement similarity measure between expression trees
    • expression complexity measures (e.g. Kolmogorov's complexity)
    • implement expressions signatures and heuristic equivalence testing
    • implement semantic matching (e.g. expression: cos(x), pattern: sin(a*x) + b)
      • e.g by using power series for this purpose (improve series speed)
    • Expand the capabilities of Wild() and match() to support regular expression-like quantifiers.

  • improve simplification and term rewriting algorithms

    • add (improve) verbatim and semi-verbatim modes (more control on expression rewriting)
    • implement more expression rewrite functions (to an exact form that user specifies). This may involve rewriting the rewrite framework to be more expressive. For example, should cos(x).rewrite(sin) return sqrt(1 - sin(x)**2) or sin(pi/2 - x)?
    • maybe put transformation rules in an external database (e.g. prolog), what about speed?
    • improve context (e.g. input) depended simplification steps in different algorithms
      • e.g. the integrator needs different sets of rules to return "better" output for different input
      • but there are more: recurrences, summations, solvers, polynomials with arbitrary coefficients
    • what about information carried by expressions?
      • what is simpler: chebyshevt(1, x) or x ?
      • what is simpler: chebyshevt(1000, x) or (...) ?
    • improve trigonometric simplification. See for example the paper by fu et. al.

  • implement symbolic (formal) logics and set theory

    • implement predicate (e.g. first-order), modal, temporal, description logics
    • implement multivalued logics; fuzzy and uncertain logics and variables
    • implement rewriting, minimization, normalization (e.g. Skolem) of expressions
    • implement set theory, cardinal numbers, relations etc.
    • This task is heavily tied to the assumptions system.

  • implement symbolic global optimization (value, argument) with/without constraints, use assumptions

  • continue work on objects with indices (tensors)

    • include the index simplification algorithms used in xAct and cadabra.

  • improve the plotting module Bear in mind that our plotting module is being overhauled at the moment (https://github.com/sympy/sympy/pull/673). A very approximate difficulty guesstimate is given:

    • medium-hard: Manipulate parameters in graphs (needs some kind of GUI (matplotlib provides widgets)) (IPython's notebook?)
    • medium: Animations (in matplotlib and IPython's notebook)
    • easy-medium: Write/fix/extend/port backends: matplotlib, google chart API link, pyglet, asciart...
    • easy: The old pyglet module does not work with the new module. Simplify the old module and write a backend for it.
    • medium-hard: Write an openGL backend for matplotlib (that should be discussed with the matplotlib team) (you may start with our pyglet module)
    • hard: Implement an intelligent routine that decides on the sampling rate so that sharp edges are better plotted. An "asymptote detector" would be nice.
    • easy: Make sure that all SymPy functions/expressions can be nicely plotted
    • easy: Plot:
      • implicit plots
      • objects from the geometry module
      • 2D and 3D linear operators (the effect of a matrix on a plane/3D space)
      • the effect of complex maps
      • vector fields
      • contours
    • medium: Work on lambdify and experimental_lambdify(from the new module) (merge them)
    • Fix related things/bugs in SymPy
    • Implement high level features, so that it works akin to Mathematica (http://reference.wolfram.com/mathematica/ref/Plot.html)
    • Improve textplot so that it can support all kinds of plots using ascii/unicode characters right in the terminal (with no dependencies).

  • generalized functions -- Dirac delta, P(1/x), etc... Convolution, Fourier and Laplace transforms

    • Fourier and Laplace transforms are implemented but we can not do many cases involving distributions Is this enough alone for a project though? -Aaron

  • vector calculus, differential fields, maybe Lie algebras & groups

  • parametric integrals asymptotic expansion (integral series)

  • Ordinary Differential Equations. Currently, SymPy only supports many basic types of differential equations, but there are plenty of methods that are not implemented. Maybe support for using Lie groups to help solve ODEs. See the ODE docs and the current source for information on what methods are currently implemented. Also, there is no support currently for solving systems of ODEs. You also might want to look at Manuel Bronstein's sumit.

    • Separation ansatz:

      • "A simple method to find out when an ordinary differential equation is separable" by José ́Ángel Cid

    • "Solving Differential Equations in Terms of Bessel Functions" by Ruben Debeerst.

    • Lie groups and symmetry related:

      • "Computer Algebra Solving of First Order ODEs Using Symmetry Methods" by E.S. Cheb-Terrab, L.G.S. Duarte and L.A.C.P. da Mota. There is a short (15 pages) and an updated (24 pages) version of this paper.
      • "Computer Algebra Solving of Second Order ODEs Using Symmetry Methods" by E.S. Cheb-Terrab, L.G.S. Duarte, L.A.C.P. da Mota
      • "Integrating factors for second order ODEs" by E.S. Cheb-Terrab and A.D. Roche
      • "Symmetries and First Order ODE Patterns" by E.S. Cheb-Terrab and A.D. Roche
      • "Abel ODEs: Equivalence and Integrable Classes" by E.S. Cheb-Terrab and A.D. Roche Note: Original version (12 pages): July 1999. Revised version (31 pages): January 2000
      • "First order ODEs, Symmetries and Linear Transformations" by E.S. Cheb-Terrab and T. Kolokolnikov
      • "Non-Liouvillian solutions for second order linear ODEs" by L. Chan, E.S. Cheb-Terrab
      • And probably some more by these authors ...

    • Solutions in terms of Series

      • "An algorithmic approach to exact power series solutions of second order linear homogeneous differential equations with polynomial coefficients" by Onur Kiymaz, Seref Mirasyedioglu
      • Google for "seriessolve axiom" ...

  • Integral equations. See for example the work started at http://code.google.com/p/sympy/issues/detail?id=2344. This could be part of a project on ODEs, for example.

  • partial differential equations. Currently, SymPy can't solve any PDEs, though a few tools related to separation of variables are implemented. The PDE module should be structured similarly to the ODE module (see the source code of sympy/solvers/ode.py).

  • increase image processing of PIL+SymPy functionality to match that of octave or matlab Is this within the scope of our project? -Aaron

  • improve SymPy's interoperatibility with other CAS software

    • implement general code parsing (Mathematica, Maxima, Axiom etc.) using e.g. pyparsing
    • implement Python + SymPy (structure + semantics) translation to your favorite CAS (other than SymPy :)

  • Symbolic quantum mechanics in SymPy. See below for details on projects related to this.

  • improve SymPy's Common Subexpression Elimination (CSE) abilities.

  • Singular analysis and test continuous.

    • find singularities of the function and classify them.
    • test the function whether it is continuous at some point or not. And in the interval. Note: Please discuss this idea with us if you are interested, as as it currently presented, it is somewhat vague.

Some Detailed Ideas (Projects)

SymPy Live and SymPy Gamma

WolframAlpha recently released a big update. You can now pay them and get a bunch of features. They also do things like save your search history.

Right now, our competition to WolframAlpha is SymPy Live (http://live.sympy.org/), but this works a little differently. SymPy Live is an exact duplicate of the console version of SymPy, running on the App Engine, but WolframAlpha tries to be smart about what the user wants. A while back, Ondřej whipped up a thing called SymPy Gamma (http://gamma.sympy.org/), which is a little closer to WolframAlpha.

The GSoC project would be to improve one or both of these things. SymPy Gamma could be improved a lot, by making it more intelligent about what output it produces for different inputs, making it parse expressions that aren't given in exact SymPy syntax, making it produce plots, perhaps replacing the notebook with an IPython notebook. SymPy Live could use a lot of the same features.

Many of these things should be implemented in SymPy and simply called from the web applications, for example, improved parsing for SymPy Gamma.

Mobile app for iOS and/or Andriod

Write a mobile app for Android and/or iOS. Other app developers have already demonstrated that it's possible to run SymPy natively on both of these operating systems. The project would be to write an app that gives a nice interface to it. One thing that could be done would be to make a soft keyboard that is conducive to math input (similar to what WolframAlpha has for their mobile apps). If there are issues with running SymPy on the device itself, we could make the app to just be a nice interface to SymPy Live/Gamma. Perhaps it would be best to start doing this, and then once you have a nice interface, to work on running SymPy itself.

An idea relating to soft keyboards: let people design their own keyboards, with each key showing some unicode text, and running Python code on the input. Then, create some site (on the App Engine for example) where we can let people submit their keyboards and review them, and download other people's keyboards.

NOTE: If you want to do this project, you MUST discuss it with us first, so that we can be sure that we have a mentor.

Equation editor

Some kind of equation editor. It could be considered part of a mobile app interface, part of a potential desktop app interface, or even a terminal curses interface. More users would be attracted to SymPy if it had some kind of 2d equation editing capabilities.

For example, a curses interface could be built on top of our current pretty-printing system. You would need to extend the printer to hold the printing information in such a way that it can be accessed by parts, then write a curses interface over it so that a user can select different parts of an equation and manipulate them.

Note: Please discuss this idea with us if you are interested, as as it currently presented, it is somewhat vague.

Step-by-step Expression Manipulation

Many times, people ask how they can tell what some functions are doing. For example, they want to know step by step how something like diff(x*sin(x**2), x) or integrate(x*sin(x**2), x) works. For the former, the best you can do is to follow the code; for the latter, the algorithm doesn't work at all like you would do it by hand, so there's really no way.

The idea is to implement a way to do this. It would be along the lines of WolframAlpha, where if you do certain operations (including the above two), there is a button "Show steps," which shows everything step by step.

Some questions:

  • What would be a good interface for this? For the most part, it would probably mean reimplementing the basic "by hand" algorithms, so that you can determine exactly what steps are used.

  • What should the output look like, so that it is both readable and usable (e.g., maybe some kind of annotated objects representing operations that you can literally apply to an expression to do those things)?

  • For those operations where what SymPy does is pretty close to what you'd do by hand (e.g., differentiation), what is a good way to avoid code duplication and make things extensible?

Note, not all of these questions are unanswered. It's probably a good idea to discuss this with us (as always) if you are interested, as we will probably have some ideas ourselves on how to answer these questions.

Improve Documentation

Your task will be to improve our documentation. For example, this project might involve doing these things:

Note that some of these things may require you to contribute some code to the IPython project. So if you are interested, you should also discuss things with them as well, and make sure that they are on board with things.

Also note that according to the official GSoC FAQ, pure documentation projects are not allowed. So this project must include a significant portion that involves coding.

Group theory

Implement a module to work with groups. You should take a look at the GAP library, as this is the canonical group theory computation system right now. Some things to think about:

  • How do you represent a group?
  • How do you represent the elements of a group?
  • Can we support both finite and infinite groups?
  • Can we support defining groups by generators?

Algorithms to think about implementing:

  • Computation of subgroups of various types (e.g., normal subgroups).
  • Computation of Galois groups for a given polynomial.

Also take a look at the Permutation class already implemented in SymPy.

Assumptions

The project is to completely remove our old assumptions system, replacing it with the new one. Once you complete this, you will try to improve the assumptions system however you can, for example, by adding new handlers and rules, or by extending the places the use the system (for example, solve()).

Note, you absolutely MUST discuss this one with us, as we need to agree on your plans. Some things were already discussed at Assumptions.

Risch algorithm for symbolic integration

  • The project is to continue where Aaron Meurer left off in his 2010 GSoC project, implementing the algorithm from Maunel Bronstein's book, Symbolic Integration I: Transcendental Functions. If you want to do this project, be sure to ask on the mailing list or our IRC channel to get the status of the current project.

  • Status The algorithm has already been partially implemented, but there is plenty of work remaining to do. Contact Aaron Meurer for more information.

  • Idea The Risch algorithm is a complete algorithm to integrate any elementary function. Given an elementary function, it will either produce an antiderivative, or prove that none exists. The algorithm described in Bronstein's book deals with transcendental functions (functions that do not have algebraic functions, so log(x) is transcendental, but sqrt(x) and sqrt(log(x)) are not).

  • Rating 3-4 (hard)

  • Prerequisites You should have at least a semester's worth of knowledge in abstract algebra. Knowing more, especially about differential algebra, will be beneficial, as you will be starting from the middle of a project. Take a look at the first chapter of Bronstein's book (you should be able to read it for free via Google Books) and see how much of that you already know. If you are unsure, discuss this with Aaron Meurer.

Series expansions

  • improve series expansions

  • formal power series

  • improve limits - make sure all basic limits work

    • limit of series

  • asymptotic series

  • Better support for Order term arithmetic (for example, expression of the order term of the series around a point that is not 0, like O((x - a)**3)).

  • All other problems, which are described in wiki page about series and current situation

  • Some references:

    • "Formal Power Series" by Dominik Gruntz and Wolfram Koepf
    • "A New Algorithm Computing for Asymptotic Series" by Dominik Gruntz
    • "Computing limits of Sequences" by Manuel Kauers
    • "Symbolic Asymptotics: Functions of Two Variables, Implicit Functions" by Bruno Savly and John Shackell
    • "Symbolic Asymptotics: Multiseries of Inverse Functions" by Bruno Savly and John Shackell

Cylindrical algebraic decomposition

  • Implement the Cylindrical algebraic decomposition algorithm

  • Use CAD to do quantifier elimination

  • Provide an interface for solving systems of polynomial inequalities

  • Some references:

    • Cylindrical Algebraic Decomposition http://mathworld.wolfram.com/CylindricalAlgebraicDecomposition.html
    • "Algorithms in Real Algebraic Geometry" http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html (usefull background ressource, but contains much more information)
    • "Cylindrical Algebraic Decomposition I: The Basic Algorithm" by Dennis S. Arnon, George E. Collins, Scot McCallum
    • "Computing Cylindrical Algebraic Decomposition via Triangular Decomposition" by Marc Moreno Maza, Changbo Chen, Bican Xia, Lu Yang
    • "Simple CAD Construction and its Applications" by Christopher W. Brown
    • "Improved Projection for Cylindrical Algebraic Decomposition" by Christopher W. Brown

Symbolic quantum mechanics (sympy.physics.quantum)

Please contact the sympy list (or Brian E. Granger, Ondřej Čertík) for questions about the physics related topics.

Abstract Dirac notation

  • Status: In sympy.physics.quantum we have code for symbolic Dirac notation. There is a lot there, but much more could be done on this.
  • Idea: Continue to improve this code by adding any number of features. The sky is the limit on this one. You could basically pick anything from quantum mechanics and implement it (a physical system, scattering theory, perturbation theory, etc.). A student interested in working on this should minimally have already taken an upper division (undergrad) quantum course and have a solid understanding of quantum mechanics. You would need to dig into the code and figure out what the next steps are.
  • Rating: 3 (moderate)

Implement All Known Analytical Solutions to Quantum Mechanical Systems

  • Status: Currently, we have Hydrogen Schroedinger/Dirac energies and nonrelativistic wavefunctions implemented in sympy.physics.hydrogen and 1-dimensional infinite square well wavefunctions in sympy.physics.quantum.piab. Before this can be done, we have to finish implementing basic position/momentum bases in sympy. There is still a ton of work let to do on that, so this project may be premature.
  • Idea: Implement all known analytical formulas for energies and wavefunctions for all QM systems that can be solved analytically (there are not that many, see http://en.wikipedia.org/wiki/List_of_quantum-mechanical_systems_with_analytical_solutions). In particular, 1d: finite/infinite well, oscillator, Coulombic field, 1d radial equation: Coulombic field, oscillator, finite/infinite well, Dirac wavefunctions, 2d: Coulombic field, oscillator, finite/infinite well, 3D: finite/infinite well. Then there are systems in cylindrical coordinates and other things. There will be a submodule in the quantum, that would contain as much analytical knowledge about these systems as possible, and one would retrieve the knowledge using physical parameters (e.g. (Z, n) for Hydrogen states, (n1, n2, n3) for 3D oscillator, and so on). When this is done, more things can be added --- there are many systems, whose energies can be obtained with a simple numerical procedure (like zeros of bessel functions), and systems whose solution is given as a series. The devil is in little details, and there is high value in having all these systems implemented and tested, that they are correct. Usage of this is for testing numerical codes, that they can reproduce analytical results, as well as when playing with and learning about QM. This project should be quite easy in terms of Python/SymPy programming, but it requires knowledge about QM.
  • Rating: 3 (moderate)

Spin states and operators for arbitrary spin

  • Status: Spin is a critical part of quantum mechanics. The spin algebra in quantum mechanics is rich and complex, even for spin 1/2. We would like to have a complete implementation of various spin states and operators for arbitrary spin s. Last summer, we had a project add in symbolic Clebsch-Gordan/Wigner-3nj coefficients and coupling/uncoupling algebra, but there is still more that can be done.
  • Idea: Continue work on sympy.physics.quantum.spin. This would include rotation operators, testing, Wigner-Eckart theorem, tensors, etc. While SymPy already has spherical harmonics, it would be nice to integrate those into the treatment of orbital angular momentum as well. Basically pick up Zare or Varshalovich and start implementing things. These ideas could also be expanded to SU(N) for N>2 as well (very interesting and non-trivial).
  • Rating: 3-4 (moderate-hard)

Position and momentum basis functions

  • Status: The position and momentum basis functions in quantum mechanics are somewhat pathological because the basis functions are not square integrable. In spite of this, these representations are immensely useful and are introduced to students early on. We would like to be able to handle position and momentum wavefunctions on arbitrary domains in 1D, 2D and 3D. NOTE: This was the topic of a GSoC project last year, and this description has not been updated to reflect the work that has been done and what could still be implemented. Anyone intersted in this topic should consult the list.
  • Idea: Implement full machinery for position and momentum wavefunctions, including modified Hilbert spaces, various coordinate systems, Dirac delta functions, basis transformations in 1D, 2D and 3D. This should use the base layer of quantum states and operators in sympy.physics.quantum. The test suite/code should include classic examples from quantum mechanics, such as particle in box, H atom, simple harmonic oscillator, scattering, etc. There are some real subtle issues in this work in how operators, states and general quantum expressions are represented in the position and momentum bases.
  • Rating: 3-4 (moderate-hard)

Symbolic quantum computing

  • Status: Quantum computing refers to the usage of quantum states, operators, time-evolution and measurement to perform non-trivial computations. Sympy already has a quite sophisticated symbolic quantum computing library and work continues on this.
  • Idea: Quantum error correction, density matrices, Solovay-Kitaev algorithm, gate+circuit simplification using genetic algorithms, etc.
  • Rating: 3-5 (hard)

Second quantization capabilities

  • Status: SymPy currently a solid module for second quantization implemented, but it needs to be updated to take advantage of the new stuff in sympy.physics.quantum. Interesting, but challenging work.
  • Idea: Work on sympy.physics.secondquant in the following areas:
    1. Refactor to use the new assumptions system.
    2. Refactor to use the stuff in sympy.physics.quantum.
    3. Implement Wick's theorem for Bosons, including the macroscopic population of the ground states.
    4. Density matrices.
    5. Time evolution.
    6. Various approximations, such as perturbation theory, Hartree-Fock, time-dependent Hartree-Fock, Hartree-Fock-Bogoliubov, etc.
    7. Implement new functions for simplifying products of second quantized operators in different ways (such as moving an annihilation operator R).
  • Rating: 5 (hard)

Polynomials module

Efficient Groebner bases and their applications

  • Status: Groebner bases computation is one of the most important tools in computer algebra, which can be used for computing multivariate polynomial LCM and GCD, solving systems of polynomial equations, symbolic integration, simplification of rational expressions, etc. Currently there is an efficient version of Buchberger algorithm implemented and of the F5B algorithm, along with naive multivariate polynomial arithmetics in monomial form. There is also the FGLM algorithm converting reduced Groebner bases of zero-dimensional ideals from one ordering to another.
  • Idea: Improve efficiency of Groebner basis algorithm by using better selection strategy (e.g. sugar method) and implement Faugere F4 algorithm and analyze which approach is better in what contexts. Implement the generic Groebner walk converting between Groebner basis of finite-dimensional ideals; there are efficient algorithms for it, by Tran (2000) and Fukuda et al. (2005). Apply Groebner bases in integration of rational and transcendental functions and simplification of rational expressions modulo a polynomial ideal (e.g. trigonometric functions). Note: There was a project last year relating to Groebner bases. Please take a look a the source and discuss things with us to see what remains to be done. Second Note: Some Groebner bases algorithms, in particular F4, require strong linear algebra. Thus, if you want to do that, you may have to first improve our matrices (see the ideas relating to this above).
  • Rating: 5 (very hard)

Multivariate polynomials and factorization

  • Status: Factorization of multivariate polynomials is an important tool in algebra systems, very useful by its own, also used in symbolic integration algorithms, simplification of expressions, partial fractions, etc. Currently multivariate factorization algorithm is based on Kronecker's method, which is impractical for real life problems. Undergo there is implementation of Wang's algorithm, the most widely used method for the task.
  • Idea: Start with implementing efficient multivariate polynomial arithmetics and GCD algorithm. You do this by improving existing code, which is based on recursive dense representation or implement new methods based on your research in the field. There are many interesting methods, like Yan's geobuckets or heap based algorithms (Monagan & Pearce). Having this, implement efficient GCD algorithm over integers, which is not a heuristic, e.g. Zippel's SPMOD, Musser's EZ-GCD, Wang's EEZ-GCD. Help with implementing Wang's EEZ factorization algorithm or implement your favorite method, e.g. Gao's partial differential equations approach. You can go further and extend all this to polynomials with coefficients in algebraic domains or implement efficient multivariate factorization over finite fields. Note: Some work on this may already be done. Take a look at sympy/polys/factortools.py in the SymPy source code.
  • Rating: 4-5 (quite hard)

Univariate polynomials over algebraic domains

  • Status: Currently SymPy features efficient univariate polynomial arithmetics, GCD and factorization over Galois fields and integers (rationals). This is, however, insufficient in solving real life problems, and has limited use for symbolic integration and simplification algorithms.
  • Idea: Choose a univariate polynomial representation in which elements of algebraic domains will be efficiently encoded. By algebraic domains we mean algebraic numbers and algebraic function fields. Having a good representation, implement efficient arithmetics and GCD algorithm. You should refer to work due to Monagan, Pearce, van Hoeij et. al. Having this, implement your favourite algorithm for factorization over discussed domains. This will require algorithms for computing minimal polynomials (this can be done by using LLL or Groebner bases). You can also go ahead and do all this in multivariate case.
  • Rating: 4-5 (quite hard)

Concrete module

Implement Karr algorithm, a decision procedure for symbolic summation

  • Status: SymPy currently features Gosper algorithm and some heuristics for computing sums of expressions. Special preference is for summations of hypergeometric type. It would be very convenient to support more classes of expressions, like (generalized) harmonic numbers etc.

  • Idea: Algorithm due to Karr is the most powerful tool in the field of symbolic summation, which you will implement in SymPy. There are strong similarities between this method and Risch algorithm for the integration problem. You will start with implementing the indefinite case and later can extend it to support definite summation (see work due to Schneider and Kauers). Possibly you will also need to work on solving difference equations.

  • Rating: 3-5 (very hard)

  • Some references:

    • "A=B" by Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger
    • "Symbolic Summation with Radical Expressions" by Manuel Kauers and Carsten Schneider
    • "An Implementation of Karr's Summation Algorithm in Mathematica" by Carsten Schneider
    • Manuel Kauers, webpage: http://www.risc.jku.at/home/mkauers
    • Carsten Schneider, webpage: http://www.risc.jku.at/people/cschneid
    • "Algorithmen für mehrfache Summen", by Torsten Sprenger

Linear Algebra

Tensor core

  • Status: SymPy has a number of disconnected projects related to Tensor/Linear algebra. These include Matrices, Sparse Matrices, Matrix Expressions, Indexed (for code generation), Geometric Algebra, and various projects in Physics.

  • Idea: Build a Tensor core that can serve as a base to connect these projects and others. This core should be able to seamlessly support a broad range of applications ranging from very abstract (vector spaces, geometry, multi-linear operators) to very numerical (explicit matrices, numpy integration, code generation). This project should include both a general Tensor Expression class and a general refactoring of the existing code-base. See Linear-Algebra-Vision. This project requires experience both in abstract linear algebra and in good code organization.

Parsing

  • Status: Currently SymPy has the ability to generate Python, C, and Fortran code from SymPy expressions.

  • Idea: It would be very interesting to go the other way. Can we parse Python, C, and Fortran code and produce SymPy expressions? This would allow SymPy to easily read in, alter, and write out computational code. This project would enable many other projects in the future. As a first step take a look at the current code generation and autowrap functionality. Ideally this project would create a general framework for parsers and then use this system to implement parsers for a few of the languages listed above. See the other parsing ideas on this page, as well as Parsing.

  • Rating: 3 (moderate)

Potential Mentors

If you are willing to mentor, please add yourself here. In parentheses, put your link-id from http://www.google-melange.com.

  • Aaron Meurer (asmeurer)
  • Andy R. Terrel (aterrel)
  • Sean Vig (flacjacket)
  • Matthew Rocklin (mrocklin)
  • Roberto Colistete Jr. (rcolistete), about "Mobile app for Android" using Python SL4A
  • Ondrej Certik (certik)
  • Ronan Lamy (rlamy)
  • Mateusz Paprocki (mattpap)
  • Christian Muise (haz)
  • Brian Granger (ellisonbg)
  • Vinzent Steinberg (vsteinberg)
  • Alexey Gudchenko (proga_goodok_ru), about "Series expansions", only if no one other willing with it.
  • Gilbert Gede (gilbertgede)
  • Dale Lukas Peterson (luke)
  • Tom Bachmann (ness)
  • Jason Moore (moorepants) - sympy.physics.mechanics
Add a custom footer
Add a custom sidebar
Clone this wiki locally