[Axiom-developer] Re: Axiom' integrator (was: Axiom Volume 1: Tutorial)

[Martin Rubey]

Dear Bill,

> Martin,
> 
> On January 3, 2006 6:49 AM you wrote:
> >...
> >   "... Axiom's integrator gives you the answer when an answer
> >   exists. If one does not, it provides a proof that there is
> >   no answer."
> >
> > on page 2 is simply wrong. (Apart from containing a typo).
> 
> Rather than just state that there is a typo: please, please
> state exactly the error and the correction. 

You're right. In fact, I realize now that there is no typo. I thought that

 "If one does not, " ...

should read

 "If it does not, " ...

but I suppose that the above version is correct English, too. Sorry.

> > Even if read as

> >   ... Axiom's integrator gives you the answer when an answer in terms of
> >   elementary functions exists. If one does not, it provides a proof that
> >   there is no answer.

> > it is not true. The Risch algorithm is not completely implemented in Axiom,
> > unfortunately.

Well. I should have been more careful in my wording: I doubt that the Risch
algorithm is completely implemented in Axiom. I should also have added what you
cited from wikipedia:

> http://en.wikipedia.org/wiki/Risch_algorithm

> "The Risch decision procedure is not formally an algorithm because it
> requires an oracle that decides whether a constant expression is zero, a
> problem shown by Daniel Richardson to be undecidable.

Therefore, the answer to

> If, we can finish the implementation of this algorithm in Axiom,
> then would your re-worded statement above be correct?

is no. Furthermore, Axiom only returns "failed" if the Risch procedure didn't
succeed, which constitutes hardly a proof...

Still, it would be great if we could complete the implementation of the Risch
"algorithm". (Or find out that it is completely implemented anyway.)

> So what "elementary functions" are being considered by Axiom's algorithm?
> E.g. addition, division, exponents, logarithms, multiplication, polynomials,
> radicals, rationals, subtraction, and trigonometric expressions

yes.

> Since it was obviously the intention of the author of Axiom's integration
> algorithm that it completely implement the Risch algorithm and in spite of:
> 
> http://mathworld.wolfram.com/RischAlgorithm.html
 
> "The case of algebraic extensions is quite complicated and is therefore not
> completely implemented in any computer algebra system."
 
> What are the prospects for actually completing this programme in Axiom rather
> than "correcting" the documentation? 

Well, hopefully SumIt will become open source some time -- they
promised. Renaud Rioboo told me that the integrator in SumIt *might* be an
updated version of Axioms integrator... The person in charge with open-sourcing
Manuels code is Stephen Dalmas, I was told. However, he did not respond to my
queries. I don't know why we are so unlucky regarding these Aldor related
things.

> So far we have documented the following cases:
 
> http://wiki.axiom-developer.org/198IntegrateSinX2XIsNotHandled
> 
> http://wiki.axiom-developer.org/199IntegrateExpX2ExpXXX

Both of these are unrelated to the Risch procedure, since the results are not
elementary.

However, INTALG in intalg.spad knows the following errors:

  FAIL0 ==> error "integrate: implementation incomplete (constant residues)"
  FAIL1==> error "integrate: implementation incomplete (non-algebraic
  residues)"
  FAIL2 ==> error "integrate: implementation incomplete (residue poly has
  multiple non-linear factors)"
  FAIL3 ==> error "integrate: implementation incomplete (has polynomial part)"

At least FAIL0 does occur:

http://wiki.axiom-developer.org/SymbolicIntegration

However, I do not know whether the integrals are doable by Risch -- I doubt
that they are. Maybe Richard Fateman can help here. He might also know how to
find out whether the Risch algorithm is completely implemented.

> And we also have Manuel Bronstein's work on
> pmint - The Poor Man's Integrator
 
> It would be wonderful to have this available in Axiom.

Yes. Although the implementation of the Risch algorithm in Axiom seems pretty
good, Axiom's integrator is quite weak in pattern matching and integration of
special functions and the like. So it would be nice to do some work here. If
you have too much spare time, maybe you could try to understand what pmint
does? (Do you have Maple available?)

HOWEVER: I am not an integration expert, and I guess that I would waste my time
trying to work on all parts of Axiom. I think we should rather hire an
integration expert :-)

Martin

PS: Google came up with the following by Bronstein himself, confirming that
there are unimplemented branches. This should go into the documentation, I
suppose:

http://groups.google.com/group/sci.math.symbolic/browse_frm/thread/61795a53c580d892

There is also 

http://www.math.univ-montp2.fr/FODESIT/SemJuin2004/Bronstein/bronstein.pdf

which might shed some light on the subject.