[GSoC'18 | VisMa | Week #03-05] – Integrating the Integrator

This is GSoC log#02 (view log#01 here). Here I will cover on what I have done in week #03-05 and a gist of what has been accomplished in Phase I coding period.

Done so far...

• Created parser.py which handles conversion of tokens to LaTeX or strings and vice-versa.
• Some simplification issues were fixed
• Integrated the differentiation.py and integration.py to the project along with the step-by-step explanation.
• Support for partial differentiation and "partial integration" was added.
• The code was again refactored to decrease complexity and remove unused modules.
• Added factorize.py module. Can currently factorize polynomials.

The differentiation.py works for all functions. The integration.py is a tough one. There are going to be many checks for integration as when to apply by-parts or some another method. I am working on a simpler version of integration by-parts algorithm. For now, VisMa supports basic calculus operations. Also, transform module was added to change from one function type to another.

The below demo shows the newly added functionalities like factorizing polynomials, differentiating and integrating expressions with respect to a variable.

Phase - 1 deliverables:

• Modules created: 
• Functions - All function classes added
• GUI/Plotter - Graph plotting added
• IO - Input, output parsers
• Transform - Change one function type to another
• Calculus - Diff and integrate
• Issues fixed: 
• Refactored code to follow object class style
• Rectified equation/expression simplifications
• Embedded solver into main GUI
• Reorganised code into smaller modules

What I will be doing next...

The next thing which I will work on is a basic equation solver. For making the equation solver modules like factorization, expression multiplication and division are required.
Also as the number of functions are increasing, the cases to test are increasing. I will try to automate testing using unit tests.
Most of the time of phase II period will be spent on working on all kinds of solvers. Also, calculus functionalities will be enhanced and support for more types of functions will be added.

Link to project source and to-do board.

[GSoC'18 | VisMa | Week #01-02] – Making VisMa 'classy'

I came across AerospaceResearch.net when browsing through GSoC organizations. It offered projects both in my field of interests and academic domain. I had to make a hard choice between DirectDemod and VisMa and I finally chose VisMa as my project for GSoC.

This is my first GSoC dev log (more to come). Here I will be logging about what I learned, what I have done and what I will do. So following is the work I have done in VisMa.


Done so far...

I used the community bonding period to fix minor errors and get more familiar with the source. I restructured the code base so that new modules could be accommodated. Code duplication was reduced using proper imports between modules. New modules like calculus, transform, solvers, gui etc were initialized. A token IDing module was written to handle equations during calculus operations.

Till now VisMa processed input equations into 'tokens' which were formatted in the form of python dictionaries. Erm?! Tokens? Check this out.
The main aim during this two week period was to convert all the dictionaries to class-objects i.e. to follow the object-oriented style. Classes for the following function types were created:

• trigonometric
• hyperbolic
• exponential
• variable
• constant

While making these, class methods like 'differentiate' and 'inverse' were added to these function classes.

While everything worked perfectly with objects, the steps animator didn't comply. The animator used JSON serializer which would use only strings/dictionary format. Although the object properties could be converted to dictionary format, it would defeat the main purpose. So I decided to use TeX to render equations. The step animator was remolded to render the equations in TeX format using matplotlib's renderer.

An equation plotter was built with the help of matplotlib. The plotter supports plotting equations in one and two variables. While working on the GUI I learned a lot about PyQT4, a GUI library for python. I have updated the GUI so that the plotter and step-animator are embedded in the main window itself. Here is the new GUI in action.




What I will be doing next...

The above example is one of the test cases of the input equations. The animator and plotter have to be fixed to run all cases. Adding animations to the animator is one of the things. I will try to add support for a 3d graph as well(for equations in three variables).

The next thing to do will be integrating the token IDing module. The rules of calculus will be based on this IDing module. The code can be optimized by converting some functions to class methods. Also, some work relating to equation solvers will be initiated.

From now on I will be updating the log on a fortnightly basis (read on AerospaceResearch.net). The project progress can be viewed here. BTW I added a new VisMa logo.

VisMa, now classy and sassy !!

Test Post

How to approach the following two dimensional recurrence relation ?
>For $i,j\ge2$,
>$$a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$$
>where $a_{p,\ 1}=1$ (for $p\ge1$) and $a_{1,\ q} = 1$ (for $q\ge1)$.

Solution:
One way to go about this and generally about solving recurrence relations is to use generating functions, in this case this will lead to two variable generating function.
Let's suppose we have $f(x,y)=\sum_{i,j=0}^{\infty}a_{i,j} x^i y^j$ formal powers series which encodes coefficients of your sequence. For simplicity, here we have it shifted, so actually $a_{0,q}=a_{p,0}=1$, but don't worry about that, we can shift this back at the end. Now let's play with coefficients a little to see if we can get better form of $f(x,y)$:
\begin{align}
f(x,y)&=\sum_{i,j=0}^{\infty}a_{i,j} x^i y^j \\
&=a_{0,0}+\sum_{i=1}^{\infty}a_{i,0} x^i+\sum_{j=1}^{\infty}a_{0,j} y^j + \sum_{i,j=1}^{\infty}a_{i,j} x^i y^j \\
\end{align}
Now we have shifted the indices (you will see later why), but before proceeding, notice $a_{0,0}=1$ and that
$$
\sum_{i=1}^{\infty}a_{i,0} x^i = x+x^2+x^3+\dots = \frac{x}{1-x}
$$
and similarly for the second sum. So overall we have
$$
f(x,y) = 1+\frac{x}{1-x}+\frac{y}{1-y}+\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j
$$
Now for the rightmost sum, lets write
\begin{align}
\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j &= \sum_{i,j=1}^{\infty}(a_{i,j-1}+a_{i-1,j-1}) x^i y^j \\
&= \sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^j+\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^i y^j \\
&= y\sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^{i-1} y^{j-1}\\
\end{align}
Here we have just applied the recurrence relation (this is why we moved the $0$ indices out before) and then moved the $x$,$y$ out of the sum, so that indices match. Now lets just re-index the sum
\begin{align}
\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j &= y\sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^{i-1} y^{j-1}\\
&= y\sum_{i=1,j=0}^{\infty}a_{i,j} x^i y^{j}+xy\sum_{i,j=0}^{\infty}a_{i,j} x^{i} y^{j}\\
&= y\left(\sum_{i=0,j=0}^{\infty}a_{i,j} x^i y^{j}-\sum_{j=0}^{\infty}a_{0,j}\right)+xy\sum_{i,j=0}^{\infty}a_{i,j} x^{i} y^{j}\\
&= y\left(f(x,y)-\sum_{j=0}^{\infty}a_{0,j}\right)+xyf(x,y)\\
&= y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\
\end{align}
Here we have just substituted back the definition of $f(x,y)$ itself. Now putting back together we have
\begin{align}
f(x,y)=1+\frac{x}{1-x}+\frac{y}{1-y}+ y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\
\end{align}
and after some simple algebraic manipulations we finally get:
\begin{align}
f(x,y) = \frac{1}{(1-x)(1-y-xy)}\\
\end{align}
Now the $f(x,y)$ encodes all of the coefficients in a compact way. We can now try to write it in a way that will allow us to see the coefficients more clearly.
For this notice that $\frac{1}{1-x}=1+x+x^2+x^3+\dots$. Also second expression is well known generating function $$\frac{1}{1-y-yx}=\frac{1}{1-y(x+1)}=\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j.$$
So we can view our function in this form as a product
$$
f(x,y) = (1+x+x^2+x^3+\dots) \left(\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j\right)
$$
Now to ask what is the value of $a_{i,j}$ is same as to ask what coefficient of $x^i y^j$ is in this product. It is not hard to see that it will be $\binom{j}{i}+\binom{j}{i-1}+\dots+\binom{j}{0}$. So overall, also with correcting the original offset from $i$ to $i-1$ and $j$ to $j-1$, we get
$$a_{i,j} = \sum_{k=0}^{i-1}\binom{j-1}{k}.$$