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.

It appears you don't have a PDF plugin for this browser. No biggie... you can click here to download the PDF file.

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, CASC 2021

  • Computational schemes for subresultant chains, 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.

    Questions & Comments

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


  • 2021-05-23: Subresultant chains, parallel power series
  • 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