The Basic Polynomial Algebra Subprograms (BPAS) library provides support for arithmetic operations with polynomials on modern computer architectures, in particular hardware accelerators. Typical operations are polynomial multiplication, multi-point evaluation and interpolation, real root isolation for both univariate and multivariate systems. Its code is written in C++ with CilkPlus extension targeting multi-core processors. BPAS is also available on GitHub.
• Polynomial multiplication and matrix multiplication are at the core of many algorithms in symbolic computation.
• Algebraic complexity is often estimated in terms of multiplication time. At the software level, this reduction to multiplication is also common (Magma, NTL, FLINT, ...).
• BPAS design follows the principle reducing everything to multiplication.

Notice: BPAS continues to go through major revisions. Code may not be stable or backward compatible until the next major release.

### New in 2021

• Power Series: Parallel processing for Hensel's lemma and Weierstrass preparation (submitted to CASC 2021)

• Computational schemes for subresultant chains (submitted to CASC 2021)
• Half-GCD, speculative, modular

### New in 2020

• Power Series: Multivariate Lazy Power Series in C, CASC 2020
• Univariate Polynomials over Multivariate Power Series
• Weierstrass Preparation, Factorization via Hensel's Lemma

• Parallel Fourier-Motzkin Elimination, CASC 2020
• Compiled binary available here.

• RegularChain: triangular decomposition parallelized, ISSAC 2020
• ### New in 2019

• Big Prime Field FFT (ISSAC 2020)
• Fourier-Motzkin Elimination
• ### Exposed BPAS ring classes

• Integer
• RationalNumber
• ComplexRationalNumber
• Fraction
• SmartFraction
• SmallPrimeField
• BigPrimeField
• GeneralizedFermatPrimeField

• DenseUnivariateIntegerPolynomial (also named as DUZP)
• DenseUnivariateRationalPolynomial (also named as DUQP)
• SparseMultivariateIntegerPolynomial (also named as SMZP)
• SparseMultivariateRationalPolynomial (also named as SMQP)
• SparseUnivariatePolynomial<Ring>, taking any BPAS ring as the coefficient type
• DenseUnivariatePolynomial<Field>, taking any BPAS field as the coefficient type
• UnivariateRationalFunction<UnivariatePolynomialOverField, Field>
• SmallPrimeFieldDistributedDenseMultivariateModularPolynomial (also named as SFDDMMP)
• DistributedDenseMultivariateModularPolynomial<Field>
• ### Exposed BPAS triangular set classes

• TriangularSet<Field, RecursivePoly>
• RegularChain<Field, RecursivePoly>
• ZeroDimensionalRegularChain<Field, RecursivePoly>
• ### Nice Features

Polymorphic integration code features exact integration (as a formal sum) and symbolic-numeric integration of both dense and sparse representations of rational functions.

If you have questions or bug reports, please contact bpas <at> scl <dot> csd <dot> uwo <dot> ca.

### News

• 2020-06-15: Multivariate Lazy Power Series
• 2020-04-14: v1.720 documentation update
• 2020-02-07: New build process with CMake
• 2020-02-07: Improved RegularChain and triangular decomposition.
• 2019-02-11: Big prime field FFT
• 2019-02-11: Polyhedral Sets and Fourier-Motzkin elimination.
• 2018-10-18: RegularChain and TriangularSet for polynomial system solving.
• 2018-10-18: Optimized sparse multivariate polynomials over the integers (SMZP).
• 2018-05-07: Move to GCC 6+ from GCC 4.8
• 2018-05-07: Class hierarchy restructuring. Finite fields. High-performace sparse polynomial arithmetic and data structures in SMQP.
• 2016-03-18: Symbolic-numeric integration of rational functions as well as a symbolic-numeric brute-force partial fraction decomposition method are incorporated into BPAS library using MPSolve for numerical rootfinding.
• 2015-08-23: Truncated Fourier transform is implemented as a low-level function.
• 2015-04-13: Sparse univariate polynomial supports for resultant and subresultant chains operations.
• 2015-04-13: GCD and Square Free operations are supported for BPAS univariate polynomials.
• 2014-08-14: BPAS has contributed to Symbolic Integration, thanks to Robert Moir (U. Western Ontario).
• 2014-04-28: BPAS moved from 32-bit to 64-bit arithmetic.
• 2013-11-27: First release was online.

• ORCCA Lab, Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7