Sparse polynomial representations are used in a number of algebraic manipulation systems, including Altran. This paper discusses the arithmetic operations with sparsely represented polynomials; we give particular attention to multiplication and division. We give new algorithms for multiplying two polynomials, with n and m terms, in time mn log m ;, these algorithms have the property that, in the usual univariate dense case, the algorithm is bounded by mn. Division algorithms are discussed which run in comparable time.
No takes yet. Share an insight, caveat, or question.
S. C. Johnson (1974) studied this question.