Help in understanding risch algorithm

519 Views Asked by At

This is an excerpt from the paper that explains risch algorithm for symbolic integration. I do not understand how do we get to the residue directly and also how does it help us in the integration. Moreover I would be really glad if one could give me the brief idea about what are residues and how do they help us in integrating functions. I hvae some idea but I am not clear about it. Link to the paper.

The remaining integrand has only simple poles, so we proceed by computing the residues at its poles, from which we obtain the logarithmic part of the integral. For an integrand $\frac{a(x)}{b(x)}$ , where a(x) and b(x) are polynomials and b(x) is squarefree, the residue at a root $x_0$ of b(x) is given by $z_0$ := $\frac{a(x)}{b′(x_0)}$ and we get a contribution $z_0$log(x − $x_0$ ) to the integral.

1

There are 1 best solutions below

0
On BEST ANSWER

The residue is computed using the Rothstein-Trager resultant algorithm (there are other ways, but this is the most efficient). Chapter 2 of Bronstein's book is a good reference for this. The basic idea is that if $R = \mathrm{resultant}_x(b(x), a(x) - tb(x))$ ($t$ here is a new indeterminate) at this stage of the algorithm (when $b(x)$ is squarefree), then the roots of R are exactly the residues.

The residues, at least for a rational function, of $\frac{p}{q}$, are those roots of $q$ of multiplicity 1. The idea is if you think of doing a full partial fraction decomposition (i.e., over $\mathbb{C}$) of $\frac{p}{q}$ and integrating, the integral of every term will be a rational function, except for those terms that are of the form $\frac{a}{x - b}$. The integral of those terms will be logarithms.

One of the basic ideas behind the Risch algorithm is that this all generalizes to elementary functions. Under the right generalizations of "simple" and "multiplicity", you can define the residues in a similar way, and they will be exactly the arguments of the parts of the resulting integral that are contained in logarithms. The generalization is non-trivial; among other issues, it is possible that an elementary function not have an elementary antiderivative in the first place.