Sources for Download

Installation Guide


- Linux systems, i.e. Ubuntu
- GCC version 4.8.* so as to compile CilkPlus programs
- GMP library version 5.1.* or later with C++ support
- MPSolve version 3.1.4

Shell configuration (with bash)

The following environment variables and directory pathes must be added in order to compile and run the BPAS library.

- library path: - include path: Run "source ~/.bashrc" once it is done.


- tar -zxvf bpas_src.tar.gz
- cd BPAS
- make

Note: "make" contains a sanity test to check whether BPAS library is installed successfully.
          Run "make test" to execute the sanity test only.
          Run "make serial" to build serial BPAS library with a sanity test.

Building a BPAS application with g++ compiler

- compiling:

-fcilkplusCilkPlus flagrequired
-DLINUXINTEL64=1 Modpn 64-bit mode required
-DBPASDEBUG=1BPAS debug mode optional

- linking:

-lgmpxx -lgmpGMP libraryrequired
-lcilkrtsCilkPlus library required
-lmodpnLINUXINTEL64Modpn libraryrequired
-lmps -lpthreadMPSolverequired
-lbpas BPAS libraryrequired

Real root isolation examples: examples.zip

We provide some examples, that is, the input files in "examples.zip", for univariate and multivariate real root isolation.

To run those examples:
- Put the "examples" folder under the same directory as "BPAS" folder
- cd BPAS/tests/RealRootIsolation
- make univariate (executing univariate cases) or make multivariate (executing multivariate cases)

A Simple Example

In main.cpp:
#include <bpas.h>

int main(int argc, char *argv[]) {
    int d = 4095;
    DUZP a(d+1), b(d+1);
    // Assigning random coefficients to a and b
    gmp_randclass r (gmp_randinit_default);
    for (int i = 0; i <= d; ++i) {
            a.setCoefficient(i, r.get_z_bits(d));
            b.setCoefficient(i, r.get_z_bits(d));
    /* Univariate Integer Polynomial Multiplication */
    DUZP c = a * b;
    std::cout << "c = " << c << std::endl;

    /* Univeriate Real Root Isolation */
    DUQP p;
    p = ((p + mpq_class(1)) << 2) - mpq_class(2);  // p := x^2-2
    mpq_class width(1, 20);
    Intervals boxes = p.realRootIsolate(width);
    std::cout << "boxes = " << boxes << std::endl;

    /* Conversion Between Polynomial Classes */
    SMQP x("x"), y("y"), q(2);                     // q := (x+1)*y^4-2*x*y^2+3*x^2+1
    q = (x + mpq_class(1)) * (y^4) -  mpq_class(2) * x * (y^2)  + mpq_class(3) * (x^2) + mpq_class(1);
    SparseUnivariatePolynomial<SMQP> s = q.convertToSUP("x");
    SMQP z (s);
    if (z != q) 
        std::cout << z << " & " << q << " should not differ " << std::endl;

    /* Real Root Isolation of a Regular Chain */
    string xs[] = {"y", "x"};
    RationalRegularChain rc(2, xs);
    rc += p;
    rc += q;
    Intervals mpIs = rc.realRootIsolate(width);

    /* Symbolic Integration */
    SparseUnivariatePolynomial<RationalNumber> f, g;
    f.one(); f.setVariableName("x");
    g = (polymomialParser("1+2*x+2*x^2"))^4;
    UnivariateRationalFunction<SparseUnivariatePolynomial<RationalNumber>, RationalNumber> h (f, g);

    return 0;
Its Makefile:
CILKPP  = g++
LIBARG  = -lbpas -lgmpxx -lgmp -lcilkrts -lmodpnLINUXINTEL64 -lmps -lpthread
COMPILEARG = -c -O2 -g -fcilkplus -DLINUXINTEL64=1
TARGET  = main

all: $(TARGET)

$(TARGET): main.o 
        $(CILKPP) -o $@ $^ $(LIBARG)

main.o: main.cpp
        $(CILKPP) $(COMPILEARG) $<

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