From: rittri@cs.chalmers.se (Mikael Rittri)
Newsgroups: sci.math
Subject: Symbolic integration: summary of answers
Date: 1 Oct 92 11:49:04 GMT
Organization: Dept. of CS, Chalmers, Sweden

Thanks for all replies on symbolic integration of elementary functions. 
I got very useful advice from 
	Dave Gladstein, daveg@icad.COM;
	Michael Greenwald, michaelg@CS.Stanford.EDU;
	Mike Hotchin, mhotchin@microsoft.com;
	Wolfram Koepf;
	Daniel Polani, polani@informatik.mathematik.uni-mainz.de;
	Kelly Roach, roach@wri.com;
	Arno Siebes, Arno.Siebes@cwi.nl;
	Don Taylor, dont@klic.rain.com;
and I will give a summary of their replies. 
The majority of replies has pointed to the Risch algorithm, which 

  *) is described (at least partially) in the book
	  J. H. Davenport, Y. Siret, and E. Tournier,
	  Computer Algebra: Systems and algorithms for algebraic computation,
	  Academic Press, London, 1988, ISBN 0-12-204230-1.
	  Originally published in French by Masson, Paris.
     (thanks to Kelly Roach, Wolfram Koepf, Daniel Polani, and Dave Gladstein) 

  *) "will either provide the answer, or PROVE that no analytic
      answer exists"  (Mike Hotchin) 

  *) "Unfortunately the complexity of the algorithm is considerable,
     so you will perhaps look for a simplified version"  (Daniel Polani).

I have found the book by Davenport et al., and it looks like a very nice
introduction to symbolic computation, with lots of pointers to the 
literature.  I think it will be a good source for the student I am
supervising.  
     Two of the replies suggested some earlier work: 

*)"If you are interested in reading an historically interesting piece,
   see Slagle's PhD thesis (early 60's, MIT [?], James Slagle).  Many 
   computer science libraries should have it.  For more modern (and more
   complete) work, look in your index for the Risch algorithm --- that
   should lead to some useful references."  
		(Michael Greenwald) 

   According to Davenport et al., Slagle's thesis is:
	  James Slagle, 
	  A Heuristic Program that Solves Symbolic Integration
	  Problems in Freshman Calculus,
	  Ph.D. Dissertation,
	  Harvard U., Cambridge, Mass., USA, May 1961.

*)"Davenport, Siret & Tournier's ``Computer Algebra'' might be a place to
   start looking.  If Stephen Wolfram doesn't say anything, you could ask
   him directly about what goes on in Mathematica.
       Back in the late 70's a Russian came up with an algorithm which (if 
   I remember correctly) was supposed to produce an antiderivative if there
   was one, or say so if not.  It was published in one of the Nauka i
   Technika journals which was then translated into English and published
   under a different name.  I'm sorry I'm so vague, but it's been a
   while.
       I asked Wolfram about Mathematica's integrator, and he said the one
   they use is better than the one I mentioned.  (Actually he maintained
   that the algorithm I was thinking of was invented by an American...).
   In any case it might be interesting to unearth the Russian guy's
   algorithm.  If it has defects like running in exponential time, it
   might be easier to implement than some of the more modern algorithms."
		(Dave Gladstein)

Again, many thanks to all who replied.

-- Mikael Rittri (rittri@cs.chalmers.se)
Newsgroups: sci.math,rec.puzzles,comp.theory