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.
### New in 2021

### New in 2020

Power Series: Multivariate Lazy Power Series in C, **CASC 2020**

Parallel Fourier-Motzkin Elimination, **CASC 2020**

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

### Questions & Comments

- 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.

- 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

- Univariate Polynomials over Multivariate Power Series
- Weierstrass Preparation, Factorization via Hensel's Lemma

- Compiled binary available here.

- A stand-alone system solver is available in contrib/BPAS_Solver

- Relies on Flint 2 for linear algebra and CDD Library

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.

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