Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: If Integrate returns no result, can we conclude that no closed-form

• To: mathgroup at smc.vnet.net
• Subject: [mg87793] Re: [mg87759] If Integrate returns no result, can we conclude that no closed-form
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Wed, 16 Apr 2008 22:35:07 -0400 (EDT)
• References: <200804161052.GAA29333@smc.vnet.net>

You are right that all computer algebra systems that perform 
indefinite integration use the Risch algorithm (arguably misnamed 
since Risch's original work in 1968 dealt chiefly with the easier part 
of the algorithm, and others such as Liouville, Hermite, Hardy and 
Ritt earlier and Davenport, Trager and others later, contributed at 
least as much).

A completely implemented Risch algorithm will either return an 
explicit answer for an integral that can be evaluated in terms of 
elementary functions or determine that no such answer can be given.

The Risch algorithm consists of two parts. The first deals with so 
called "transcendental elementary functions". This is the easy part 
and is very similar to the Hermite's method of integrating arbitrary 
rational functions (a part of which is taught in calculus courses). 
However, the second part, which deals with algebraic functions is much 
harder and uses some quite advanced computational algebraic geometry.

As far as there is no complete implementation of the Risch algorithm 
in any CAS. Anyway, this was sure about 10 years ago and I doubt that 
anything has changed since then (but would not stake my life on that). 
The problem lies, of course, with the part involving computational 
algebraic geometry. Algorithms in computational algebraic geometry are 
often  very hard to implement (and the number of people who understand 
them and can program at the professional level and also have the time 
that would be needed for this is surely rather limited). As a result I 
believe there are certain "branches" of the Risch algorithm where some 
kind of "heuristics" are used instead of the algorithm itself.

I have no idea will happen if the Mathematica implementation gets into 
one of such branches. One possibility,of course, it that the heuristic 
method will work anyway and you will get an answer (possible a wrong 
one;-)). Or the thing may just run for ever. I doubt that it will just 
admit defeat and return the integral unevaluated. I think it is fairly 
safe to assume that if an indefinite integral is returned unevaluated 
than it can't be integrated in terms of elementary functions. But 
this, of course, is only mere speculation.

Andrzej Kozlowski




On 16 Apr 2008, at 19:52, Szabolcs Horv=E1t wrote:
>
> The documentation says:
>
> "In the most convenient cases, integrals can be done purely in terms 
> of
> elementary functions such as exponentials, logarithms and 
> trigonometric
> functions. In fact, if you give an integrand that involves only such
> elementary functions, then one of the important capabilities of
> Integrate is that if the corresponding integral can be expressed in
> terms of elementary functions, then Integrate will essentially always
> succeed in finding it."
>
> http://reference.wolfram.com/mathematica/tutorial/IntegralsThatCanAndCannotBeDone.html
>
> How precise is this?  Can one rely on this information?  Is it really
> true that if Mathematica cannot integrate an expression made up of
> elementary functions, then no closed-form result exists?
>
> Szabolcs
>
> (P.S. I do not know how Integrate works.  I heard that CASs use a
> so-called "Risch-alogrithm", but there is relatively little 
> information
> about this on the web (except in academic papers, most of which expect
> the reader to be familiar with the topic).)
>

• Follow-Ups:
  • Re: Re: If Integrate returns no result, can we conclude that no closed-form
    • From: "Matthias Bode" <lvsaba@hotmail.com>

• References:
  • If Integrate returns no result, can we conclude that no closed-form
    • From: Szabolcs Horvát <szhorvat@gmail.com>