About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SYMSAC 1976
Conference paper
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.