On the data structure straight-line program and its implementation in symbolic computation

In this paper we describe a recent computer implementation (the PASCAL prog ram TERA) of a well known Computer Algebra algorithm. The particularity of this implementation consists in the fact that it is based on a special abst ract data type, namely that of a directed acyclic graph (DAG) which is of s eldom use in Computer Algebra packages. This data type is particularly adap ted to the algorithmic problem which we are considering in this paper: the computation of the of two multivariate polynomials. This task is solved by an algorithmic approach based on linear recurring sequences (see [ER. Gantm acher, The Theory of Matrices, vol. 1/2, Chelsea, New York, 1959; R. Sendra , J. Llovet, Journal of Symbolic Computation 13 (1992) 25-39; J. Llovet, R. Sendra, J.A. Jaen, R. Martinet, Computer Science, 1992, pp. 159-165; R. Ma rtinet, Procedimientos de Recurrencia Lineal en Algebra Computacional, PhD Thesis, Depto. de Matematicas, Universidad de Alcala de Henares, Espana, 19 92; J. Llovet, R. Martinet, J.A. Jaen, Journal of Computational and Applied Mathematics 49 (1993) 145-152]). An experimental study shows that the time and memory space performance of the TERA program improves significantly up on that of traditional Computer Algebra Systems (MAPLE and MAGMA in our cas e). (C) 2000 IMACS/Elsevier Science B.V. All rights reserved.