Basic Polynomial Algebra Subprograms (BPAS)

The BPAS library provides support for arithmetic operations with polynomials on modern computer architectures. Typical operations are addition, multiplication, division, evaluation and interpolation. The BPAS library also supports polynoial system solving and real root isolation. The code is mainly written in C++ for ease of use, with underlying C for performance. The CilkPlus extension is used in places for parallelism targeting multi-core processors.

Class Overview

Many different ring classes are supplied:

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

Many different polynomal classes are supplied:

• DenseUnivariateIntegerPolynomial (DUZP)
• DenseUnivariateRationalPolynomial (DUQP)
• SparseMultivariateIntegerPolynomial (SMZP)
• SparseMultivariateRationalPolynomial (SMQP)
• SparseUnivariatePolynomial<Ring> (SUP)
• DenseUnivariatePolynomial<Field> (DUP)
• SmallPrimeFieldDistributedDenseMultivariateModularPolynomial (SDMP)
• DistributedDenseMultivariateModularPolynomial (DDMP)

For polynomial system solving, the TriangularSet and RegularChain classes are both templated by a polynomial over a field :

• TriangularSet<Field, RecursivePoly>
• RegularChain<Field, RecursivePoly>

Library Structure

The BPAS library makes use of abstract classes to define the inteface of many common types. Classes which begin with "BPAS" are abstract. Concrete classes then make use of multiple inheritance to satisfy many interfaces. For example, SMQP is both a BPASMultivariatePolynomial and a BPASGCDDomain. Indeed, these both further inherit from BPASRing, leading to diamond inheritance in SMQP.

It is possible that two BPASRing subclasses are incompatible. Consider a RationalNumber and a DenseUnivariateIntegerPolynomial. Operators between these two rings is not well-defined. To restrict BPASRing subclasses to operate polymorphically while also maintaining mathematical compatibility we make use of the "Curiously Recurring Template Pattern" (CTRP) and heavy use of templating.

Moreover, it is advantageous to implement conditional exporting of particular functions. That is, depending on the run-time characteritics of a particular instance, it should provide certain funcionality. For example, consider SparseUnivariatePolynomial<Integer> versus SparseUnivaraitePolynomial<RationalNumber>. The first is a BPASGCDDomain but the second is a BPASEuclideanDomain. To capture that the characteristics of a polynomial change with its coefficeint ring, we implement conditional exporting using introspection and conditional inheritance.

With so much interesting inheritance and templating occuring within the classes of BPAS, each class provides two versions of its class inheritance diagram. The first shows a simplified semantic inheritance diagram, free from excessive templating (in particular, removing the CRTP) and providing a semantic over-view of the class and its interactions with other classes, both contrete and abstract. The second inheritance diagram provides the full picture of inheritance as it is actually programmed, providing a full view of the templating and inheritance of a class.

Questions

Questions, comments, bug reports: bpas <at> scl <dot> csd <dot> uwo <dot> ca