• Kovacic Algorithm Implementation

    From Naveen Saisreenivas Thota@21:1/5 to All on Mon Mar 15 08:45:54 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Nasser M. Abbasi@21:1/5 to Naveen Saisreenivas Thota on Mon Mar 15 10:51:34 2021
    On 3/15/2021 10:45 AM, Naveen Saisreenivas Thota wrote:
    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


    There is collection of Kovacic related papers here

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

    --Nasser

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Naveen Saisreenivas Thota@21:1/5 to All on Mon Mar 15 09:55:10 2021
    Hi Nasser,

    Thanks a lot for sharing those resources!

    Naveen

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From antispam@math.uni.wroc.pl@21:1/5 to Naveen Saisreenivas Thota on Wed Mar 17 13:37:05 2021
    Naveen Saisreenivas Thota <naveensaisreenivas@gmail.com> wrote:
    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?

    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)