Univariate polynomials are derived from the vectors. They have a multiplication, a degree and are print function using the variable x. Here is an example of a definition of univariate polynomials, with coefficients modulo $31$

 typedef UPolDse<Z<31> > upol_t;

The internal representation is an array of all the coefficients of the polynomials, up to its degree. This type can be used, once the following files have been included:

#include <synaps/arithm/Zp.h> //modular arithmetic
#include <synaps/upol.h> //univariate polynomials

A polynomial can be constructed from an array of coefficients or parsed from a string:

 upol_t p("x^3-34*x+23");

which yields the polynomial:

$p \assign x_{}^3 + 28 x_{} + 23$

For univariate polynomials, the variables $x_0$ and $x$ are equal. The natural operations of polynomials are available. For instance,

 upol_t q= p*p;
 p += upol_t("4*x+32");
 upol_t r = q%p;
 Z<31> v =q(Z<31>(1)), w= q[2];

yields:

$\begin{eqnarray*} q & \assign & x^6 + 28 x^4 + 15 x^3 + 9 x^2 + 17 x + 2\\ p & = & x^3 + x + 24\\ r & \assign & 16 x^2 + 8 x + 1\\ v & \assign & 7\\ w & \assign & 9 \end{eqnarray*}$

Notice that the operator % compute the remainder of the Euclidean division if the leading term is invertible (here it is the case since 31 is prime). The quotient is given by the operator /. For more details on the available operators see synaps/upol/UPolDse.h.

#include <synaps/arithm/Zp.h>
#include <synaps/upol.h>
typedef UPolDse< Z<31> > upol_t;

int main(int argc, char** argv) 
{
  using std::cout;
  using std::endl;

  upol_t p("x^3-34*x+23");
  cout<< p <<endl;
  upol_t q = p*p;
  cout<< q <<endl;
  p += upol_t("4*x+32");
  cout<< p <<endl;
  upol_t r = q%p;
  cout<< r <<endl;
  Z<31> v = q(Z<31>(1));
  cout<< v <<endl;

}

Exercise: Build a function which compute the companion matrix of a univariate polynomial with double coefficients and which output its eigenvalues (using the internal representation lapack::rep2d<double>) $\boxdot$

Exercise: Build a function Wilkinson which given $n$ computes $W_n (x) = \prod_1^n (x - i) \in \mathbbm{Q}[x]$ $\boxdot$

Instead of using the monomial basis, one might be interested by using coefficients in another basis, eg. the Bernstein basis. In order to manipulate such representations, one has only to change the container:

 typedef UPolDse<double, bezier::rep1d<double> > upolb_t;

and to provide the needed functions (access and specialisation of the algebraic operations) on this container:

#include <synaps/upol/bezier/rep1d.h>

Here is an example of computation, where the internal representation is the array of coefficients of the polynomial in the Bernstein basis on the interval $[0, 1]$

 upolb_t b1("x^2+1"), b2("x"), b3;
 VECTOR::print(cout,b1)<<endl; //b1 printed as a vector of coefficients
 VECTOR::print(cout,b2)<<endl; //b2 printed as a vector of coefficients
 b3 = b1*b2;
 VECTOR::print(cout,b3)<<endl; //b3 printed as a vector of coefficients

It yields:

$\begin{eqnarray*} & [1, 1, 2] & (\tmop{coefficients} \tmop{of} b_1 \tmop{in} \tmop{the} \tmop{Bernstein} \tmop{basis} \tmop{on} [0, 1])\\ & [0, 1] & (\tmop{coefficients} \tmop{of} b_2 \tmop{in} \tmop{the} \tmop{Bernstein} \tmop{basis} \tmop{on} [0, 1])\\ & b_3 \assign x^3 + x & \\ & [0, 0.333333, 0.666667, 2] & (\tmop{coefficients} \tmop{of} b_3 \tmop{in} \tmop{the} \tmop{Bernstein} \tmop{basis} \tmop{on} [0, 1]) \end{eqnarray*}$

Notice that even if the coefficients of $b_1$ and $b_2$ are integers, the coefficients of $b_3$ are not. {{When we use the Bernstein representation, the coefficient type of UPolDse should be a field type}}.

#include <synaps/init.h>
#ifdef SYNAPS_WITH_GMP
#include <synaps/arithm/Zp.h>
#include <synaps/upol.h>
#include "synaps/arithm/gmp.h"
#include <synaps/upol/bezier/rep1d.h>

typedef UPolDse<double, bezier::rep1d<double> > upolb_t;



int main(int argc, char** argv) 
{
  using std::cout;
  using std::endl;

  upolb_t b1("x^2+1"), b2("x"), b3;
  VECTOR::print(cout,b1)<<endl;
  VECTOR::print(cout,b2)<<endl;
  b3 = b1*b2;
  cout <<b3<<endl;
  VECTOR::print(cout,b3)<<endl;

} 
#else
int main(int argc, char** argv) {}
#endif //SYNAPS_WITH_GMP

Multivariate distributed polynomials

Multivariate polynomials are represented by a list of sorted monomials, which are defined by for the coefficients of type C and exponents of type E. The order in which the monomials are stored in the list is a parameter of the multivariate polynomial type. A usual declaration of multivariate polynomials with big integer is:

 typedef MPol<QQ> mpol_t;

This type can be used, once the following files have been included:

#include <synaps/arithm/gmp.h> //big numbers
#include <synaps/mpol.h>       //multivariate polynomials

The previous definition corresponds to the actual type:

 typedef MPol<QQ,DegLex,std::list<Monom<ZZ,dynamicexp<unsigned> > > > mpol_t;

where

DegLex is the class implementing the degree-lexicographic order,

std::list<Monom<QQ,dynamicexp<unsigned> > > is the container type, for the multivariate polynomials.

Monom<QQ,dynamicexp<unsigned> > is the monomial type, implemented as a coefficient of type QQ (rational numbers) and an array of exponents dynamicexp<unsigned>.

The multivariate polynomials MPol<C,O,R> are parameterised by the coefficient type C, the order class O and the \ container type R. For more details on this class, see synaps/mpol/MPol.h .

They share, with the univariate polynomials, algebraic operators such as addition, multiplication, ... They can also be constructed from strings. The following examples

 mpol_t a("x1^2*x0+2*x1+3;"), b("x1^2+123*x2;"); 
 a *= b;

yields

$\begin{eqnarray*} a & \assign & x_0 x_1^2 + 2 x_1 + 3\\ b & \assign & x_1^2 + 123 x_2\\ a & = & x_0 x_1^4 + 123 x_0 x_1^2 x_2 + 2 x_1^3 + 3 x_1^2 + 246 x_1 x_2 + 369 x_2 \end{eqnarray*}$

Iterators are available to scan a multivariate polynomial, as it is illustrate now:

 VECTOR::print(cout,a)<<endl;
 for(mpol_t::iterator it =a.begin(); it !=a.end();it++) cout<< it->coeff()<<" ";
 cout<< endl;
 for(mpol_t::iterator it =a.begin(); it !=a.end();it++) it->coeff()*=it->coeff();
 cout<< a <<endl;

yields

$[x_0 x_1^4, 123 x_0 x_1^2 x_2, 2 x_1^3, 3 x_1^2, 246 x_1 x_2, 369 x_2]$

(that is the list of monomials printed as a vector of monomials)

$1 123 2 3 246 369$

(that is the list of coefficients of the monomials)

$\begin{eqnarray*} a & = & x_0 x_1^4 + 15129 x_0 x_1^2 x_2 + 4 x_1^3 + 9 x_1^2 + 60516 x_1 x_2 + 136161 x_2 \end{eqnarray*}$

(that is the polynomial with the coefficients squared).

#include <synaps/init.h>
#ifdef SYNAPS_WITH_GMP
#include "synaps/arithm/QQ.h"
#include "synaps/mpol.h"
typedef MPol<QQ>   mpol_t;

int main(int argc, char** argv) 
{
  using std::cout;
  using std::endl;

  mpol_t a("x1^2*x0+2*x1+3"), b("x1^2+123*x2");
  a *= b;
  cout<<a<<endl;
  VECTOR::print(cout,a)<<endl;
  for(mpol_t::iterator it=a.begin(); it !=a.end(); it++)
    cout<<it->coeff()<<" ";
  cout<<endl;
  for(mpol_t::iterator it =a.begin(); it !=a.end();it++)
  it->coeff()*=it->coeff();
  cout<<a<<endl;

} 
#else
int main(int argc, char** argv) {}
#endif //SYNAPS_WITH_GMP

Exercise: Build a function which reduces a polynomial by another according to their leading terms. Test it with $a = 2 x_0^3 x_1 - 34 x_{0^{}}^2 + 23$ and $b = 3 x_0^2 - 1$ . Compare with different types of coefficients QQ, double, Zp, ... Make your first implementation more robust $\boxdot$

Exercise: Define a function shifteval which given a multivariate polynomial $f$ (s,t) (with $x_0 = s, x_1 = t$ and a value $v_0$ of type double, compute the mutlivariate polynomial $f (u, v_0)$ (with $x_2 = u$ ) $\boxdot$

Multivariate dense polynomials

In some cases such as when using Bernstein basis, it is interesting to store all the coefficients of the polynomial, without storing the exponents, which are implicitely deduced from the representation. Only an array of coefficients and partial degrees in the variable are sufficient to recover the polynomial. This is what the class MPolDse provides, once the following include directive is used:

#include <synaps/mpol/MPolDse.h>

We need a new interface (not just a new container) since the concept of exponents is not attached to this class. Here are some examples, using the Bernstein basis:

 #include <synaps/arithm/gmp.h>
 typedef MPolDse<QQ, MPOLDSE::bernstein<QQ> > mpolb_t;

The following instructions

 mpolb_t A("x1^2*x0+2*x1+3"), B("x0+x1+1"), C=A*B; 
 VECTOR::print(cout,A.rep())<<endl;
 VECTOR::print(cout,B.rep())<<endl;
 VECTOR::print(cout,C.rep())<<endl;

yields:

$\begin{eqnarray*} & & [3, 3, 4, 4, 5, 6]\\ & & [1, 2, 2, 3]\\ C & \assign & x_0^2 x_1^2 + x_0 x_1^3 + x_0 x_1^2 + 2 x_0 x_1 + 2 x_1^2 + 3 x_0 + 5 x_1 + 3\\ & & [3, \frac{14}{3}, 7, 10, \frac{9}{2}, \frac{13}{2}, \frac{28}{3}, \frac{27}{2}, 6, \frac{25}{3}, 12, 18] \end{eqnarray*}$

{{Here also, the coefficient type of MPolDse should be a field type, when we use the Bernstein representation}}.

The default construction

 typedef MPolDse<double> mpold_t;

is using the monomial basis.

#include <synaps/init.h>
#ifdef SYNAPS_WITH_GMP
#include "synaps/arithm/gmp.h"
#include "synaps/mpol.h"
#include "synaps/mpol/MPolDse.h"

typedef MPolDse<QQ> mpold_t;
typedef MPolDse<QQ, mpoldse::bernstein<QQ> > mpolb_t;

int main(int argc, char** argv) 
{
  using std::cout;
  using std::endl;

  mpolb_t A("x1^2*x0+2*x1+3"),B("x0+x1+1"),C=A*B; 
  VECTOR::print(cout,A.rep())<<endl;
  VECTOR::print(cout,B.rep())<<endl;
  VECTOR::print(cout,C.rep())<<endl;
  std::cout<<C<<std::endl;

} 

#else
int main(int argc, char** argv) {}
#endif

SYNAPS DOCUMENTATION

Polynomials

Univariate polynomials

Multivariate distributed polynomials

Multivariate dense polynomials