The Partial Fraction Expansion Problem and Its Inverse
Francis Y. L. Chin · SIAM Journal on Computing · 1977
The partial fraction expansion problem and its inverse are studied and it is shown that these two problems can be solved in $O(N\log^2N)$ steps for those rational functions with N simple poles, $O(N\log N)$ steps for those with a single multiple pole of order N and $O(N\log N(\log n+1))$ steps for the general multiple pole case, where N is the degree of the denominator polynomial and n is the number of distinct poles. We further show that the evaluation of a rational function and its derivatives at a given point can be done more efficiently than previously known. Previous known algorithms for the partial fraction problem and its inverse require $O(n^{2})$ steps.