> <\body> Multivariate polynomials in sparse representation over with monomials of type are implemented in the class C,Monomial,V\>|mmx::sparse_polynomial>, defined in |multimix/sparse_polynomial.hpp>. The default variant |mmx::sparse_polynomial_naive> assumes that is a field, not necessarily commutative, and it implements the naive algorithms. <\cpp-code> #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 C,Monomial\>, or to retrieve the coefficient of a monomial given in argument. The support of a sparse polynomial, of type monomial\M\ \> is obtained thanks to the function |vector\ Monomial \ mmx::supp(const sparse_polynomial\ C, Monomial, V \ &p)>. Let be one of the two types or , and let be a polynomial function from > to . Let be an instance of type integer,const vector\C\&,const integer&\>, where is defined in , and such that > computes |)>> modulo , where is a vector of size . Of course if involves a division by zero then can raise an error. If has a total degree known to be at most , then one can try to construct its sparse representation from > by calling the function |bool mmx::pr_set_as_sparse_polynomial(sparse_polynomial\ C, monomial\ M \, V \ &pol, const function_2\ integer, const vector\ C \ &, const integer & \ &f, nat n, const integer &d)> as follows: <\cpp-code> #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 this means that the interpolation process has failed. Otherwise the found candidate is returned in . Sparse interpolation is still work in progress. Verbosity and profiling information can be obtained by setting the following global boolean variables to : |mmx::sparse_interpolation_debug> and |mmx::sparse_interpolation_profile>. The following implementation variants are available: <\itemize> Blockwise algorithms are implemented in |multimix/sparse_polynomial_dicho.hpp>. Kronecker substitution, hence reduction to dense representation is available from |multimix/sparse_polynomial_dense.hpp>. A cache oblivious product is implemented in |multimix/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 |multimix/sparse_polynomial_packed.hpp>. For very large polynomials, fast FFT based products are available from the file |multimix/sparse_polynomial_fast.hpp>. Product Chinese remaindering on coefficients is in |multimix/sparse_polynomial_crt.hpp>. Dedicated variants are available to , , , , and modular integers. . If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.> <\initial> <\collection>