Algorthms for Rational Function Arithmetic Operations

Abstract

Despite recent advances in speeding up many arithmetic and algebraic algorithms plus an increased concern with algorithm analysis, no computing time study has ever been done for algorithms which perform the rational function arithmetic operations. Mathematical symbol manipulation systems which provide for operations on rational functions use algorithms which were initially given by P. Henrici in 1956. In this paper, these algorithms are precisely specified and their computing times analyzed. Then new algorithms based on the use of modular arithmetic are developed and analyzed. It is shown that the computing time for adding and taking the derivative of univariate rational functions is 2 orders of magnitude faster using the modular algorithms. Also, the computing time for rational function multiplication will be one order of magnitude faster using the modular algorithm. The new method is generalized to the multivariate case and extensive empirical results are given. Keywords: Rational functions, modular arithmetic, arithmetic oeprations, algebraic algorithms.