Polynomials

Univariate polynomials

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 :
 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:

For univariate polynomials, the variables and 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:

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)

 Exercise: Build a function Wilkinson which given computes

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 .
 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:

Notice that even if the coefficients of and are integers, the coefficients of 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

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

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

(that is the list of coefficients of the monomials)

(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 and . Compare with different types of coefficients QQ, double, Zp, ... Make your first implementation more robust

 Exercise: Define a function shifteval which given a multivariate polynomial (s,t) (with and a value of type double, compute the mutlivariate polynomial (with )

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:

{{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