This research paper presents two principal results, both of which are algorithms for manipulating polynomials represented by straight-line programs. The first computes the greatest common divisor of a family of multivariate polynomials, and the second finds the reduced numerator and denominator for a given rational function.

The outputs of both algorithms, like their inputs, are themselves straight-line programs. In the following sequence of polynomial representations (in order of increasing generality), this model of representation in some sense belongs in fourth (most general) place: the dense representation, the sparse representation, formulas, and straight-line programs. Both principal algorithms run in random polynomial time for the rationals and finite coefficient fields and return correct results with high probability.

Besides the algorithms themselves, the author presents the important axiomatization of straight-line programs and the time and space complexity of algebraic RAMs. In fact, this development constitutes a major portion of this paper. The paper also includes major revisions of an earlier work of the author’s [1] and is one of a group in which the author considers factorization [2,3], other bounding approaches in his GCD algorithm [4], and MACSYMA implementation of his routines [5]. His result on the reduced numerator and denominator answers Strassen’s question as to the existence of such algorithms [6] in the affirmative.

In addition to the major theorems, some of the corollaries are of interest in their own right. For example, one of the corollaries to the rational function reduction has significance for parallel algebraic processing.

The methods of proof and the tone of the paper are mathematical. Important ingredients include the reductions with high probabilities of arbitrary straight-line polynomials to monic ones and of families of polynomials to two polynomials (in computing GCDs). A Taylor series method is used to find polynomial coefficients, but an alternate approach, which may be more efficient under certain circumstances, is also provided.

Both the methods and the results in this paper seem very interesting and current--so current, in fact, that some last-minute improvements are included in a note added at the proof stage. The effectiveness of this paper would be enhanced, I believe, by the inclusion of some MACSYMA examples. The bibliography is excellent.