Re: Kovacic Algorithm Implementation

[Naveen Saisreenivas Thota]

Hi all,

I wanted to know which papers are best to implement Kovacic's Algorithm. I have gone through the following papers, but all of them seem to be quite old.

https://www.sciencedirect.com/science/article/pii/S0747717186800104
https://cs.uwaterloo.ca/research/tr/1984/CS-84-35.pdf
https://www.math.fsu.edu/~hoeij/papers/issac05/f99HoeijWeil.pdf

Please suggest some recent papers if there are any. Also, what papers are implemented in CAS' like Maple, Mathematica?

Regards
Naveen

[Nasser M. Abbasi]

There is collection of Kovacic related papers here

https://www.12000.org/my_notes/kovacic_algorithm/index.htm

--Nasser

[Naveen Saisreenivas Thota]

Hi Nasser,

Thanks a lot for sharing those resources!

Naveen

[anti...@math.uni.wroc.pl]

Hoeij&Weil papers is quite good, but you need material also
from earlier papers, about factorization and associated
equations. Also it is good to see:

F. Ulmer, J. A. Weil, Note on Kovacic's algorithm, JSC 22 (1996), 179--200.

Idea to "implement Kovacic's Algorithm" is quite old. Modern trend
is to treat Kovacic's Algorithm as special, easier case of solver
for linear ODE. Basicaly the algorithm is:
- factor operator giving the ODE, this effectively solves a lot
of examples (when factors are of order 1, giving exponential
solutions)
- do little extra computations to recognize monomial case
- compute enough invariants to recognize differential
Galois group, use gathered info to find solutions

Early results in this direction are:

M. F. Singer, F. Ulmer, Galois groups of second and third order
linear differential equations. JSC 16 (1992), 9--36

M. F. Singer, F. Ulmer, Liouvillian and algebraic solutions of second
and third order linear differential equations. JSC 16 (1992), 37--73.

There are also results about equations of order 4, but I do not
know if this is worked out to an algorithm.

Actually, modern trend is to directly handle systems of
linear equations of order 1 (old way was to use cyclic
vector method to get single equation of higher order).
For systems see recent (few years old) papers by Barkatou
and colaborators.

There are also works about going above Liouvillian solutions.

Concerning implementation, you can look at implementation is FriCAS,
in particular:

https://github.com/fricas/fricas/blob/master/src/algebra/kovacic.spad

which implements case 2. Case 1 is handled by general approach
(factorization). Currently case 3 remains unimplemented
(I have code which theoretically solves case 3, but it is
so slow that I was not able to test it). Commercal competiton
probably have better implementation, but main improvements
are not in core algorithm, but in supporting parts, in
particular factorizer for differential operators and
solver for associated equations.

BTW: I do not know of system that fully implements case 3,
namely in case 3 "explicit" result is very large and
Hoeij&Weil suggest using shorthand notation to avoid
dealing with problematic expressions.

--
Waldek Hebisch

[Nasser M. Abbasi]

On Wednesday, March 17, 2021 at 8:37:06 AM UTC-5, anti...@math.uni.wroc.pl wrote:

>
> Concerning implementation, you can look at implementation is FriCAS,
> in particular:
>
> https://github.com/fricas/fricas/blob/master/src/algebra/kovacic.spad
>
> which implements case 2. Case 1 is handled by general approach
> (factorization). Currently case 3 remains unimplemented
> (I have code which theoretically solves case 3, but it is
> so slow that I was not able to test it). Commercal competiton
> probably have better implementation, but main improvements
> are not in core algorithm, but in supporting parts, in
> particular factorizer for differential operators and
> solver for associated equations.
>
> BTW: I do not know of system that fully implements case 3,
> namely in case 3 "explicit" result is very large and
> Hoeij&Weil suggest using shorthand notation to avoid
> dealing with problematic expressions.
>
> --
> Waldek Hebisch

It looks like case 3 is not really needed in practice.

"Analysis and object oriented implementation of the Kovacic algorithm"

https://arxiv.org/abs/2211.00804

It says

"The software was then used to analyze over 3000 differential equations. The
results showed that case one and two combined provided coverage for 99.9% of the ode’s
with 97.36% of the ode’s solved using case one algorithm and 2.54% solved using case 2
algorithm with only 0.1% requiring case 3. Not a single ode was found that required the
use of case three with n = 6 or n = 12."

The software attached in the above link implements all 3 cases using Maple.

But as you said, case 3 can sometimes become very slow as the polynomials
become very large.

--Nasser

[Валерий Заподовников]

>Currently case 3 remains unimplemented
>(I have code which theoretically solves case 3, but it is
>so slow that I was not able to test it).

Where is the code? Git diff for fricas?