Stuck in the guessing game

Hello. I had thought that at the time of writing this post, I would have comfortably finished the sixth heuristic. However the Maple paper hasn’t been kind to me, because not knowing how to implement an algorithm is tough enough, but not knowing what the algorithm is, is hell. The good part (?)  is that Sean too had no idea, when he had a quick look (though he said he may help me get some insight later on), when I talked to him on GTalk and Aaron too when I met on IRC. I’ve also not written anything for ten days, so I’m trying to write, a detailed post here, so that if anyone at Planet SymPy stumble upon this, they could comment here.

The fifth heuristic:
The Maple paper has been giving me mixed signals, and half of my time goes in interpreting what the authors are trying to say, and most of the time I get it wrong, and so the other half goes in trying to interpret it the right way. So these are the two steps, as described by the paper.
1. A basis of functions and algebraic objects is built by taking, from the given ODE, all the known functions and composite algebraic objects, together with their derivatives, as well as all the unknown functions
2. A polynomial of degree 2 in such objects is built; its coefficients, in turn, are polynomials of degree d in x and y

So what does this mean? This is what even I was trying to figure out. Let us now look at the single example that they managed to provide.

x*\frac{dy}{dx}*log(x)*sin(x) + cos(y)*(1 - x*cosy) = 0. Rearranging this gives me h as \frac{cos(y)*(1 - x*cosy)}{x*log(x)*sin(x)}. Fair enough.

My first impression was that I had to take all algebraic objects from h like cos(y)/x, x*cos(y)^{2}, cos(y)/log(x), cos(y)/sin(x), and I wrote a bit of optimised code, (atleast I think), I found out that there are 19 possible factors, and according to the step 2, including the derivatives, and the second degree terms I would get a maximum of 19 + 19(derivatives) + 19*C_{2}(second degree terms of power one) + 19(terms of power 2) from which I can built the polynomial. Obviously, substituting it in the PDE, grouping terms, and using solve, would be computationally expensive for SymPy. Sean then told me its since the paper tells only ‘composite algebraic objects’  it is enough to limit to three algebraic objects, cos(y), x*cos(y)^{2}, x*log(x)*sin(y). So this is the approach, that I used.

1. Use as_numer_denom() to extract the numerator, denominator of unsimplified h,  expand the numerator and denominator,  which would give the list of factors. Obviously suppose I have something like 2*siny and - siny, they should be treated as same, I wrote a helper function called _rem_num, which would remove the numeric arguments from Mul and Pow.

2. Iterate over the list and add derivatives, From this add the second degree terms, and first terms. This gives the basis with which I can build the polynomial. For the given differential equation, I get the following basis, https://gist.github.com/Manoj-Kumar-S/5989623.

3. Now, since instead of taking the factors, one at a time, two at a time, three at a time and so on, I thought it would be better to build a general polynomial, \sum_{k=1}^nCk*termk and substitute it in the PDE, \frac{\partial \chi}{\partial x} + h*\frac{\partial \chi}{\partial y} - \chi*\frac{\partial h}{\partial y}. If it is a single term polynomial, then the coefficients of the other terms become zero. So the first sub-step is done.

4. For the second step, Maple says I need bivariate coefficients in x and y, for the terms in the polynomial, So to sum up this is the pseudocode I used,

  • Initialize a coefficient dict to {}
  • Take the first term in the basis, substitute it in the PDE, if it simplifies to zero, great you’ve got your infinitesimal, If it doesn’t group the like terms and store it in the coefficient_dict
  • Repeat the above mentioned process for all the terms in the basis
  • Once, it is done for all the terms in the basis, use solve to find if the coefficients, give a non-trivial solution.
  • If it doesn’t then start from beginning, however use (a*x + b*y)*term, and then a*x^{2} + b*x*y + c*y^{2} till it reaches a maximum limit.

This is the most optimized way that I could think of,  and the code works well for the example given. But I am facing weird test failures, for the tests that I have added, For example when I do

eq3 = (1 + 2*x)*f(x).diff(x) + 2 - 4*exp(-f(x))
infinitesimals(eq3)
[{eta(x, f(x)): 0, xi(x, f(x)): 2*x + 1},
{eta(x, f(x)): 0, xi(x, f(x)): 1/(exp(f(x)) - 2)}]

However, when I try to print it while running tests, I get an extra term. I have no idea how I get this difference.
The sixth heuristic:
Okay, so this is where I had no idea what to implement and how, and I am in this position for about three days, and that isn’t promising. Let us take the PDE again, \frac{\partial \eta}{\partial x} + (\frac{\partial \eta}{\partial y} - \frac{\partial \xi}{\partial x})*h - \frac{\partial \eta}{\partial x}*h^{2} - \xi*\frac{\partial h}{\partial x} - \eta*\frac{\partial h}{\partial y} = 0 . So I make the following four assumptions on \eta and \xi

1. \eta = f(x), \xi = g(y)
2. \eta = f(x), \xi = g(x)
3. \eta = f(y), \xi = g(y)
4. \eta = f(y), \xi = g(x)

Let us take the fourth assumption, the PDE reduces to (\frac{df}{dy} - \frac{dg}{dx})*h - f*\frac{\partial h}{\partial x} - g*\frac{\partial h}{\partial y} = 0. The Maple paper says:
1. subdivide the equation into subexpressions involving only one of {f, g};
2. build a list of candidates for f and for g with the solutions to these subexpressions;
3. build a list of pairs of candidates by taking one candidate from each list.

Now what on earth, the first step is supposed to mean, I have no idea. My first impression, when I was writing my proposal and a few days back, was that I had to split it into,  two different ODE’s so that I should solve \frac{df}{dy} - f*\frac{\partial h}{\partial x}= 0and \frac{dg}{dx}*h + g*\frac{\partial h}{\partial y} = 0 individually. However I can never be more wrong, since it then is a sub-part of the first heuristic, and also according to the example given that is \frac{dy}{dx} = \frac{e^{x}}{\sqrt{y}}*F(\sqrt[3]{y} - \frac{3*e^{x}}{2}) , the infinitesimals found out are \frac{1}{e^{x}} and \frac{1}{\sqrt{y}} , there seems to be a term that is common to both f and g.

So that sums up, my last ten days coding or trying to code rather. I know Maple is not open-source and all that, but it would have been really nice if they had provided a few more examples on each of the heuristics, instead of just giving a single line which can be comprehended in a thousand different ways.

Advertisements

3 comments

  1. Can you please repost the reference to the mentioned paper again?

    1. Thanks for your comment. It is on the middle of page 9 of the paper in the top right corner of this web-page http://arxiv.org/abs/gr-qc/9607037v1

  2. My suggestion is to try search the websites of the authors of the paper for any additional resources that might help you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: