login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for RischImplementationStatus revision 4 of 4

1 2 3 4
Editor: Oioioioioi
Time: 2020/04/03 05:27:38 GMT+0
Note: grammar and wording cleanup

changed:
-In FriCAS Risch algorithm is split into two stages, preparatory one when integrand
-is rewritten to express it in terms of differential fields and
-the core part.
-
-In first stage FriCAS to have theoretically correct result should
-find transcendental basis of constants needed to express the
-integral.  ATM there is no known algorithm to do this without
-extra assumptions.  For elementary constants assuming that Schanuel
-conjecture is true one can give efficient solution.  FriCAS
-contains code handling transcendental part of this: FriCAS can
-discover algebraic dependencies between transcendental elementary
-functions provided that it can correctly decide if constants
-are zero or not.  For transcendental elementary constants
-FriCAS can discover algebraic dependencies provided that
-Schanuel conjecture is true.  Currently FriCAS does not
-handle dependencies between algebraic expressions (roots
-of polynomials).
-
-Core integrator should be complete for for purely transcendental
-functions.  More preciesly, in the past there were gaps
-in transcendental part.  In 2014 offending code was rewritten
-eliminating all known reasons for incompleteness.
-
-For integrands involving algebraic quantities situation is
-more complicated.  If highest rank kernel is transcendental
-FriCAS still can use main part of transcendental algorithm,
-but there are gaps in auxiliary routines.  More precisely,
-extended integration routine is implemented only in two
-cases, one if algebraic extension is a single root, the
-second is purely algebraic.  Solver for Risch differential
-equation can only handle purely algebraic case.  Logarithmic
-derivative problem is unimplemented in algebraic case.
-
-If highest rank kernel is algebraic than FriCAS can do
-Hermite reduction.  FriCAS can find logarithmic part only
-in purely algebraic case.  Otherwise, if Hermite reduction
-does not solve the integral, then FriCAS can not do it.
-Also, in purely algebraic case there are restrictions
-on the Trager resultant: in general FriCAS can only
-handle case when Trager resultant has a single
-nonlinear factor and in such case FriCAS requires that
-this factor has nonzero coefficient before second highest
-power of indeterminate (so called trace 0 case is excluded).
-
-In case of hitting unimplemented part of Risch algorithm
-FriCAS signals error.  So getting back unevaluated integral
-means that FriCAS claims the integral to be nonelementary.
-
-FriCAS implementation of Risch algorithm contains several
-shortcuts which can solve some integral not handled by
-main part.  Together implemented part and shortcuts cover
-a lot of typical examples of elementary functions, but
-in fact large part of Risch algorithm dealing with
-algebraic extensions remain unimplemented.
-
-In FriCAS Risch algorithm is generalized, so that beside
-logarithms integrand may contain Liovillian functions.
-Transcendental part of Risch algorithm should be complete
-for such functions, but currently in preparatory stage
-FriCAS assumes that all Liouvillian functions are
-algebraically independent.
-
-FriCAS can express integral not only in terms of elementary
-functions but also in terms of exponential integral, error
-function, incomplete Gamma function with and polylogartims.  For exponential integral, error
-function and incomplete Gamma function
-in theory there is complete algorithm, but current
-FriCAS implementations contains several gaps.
In FriCAS the Risch algorithm is split into two stages, a preparatory one
where the integrand is rewritten to express it in terms of differential
fields, and the core part.

In the preparatory stage, to obtain a theoretically correct result, FriCAS
should find a transcendental basis of constants needed to express the
integral. Currently no algorithm is known to achieve this without extra
assumptions. For elementary constants one can give an efficient solution
assuming that the Schanuel conjecture holds. FriCAS contains code handling
the transcendental part of this: it can discover algebraic dependencies
between transcendental elementary functions provided that it can decide
correctly if constants are zero or not. For transcendental elementary
constants, it can discover algebraic dependencies provided that the Schanuel
conjecture holds. FriCAS is currently not equipped to handle dependencies
between algebraic expressions (roots of polynomials).

The core integrator should be complete for purely transcendental functions.
In the past there were gaps in the transcendental part, but the offending
code was rewritten in 2014 to eliminate all known reasons for
incompleteness.

For integrands involving algebraic quantities the situation is more
complicated. If the highest rank kernel is transcendental FriCAS can still
use the main part of the transcendental algorithm, but gaps exist in
auxiliary routines. More precisely, the extended integration routine is
implemented for two cases only: if the algebraic extension involves a single
root, and if the integrand is purely algebraic. The solver for the Risch
differential equation can only handle the purely algebraic case. The
logarithmic derivative problem is unimplemented in the algebraic case.

If the highest rank kernel is algebraic then FriCAS can apply Hermite
reduction. It can find the logarithmic part only in the purely algebraic
case. Otherwise, if Hermite reduction does not already yield the integral,
FriCAS cannot solve it. Also, in the purely algebraic case there are
restrictions on the Trager resultant: in general FriCAS can only handle
resultants having a single nonlinear factor, this factor being moreover
required to possess a nonzero coefficient in front of the second highest
power of the indeterminate (the so called trace-0 case is excluded).

In the case of hitting an unimplemented part of the Risch algorithm, FriCAS
signals an error. So getting back an unevaluated integral means that FriCAS
claims the integral to be nonelementary.

The implementation of the Risch algorithm in FriCAS features several
shortcuts enabling it to solve some integrals not handled by the main part.
The shortcuts together with the implemented part cover many typical examples
of elementary functions, but in fact a large part of the Risch algorithm
dealing with algebraic extensions remains unimplemented.

In FriCAS, the Risch algorithm is generalized so that besides logarithms an
integrand may contain Liouvillean functions. The transcendental part of the
algorithm should be complete for such functions, but in the preparatory
stage all Liouvillean functions are currently assumed to be algebraically
independent.

FriCAS can express an integral not only in terms of elementary functions but
also in terms of exponential integrals, error functions, incomplete Gamma
functions, and polylogarithms. For the exponential integral, error function,
and incomplete Gamma function, a complete algorithm exists in theory, but
the current implementation in FriCAS has several gaps.


In FriCAS the Risch algorithm is split into two stages, a preparatory one where the integrand is rewritten to express it in terms of differential fields, and the core part.

In the preparatory stage, to obtain a theoretically correct result, FriCAS should find a transcendental basis of constants needed to express the integral. Currently no algorithm is known to achieve this without extra assumptions. For elementary constants one can give an efficient solution assuming that the Schanuel conjecture holds. FriCAS contains code handling the transcendental part of this: it can discover algebraic dependencies between transcendental elementary functions provided that it can decide correctly if constants are zero or not. For transcendental elementary constants, it can discover algebraic dependencies provided that the Schanuel conjecture holds. FriCAS is currently not equipped to handle dependencies between algebraic expressions (roots of polynomials).

The core integrator should be complete for purely transcendental functions. In the past there were gaps in the transcendental part, but the offending code was rewritten in 2014 to eliminate all known reasons for incompleteness.

For integrands involving algebraic quantities the situation is more complicated. If the highest rank kernel is transcendental FriCAS can still use the main part of the transcendental algorithm, but gaps exist in auxiliary routines. More precisely, the extended integration routine is implemented for two cases only: if the algebraic extension involves a single root, and if the integrand is purely algebraic. The solver for the Risch differential equation can only handle the purely algebraic case. The logarithmic derivative problem is unimplemented in the algebraic case.

If the highest rank kernel is algebraic then FriCAS can apply Hermite reduction. It can find the logarithmic part only in the purely algebraic case. Otherwise, if Hermite reduction does not already yield the integral, FriCAS cannot solve it. Also, in the purely algebraic case there are restrictions on the Trager resultant: in general FriCAS can only handle resultants having a single nonlinear factor, this factor being moreover required to possess a nonzero coefficient in front of the second highest power of the indeterminate (the so called trace-0 case is excluded).

In the case of hitting an unimplemented part of the Risch algorithm, FriCAS signals an error. So getting back an unevaluated integral means that FriCAS claims the integral to be nonelementary.

The implementation of the Risch algorithm in FriCAS features several shortcuts enabling it to solve some integrals not handled by the main part. The shortcuts together with the implemented part cover many typical examples of elementary functions, but in fact a large part of the Risch algorithm dealing with algebraic extensions remains unimplemented.

In FriCAS, the Risch algorithm is generalized so that besides logarithms an integrand may contain Liouvillean functions. The transcendental part of the algorithm should be complete for such functions, but in the preparatory stage all Liouvillean functions are currently assumed to be algebraically independent.

FriCAS can express an integral not only in terms of elementary functions but also in terms of exponential integrals, error functions, incomplete Gamma functions, and polylogarithms. For the exponential integral, error function, and incomplete Gamma function, a complete algorithm exists in theory, but the current implementation in FriCAS has several gaps.