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

Edit detail for RischImplementationStatus revision 1 of 4

1 2 3 4
Editor: test1
Time: 2015/07/03 17:47:43 GMT+0
Note:

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
Schanule 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 preciesely, in the past there were gaps
in transendendtal 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
logaritms 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 rational first
argument and polylogartims.  For exponential integral, error
function and incomplete Gamma function with rational first
argument in theory there is complete algorithm, but current
FriCAS implementations contains several gaps.

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 Schanule 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 preciesely, in the past there were gaps in transendendtal 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 logaritms 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 rational first argument and polylogartims. For exponential integral, error function and incomplete Gamma function with rational first argument in theory there is complete algorithm, but current FriCAS? implementations contains several gaps.