week 5

Solving Trigonometric Function (part I)

This week I spend time on making trigonometric solvers work. Every trigonometric function can be written in terms of tan.

$$sin(x) = \frac{2*tan(x/2)}{tan^{2}(x/2)}$$

$$cos(x) = \frac{-tan^{2}(x/2) + 1}{tan^{2}(x/2) + 1}$$

$$cot(x) = \frac{1}{tan(x)}$$

A basic technique to solve trigonometric equations can be rewriting the equation in terms of tan. And if the equation is made by addition, multiplication or quotient of trigonometric functions then the transformed equation is a equivalent to a rational function in tan. That equation can be solved by the usual polynomial solving techniques.

Taking the example from the doc $cos(x) + sin(x)$ gets converted to $\frac{-tan^{2}(x/2) + 2*tan(x/2) + 1}{tan^{2}(x/2) + 1}$

The solution of this equations is $tan(x/2) = 1 +- sqrt(2)$. Since the inverse of tan is $\left\{2 \pi n + \operatorname{atan}{\left (y \right )}\; |\; n \in \mathbb{Z}\right\}$ the solution of the given equation is $$\left\{2 \pi n - \frac{\pi}{8}\; |\; n \in \mathbb{Z}\right\} \cup \left\{2 \pi n + \frac{3 \pi}{8}\; |\; n \in \mathbb{Z}\right\}$$

Though it appears this technique should work universally for trigonometric equation it fails for even $sin(x) = 0$. From the table above $sin(x) = \frac{2*tan(x/2)}{tan^{2}(x/2)}$ So, the $sin(x) = 0$ occurs at $tan(x/2) = 0$ which has solution $\left\{2 \pi n\; |\; n \in \mathbb{Z}\right\}$ But the solution is $\left\{ \pi n\; |\; n \in \mathbb{Z}\right\}$ . Why are we missing some solutions? The reason is $sin(x) = 0$ also occurs when denominator tends to $\infty$, i.e., the values where $tan^{2}(x/2) + 1$ tends to $\infty$. We had encountered a similar problem for the solution of $$\frac{1}{\left(\frac{x}{x + 1} + 3\right)^{2}}$$

here $x = -1$ is not a point in the domain of the of the equation. The solver simplifies the equation to

$$\frac{\left(x + 1\right)^{2}}{\left(4 x + 3\right)^{2}}$$

which extends the domain to include the point $x = -1$ which is also the solution to the transformed equation. There we wrote a sub procedure domain_check to verify if the returned solution is part of the domain of the original equation. The problem here is slightly different in the sense that transforming the equation decreases the domain of the solutions and not increase it.

To find such solution we have allow $\infty$ to be solution to equations, we will be working on extended reals instead of just reals. I think this change will simplify a lot of things.

Another thing which should be taken care off is that we cannot naively search for the values for which the denominator tends to infinity as for the same value numerator might also attain infinitely large value, we will have to conceder the limiting value of the equation.

week 4

Intersections of Infinitely indexed sets

This week I implemented a method to do intersection of imagesets using the solutions of Diophantine equations at PR.

Say you have to find the intersection of sets 2*n| n in Integers and 3*m| m in Integers. The intersection of these sets is the set of the common values in the two sets, which in this case is equivalent to the values of n for which the equation 2*n - 3*m has some integral solution in m. Or the values of m for which the 2*n - 3*m has some integral solution in n. Diophantine equations are equations for which only integral solutions are searched for. The Diophantine module was written by Thilina as his GSoC project last year. It gives the parametric solution for such equation.

In [17]: diophantine(2*n - 3*m)
Out[17]: {(-2*t, -3*t)}


The Solution is sorted according to alphabetic order of the variables involved. So the value of LHS (2*n) for which the equation is 2*(-3*t) that is -6*t and it is the intersection of the sets described above -6*t| t in Integers. Since -6*t| t in Integers is same as 6*t| t in Integers I also wrote some simplification rules for the imagesets with Integers as baseset.

Sets for Invert Function

The sets module turned out to be better than I expected. I had a perception that substitutions doesn't work properly with sets and I have even opened an issue for that but it turned out I hadn't looked closely enough. It worked well for the free variables and it didn't worked for the things it shouldn't work i.e., the bound variables in the imagesets.

Using sets simplified the code. All the list comprehensions like this [i.subs(symbol, symbol/g) for i in _invert(h, symbol)] were converted to simple substitutions for sets and other sets operations. _invert(h, symbol).subs(symbol, symbol/g)

Just by changing the output of invert to sets, then by adding the inverse of trigonometric function and writing the code to rewrite then as tan I was able to return all the solutions of the equations like cos(x) + sin(x) == 0 it turned to out to easier than I thought. Using sets as output makes thinking about the mathematics of the solvers much more easier and the code comes out to be pretty natural. Now when we can see the results I can surely say there can be no better output for solvers than sets.

This week I'll study LambertW function and then code additional techniques to solve real equations. I'll also try to figure out techniques to perform Union on infinitely indexed sets.

week 3

Hi, At the start of this week I wrote a method to check if a given solution lies in the domain of the equation or not. The problem it targeted was equations like (x - 1)/(1 + 1/(x - 1)) though at x = 1 the eqution has value zero the point is not present in the domain of the given equation. Though there is some disagreement on the implementation, the idea was to traverse the expression tree and check if any of the subexpression goes unbounded for the given value. Later I observed that caching was messing with the tests. Sometimes the tests passed and sometimes the same test suit run without any modification in the code failed. To do the check on the subexpressions I need to have a copy of the original equation before the solver performs any simplification on it. Being not sure of the mutability of the equations I used deepcopy to copy the original equation to a variable. Later in a meeting we figured out that deepcopy was messing with caching. Aaron told me that every expression in sympy is immutable so don't need to perform deepcopy on anything.

This week we will restart working on the sets to represent infinite solutions, Almost every equation in complex domain other than polynomials and rationals has infinitly many solutions. For example even the simple equation exp(x) == 1 has infinitely many solutions that is i*2*n*pi where n is an integer. To return these solutions we first need to have infrastructure to handle them. The old(current) solvers does it wrong, it implicity mixes up the complex and real domains, the answer it returns to exp(x) == 1 is only [0]. Earlier I was also doing it wrong so I decided that I should have two seperate solvers for reals and complex instead of one. This also simplifed the code for the reals solvers to a large extent.

Week 1 and Week 2

Hi, As I told you about in the previous post, My work for this summer will be improving the current equation solvers of sympy. There are basically three thing I'll have to do.

1. Create a basic set infrastructure for solvers to return sets.
2. Rewrite the current solvers to be clean and robust.
3. On the top of 1 and 2 write new solvers and function, they will returning and handling all the solutions of equations like sin(x) == 0 and a general singularity finder.

You can look at the details in my proposal

A started working on the sets module in the community bonding period, basically writing a set difference class at this PR , I try to get it merged by the end of this week.

Set are a pretty general mathematical constructs, and you can solve a lot of hard problems if you could compute general set operations. The whole number theory can be defined in terms of sets. So, computing general set operations, e.g, intersection, unions is pretty hard problem too and we should not aim to do all them. In a meeting with Matthew and Sergey we discussed that it would be better if complete the part 2 first. It will give a general idea about what capabilities of sets we need. Also some sets problems can be reduced to equations and vice versa.

I've started working on the univariate solvers at PR. My aim for this week will be.

1. Completing the rational solvers
2. Getting the open PR for the sets merged.

GSoC 2014 with Sympy

Hi, I'm Harsh Gupta an undergrad student at IIT Kharagpur, I've been accepted this year for the Google Summer of Code program with Sympy.

So, What is a Google Summer of Code?

Google Summer of Code is a program by Google to promote opensource development. In this program Google pays handsome stipends to students to work for various opensource organisations. In the application phase the students have to write proposals to the organisations describing the projects they want to do and how do they fit for it. If the proposal is accepted the student is provided with a mentor and with the guidance of the mentor the student has to complete the project in the given timeline. You can look at my proposal. I proposed to work on improving the current equation solvers in Sympy. My mentors for the Project are Matthew Rocklin and Sergey B Kipirchev.