Sparse polynomial arithmetic

S. C. Johnson · ACM SIGSAM Bulletin · 1974

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.

Cited by 67 works. doi:10.1145/1086837.1086847 Open-access PDF

Authors

References