Sparse polynomial arithmetic

1 August 1974

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGSAM Bulletin

Vol. 8 (3) , 63-71
https://doi.org/10.1145/1086837.1086847

Abstract

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.

Keywords

DIVISION ALGORITHM
ALGEBRAIC MANIPULATION SYSTEM
TIME MNLOGM
SPARSE POLYNOMIAL REPRESENTATION
NEW ALGORITHM
USUAL UNIVARIATE DENSE CASE
SPARSE POLYNOMIAL ARITHMETIC
ARITHMETIC OPERATION
SECTION O: INTRODUCTION A UNIVARIATE POLYNOMIAL OF DEGREE D IN AN IN- DETERMINATE X IS USUALLY REPRESENTED AS D ~AI XI
M TERM
PARTICULAR ATTENTION
COMPARABLE TIME

This publication has 1 reference indexed in Scilit:

An algebra system
The Computer Journal, 1970