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

In this paper we describe a recent computer implementation (the PASCAL program TERA) of a well known Computer Algebra algorithm. The particularity of this implementation consists in the fact that it is based on a special abstract data type, namely that of a directed acyclic graph (DAG) which is of seldom use in Computer Algebra packages. This data type is particularly adapted 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 [F.R. Gantmacher, 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. Jaén, R. Martínez, Computer Science, 1992, pp. 159–165; R. Martínez, Procedimientos de Recurrencia Lineal en Algebra Computacional, PhD Thesis, Depto. de Matemáticas, Universidad de Alcalá de Henares, España, 1992; J. Llovet, R. Martínez, J.A. Jaén, 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 upon that of traditional Computer Algebra Systems (MAPLE and MAGMA in our case).