next up previous
Next: Rothstein-Trager Method Up: HermiteHorowitz, Rothstein, Previous: Algorithm for square-free

Hermite's method

Given , by division we can reduce this as in the classical case to . Now instead of complete factorization of , we compute the square-free factorization:

Now we write


where each has degree less than (which is a much stronger requirement than being less than degree , of course). This is analogous to the familiar partial fraction decomposition where the repeated roots decomposed into .

Now let us consider integration of one of these terms, say where j > 1 (that is, we look at reducing the repeated-root integrations to the simple root case).

Since is square-free, this means that . This means that there exist polynomials s and t with degree s < degree degree , and degree t < degree , such that

These polynomials s and t can be computed by the extended Euclidean algorithm (see Geddes et al. for details).

Thus we may write our term to be integrated as

and after an integration by parts with u = t and , we get

Notice that we have reduced the power of the denominator by 1. Carrying on recursively, we can show that




is square-free (i.e. has only simple roots). I was going to ask you, in your homework, to fill in the details of a method based directly on this formula (5), but the assignment is already large enough. The basic idea is that you can write out the unknown coefficients of and , differentiate the formula, and collect like terms to get m+n equations in m+n unknowns. This avoids the sequence of Hermite reductions and GCD calculations.

Rob Corless
Thu Nov 16 13:46:20 PST 1995