Browse Prior Art Database

Unordered Sparse Polynomial Arithmetic Algorithms

IP.com Disclosure Number: IPCOM000087009D
Original Publication Date: 1976-Nov-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 36K

Publishing Venue

IBM

Related People

Gustavson, FG: AUTHOR [+2]

Abstract

Some sparse polynomial arithmetic operations (+,-, and *) are more efficiently performed by the method described below.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 3

Unordered Sparse Polynomial Arithmetic Algorithms

Some sparse polynomial arithmetic operations (+,-, and *) are more efficiently performed by the method described below.

Arithmetic operations on sparse polynomials are considered. Ordered sparse polynomial representations are unnecessary for some operations, namely addition, subtraction, and multiplication. The use of unordered polynomial representations leads to practical algorithms which achieve the expected minimum complexity bounds--m+n for "+/-" and mn for "*". Two important concepts in the derivation of these fast algorithms are (1) unordered merge and
(2) indirect addressing. Extending these concepts to the case of ordered polynomial representations, it is possible to improve the bound for the multiplication algorithm of S. C. Johnson (*) to 0(mn) 0(min(p log n,P)), where p is the number of terms in the product and P is its degree. Suppose two univariate polynomials (

(Image Omitted)

), are given where the Alpha(i) and Beta(i) are unordered. It is assumed that these polynomials will never have exponents greater than some upper limit L and that a full vector X of size L is initially set to zero.

To Compute (

(Image Omitted)

), it is assumed that n </- m; if not, reverse the role of f and g. In the ADD algorithm to follow, f is first copied in X; the sparse copy of X remains in f.

Next g is compared with f for exponent equality. When equality occurs, the g and f terms are added together in X; otherwise the g term is copied into s(x), the sum. Note that this term cannot cancel. Finally, f is passed over again to look for cancellation, X is set back to zero, and the rest of the sum, s(x), is put away. Addition Algorithm

(Image Omitted)

Multiplication is equally simple. Again assume m</-n. Besides X, a vector XS (a sparse copy of X) and a sc...