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

Bonifacio Castaño, Joos Heintz, Juan Llovet and Raquel Martínez

Mathematics and Computers in Simulation (MATCOM), 2000, vol. 51, issue 5, 497-528

Abstract: 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).

Keywords: Directed acyclic graph; Straight-line program; Evaluation; Arithmetic-boolean circuit; Multivariate polynomial; Mixed representation; Greatest common divisor of multivariate polynomials; Linear recurring sequence (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475499001408
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:51:y:2000:i:5:p:497-528

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().