56 views

Skip to first unread message

Mar 15, 2021, 11:45:55 AM3/15/21

to

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

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

Mar 15, 2021, 11:51:37 AM3/15/21

to

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

--Nasser

Mar 15, 2021, 12:55:12 PM3/15/21

to

Hi Nasser,

Thanks a lot for sharing those resources!

Naveen

Thanks a lot for sharing those resources!

Naveen

Mar 17, 2021, 9:37:06 AM3/17/21

to

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

Nov 11, 2022, 10:01:01 AM11/11/22

to

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.
>

> 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

"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

Dec 19, 2022, 11:04:34 PM12/19/22

to

>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?
>(I have code which theoretically solves case 3, but it is

>so slow that I was not able to test it).

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu