Sparse polynomials

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:

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU General Public License. If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.