Algorithms and Data Structures for Sparse Polynomial Arithmetic

We provide a comprehensive presentation of algorithms, data structures, and implementation techniques for high-performance sparse multivariate polynomial arithmetic over the integers and rational numbers as implemented in the freely available Basic Polynomial Algebra Subprograms (BPAS) library. We r...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2019-05, Vol.7 (5), p.441
Main Authors: Asadi, Mohammadali, Brandt, Alexander, Moir, Robert H. C., Moreno Maza, Marc
Format: Article
Language:English
Subjects:
Algorithms
Arithmetic
Canonical forms
Data structures
Dividing (mathematics)
Experimentation
Hierarchies
Integers
Libraries
Mathematics
Multiplication
Multiplication & division
normal form
polynomial arithmetic
Polynomials
pseudo-division
pseudo-remainder
sparse data structures
sparse polynomials
Subroutines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We provide a comprehensive presentation of algorithms, data structures, and implementation techniques for high-performance sparse multivariate polynomial arithmetic over the integers and rational numbers as implemented in the freely available Basic Polynomial Algebra Subprograms (BPAS) library. We report on an algorithm for sparse pseudo-division, based on the algorithms for division with remainder, multiplication, and addition, which are also examined herein. The pseudo-division and division with remainder operations are extended to multi-divisor pseudo-division and normal form algorithms, respectively, where the divisor set is assumed to form a triangular set. Our operations make use of two data structures for sparse distributed polynomials and sparse recursively viewed polynomials, with a keen focus on locality and memory usage for optimized performance on modern memory hierarchies. Experimentation shows that these new implementations compare favorably against competing implementations, performing between a factor of 3 better (for multiplication over the integers) to more than 4 orders of magnitude better (for pseudo-division with respect to a triangular set).
ISSN:2227-7390
2227-7390
DOI:10.3390/math7050441