next up previous
Next: Heuristics Versus Algorithms Up: Today's Notes Previous: Today's Notes

Remarks on Last Week

We saw last week that there was a plethora of algorithms to integrate where p and q were polynomials in x.

  1. Classical (real and complex versions), based on complete factorization
  2. Hermite or Horowitz reduction to where is square-free, and we do the last integral by the Rothstein-Trager algorithm:

    where the are the distinct roots of and the are computed by . This algorithm is very impressive.

I remark that all of this is algebraic, and depends heavily on the `rule of logarithms' , which, as we know, is not true analytically. The branch cut problems introduced by this abuse of the rule of logarithms are open problems.

And they get worse in the elementary function case. In some sense we are going to see that the Hermite reduction/ Rothstein-Trager algorithm generalizes nicely to the elementary function case, and this is good in the sense that we will have an algorithm, but it is bad in the sense that we will inherit all the branch cut problems.

Rob Corless
Thu Nov 23 10:59:42 PST 1995