1.Representation

Multivariate polynomials in functional representation over C are implemented in the class dag_polynomial<C>, defined in dag_polynomial.hpp.

#include <numerix/integer.hpp>
#include <multimix/dag_polynomial.hpp>
…
monomial<> e (vec<nat> (1, 2));
dag_polynomial<integer> x (integer (2), e); // defines the term 2 * x * y^2

An upper bound on the degree can be obtained with degree_bound. Dag polynomials can also be directly constructed from sparse_polynomial<C>.

2.Evaluation

Dag polynomials can be evaluated straightforwardly with the eval function. However for evaluating at several points, it is more efficient to build a straight-line program first as follows:

#include <dag_polynomial.hpp>
…
vector<dag_polynomial<C> > dags= …;
slp_polynomial<C> slp= as_slp (dags);

vector<C> a, b, c,…; // points to evaluate at
vector<C> va= slp (a); // values of dags at a
vector<C> vb= slp (b); // values of dags at b
vector<C> vc= slp (c); // values of dags at c

Straight-line programs are defined in slp_polynomial.hpp.

3.Expansion and sparse interpolation

The expansion of a dag polynomial into a sparse polynomial can be achieved deterministically via the function as_sparse_polynomial.

It is also possible to convert a dag polynomial over integer or rational into functions of type function_2<integer,const vector<C>&,const integer&> by using as_function_modulo. Then the probabilistic sparse interpolation functions of sparse_interpolation.hpp can be used, or, in a simpler way:

dag_polynomial<integer> dag= …
sparse_polynomial<integer> pol;
bool b= pr_set_as_sparse_polynomial (pol, dag);

If b is false, this means that the sparse interpolation algorithm has failed. Otherwise pol contains a candidate that is probable but not guaranteed.