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, Pade approximation, and various interpolation problems. If n is the input size, then all algorithms run in parallel time O(log/sup 2/ n) and use n/sup O(1)/ processors. They work over an arbitrary field.
['Joachim von zur Gathen']
Representations and parallel computations for rational functions