UCD ECS 193A B (CS Senior Design) Proposal

Jason K. Moore edited this page Dec 5, 2015 · 4 revisions
Clone this wiki locally

Fast Series-Expansion for SymPy and SymEngine

Aim

The goal is to significantly improve and expand the new polynomial-based series expansion modules in SymPy and SymEngine. A long term goal (currently optional) is to replace the default series module in SymPy with the new one.

Background

SymPy is a popular open source computer aided algebra system with over 400 contributors and thousands of users. It is part of the core SciPy stack and is included in many Scientific Python and Linux distributions. SymPy has core mathematics but also a variety of domain specific sub-packages.

SymEngine is a standalone fast C++ symbolic manipulation library. Optional thin wrappers allow usage of the library from other languages. For example, SymEngine interoperates with SymPy through the Python bindings.

One of the most widely used parts of SymPy is its series expansion module. However, its average execution time leaves much to be desired. The new series expansion module (called ring series as it leverages SymPy's efficient sparse polynomial module) is an attempt to write a much faster and efficient implementation. A number of elementary trigonometric and hyperbolic functions have already been implemented. Current execution times are extremely promising, with average speed-up of over 100 times for most expansions and it is especially optimized for operations on large series. For further details, have a look at this.

The next step is to port it to SymEngine so that it can be used in multiple languages through wrappers.

Approach

The new module makes use of a very efficient sparse data-structure that was implemented earlier for polynomials. Because of this, basic operations like addition and subtraction of series are very fast. The idea is to implement fast algorithms for expansion of all the important functions in SymPy and a wrapper series method that can accept an arbitrary expression as input. For reference, have a look at the code in ring_series.py.

Skills

Students should be familiar with or want to learn about Python, C++, SymPy, SymEngine and ring theory. Further, familiarity with or interest in exploring new data-structures and fast algorithms and analysing their complexity is expected.

Deliverables

The students will be expected to deliver the source code in the form of atomic Github pull requests to the main SymPy/SymEngine website repository where each contribution includes unit tests and accompanying documentation. The code will be reviewed by the SymPy and SymEngine software developers.

Expected Outcome

Unit tested and documented ring series modules for SymPy and SymEngine with an assortment of examples in the documentation.