Representations and Parallel Computations for Rational Functions
Joachim von zur Gathen · SIAM Journal on Computing · 1986
Representations of univariate rational functions over a given base of polynomials are considered, and a fast parallel algorithm for converting from one base representation to another is given. Special cases of this conversion include the following symbolic manipulation problems: Taylor expansion, partial fraction decomposition, Chinese remainder algorithm, elementary symmetric functions, Padé approximation, and various interpolation problems. If n is the input size, then all algorithms run in parallel time $O(\log ^2 n)$ and use $n^{O(1)} $ processors. They work over an arbitrary field.