From: ajung@informatik.uni-rostock.de (Andreas Jung)
Subject: Re: Risch Algorithm
Date: 12 Mar 1999 18:41:40 +0100
Newsgroups: sci.math.symbolic
Keywords: Why isn't the Risch algorithm implemented?

G. A. Edgar (edgar@math.ohio-state.edu.nospam) wrote:
: In article <19990312013001.25053.00001011@ng-cf1.aol.com>, Jemfinch02 <jemfinch02@aol.com> wrote:

: > Why doesn't any CAS implement the full algorithm?

: Axiom claims to, I believe.

But it's only a claim. For at least the following integrals,
the 1996 version of Axiom failed to find out if a symbolic 
integral exists or not, but printed an error message instead:

  integrate(asin(exp(x)), x)
  integrate(acos(exp(x)), x)
  integrate(asin(log(x)), x)
  integrate(acos(log(x)), x)
  integrate(log(1+sqrt(1-q^2*sin(x)^2)), x)

Perhaps, someone can feed these examples into an actual version
of Axiom and tell us if things have changed.

Greetings,
						Andreas Jung.
--
Andreas Gisbert Jung     DL9AAI Tel:0381/498-3364 Fax:0381/498-3366
Theoretische Informatik  mailto:ajung@informatik.uni-rostock.de
Universitaet Rostock     http://www.informatik.uni-rostock.de/~ajung/
PGP fingerprint =  8A 0B 05 CA EE AB 7B 01  D9 07 6A D0 84 38 BB 82
==============================================================================

From: fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman)
Subject: Re: Risch Algorithm
Date: 12 Mar 1999 21:58:48 GMT
Newsgroups: sci.math.symbolic

In article <36e951d4@news.uni-rostock.de>,
Andreas Jung <ajung@informatik.uni-rostock.de> wrote:
>G. A. Edgar (edgar@math.ohio-state.edu.nospam) wrote:
>: In article <19990312013001.25053.00001011@ng-cf1.aol.com>, Jemfinch02 <jemfinch02@aol.com> wrote:
>
>: > Why doesn't any CAS implement the full algorithm?
>
>: Axiom claims to, I believe.
>
>But it's only a claim. For at least the following integrals,

There is a fallacy in claiming the Risch "algorithm" is an
algorithm at all:  it depends, for solution of subproblems,
on heuristics to tell if expressions are equivalent to zero.
It was shown in 1968 or so by Daniel Richardson, that the
zero equivalence problem over a class of expressions including
the Risch target class, is recursively unsolvable.  You
can always tell if a polynomial is identically zero. But you cannot
tell by a uniform algorithm if a rational expression in 1 variable
including exp sin sqrt, composition, pi, +-/, constants is zero.
[I think I got that about right..].

But that is not the problem with most implementations of the
Risch algorithm.  They mostly have not been programmed completely,
because, even assuming you can solve the zero-equivalence problem,
the procedure is hard to program.  Why aren't people pushing
to do this more?...

Another reason is, it is not nearly as useful as you might think,
because it returns algebraic antiderivatives whose validity may
be on a set of measure zero.  It may also, in the vast majority
of problems, simply say, after an impressive pause, nope. can't do it.

Also, most people are interested in definite, not INdefinite integrals,
at least once they've finished with Freshman calculus.

And in cases where approximate solutions are easily obtained 
for the corresponding definite integral, the Risch algorithm
may grind on for a while and then say there is no closed form.

The theory of algebraic integration, and the history of this
problem is interesting, but the connection with computer algebra
systems aimed at solving applied mathematics problems in
complex analysis is not nearly as central as one might think.

  My opinion, anyway.


-- 
Richard J. Fateman
fateman@cs.berkeley.edu   http://http.cs.berkeley.edu/~fateman/