Sparse polynomial arithmetic
SC Johnson - ACM SIGSAM Bulletin, 1974 - dl.acm.org
SC Johnson
ACM SIGSAM Bulletin, 1974•dl.acm.orgSparse 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.
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.
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 mnlogm;, 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.