Algorithms and Data Structures for Sparse Polynomial Arithmetic

Mohammadali Asadi, Alexander Brandt, Robert H. C. Moir and Marc Moreno Maza
Additional contact information
Mohammadali Asadi: Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada
Alexander Brandt: Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada
Robert H. C. Moir: Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada
Marc Moreno Maza: Department of Computer Science, University of Western Ontario, London, ON N6A 5B7, Canada

Mathematics, 2019, vol. 7, issue 5, 1-29

Abstract: 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).

Keywords: sparse polynomials; polynomial arithmetic; normal form; pseudo-division; pseudo-remainder; sparse data structures (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/5/441/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/5/441/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:5:p:441-:d:232243

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().