Skip to content

GSOC 2016 Rehas Mehar Kaur Sachdeva: Series Expansion

Jump to bottom Edit New page
Rehas Sachdeva edited this page Mar 25, 2016 · 7 revisions

Pdf version at https://drive.google.com/file/d/0BzcgXVpGzt63VzRQbi1wLWt0QjA/view?usp=sharing

SymPy’s series module is currently capable of representing and manipulating series, sequences, formal power series and calculating limits of functions, series and sequences along with order term representation. There is also implementation of rs_series which makes use of efficient representation and operations of sparse polynomials for blazingly fast multivariate series manipulations. This project will focus on extending these functionalities in the following ways:

  • Work on series related issues reported.

  • Extend rs_series for all functions and make it the default series expansion of SymPy.

  • Improve formal power series, make it faster, correct known bugs, add more operations and extend support for multivariate series.

  • Improve limits to correct known bugs and extend support for limits of formal power series.

  • Add better support for order-term arithmetic.

  • Implement asymptotic series.

About Me

I am currently pursuing Bachelor of Technology in Computer Science and Engineering (Sophomore year). I have always been driven by the curiosity about the possibilities of science and technology and have had this drive in me to solve problems and challenges. From making world high scores in my favorite computer games, to solving tough mathematical puzzles on my own in my early teens, to now being exposed to interesting research problems in college, to learning new algorithms, technologies and programming my heart out at competitive coding platforms all interests me. But mathematical problem-solving brings a wave of exhilaration I can’t explain. The powers of SymPy fascinate me and I really want to learn more and add more to the list.

Programming Background

Languages and technologies: I have been programming for the last two years, and have experience of 1 year of programming in python. I also code well in C, C++ and know Matlab, Web2py, OpenGL 3, HTML, CSS and JS. I use git for version control.

Platform and Editors: I work on Ubuntu 15.10 with vim as my primary editor. I like vim because it is fast, versatile, neat and has great command-set and plugin support. I also use Sublime Text 3 because of its ease of use.

Projects

Ultimate-Tic-Tac-Toe-Bot - A weighted features heuristic based AI with search depth 4-7 for a variation of the original Ultimate Tic Tac Toe game, developed in Python.

- A Web2py Project for the healthcare centre (Aarogya) at IIIT Hyderabad.

- A game written in Python based on the original Donkey Kong game.

- Plots graph between restaurants, costs and ratings for a zomato.com page.

- Simple Application Level File Sharing Protocol with support for download of files, evaluating checksum and indexed searching.

Other cool games like Angy-Buhdz, Valar-Morghulis-Game are shared on my Github page. I have also worked with Threads, locks and semaphores, C-Shell (with job control, piping etc), image and audio signal processing in matlab, concurrent merge sort for (>4GB) files, perf testing, code review tools for python, UML design tools, Ruby and Rails etc.

Experience with Python {#experience-with-python .unnumbered}

I started programming in Python a year ago and I still get amazed by how beautiful a language it is (simply by its look and feel). I prefer Python over C, C++ because of its automatic memory management, ease of programming with OOP concepts, ease of shallow copy, the fact that it’s easily extensible with and embeddable in C, C++. Also its huge Library support is amazing. The most advanced libraries I have used are SymPy, NumPy, Matplotlib and Pygame.

Experience with SymPy {#experience-with-sympy .unnumbered}

I started using SymPy in February-end this year and to be honest, I still have a long way to go to have explored it enough. I love the fact that it is effortless in the sense that we can just write like we do on paper. The fact that a complicated differential equation or a complex integral can be solved just like that:

  >>> dsolve(f(x).diff(x, 2) + 2*f(x).diff(x) - sin(x), f(x))

$$f{\left (x \right )} = C_{1} + C_{2} e^{- 2 x} - \frac{1}{5} \sin{\left (x \right )} - \frac{2}{5} \cos{\left (x \right )}$$

is amazing. It essentially liberates one to to focus on the application of the formulation and not worry about solving it.

Contributions {#contributions .unnumbered}

Merged PR’s {#merged-prs .unnumbered}

  • 10883 - Made limit work with binomial expression.

Issues Reported {#issues-reported .unnumbered}

  • 10901 - Limit of expression with binomial and sin doesn’t evaluate.

The Project

In this section I will detail my vision for what all I want to achieve in this project. I expect this structure to be considerably enhanced under the guidance of my mentor.

Series

SymPy has rs_series which makes use of the efficient representation and operations of sparse polynomials for very fast multivariate series manipulations. This project would extend it to work for all functions. Eventually the goal is to make it the default series expansion in SymPy. Some things to be implemented are:

  • |rsseriesinversion| can be extended to support cases with constant term in series.

  • |rsseriesreversion| can be extended to support puiseux series.

  • Univariate series expansion of the nth root can be extended to support cases with constant term in series.

  • Implementation of |rslog| is incomplete. Extend it for cases with no constant term.

  • Series expansion of principal branch of Lambert W function is not implemented for case where polynomials have constant term in series variables. Similarly for arcsine.

  • Hadamard exponentiation can be extended for non-rational domains.

  • Efficiency can be improved by using |paralleldictfromexpr| and not sring

Improvements to formal power series

Implementation of Formal Power Series (series.formal) is more or less complete according to this paper @fps.

  • The project will work on making the module faster.

  • There are currently some XFAIL tests in |testformal.py|. Particularly errors are common with asech(x), truncate and sigma representations of infinte series. Example:

      >>> f = asech(x)
  >>> fps(f, x)

    $${\lim_{x \to 0^+}\left(\frac{x^{2}}{4} + \log{\left (x \right )} + \operatorname{asech}{\left (x \right )}\right) - \log{\left (x \right )} - \frac{x^{2}}{4} - \frac{3 x^{4}}{64} + \mathcal{O}\left(x^{6}\right)}$$

    As we can see the unevaluated limit which should come out to be log(2) is the error. This error also results in limit calculations which will be discussed in next section. Other errors in this module are also sources of errors in calculation of limits.

  • Implementation of Multivariate formal power series. This will look something like this:

     >>> fps(sin(x + y), {x, 0, 3}, {y, 0, 3})
  ( (y-y**3/6 + O[y]**4) + (1-y**2/2 + O[y]**4)*x
  + (-y/2 + y**3/12 + O[y]**4)*x**2 + (-1/6 + y**2/12 +
    O[y]**4 ) + O[x]**4)

    Example taken from Wolfram. Currently formal power series is calculated by computing a formula for the coefficients. For the multivariate case, we do not have to start again from scratch to define series in several variables. For the above example, we can find it for ’x’ and subsequently for ’y’. We can also define operations on multivariate formal power series. For example, inversion by formula is described in detail in this paper. @inversion

  • Currently we have support of many binary and unary operations of formal power series. But more can be added. Like convolution or cauchy product, composition, inversion or reversion, composition inverse. The theory of all these operations can be found here. @theory For instance for inversion, we may derive explicit formulae for the desired coefficients and substitute directly. This method has the drawback usually encountered in substituting in formulae, namely that the computations are usually unsystematic and therefore become tedious and subject to many errors. Furthermore the formulae become extremely long and complicated for coefficients of appreciable order. A better method is available here @method which we can implement.

Improvements to limits

There is large scope of improvement in limits module. There are many limits which SymPy is currently unable to evaluate or gives wrong results at times. Example:

  • >>> limit(4*x*hyper([S(1)/2],[S(3)/2, S(3)/2],-x**2), x, oo)
This gives error.
>>> limit((sin(x)/x)*16**x/(x*binomial(2*x,x)**2), x, oo)

    This is not evaluated by SymPy while Wolfram gives 0. Corrections for such type of bugs will usually involve adding rewrite or expand methods to respective classes to change their form to be evaluated by gruntz algorithm, and/or modifications in the gruntz algorithm. There are already many open issues reporting such bugs which can be targetted. Example:

    • 10901 - Limit of expression with binomial and sin doesn’t evaluate.

    • 10802 - limit doesn’t work with hyper

  • Errors in limits are also common in expressions involving oscillating terms like

    >>> limit(x/sin(x),x,oo)

    This is not evaluated by SymPy. But we can return the result like Wolfram returns. (<-oo, >oo).

    >>> limit((sin(x)/x)*16**x/(x*binomial(2*x,x)**2), x, oo)

    This one is also not evaluated while wolfram gives 0.

  • The functions whose limits can be calculated are limited by the functions whose series can be calculated as the algorithm (gruntz) uses series.

  • Currently we are unable to evaluate limits of series. Example:

    >>> s = fps(sin(x), x)
>>> limit(s, x, 0)

    This doesn’t evaluate to 0 like it should. So such limits for series will also be implemented.

Better support for Order term arithmetic

This section will work on providing better support for Order term arithmetic, for example, for an expression of the order term of a series around a point that is not 0, like O((x - a)**3)).

Asymptotic series

This section will work representing the asymptotic series of an expression around a point by implementing the algorithm mentioned here. @asym. We already have implementation of gruntz algorithm which is based on this for calculation of limits. The results can look something like this:

>>> MrvSeries(sin(1/x+exp(-x))-sin(1/x), x, oo)

$$e^{- x} - \frac{e^{- x}}{2 x^{2}} + O(\frac{e^{- x}}{x^{4}})$$

Why this project and Why me

The idea that I’ll get to know a tremendous amount of new concepts in Mathematics, in the domain of Series Expansions and others, excites me. I am also interested in the optimization algorithms like rs_series that will be involved in this project. And of course, coding up new algorithms and enhancing existing ones is fun. This sort of conceptual coding is what I really prefer. Coming to why I think I should be chosen. To be honest, I have a long way to go to get a deep understanding of SymPy. But I am competent enough for the coding aspect. I have only taken basic courses in Series and Sequences comprising Taylor series, Laurentz series, Residue Integration, and in Group Theory, Linear Algebra and Probability. But I’m willing to take a plunge and dedicate my Summer completely to this one beautiful project.

Road-map

Since my summer vacation starts by the first week of May, I plan to utilise the period before coding phase to get a clear design of what needs to be done and make sure I’m acquainted with all the necessary concepts. I will not be available for two-four separate days in July (travelling). Apart from this I have no prior commitments. I will be able to devote 40-45 hrs a week.

Community Bonding Period

  • Discuss any doubts about the project with my mentor.

  • Get more acquainted with Sympy’s codebase by reading, playing around more with the code and fixing issues.

  • Read the below listed references in further detail.

Coding Period

  • Improve rs_series expansions (First week of June)

  • Improvements to formal power series (Third week of June)

  • Improvements to limits. (First week of July)

  • Better support for Order term arithmetic (Third week of July)

  • Asymptotic series (Second week of August)

  • One buffer week for any unexpected delays (or more enhancements)

Post GSoC

I’m sure that after a six month long attachment with SymPy, it will become more of a perpetual habit to contribute to SymPy in every way I can. I would love to look at other modules of SymPy that I may not directly interact with during this project. I also hope this period will provide enough experience to think beyond and bring in new ideas of enhancing SymPy’s abilities.

6 Wolfram Research, Mathematica
http://www.wolfram.com/mathematica “Formal Power Series” by Dominik Gruntz and Wolfram Koepf
http://arxiv.org/pdf/math/9404218v1.pdf “A New Algorithm Computing for Asymptotic Series” by Dominik Gruntz
http://delivery.acm.org/10.1145/170000/164136/p239-gruntz.pdf “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 Formal power series, by Peter J. Cameron
http://www.ltcc.ac.uk/courses/enumerative_combinatorics/l2.pdf

http://arxiv.org/pdf/1203.3834v1.pdf https://en.wikipedia.org/wiki/Formal_power_series#Operations_on_formal_power_series http://www.ams.org/journals/mcom/1947-02-020/S0025-5718-1947-0022717-X/S0025-5718-1947-0022717-X.pdf

Add a custom footer
Add a custom sidebar
Clone this wiki locally