Fast Algorithms for Partial Fraction Decomposition
H. T. Kung, D. M. Tong · SIAM Journal on Computing · 1977
The partial fraction decomposition of a proper rational function whose denominator has degree n and is given in general factored form can be done in $O(n \log^{2}n)$ operations in the worst case. Previous algorithms require $O(n^{3})$ operations, and $O(n \log^{2}n)$ operations for the special case where the factors appearing in the denominator are all linear.