GSoC Project Idea Discussion

[Naveen Saisreenivas Thota]

Hi all,

I wanted to discuss the project "Integrating factors for second order ODEs". First off, is the paper too big for a GSoC project this year since the time limit is reduced? If not, even parts of the paper can be implemented. I have already gone through the paper, and I have some doubts regarding it. 

1. For integrating factors of the form µ(x, y') in Section 2.2.1 Case B, the paper states that the integrating factor reduces to a search for µ(x) using the adjoint of the original ODE. Is this already implemented? If not, should it be considered as part of the project? If so, could someone suggest a good paper for this method?

2. In Section 2.2.3 Case A, how is F(x, y') being determined? What I think is the process - Factorize Υ and look for factors which contain y' but not y and take their reciprocal. But what if there are multiple factors? 

In the given example, there are no such factors, so Derivative(F(x, y'), y') = 1 which gives F(x, y') = y'. Please tell me if I understood it correctly.

3. I couldn't understand how to find F(x, y') in Section 2.2.3 Case B.

4. For integrating factors of the form µ(x, y') in Section 2.3, I couldn't understand how an integrating factor of 1/(y'**2*x) for the transformed ODE implies an integrating factor of 1/y for the original ODE. I tried applying the transformations x->y(x) and y(x)->x to the integrating factor, but I'm getting the integrating factor as y'**2/y.

Naveen

[Oscar Benjamin]

On Sat, 13 Mar 2021 at 14:27, Naveen Saisreenivas Thota
<naveensai...@gmail.com> wrote:
>
> Hi all,
>
> I wanted to discuss the project "Integrating factors for second order ODEs". First off, is the paper too big for a GSoC project this year since the time limit is reduced? If not, even parts of the paper can be implemented. I have already gone through the paper, and I have some doubts regarding it.

It is polite to give links to what you are referring to rather than
expecting others to go look it up:

https://github.com/sympy/sympy/wiki/GSoC-Ideas#other-ode-ideas

The paper is "Integrating factors for second order ODEs" by E.S.
Cheb-Terrab and A.D. Roche and is linked to here:

https://drive.google.com/file/d/1-XktJVEzpRK9nOlaMjE7arEgMgGlV_sN/view

I have just looked very briefly at the paper. Not having read it I
can't answer your detailed questions. What I can say is that the
algorithm looks fairly complicated and the kinds of ODEs that it can
solve are not that common compared to other cases that dsolve is
unable to solve.

There are simpler and more useful algorithms that have not yet been
implemented in sympy. In particular the Kovacic algorithm gives
solutions for a useful and commonly occurring class of ODEs:
https://www.sciencedirect.com/science/article/pii/S0747717186800104
The Kovacic algorithm can find any Liouvillian solution to any 2nd
order linear ODE with rational function coefficients. This makes it
somewhat like the Risch algorithm in that it can prove the
non-existence of solutions from a given class of functions. (It is
based on the same theory as the Risch algorithm but is much simpler.)


Oscar

[Naveen Saisreenivas Thota]

>  It is polite to give links to what you are referring to rather than
> expecting others to go look it up:

Sorry about that. I will include links in the future.

> There are simpler and more useful algorithms that have not yet been

> implemented in sympy. In particular the Kovacic algorithm gives
> solutions for a useful and commonly occurring class of ODEs:

For Kovacic's Algorithm, I found a paper which consists of an updated Kovacic Algorithm and includes the implementation in Maple for different cases. Here is the link to it - 

https://cs.uwaterloo.ca/research/tr/1984/CS-84-35.pdf

Please let me know if this is a good idea for a GSoC project.

Naveen

[Oscar Benjamin]

On Sat, 13 Mar 2021 at 15:39, Naveen Saisreenivas Thota
<naveensai...@gmail.com> wrote:
>
> > There are simpler and more useful algorithms that have not yet been
> > implemented in sympy. In particular the Kovacic algorithm gives
> > solutions for a useful and commonly occurring class of ODEs:
>
> For Kovacic's Algorithm, I found a paper which consists of an updated Kovacic Algorithm and includes the implementation in Maple for different cases. Here is the link to it -
> https://cs.uwaterloo.ca/research/tr/1984/CS-84-35.pdf
>
> Please let me know if this is a good idea for a GSoC project.

If you can understand the algorithm and think that you would be able
to implement it then it would be a good idea for a GSOC project.

Oscar

[nijso.be...@gmail.com]

Hi,

I implemented the Lie method for second order ODEs in the maxima cas. The code for maxima is here :

https://github.com/bigfooted/maxima-odesolve

specific jupyter doc for ode2_lie (best viewed with nbviewer):

https://nbviewer.jupyter.org/github/bigfooted/maxima-odesolve/blob/master/Doc/ode2_lie.ipynb

I also implemented Kovacic method in maxima, the code is in the same repository. They are both very advanced methods. Kovacic' algorithm is a fundamental algorithm so every ODE solver should have it (or a modern version of it). But I do not recommend implementing Kovacic' method unless you are somewhat familiar with differential Galois groups. The second order integrating factor method could be done, though, because I think the learning curve for understanding, or at least working with, Lie groups is not so steep as for differential Galois. However, it is less useful than Kovacic. You can also start by writing a solver for first order rational Riccati ODEs, because Kovacic' method is basically telling you how the Liouvillian solution of a second order ODE can be found by solving a rational Riccati ODE.

You can also consider implementing a general Lie (symmetry) method to find integrating factors for first order ODEs. It is the most successful first order ODE solver and can solve e.g. 90% of the Kamke database of first order ODEs. Such a method can also solve all 'trivial' ODEs like linear, separable, Bernoulli, which sympy cannot all solve. It is more robust because symmetry methods does not depend on pattern matching the ODE. Some Lie group methods have been implemented in sympy already which can be a basis to work on. Note that all solvable first order ODEs have an integrating factor, and an integrating factor solves the first order ODE.

 

Hope this helps. If you or somebody else wants to work on any of these methods, I'll be happy to help.

All the best,

Nijso

[Oscar Benjamin]

On Mon, 15 Mar 2021 at 15:23, nijso.be...@gmail.com
<nijso.be...@gmail.com> wrote:
>
> Hi,

Hi Nijso,

> I implemented the Lie method for second order ODEs in the maxima cas. The code for maxima is here :
>
> https://github.com/bigfooted/maxima-odesolve
>
> specific jupyter doc for ode2_lie (best viewed with nbviewer):
> https://nbviewer.jupyter.org/github/bigfooted/maxima-odesolve/blob/master/Doc/ode2_lie.ipynb

Sounds like you'd be a very useful person to have around!

> I also implemented Kovacic method in maxima, the code is in the same repository. They are both very advanced methods. Kovacic' algorithm is a fundamental algorithm so every ODE solver should have it (or a modern version of it). But I do not recommend implementing Kovacic' method unless you are somewhat familiar with differential Galois groups.

How much do you actually need to understand of the theory to make it work?

I wouldn't say that I know differential Galois theory but reading
Kovacic's paper and also the Smith paper linked above I thought that I
was able to follow the algorithm itself and how to implement it. To me
it looked as if differential Galois theory was needed for the proofs
but not for the algorithm itself. I have seen other more recent papers
about extensions or modifications of Kovacic's algorithm that did seem
to be more heavily based on the Galois theory though.

> The second order integrating factor method could be done, though, because I think the learning curve for understanding, or at least working with, Lie groups is not so steep as for differential Galois. However, it is less useful than Kovacic. You can also start by writing a solver for first order rational Riccati ODEs, because Kovacic' method is basically telling you how the Liouvillian solution of a second order ODE can be found by solving a rational Riccati ODE.

Yes, some easily solvable cases of Ricatti ODEs are not yet covered by dsolve.

> You can also consider implementing a general Lie (symmetry) method to find integrating factors for first order ODEs. It is the most successful first order ODE solver and can solve e.g. 90% of the Kamke database of first order ODEs.
> Such a method can also solve all 'trivial' ODEs like linear, separable, Bernoulli, which sympy cannot all solve. It is more robust because symmetry methods does not depend on pattern matching the ODE. Some Lie group methods have been implemented in sympy already which can be a basis to work on. Note that all solvable first order ODEs have an integrating factor, and an integrating factor solves the first order ODE.

Yes, some methods have been implemented in sympy. There is a lot of
code for the Lie group solver but I think that the implementation is
buggy.

> Hope this helps. If you or somebody else wants to work on any of these methods, I'll be happy to help.

Anything you can do to help would be great!


Oscar

[Naveen Saisreenivas Thota]

Hi Nijso,

Thank you for the suggestions. Even I have found the Kovacic Algorithm to be difficult to understand since I'm not familiar with differential galois groups. 

> You can also start by writing a solver for first order rational Riccati ODEs, because Kovacic' method is basically telling you how the Liouvillian solution of a second order ODE can be found > by solving a rational Riccati ODE.

Could you suggest any paper for Ricatti ODEs? Would there be enough work for it be a good GSoC project?

> You can also consider implementing a general Lie (symmetry) method to find integrating factors for first order ODEs. It is the most successful first order ODE solver and can solve e.g.      > 90% of the Kamke database of first order ODEs. Such a method can also solve all 'trivial' ODEs like linear, separable, Bernoulli, which sympy cannot all solve. It is more robust because       > symmetry methods does not depend on pattern matching the ODE. Some Lie group methods have been implemented in sympy already which can be a basis to work on. Note that all        > solvable first order ODEs have an integrating factor, and an integrating factor solves the first order ODE.

Which paper would be more useful for SymPy - the lie symmetry methods for 1st order or the lie symmetry methods for 2nd order?

> Hope this helps. If you or somebody else wants to work on any of these methods, I'll be happy to help.

Thanks again. I will definitely ask you for help in case I end up implementing these methods!

Naveen

[Naveen Saisreenivas Thota]

>  I wouldn't say that I know differential Galois theory but reading
> Kovacic's paper and also the Smith paper linked above I thought that I
> was able to follow the algorithm itself and how to implement it. To me
> it looked as if differential Galois theory was needed for the proofs
> but not for the algorithm itself. 

Yes, the Saunders' algorithm doesn't look like it involves Galois theory, but since its quite old, it may not be as fast as newer methods. If we go ahead with this, the only part which could be difficult might be the Laurent series expansion. Does SymPy already have a Laurent Series expansion in the series module? I couldn't find it in the docs. 

> I have seen other more recent papers
> about extensions or modifications of Kovacic's algorithm that did seem
> to be more heavily based on the Galois theory though.

Yes, for instance, I saw this paper - https://www.math.fsu.edu/~hoeij/papers/issac05/f99HoeijWeil.pdf which is a more recent and faster algorithm that involves Galios theory.

Naveen

[nijso.be...@gmail.com]

> How much do you actually need to understand of the theory to make it work?

Sure, you could just implement it based on the maple code from Smith's thesis, that's how I started with my implementation. Most of what you need to do in practice is a lot of manipulation of the analytic solution of the Riccati ODE, which can be written as a finite sum of rational expressions. 

> Could you suggest any paper for Ricatti ODEs? Would there be enough work for it be a good GSoC project?

A note on the Riccati differential equation, W. Yuan:

https://www.sciencedirect.com/science/article/pii/S0022247X0200536X

A good rational Riccati solver would be a nice GSoC project, especially if you want to find all rational solutions and if you want it to be robust and validated. You could also add the Kamke database as a regression test, also for the testing the rest of the ode solvers. There is less time available compared to last year, so you could implement this first as a stand-alone algorithm. Later, the Kovacic method can then just call the Riccati solver. There are also algorithms for finding rational solutions of first order ODEs by solving a Riccati ODE, they could then also use this solver.

Best regards,

Nijso