1.Representation

Multivariate polynomials in sparse representation over C with monomials of type Monomial are implemented in the class sparse_polynomial<C,Monomial,V>, defined in sparse_polynomial.hpp. The default variant sparse_polynomial_naive assumes that C is a field, not necessarily commutative, and it implements the naive algorithms.

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

The internal representation is a vector of pairs of non zero coefficients and monomials. The bracket operator [] is overloaded to access either the -th term of type pair<C,Monomial>, or to retrieve the coefficient of a monomial given in argument.

The support of a sparse polynomial, of type vector<monomial<M> > is obtained thanks to the function supp.

2.Sparse interpolation

Let C be one of the two types integer or rational, and let be a polynomial function from C to C. Let fun be an instance of type function_2<integer,const vector<C>&,const integer&>, where function_2 is defined in basix/function.hpp, and such that computes modulo , where v is a vector of size . Of course if involves a division by zero then fun can raise an error. If has a total degree known to be at most d, then one can try to construct its sparse representation from by calling the function pr_set_as_sparse_polynomial as follows:

#include <multimix/sparse_interpolation.hpp>
…
integer f_modulo (const vector<integer>& v, const integer& p) {
  …
  // return f (v) mod p
}
function_2<integer,const vector<integer>&,const integer&> fun (f_modulo);
sparse_polynomial<integer> pol;
bool b= pr_set_as_sparse_polynomial (pol, fun, n, d);

This conversion is probabilistic and the result is never guaranteed. If the returned value is false this means that the interpolation process has failed. Otherwise the found candidate is returned in pol.

Sparse interpolation is still work in progress. Verbosity and profiling information can be obtained by setting the following global boolean variables to true: sparse_interpolation_debug and sparse_interpolation_profile.

3.Implementation variants

The following implementation variants are available:

• Blockwise algorithms are implemented in sparse_polynomial_dicho.hpp.

• Kronecker substitution, hence reduction to dense representation is available from sparse_polynomial_dense.hpp.

• A cache oblivious product is implemented in sparse_polynomial_oblivious.hpp.

• When the exponents are rather small they can be packed into machine integers for the sake of performances. This is programmed in sparse_polynomial_packed.hpp.

• For very large polynomials, fast FFT based products are available from the file sparse_polynomial_fast.hpp.

• Product via Chinese remaindering on coefficients is in sparse_polynomial_crt.hpp.

• Dedicated variants are available to double, floating, integer, rational, and modular integers.