GSoC Week 8

This week I started work on writing the series module for symengine. I am working with Sumith on Polynomials on PR 511. It is still a work in progress. A lot of the code, especially related to Piranha was new to me, so I had to read a lot. I got a PR 533 merged which uses templates to simplify code for equality and comparison of maps.

With regard to PR 9614, I had a meeting with my mentor Thilina. We decided that we should be able to call the RingSeries function on SymPy Basic expressions so that the user need not bother about creating rings and all the extra function calls. So, I will be building on top of the classes I created earlier to make the series method accept Basic expressions. I created RingFunction, RingMul and RingAdd classes. The taylor_series method now works with sums and products of functions. However, it is still not optimised, especially with series that have a low minimum exponent (say cos). I need to find a better way.

I returned to college. Once classes begin from Monday I will need to manage my time well as my schedule will get busier.

Next Week

  • Finish the Polynomials PR.

  • Further optimise the taylor_series method to work in all cases.

  • Start writing a series method that works with Basic expressions.

I think it is good to have the flexibility to work with Basic objects as that integrates the ring_series module better with the existing series infrastructure of SymPy. At the end of day, we want maximum number of people to benefit from using the code.

Cheers!

GSoC Week 7

So Far

PR 9575 and PR 9495 got merged this week. All the basic functions are now in place in polys.ring_series. The module supports Laurent as well as Puiseux series expansion. The order of the day is to extend this support for nested functions, and encapsulate the whole thing with classes. The idea is that the user need not bother about calling ring_series functions and that the class should hold all the relevant information about the series.

Given that SymPy already has series infrastructure, we need to decide whether ring_series with be integrated with it or whether it will be distinct from it.

Next Week

  • Discuss and decide how ring_series is to be used and write its classes accordingly. I will build upon PR 9614

  • Write a series function that makes use of ring_series functions to expand arbitrary expressions.

I also need to start porting some of it to Symengine. The basic polynomial operations are in place there. I need to discuss with Ondrej and Sumith how the series module will best work with the Polynomial module. If that is sorted, I can start porting the ring_series functions.

Cheers!

GSoC Week 6

I successfully passed my mid term evaluation this week and now the second half of my project has begun! It has been a challenging journey so far that has made me explore new algorithms (some very ingenious) and read a lot of code (much more difficult than I had imagined). This week, Mario whose code I am working on, helped in a big way by showing how and where to improve the algorithms. It is clear now that all the functions need to guarantee the order of the series they output. We were planning to keep it optional but since ring_series functions each other, an error in the order will propagate and eventually make it unpredictable.

So Far

PR 9575 is ready for merge except for a bug in sympify that converts PythonRational into float.

I had a discussion with Mario on PR 9495. He has suggested a lot of improvements while dealing with fractional exponents, especially the fact that Newton method may not be ideal in these cases. It is very interesting to try and compare different algorithms and come up with ways to optimise them for out needs. The scope for improvement is immense and we'll need to decide the order in which we'll push the optimisations.

I started writing the RingSeries class for series evaluation in PR 9614. I was supposed to update my blog yesterday, but I dozed off while working on it. According to my current approach, I am writing classes for all the functions so that they can be represented symbolically. Another issue that needs to be tackled is expansion of nested functions, things like sin(cos(sin(x)). This will need some work as there are many approaches to tackle it. Currently, I evaluate the inner functions( it they exist) recursively with prec + 1. This will work in simple cases, but not if there are cancellations, eg, sin(cos(x)) - sin(cos(x**2)).

Next Week

  • Get PR 9575 merged.

  • Improve PR 9495 and get it merged.

  • Finalise the series class hierarchy and the series evaluation function.

The next phase of my project is in Symengine and there have been a lot of improvements and changes there. I will need to play with the new stuff and perhaps also think of ways to port ring_series there.

Cheers!

GSoC Week 5

I am almost half way through my project and it has been an amazing learning experience. According to my timeline I am supposed to finish ring_series work in SymPy by the mid-eval (i.e, by next week) and start porting it to Symengine after it. Though I faced some hiccups, especially in figuring out how to deal with a symbolic ring, the deadline is achievable.

Till now

  • Series reversion has been added to ring_series after this PR of mine got merged.

  • I have started modifying the functions to operate on constant terms in the input series with this PR. I plan to finish it by this week. We are using the EX domain to represent the symbolic coefficients.

  • The PR to add puiseux series has not been yet merged. I have added a check_precision function that gives an approximate number of iterations with which the ring_series functions will output the series of the requested order.

Next Week

I expect both the pending pull requests to get merged by this week. After that the only major task remaining, would be to write the new Series class structure. So, the tasks are:

  • Discuss and write the new Series class structure.

  • Finish pending tasks, if any, and write more tests.

GSoC Week 4

Though I had resolved to update my blog posts by Friday every week, this one is quite late. This is mostly because this week was one of the most confusing yet, in terms of figuring out how to get things done within the existing code structure of Sympy. And that process is still on.

So Far

PR 9495 is under review. It took some time to decide how the precision/order of Puiseux series needs to be handled;

We had an interesting discussion on reverting a series here. Fredrik Johansson suggested a fast algorithm of his for it. I also got to know a very ingenuous way to expand trigonometric functions. For example, for exponential:

def exp_series(A, n):
B = [exp(A[0])]
for k in range(1, n):
B.append(sum(j*A[j]*B[k-j]/k for j in range(1,min(len(A),k+1))))
return B

Possibly the most confusing part of the project is to get ring_series working over an Expression domain, i.e, the coefficients can be any SymPy symbolic expression. Multivariate series need to have multiple gens, implying that in a multivariate series, the coefficients can be symbolic functions of PolyElement objects. However, PolyElement class is of type CantSympify, which means I can't use it in SymPy functions. I had quite a few discussions with my mentors over it and I know now what the issues are. I need to solve them next week.

Next Week

  • Finalise how to handle symbolic coefficients and finish it

  • Read Fredrik's paper and try to implement it.

Cheers!

GSoC Week 3

So far

My PR 9262 finally got merged. However, we have not yet decided which algorithm to use for the trigonometric and hyperbolic functions. In most cases there are multiple options

  • Expansion using closed form formula
  • Expansion of tan and tanh using a form of Newton's method
  • Expansion of sin, cos, sinh and cosh from tan and tanh
Newton's Method

Newton's method is rather interesting. It lets you calculate the series expansion of a function, given the series expansion of its inverse. Now, the formula for the expansion of tan is much more complicated than that of atan. So using atan's series expansion for tan makes sense. The basic idea is as follows:

Say I have a continuous and differentiable function f(x), whose inverse is g(x), i.e, f(g(x)) = x. Assume that we have an efficient implementation for g(x) and we want to use it for f(x). Let h(x) = y - g(x). On solving this equation, we'll get a root c, such that: h(c) = 0 or y = g(c) or c = f(y)

Now, using Newton's method we have the following iteration: x_j+1 = x_j + (y - g(x_j)) / g'(x_j)

The more iterations we do, higher the precision of our series expansion. If you are interested in the mathematics behind it, you can refer to this

As of now, ring_series has the code for plain vanilla formula based expansion too. I need to properly benchmark the different methods to conclude anything about their relative performance.

Puiseux Series

This week I am working on PR 9495, which will let us manipulate Puiseux series in ring_series. A Puiseux is a series which can have fractional exponents. By definition, a polynomial should have only positive integer exponents. So, I was hoping that using a Rational doesn't break anything in the polys module. Unfortunately, my PR is causing some tests to fail. I hope I don't need to make major changes because of it.

Once Puiseux series gets up and running, I will add the remaining functions dependent on it.

Next Week

A Symbolic Ring

Just as the type of series decides how the exponents of the series will be, the coefficients are determined by the ring over which the polynomial is defined. To be able to expand functions with arguments that have a constant term with respect to the expansion variable, the series should be allowed to have symbolic expressions as coefficients. For example, a 2nd order expansion about 0 of sin(x + y), wrt x, is sin(y) + x*cos(y). To be able to do this with ring_series, the polynomial needs to be defined over the EX or expression ring, which is Sympy's implementation of a symbolic ring. Currently ring_series works with EX ring but it can not handle a series with constant terms.

So, my major tasks for next week are:

  • Get ring_series working with symbolic ring
  • Implement series expansion of polylog and series reversion
  • Discuss the structure of Series class and send a PR for it.

Cheers!

GSoC Week 2

The 2nd week is now coming to an end, and by now I have a pretty good idea about how things often don't work the way we want them to.

So far

I trimmed down PR 9262 to remove all the parts not yet ready. It is undergoing review and should get merged soon.

Last week, I had planned to complete work on Laurent series by now, but it is still a work in progress. Fortunately, while discussing it with my mentors, we realized that handling Puiseux series is not as difficult as I had thought initially.

Internally, all polynomials are stored in the form of a dictionary, with a tuple of exponents being the key. So x + x*y + x**2*y**3 is stored as {(1, 0): 1, (1, 1): 1, (2, 3): 1}. For Puiseux series I need to be able to have rational exponents as keys in the dict. This isn't an issue in Python 3 as it evaluates 1/4 to 0.25 and the uses the decimal value as key. It doesn't work in Python 2 as it evaluates 1/4 to 0 and hence all fractions less than 1 become 0. The solution to this is to use Sympy's Rational data type, which lets us use the exact fraction as a key. This means that, hopefully, I will not need to make any complex changes in the code of ring.

I still have a few days to go in this week, during which I will further explore how to make the required changes.

There hasn't been much progress on the hashtable as both me and Sumith have been busy with our PRs. Hopefully, we will look into it during the weekend.

Next Week

  • Make ring_series work with Puiseux series
  • Write an interface to better handle the series, especially so that it works with the rest of Sympy.

Cheers!

GSoC Week 1

The first week of the Coding period is now almost over. Though this post is quite late, I'll try to post updates at the start of each week from now.

What makes my project so interesting (and challenging!) is that I need to work on two separate code bases- SymPy and Symengine. After discussing with Ondrej, I have started the part of my project related to SymPy.

Following are the goals of Phase I:

  • Complete ring_series : There is already a partial implementation of ring_series in SymPy. I will add more elementary and user functions, so that it has similar capabilities as the series function.
  • Write a class structure on top of ring_series so that the user need not bother about calling separate functions for each function.

So far

My main task, this week, was to port PR 609 into ring_series . I have, hence been working on PR 9262. I am done porting most elementary functions and writing their tests, with the exception of rs_nth_root and rs_cot.

A major issue that cropped up while writing tests is concerning Laurent series. As of now, polys do not accept negative exponents. I will either need to rewrite poly rings to accept negative exponents or modify operations so that they can use the present poly structure to handle negative exponents.

Next Week

My targets for the next week are:

  • Make ring_series handle Laurent series.
  • Polish PR 9262 and get it merged. It has already grown big. I will probably need to send another PR.
  • Discuss a class structure for series expansion and send a PR for it.
  • Start working on the hashtable for Symengine with Sumith

Looking forward to another exciting week.

Cheers!

Beginning of GSoC 2015

gsoc

In an earlier post I had talked about my application for Google Summer of Code, 2015. I am extremely glad to inform that my project for CSymPy (now called SymEngine) and SymPy has been selected under Python Software Foundation. Ondrej Certik and Thilina Rathnayake will be mentoring me during the course of my project. Ondrej started the SymPy library and is currently leading the development of SymEngine, while Thilina is a two time GSoC'er with SymPy and SymEngine and has research interests in Symbolic computation. Needless to say, I am extremely lucky to work under such talented people.

My project involves writing polynomial based series expansion modules for SymEngine and SymPy. I have already had very productive discussions with my mentors and hope to do some good work.

Looking forward to a great summer!

Cheers!

Hey there!

I am applying for Google Summer of Code, 2015. It is an annual program sponsored by Google, that pays students to contribute to open source organizations of their choice. My application involves two symbolic computation libraries - Sympy and CSymPy, the former written in Python and the latter in C++. CSymPy is meant to be a fast cousin of Sympy and can be used with optional wrappers.

I am proposing to implement fast series expansion in CSymPy and Sympy. Sympy already has series expansion, but suffers from speed issues and lack of a class structure. You can look at my full proposal here

I will use this blog to write about my GSoC experience, if I am selected.

I welcome your suggestions.

Cheers!