Arithmetic complexity of unordered sparse polynomials

Abstract

In this paper, we show that addition and subtraction of unordered sparse polynomials can be done in time m+n and multiplication in time m+n. So we see already that if a particular sequence of polynomials computation involves a combination of these arithmetic operations as well as tests for equivalence or zero while intermediate expressions are not important enough to be displayed, then the unordered representation could amount to substantial savings in computation time. The visual demand of human users can still be satisfied at the cost of a single sort of the final answer as opposed to sorting each intermediate result in the case of ordered representations.