mmx::sparse Namespace Reference

namespace for representation of polynomials as sequence of monomials More...

Classes

Functions

Detailed Description

namespace for representation of polynomials as sequence of monomials

Function Documentation

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const C &  c,
const monomial_seq< C, O, MONOM, poly.rep() > &  q 
) [inline]

Definition at line 228 of file sparse_monomials.hpp.

References add(), and Polynomial.

00228                                                        {
00229     Polynomial m(c); add(r,q,m);
00230   }

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  q,
const X &  c 
) [inline]

Definition at line 223 of file sparse_monomials.hpp.

References add(), and Polynomial.

00223                                                        {
00224     Polynomial m(c); add(r,q,m);
00225   }

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  p,
const C &  c 
) [inline]

Definition at line 218 of file sparse_monomials.hpp.

References add(), and Polynomial.

00218                                   {
00219     Polynomial m(c); add(p,m);
00220   }

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  p,
const typename monomial_seq< C, O, MONOM, poly.rep() >::monom_t &  m 
) [inline]

Definition at line 213 of file sparse_monomials.hpp.

References add(), and Polynomial.

00213                                                            {
00214     Polynomial q(m); add(p,q);
00215   }

I mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  p1,
I  b1,
J  e1,
const M &  m2 
) [inline]

Definition at line 185 of file sparse_monomials.hpp.

00185                                                    {
00186     typedef typename Polynomial::value_type::coeff_t coeff_type;
00187     
00188     while (b1!=e1) {
00189       if(Polynomial::less(m2,*b1))
00190         {
00191           b1++; //COUNT<M>('i');
00192         }
00193       else if(Polynomial::less(*b1,m2))
00194         {
00195           b1=p1.insert(b1,m2);
00196           return b1;
00197         }
00198       else
00199         {
00200           coeff_type c=b1->coeff() + m2.coeff();
00201           if (c !=0) {
00202             b1->set_coeff(c);
00203           }else
00204             b1 = p1.erase(b1);
00205           return(b1);
00206         }
00207     }
00208     b1 = p1.insert(b1,m2);
00209     return b1;
00210   }

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  p1,
const monomial_seq< C, O, MONOM, poly.rep() > &  p2 
) [inline]

Inplace addition.

Definition at line 153 of file sparse_monomials.hpp.

References assert, and Scalar.

00153                                              {
00154     
00155     assert(&p1 != &p2);
00156     typedef typename Polynomial::const_iterator  const_iterator;
00157     typedef typename Polynomial::iterator        iterator;
00158     typedef typename Polynomial::value_type      coeff_type;
00159     
00160     //    reserve(p1,p1.size()+p2.size());
00161     iterator        b1=p1.begin();
00162     const_iterator  b2=p2.begin();
00163     while (b1!=p1.end() && b2!=p2.end()) {
00164       if(Polynomial::less(*b2,*b1))
00165         b1++;
00166       else if(Polynomial::less(*b1,*b2))
00167         {
00168           b1 = p1.insert(b1,*b2); b1++; b2++;
00169         }
00170       else
00171         {
00172           coeff_type c=b1->coeff() + b2->coeff();
00173           if (c != (typename Polynomial::Scalar)0) {
00174             b1->set_coeff(c); ++b1;
00175           }else{
00176             b1 = p1.erase(b1);
00177           }
00178           ++b2;
00179         }
00180     }
00181     p1.insert(b1,b2,p2.end());
00182   }

void mmx::sparse::add ( monomial_seq< C, O, MONOM, poly.rep() > &  result,
const monomial_seq< C, O, MONOM, poly.rep() > &  p1,
const monomial_seq< C, O, MONOM, poly.rep() > &  p2 
) [inline]

Definition at line 112 of file sparse_monomials.hpp.

References assert, and Scalar.

00113   {
00114     assert(&result != &p1); assert(&result != &p2);
00115     
00116     typedef typename Polynomial::const_iterator  const_iterator;
00117     typedef typename Polynomial::iterator        iterator;
00118     typedef typename Polynomial::value_type      coeff_type;
00119     typedef typename Polynomial::Scalar          Scalar;
00120 
00121     const_iterator
00122       b1=p1.begin(),
00123       e1=p1.end(),
00124       b2=p2.begin(),
00125       e2=p2.end();
00126     result.resize(p1.size()+p2.size());
00127     iterator i=result.begin();
00128     while (b1!=e1 && b2!=e2) {
00129       if(Polynomial::less(*b2,*b1))
00130         *i++=*b1++;
00131       else if(Polynomial::less(*b1,*b2))
00132         *i++=*b2++;
00133       else {
00134         coeff_type c=b1->coeff()+ b2->coeff();
00135         if (c !=(Scalar)0) {
00136           *i =*b1;
00137           i->set_coeff(c);
00138           ++i;
00139         }
00140         ++b1;++b2;
00141       }
00142     }
00143     while (b1!=e1) *i++=*b1++;
00144     while (b2!=e2) *i++=*b2++;
00145     
00146     int m=std::distance(result.begin(),i);
00147     assert(m>=0);
00148     result.resize(m);
00149   }

void mmx::sparse::add ( dual< C, O > &  res,
const C &  b,
const dual< C, O > &  a 
) [inline]

Definition at line 115 of file sparse_dual.hpp.

References add().

00115                                                      {
00116   add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
00117 }

void mmx::sparse::add ( dual< C, O > &  res,
const dual< C, O > &  a,
const C &  b 
) [inline]

Definition at line 110 of file sparse_dual.hpp.

References add().

00110                                                     {
00111   add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
00112 }

void mmx::sparse::add ( dual< C, O > &  res,
const dual< C, O > &  a,
const dual< C, O > &  b 
) [inline]

Definition at line 105 of file sparse_dual.hpp.

Referenced by add(), diff(), div_rem(), homogenize(), mul(), shift(), and sub().

00105                                                             {
00106   add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
00107 }

void mmx::sparse::coefficients ( Seq< C > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  f 
) [inline]

Definition at line 467 of file sparse_monomials.hpp.

00467                                                {
00468     for(typename Polynomial::const_iterator it=f.begin(); it != f.end(); it++) {
00469       r<<it->coeff();
00470     }
00471   }

void mmx::sparse::coefficients ( Seq< U > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  f,
int  v 
) [inline]

Definition at line 455 of file sparse_monomials.hpp.

References degree(), mmx::N(), and Seq< C, R >::size().

00455                                                     {
00456     unsigned N = degree(f,v)+1;
00457     r=Seq<U>(N);
00458     typename Polynomial::monom_t m;
00459     for(typename Polynomial::const_iterator it=f.begin(); it != f.end(); it++) {
00460       m=*it;
00461       if (v<(int)m.size()) m.set_expt(v,0);
00462       r[(*it)[v]]+= U(m);
00463     }
00464   }

POL::coeff_t mmx::sparse::coeffof ( const POL &  p,
const typename POL::monom_t &  mono 
) [inline]

Return the coefficient of a monomial m in a polynomial p if it appears in p or 0 otherwise.

Definition at line 527 of file sparse_monomials.hpp.

00529   {
00530     typedef typename POL::coeff_t coeff_t;
00531     typename POL::const_iterator m;
00532     for(m = p.begin();  m!= p.end() && !IsComparable((*m),mono); m++) {}
00533     if(m != p.end())
00534       {
00535         return m->coeff();
00536       }
00537     else
00538       {
00539         return  coeff_t(0);
00540       }
00541   }

C mmx::sparse::content ( const monomial_seq< C, O, MONOM, poly.rep() > &  P  )  [inline]

Definition at line 1002 of file sparse_monomials.hpp.

References C, and mmx::gcd().

01003   {
01004     C d=0;
01005     for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
01006       d= gcd(d,i->coeff());
01007     }
01008     return d;
01009   }

MP mmx::sparse::convert ( const MP &  P,
typename MP::coeff_t  x,
typename MP::coeff_t  y,
int  ind 
) [inline]

function which return the equation of the polynomial P hiding the indice ind and evaluating at x and y.

Definition at line 700 of file sparse_monomials.hpp.

References mmx::pow().

00700                                                                           {
00701     typedef typename MP::const_iterator  const_iterator;
00702     typedef typename MP::coeff_t coeff_t;
00703     typedef typename MP::monom_t monom_t;
00704     MP  res;
00705     int ind1=0;
00706     int ind2=0;
00707     for(int i=0;i<=2;i++)
00708       {
00709         if(ind!=i) {ind1=i;break;}
00710       }
00711     for(int i=0;i<=2;i++)
00712       {
00713         if(ind!=i && ind1!=i) {ind2=i;break;}
00714       }
00715     for(const_iterator i = P.begin(); i != P.end(); ++i)
00716       {
00717         coeff_t  k=i->coeff();
00718         int puissx=(*i)[ind1];
00719         int puissy=(*i)[ind2];
00720         int d=(*i)[ind];
00721         coeff_t coeff1=pow(x,puissx);
00722         coeff_t coeff2=pow(y,puissy);
00723         k*=coeff1;k*=coeff2;
00724         MP P1=monom_t(k,ind,d);
00725         res=res+P1;
00726       }
00727     return res;
00728   }

void mmx::sparse::copy ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a 
) [inline]

Copy of a in r.

Definition at line 614 of file sparse_monomials.hpp.

Referenced by bsearch< real_t >::bsearch(), bsearch_castel< real_t >::bsearch_castel(), bsearch_newton< real_t >::bsearch_newton(), bsearch_newton2< real_t >::bsearch_newton2(), mmx::realroot::clean_result(), mmx::linear::cpolynom(), mmx::tensor::eval(), mmx::brnops::eval(), mmx::tensor::hevalm(), mmx::tensor::levalb(), mmx::tensor::levalm(), mmx::linear::library(), op_mul(), parallel< system >::process(), binary_sleeve_subdivision< K >::run(), binary_sleeve_subdivision< K >::run_loop(), binary_subdivision< K >::run_loop(), solver< C, ProjRd< MTH > >::solve_monomial(), v0restrict(), and vrestrict().

00615   {
00616     //to be modified when bug fixed in gcc
00617     //    using dense::reserve;
00618     reserve(r,a.size());
00619     std::copy(a.begin(),a.end(),r.begin());
00620   }

int mmx::sparse::degree ( const R &  p,
int  i 
) [inline]

Degree of a polynomial with respect to the i th variable..

Definition at line 502 of file sparse_monomials.hpp.

References mmx::vctops::max().

00502                               {
00503     if(!p.size())
00504       return -1;
00505     else
00506       {
00507         int d=0;
00508         for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
00509           {
00510             if(i<=it->nvars()) d = std::max(d,(int)(*it)[i]);
00511           }
00512         return d;
00513       }
00514   }

int mmx::sparse::degree ( const R &  p  )  [inline]

Degree of a polynomial.

Definition at line 488 of file sparse_monomials.hpp.

References mmx::vctops::max().

Referenced by coefficients(), homogenize(), and monomial_seq< C, O, MONOM, rep >::operator==().

00488                        {
00489     if(!p.size())
00490       return -1;
00491     else
00492       {
00493         int d = 0;
00494         for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
00495           d = std::max(d,degree(*it));
00496         return d;
00497       }
00498   }

void mmx::sparse::diff ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
int  i 
) [inline]

Derivative of p with respect to i th variable put in r.

Definition at line 581 of file sparse_monomials.hpp.

References add(), assert, Monomial, Polynomial, and Scalar.

00582   {
00583     typedef typename Polynomial::Monomial Monomial;
00584     typedef typename Polynomial::Scalar   Scalar;
00585 
00586     assert(&r != &p);
00587     r= Polynomial((Scalar)0);
00588     for (typename Polynomial::const_iterator it = p.begin(); it != p.end(); ++it) {
00589       if((*it)[i]>0){
00590         Monomial m(*it);
00591         m*=(typename Polynomial::coeff_t)(*it)[i];
00592         m.set_expt(i,(*it)[i]-1);
00593         add(r,m);
00594       }
00595     }
00596   }

void mmx::sparse::div ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const C &  c 
) [inline]

Definition at line 441 of file sparse_monomials.hpp.

References div().

00441                                                        {
00442     r = p; div(r,c);
00443   }

void mmx::sparse::div ( monomial_seq< C, O, MONOM, poly.rep() > &  f,
const typename monomial_seq< C, O, MONOM, poly.rep() >::Scalar &  c 
) [inline]

Definition at line 433 of file sparse_monomials.hpp.

00434   {
00435     for(typename Polynomial::iterator it=f.begin(); it != f.end(); it++) 
00436       it->coeff()/=c;
00437   }

void mmx::sparse::div ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  b 
) [inline]

Definition at line 426 of file sparse_monomials.hpp.

References div(), and Polynomial.

00427   {
00428     Polynomial a(r);
00429     div(r,a,b);
00430   }

void mmx::sparse::div ( monomial_seq< C, O, MONOM, poly.rep() > &  q,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const monomial_seq< C, O, MONOM, poly.rep() > &  b 
) [inline]

Definition at line 419 of file sparse_monomials.hpp.

References div_rem(), and Polynomial.

00420   {
00421     Polynomial r(a);
00422     div_rem(q,r,b);
00423   }

void mmx::sparse::div ( dual< C, O > &  r,
const dual< C, O > &  p,
const C &  c 
) [inline]

Definition at line 212 of file sparse_dual.hpp.

References div().

00212                                                    {
00213   r = p; div(r,c);
00214 }

void mmx::sparse::div ( dual< C, O > &  f,
const C &  c 
) [inline]

Definition at line 205 of file sparse_dual.hpp.

Referenced by div().

00205                               {
00206   for(typename dual<C,O>::iterator it=f.begin(); it != f.end(); it++) 
00207     it->coeff()/=c;
00208 }

void mmx::sparse::div_rem ( R &  q,
R &  a,
const R &  b0 
) [inline]

Divide a in place by b, concidering all the monomials.

Definition at line 555 of file sparse_monomials.hpp.

References add(), mmx::divide(), mul(), R, and sub().

Referenced by div(), and rem().

00555                                       {
00556     //    std::cout <<"---- Begin div-rem sparse -----"<<std::endl;
00557     typedef typename R::monom_t       monom_t;
00558     typedef typename monom_t::coeff_t coeff_t;
00559     q= R((coeff_t)0);
00560 
00561     if(a==0) return;
00562     
00563     R b(b0);
00564     //coeff_t cb =b0.begin()->coeff();
00565     //  b/=cb;
00566     monom_t mb = (*b.begin()), m;
00567     R t;
00568     while( a != (coeff_t)0 && divide(*a.begin(), mb, m) )
00569       {
00570         mul(t,b,m);
00571         sub(a,t);
00572         if ( m != 0 )  add(q,m);
00573         //      print(std::cout,a); std::cout<<std::endl;
00574       }
00575     //    std::cout <<"---- End div-rem sparse -----"<<std::endl;
00576   }

void mmx::sparse::eval ( R &  r,
const MP &  p,
const V &  v,
unsigned  n 
) [inline]

Definition at line 864 of file sparse_monomials.hpp.

References mmx::assign(), and R.

00864                                                   {
00865     r=R(0);
00866     for(typename MP::const_iterator it=p.begin(); it!=p.end(); ++it)
00867       {
00868         R c; 
00869         let::assign(c,it->coeff());
00870         for(unsigned i=0;i< it->size()&&i<n;++i)
00871           for(int k=0;k<(*it)[i];k++) {
00872             c*=v[i];
00873           }
00874         r+=c;
00875       }
00876   }

T mmx::sparse::eval ( const MP &  p,
const V &  v 
) [inline]

Definition at line 846 of file sparse_monomials.hpp.

References mmx::assign().

00846                                 {
00847     T r(0);
00848     for(typename MP::const_iterator it=p.begin(); it!=p.end(); ++it)
00849       {
00850         T c; let::assign(c,it->coeff());
00851         for(unsigned i=0;i< it->size()&&i<v.size();++i)
00852           for(int k=0;k<(*it)[i];k++)
00853             {
00854               c*=v[i];
00855             }
00856         r+=c;
00857       }
00858     return r;
00859   }

void mmx::sparse::eval ( R &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const X &  x 
) [inline]

Evaluate the polynomial p for x0=x, x1=y, and the other xi=1. **/.

Definition at line 661 of file sparse_monomials.hpp.

References R.

00661                                               {
00662     r=(R)0;
00663     for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
00664       {
00665         R c(it->coeff());
00666         for(int k=0;k<(int)(*it)[0];k++)
00667           c*=x;
00668         r+=(R)c;
00669       }
00670   }

monomial_seq<C,O,MONOM, poly.rep() >::coeff_t mmx::sparse::eval ( const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const typename monomial_seq< C, O, MONOM, poly.rep() >::coeff_t &  x,
const typename monomial_seq< C, O, MONOM, poly.rep() >::coeff_t &  y 
) [inline]

Evaluate the polynomial p for x0=x, x1=y, and the other xi=1.

Definition at line 624 of file sparse_monomials.hpp.

00626                                             {
00627     typename Polynomial::coeff_t r(0);
00628     for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
00629       {
00630         typename Polynomial::coeff_t c(it->coeff());
00631         //for(unsigned int i=0;i<2;++i)
00632         for(int k=0;k<(int)(*it)[0];k++)
00633           c*=x;
00634         for(int k=0;k<(int)(*it)[1];k++)
00635           c*=y;
00636         r+=c;
00637       }
00638     return r;
00639   }

void mmx::sparse::eval_at ( R &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const VCT &  x 
) [inline]

Definition at line 643 of file sparse_monomials.hpp.

References R.

Referenced by polynomial< C, with< Rep, Ord > >::at().

00645                         {
00646     r= (R)0;
00647     for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
00648       {
00649         R c= it->coeff();
00650         for(unsigned j=0; j< (unsigned)x.size() && j< (unsigned)it->nvars();++j)
00651           for(int k=0;k<(int)(*it)[j];k++)
00652             c*=x[j];
00653         r+=c;
00654       }
00655     //return r;
00656   }

void mmx::sparse::homogenize ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
int  n,
const monomial_seq< C, O, MONOM, poly.rep() > &  v 
) [inline]

Definition at line 686 of file sparse_monomials.hpp.

References add(), degree(), mul(), and Polynomial.

00686                                                                              {
00687     Polynomial t;
00688     int d = degree(p,n);
00689     for(typename Polynomial::const_iterator it=p.begin();it != p.end();it++) {
00690       t=*it;
00691       for (int i=0;i<d-(*it)[n];i++) mul(t,v);
00692       add(r,t);
00693     }
00694   }

void mmx::sparse::homogenize ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const monomial_seq< C, O, MONOM, poly.rep() > &  v 
) [inline]

Definition at line 674 of file sparse_monomials.hpp.

References add(), degree(), mul(), and Polynomial.

00674                                                                       {
00675     Polynomial t;
00676     int d = sparse::degree(p);
00677     for(typename Polynomial::const_iterator it=p.begin();it != p.end();it++) {
00678       t=*it;
00679       for (int i=0;i<d-degree(*it);i++) mul(t,v);
00680       add(r,t);
00681     }
00682   }

POL::const_iterator mmx::sparse::last_term ( const POL &  p  )  [inline]

Definition at line 544 of file sparse_monomials.hpp.

References assert.

00544                           {
00545     assert(p.size()>0);
00546     typename POL::const_iterator it=p.end();
00547     it--;
00548     return it;
00549   }

R::coeff_t mmx::sparse::leadingcoeff ( const R &  a  )  [inline]

Definition at line 520 of file sparse_monomials.hpp.

00520 {return a.begin()->coeff();}

R::coeff_t& mmx::sparse::leadingcoeff ( R &  a  )  [inline]

Definition at line 517 of file sparse_monomials.hpp.

00517 {return a.begin()->coeff();}

int mmx::sparse::lvar ( const R &  p  )  [inline]

Index of the leading variable (of maximal index) of a polynomial.

Definition at line 474 of file sparse_monomials.hpp.

References mmx::vctops::max().

Referenced by subs(), and swap().

00474                                              {
00475   int v = -1;
00476   for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
00477     v = std::max(v,it->l_variable());
00478   return v;
00479   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p 
) [inline]

Definition at line 413 of file sparse_monomials.hpp.

References mul(), and Polynomial.

00414   {
00415     Polynomial s(r); mul(r,s,p); 
00416   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
typename monomial_seq< C, O, MONOM, poly.rep() >::const_iterator  b,
typename monomial_seq< C, O, MONOM, poly.rep() >::const_iterator  e,
const monomial_seq< C, O, MONOM, poly.rep() > &  p 
) [inline]

Definition at line 389 of file sparse_monomials.hpp.

References add(), assert, C, mul(), mul_ext(), and Polynomial.

00392                            {
00393 
00394     
00395     typedef typename Polynomial::const_iterator  const_iterator;
00396     int n=std::distance(b,e);
00397     assert(n>=0);
00398     if (n==0) r.resize(0);
00399     if (n==1) 
00400       mul_ext(r,p,*b);
00401     else {
00402       const_iterator med=b; // b+(n/2);
00403       for(int i=0; i<n/2 && med !=e;i++,med++) {}
00404 
00405       Polynomial tmp0((C)0), tmp1((C)0);
00406       mul(tmp0,b,med,p);
00407       mul(tmp1,med,e,p);
00408       add(r,tmp0,tmp1);
00409     }
00410 
00411   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const monomial_seq< C, O, MONOM, poly.rep() > &  b,
const X &  o 
) [inline]

Specialisation for list.

Definition at line 360 of file sparse_monomials.hpp.

References add(), and mul_ext().

00363   {
00364     typedef typename Polynomial::const_iterator const_iterator;
00365     typedef typename Polynomial::iterator       iterator;
00366     typedef typename Polynomial::monomt_t       M;
00367 
00368     r.resize(0);
00369     M m;
00370     for(const_iterator i=b.begin();i !=b.end();i++)
00371       {
00372         if(r.size())
00373           {
00374             iterator ip = r.begin();
00375             for(const_iterator j=a.begin();j != a.end();j++) { 
00376               m  = *j * *i;
00377               ip = add(r,ip,r.end(),m);//,O()); 
00378             }
00379             //MPOLDST::mul_ext(tmp,a,*i);
00380             //MPOLDST::add<list<M>,vector<M>,O>(r,tmp);
00381           }
00382         else
00383           mul_ext(r,a,*i);
00384       }
00385   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const monomial_seq< C, O, MONOM, poly.rep() > &  b 
) [inline]

Multiplication of two polynomials.

Definition at line 348 of file sparse_monomials.hpp.

References mul().

00349   {
00350     if (a.size()==0) return;
00351     if (b.size()==0) return;
00352     if (a.size()<b.size())
00353       mul(r,a.begin(),a.end(),b);
00354     else
00355       mul(r,b.begin(),b.end(),a);
00356   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const typename monomial_seq< C, O, MONOM, poly.rep() >::monom_t &  m 
) [inline]

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 324 of file sparse_monomials.hpp.

00324                                                            {
00325     typename Polynomial::iterator i=r.begin();
00326     for(; i!=r.end(); ++i) *i *= m; 
00327   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const typename monomial_seq< C, O, MONOM, poly.rep() >::monom_t &  m 
) [inline]

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 318 of file sparse_monomials.hpp.

References mul_ext().

00318                                                                                 {
00319     mul_ext(r,a,m);
00320   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const X &  c,
const monomial_seq< C, O, MONOM, poly.rep() > &  p 
) [inline]

Definition at line 302 of file sparse_monomials.hpp.

References mul().

00302                                                        {
00303     r = p; mul(r,c);
00304   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const C &  c 
) [inline]

Definition at line 296 of file sparse_monomials.hpp.

References mul().

00296                                                        {
00297     r = p; mul(r,c);
00298   }

void mmx::sparse::mul ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const C &  c 
) [inline]

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 289 of file sparse_monomials.hpp.

00289                                   {
00290     for(typename Polynomial::iterator it=r.begin(); it!=r.end(); ++it) {
00291       it->coeff()*=c;
00292     }
00293   }

void mmx::sparse::mul ( monomial_seq< C, O > &  res,
const dual< C, O > &  l,
const monomial_seq< C, O > &  p 
) [inline]

Compute the product l*p where l is a linear form and p a polynomial. The result is the polynomial obtained by applying the inverse variables on the polynomial and by keeping the positive exponents.

Definition at line 189 of file sparse_dual.hpp.

References mul().

00189                                                                             {
00190   monomial_seq<C,O> t;
00191   mul(t,(monomial_seq<C,O>)l,p);
00192   typedef typename dual<C,O>::const_iterator iterator;
00193   for(iterator it=t.begin();it != t.end();it++)
00194     {
00195       bool pos=true;
00196       for(unsigned j=0;j<it->size() && pos;j++) {
00197         if((*it)[j]<0) pos=false;
00198       }
00199       if(pos) res.push_back(*it);
00200     }
00201 }

void mmx::sparse::mul ( dual< C, O > &  res,
const monomial_seq< C, O > &  p,
const dual< C, O > &  l 
) [inline]

Compute the product p*l where l is a linear form and p a polynomial. The result is the linear form obtained by applying the inverse variables on the polynomial and by keeping the negative exponents.

Definition at line 155 of file sparse_dual.hpp.

References mul(), and mmx::neg().

00155                                                                     {
00156   monomial_seq<C,O> t;
00157   mul(t,p,(monomial_seq<C,O>)l);
00158   typedef typename dual<C,O>::const_iterator iterator;
00159   for(iterator it=t.begin();it != t.end();it++)
00160     {
00161       bool neg=true;
00162       for(unsigned j=0;j<it->size() && neg;j++) {
00163         if((*it)[j]>0) neg=false;
00164       }
00165       if(neg) res.push_back(*it);
00166     }
00167 }

void mmx::sparse::mul ( dual< C, O > &  res,
const C &  b,
const dual< C, O > &  a 
) [inline]

Definition at line 145 of file sparse_dual.hpp.

References mul().

00145                                                     {
00146   mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
00147 }

void mmx::sparse::mul ( dual< C, O > &  res,
const dual< C, O > &  a,
const C &  b 
) [inline]

Definition at line 140 of file sparse_dual.hpp.

References mul().

00140                                                     {
00141   mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
00142 }

void mmx::sparse::mul ( dual< C, O > &  res,
const dual< C, O > &  a,
const dual< C, O > &  b 
) [inline]

Definition at line 135 of file sparse_dual.hpp.

Referenced by div_rem(), homogenize(), mul(), and sub().

00135                                                             {
00136   mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
00137 }

void mmx::sparse::mul_ext ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const M &  m 
) [inline]

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 308 of file sparse_monomials.hpp.

Referenced by mul().

00308                                                            {
00309     r.resize(a.size());
00310     typename Polynomial::const_iterator b=a.begin(); 
00311     typename Polynomial::iterator i=r.begin();
00312     for(; b!=a.end(); ++i, ++b) *i = (*b) * m; 
00313      //    VECTOR::apply_mult(r, a, m);
00314   }

void mmx::sparse::mul_ext_e ( monomial_seq< C, O, MONOM, poly.rep() > &  result,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const M &  m 
) [inline]

Definition at line 330 of file sparse_monomials.hpp.

References R.

00331   {
00332     typedef typename Polynomial::const_iterator  const_iterator;
00333     typedef typename Polynomial::iterator        iterator;
00334     typedef typename Polynomial::monom_t         R;
00335 
00336     result.resize(0);
00337     iterator i=result.begin();
00338     R tmp;
00339     for(const_iterator b=a.begin();b!=a.end(); ++b)
00340       {
00341         tmp = (*b) * m;
00342         (i=result.insert(i,tmp))++;
00343       }
00344   }

unsigned mmx::sparse::nbvar ( const R &  p  )  [inline]

Number of variables of a polynomial.

Definition at line 482 of file sparse_monomials.hpp.

00482                                                    {
00483     return p.nbvar();
00484   }

void mmx::sparse::neg_exponent ( dual< C, O > &  p  )  [inline]

Definition at line 70 of file sparse_dual.hpp.

Referenced by dual< C, O >::dual().

00071 {
00072   typedef typename dual<C,O>::iterator iterator;
00073   for(iterator it=p.begin();it != p.end();it++)
00074     {
00075       for(int j=0;j<(it->nvars()+1);j++)
00076         {
00077           it->set_expt(j,-(*it)[j]);
00078         }
00079     }
00080 }

void mmx::sparse::print ( const T &  x  )  [inline]

Definition at line 959 of file sparse_monomials.hpp.

00959 {std::cout<<x<<std::endl;}

OS& mmx::sparse::print ( OS &  os,
const monomial_seq< C, O, MONOM, poly.rep() > &  P 
) [inline]

Definition at line 767 of file sparse_monomials.hpp.

References variables::default_, and print().

00768   {
00769     return print(os,P,variables::default_);
00770   }

OS& mmx::sparse::print ( OS &  os,
const monomial_seq< C, O, MONOM, poly.rep() > &  P,
const VARIABLES &  V 
) [inline]

Definition at line 732 of file sparse_monomials.hpp.

References print().

00732                                                             {
00733     if ( P.begin() == P.end() )
00734       {
00735         os << '0';
00736         return os;
00737       }
00738     for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
00739       std::ostringstream sm;
00740       print(sm,*i,V);
00741       if(sm.str()[0] != '-' && sm.str()[0] != '+' && i != P.begin())
00742         os <<'+';
00743       os<<sm.str().c_str();
00744     }
00745     return os;
00746   }

OSTREAM& mmx::sparse::print ( OSTREAM &  os,
const dual< C, O > &  P,
const variables &  V 
) [inline]

Output operator.

The inverse variables are denoted by di. The opposite of their exponents is printed.

Definition at line 260 of file sparse_dual.hpp.

References print_dual(), and with_plus_sign().

Referenced by print().

00260                                                               {
00261  if ( P.begin() == P.end() ) {
00262    os << '0';
00263    return os;
00264  }
00265  typename dual<C,O>::const_iterator i = P.begin();
00266  while ( i != P.end() ) {
00267    if ( with_plus_sign(i->coeff()) && i !=P.begin())
00268      os <<'+';
00269    print_dual(os,*i++,V);
00270  }
00271  return os;
00272 }

OS& mmx::sparse::print_as_double ( OS &  os,
const monomial_seq< C, O, MONOM, poly.rep() > &  P,
const VARIABLES &  V 
) [inline]

Definition at line 750 of file sparse_monomials.hpp.

00750                                                                       {
00751     if ( P.begin() == P.end() )
00752       {
00753         os << '0';
00754         return os;
00755       }
00756     for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
00757       std::ostringstream sm;
00758       print_as_double(sm,*i,V);
00759       if(sm.str()[0] != '-' && sm.str()[0] != '+' && i != P.begin())
00760         os <<'+';
00761       os<<sm.str().c_str();
00762     }
00763     return os;
00764   }

OSTREAM& mmx::sparse::print_dual ( OSTREAM &  os,
const monom< C > &  m,
const variables &  V 
) [inline]

Definition at line 223 of file sparse_dual.hpp.

References monom< C, E >::coeff(), and monom< C, E >::size().

Referenced by print().

00223                                                                  { 
00224   if (m.coeff() ==0 ) {
00225     os<<"0"; return os;
00226   }
00227   int i=m.size()-1;
00228   while(i> -1 && m[i]==0) i--;
00229   if(i<0)
00230     os <<m.coeff();
00231   else {
00232     if(m.coeff() != 1) {
00233       if(m.coeff()==-1) 
00234          os << "-"; 
00235       else {  
00236         os << m.coeff(); os <<"*"; 
00237       }
00238     }
00239   }
00240   bool first=true;
00241   for (unsigned i = 0; i < m.size(); ++i) {
00242     if (m[i] !=0) {
00243       if(first)
00244         first =false;
00245       else
00246         os<<'*';
00247       os << 'd'<<V[i];
00248       if (m[i] != -1)
00249         os << '^' <<(-m[i]);
00250     }
00251   }
00252   return os;
00253 }

OS& mmx::sparse::print_verbatim ( OS &  os,
const monomial_seq< C, O, MONOM, poly.rep() > &  P 
) [inline]

Definition at line 775 of file sparse_monomials.hpp.

00776   {
00777     if ( P.begin() == P.end() )
00778       {
00779         os << '0';
00780         return os;
00781       }
00782     for( typename Polynomial::const_iterator i=P.begin(); i != P.end();++i)
00783       {
00784         os<<" "<<i->coeff()<<" [";
00785         for(int l=0;l<i->size();l++) os<<(*i)[l]<<" ";
00786         os<<"]";
00787       }
00788     return os;
00789   }

void mmx::sparse::rem ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  a,
const monomial_seq< C, O, MONOM, poly.rep() > &  b 
) [inline]

Definition at line 447 of file sparse_monomials.hpp.

References div_rem(), and Polynomial.

00448   {
00449     Polynomial q; r=a;
00450     div_rem(q,r,b);
00451   }

POL mmx::sparse::scale ( const POL &  p,
C  a,
int  v 
) [inline]

The variables of a "tri-variate" polynomial are multiplied as follows: x0 = a*x0, x1 = b*x1, x2 = c*x2.

Definition at line 832 of file sparse_monomials.hpp.

References POL, and mmx::pow().

00832                                    {
00833     
00834     typedef typename POL::monom_t monomial;
00835     
00836     POL  np(p);
00837     
00838     for ( typename POL::const_iterator i = np.begin(); i != np.end(); ++i ) {
00839       i->coeff()*= pow( a, int( i->operator[]( v ) ) );
00840     }
00841     return np;
00842     
00843   }

POL mmx::sparse::shift ( typename POL::const_iterator  monom,
const C &  a,
int  i 
) [inline]

Function applicable only to the polynomials which has three variables. Carry out a change of variable x_i = x_i + a on the multivariable monomial passed as parameter.

Definition at line 795 of file sparse_monomials.hpp.

References C, and POL.

00795                                                              {
00796     
00797     POL polynom;
00798     // Definition du type monome.
00799     typedef typename POL::monom_t monomial;
00800     // monomiale temporaire.
00801     monomial tmpmonomial;
00802     
00803     int i0 = i;
00804     int i1 = (i + 1) % 3;
00805     int i2 = (i + 2) % 3;
00806     
00807     // Si la variable est presente dans le monome.
00808     if ( (a!=0) && ( monom->operator[](i0) !=0 ) )
00809       {
00810         polynom = binomial< POL >(C(1.), i0, monom->operator[](i0), a);
00811         int expt[3];
00812         expt[i0] = 0;
00813         expt[i1] = monom->operator[](i1);
00814         expt[i2] = monom->operator[](i2);
00815         
00816         if ( ( expt[i0] == 0 ) && ( expt[i1] == 0 ) && ( expt[i2] == 0 ) )
00817           tmpmonomial = monomial( monom->coeff(), 0, 0 );
00818         else   tmpmonomial = monomial( monom->coeff(), 3, expt );
00819         
00820         polynom *= tmpmonomial;
00821       }
00822     // Si a = 0 alors le monome reste inchange.
00823     else polynom = ( *monom );
00824     
00825     return polynom;
00826     
00827   }

void mmx::sparse::shift ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  p,
const typename monomial_seq< C, O, MONOM, poly.rep() >::monom_t &  m 
) [inline]

Multiply p by a monomial m and put the result in r.

Definition at line 601 of file sparse_monomials.hpp.

References add(), assert, Monomial, and Polynomial.

00602   {
00603     assert(&r != &p);
00604     typedef typename Polynomial::monom_t Monomial;
00605     r= Polynomial(0);
00606     for (typename Polynomial::const_iterator it = p.begin(); it != p.end(); ++it) {
00607       add(r,*it*m);
00608     }
00609   }

void mmx::sparse::sub ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const X &  c,
const monomial_seq< C, O, MONOM, poly.rep() > &  q 
) [inline]

Definition at line 283 of file sparse_monomials.hpp.

References Polynomial, and sub().

00283                                                        {
00284     Polynomial m(c); sub(r,m,q);
00285   }

void mmx::sparse::sub ( monomial_seq< C, O, MONOM, poly.rep() > &  r,
const monomial_seq< C, O, MONOM, poly.rep() > &  q,
const X &  c 
) [inline]

Definition at line 278 of file sparse_monomials.hpp.

References add(), C, and Polynomial.

00278                                                        {
00279     Polynomial m(C(-c)); add(r,q,m);
00280   }

void mmx::sparse::sub ( monomial_seq< C, O, MONOM, poly.rep() > &  p,
const monomial_seq< C, O, MONOM, poly.rep() > &  q 
) [inline]

Definition at line 272 of file sparse_monomials.hpp.

References add(), C, mul(), and Polynomial.

00272                                            {
00273     Polynomial m(q); mul(m,(C)-1);
00274     add(p,m);
00275   }

void mmx::sparse::sub ( monomial_seq< C, O, MONOM, poly.rep() > &  result,
const monomial_seq< C, O, MONOM, poly.rep() > &  p1,
const monomial_seq< C, O, MONOM, poly.rep() > &  p2 
) [inline]

Definition at line 233 of file sparse_monomials.hpp.

References assert.

00234   {
00235     assert(&result != &p1); assert(&result != &p2);
00236     typedef typename Polynomial::const_iterator  const_iterator;
00237     typedef typename Polynomial::iterator        iterator;
00238     typedef typename Polynomial::value_type      coeff_type;
00239     const_iterator
00240       b1=p1.begin(),
00241       e1=p1.end(),
00242       b2=p2.begin(),
00243       e2=p2.end();
00244     result.resize(p1.size()+p2.size());
00245     iterator i=result.begin();
00246     while (b1!=e1 && b2!=e2) {
00247       if(Polynomial::less(*b2,*b1))
00248         *i++=*b1++;
00249       else if(Polynomial::less(*b1,*b2))
00250         {
00251           *i=*b2++; i->coeff()*= -1; i++;
00252         }
00253       else {
00254         coeff_type c=b1->coeff()- b2->coeff();
00255         if (c !=0) {
00256           *i =*b1;
00257           i->set_coeff(c);
00258           ++i;
00259         }
00260         ++b1;++b2;
00261       }
00262     }
00263     while (b1!=e1) *i++=*b1++;
00264     while (b2!=e2) {*i=*b2++;i->coeff()*=-1;i++;}
00265     
00266     int m=std::distance(result.begin(),i);
00267     assert(m>=0);
00268     result.resize(m);
00269   }

void mmx::sparse::sub ( dual< C, O > &  res,
const C &  a,
const dual< C, O > &  b 
) [inline]

Definition at line 130 of file sparse_dual.hpp.

References sub().

00130                                                     {
00131   sub((monomial_seq<C,O>&)res,a,(const monomial_seq<C,O>&)b);
00132 }

void mmx::sparse::sub ( dual< C, O > &  res,
const dual< C, O > &  a,
const C &  b 
) [inline]

Definition at line 125 of file sparse_dual.hpp.

References sub().

00125                                                     {
00126   sub((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
00127 }

void mmx::sparse::sub ( dual< C, O > &  res,
const dual< C, O > &  a,
const dual< C, O > &  b 
) [inline]

Definition at line 120 of file sparse_dual.hpp.

Referenced by div_rem(), and sub().

00120                                                             {
00121   sub((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
00122 }

MP mmx::sparse::subs ( const MP &  P,
char *  x,
typename MP::coeff_t  val 
) [inline]

Substitute the variable x by the value val.

Definition at line 950 of file sparse_monomials.hpp.

References subs().

00950                                                       {
00951     int xi = MP::var(x);
00952     if (xi<0)
00953       return P;
00954     else
00955       return subs(P,xi,val);
00956   }

MP mmx::sparse::subs ( const MP &  P,
int  var,
typename MP::coeff_t  val 
) [inline]

Substitute the variable x_(var) by the value val.

Definition at line 905 of file sparse_monomials.hpp.

References C, lvar(), and Monomial.

00906   {
00907     MP Result= 0;
00908     typedef typename MP::coeff_t coeff_t;
00909     typedef typename MP::Monomial monom_t;
00910     //std::cout<<"Begin subs!! " << std::endl;
00911     coeff_t C=0;
00912     for ( typename MP::const_iterator it = P.begin();
00913           it != P.end(); ++it )
00914       {
00915         monom_t m(it->coeff());
00916         for(int ind=0; ind<(lvar(P)+1); ++ind)
00917           {
00918             if (ind == var)
00919               {
00920                 for(int k=0;k<(int)(*it)[ind];k++)
00921                   m*=val;
00922               }
00923             else
00924               {
00925                 if ((*it)[ind] != 0)
00926                   {
00927                     monom_t mon(coeff_t(1),(*it)[ind],ind);
00928                     m*= mon;
00929                   }
00930               }
00931           }
00932         if (m.nvars() == -1)
00933           {
00934             C += m.coeff();
00935           }
00936         else if (m != 0)
00937         {
00938           Result+= m;
00939         }
00940       }
00941     if (C != 0)
00942       Result += monom_t(C);
00943 
00944     return Result;
00945   }

MP mmx::sparse::subs ( unsigned  var,
const X &  val,
const MP &  P 
) [inline]

Substitute the variable x_(var) by the value val.

Definition at line 881 of file sparse_monomials.hpp.

References Monomial, and mmx::pow().

Referenced by solver_mv_monomial< FT, POL >::solve_system(), and subs().

00882   {
00883     MP Result;//("0");
00884     typedef typename MP::coeff_t coeff_t;
00885     typedef typename MP::Monomial monom_t;
00886     
00887     for( typename MP::const_iterator it = P.begin(); it != P.end(); ++it )
00888       {
00889         if ( it->size() > var )
00890           {
00891             monom_t m (*it);
00892             X tmp = pow(val,m[var]);
00893             m.rep()[var] = 0; 
00894             Result += tmp*m;
00895           }
00896         else 
00897           Result += *it;
00898         
00899       }
00900     return Result;
00901   }

MP mmx::sparse::swap ( const MP &  P,
char *  x_i,
char *  x_j 
) [inline]

Swap the variable x_i and x_j in the polynomial P.

Definition at line 992 of file sparse_monomials.hpp.

References swap().

00993   {
00994     typedef typename MP::monom_t monom_t;
00995     int xi = monom_t::index_of_var(x_i);
00996     int xj = monom_t::index_of_var(x_j);
00997     return swap(P,xi,xj);
00998   }

MP mmx::sparse::swap ( const MP &  P,
int  var_i,
int  var_j 
) [inline]

Swap the variable x_(var_i) and x_(var_j) in the polynomial P.

Definition at line 963 of file sparse_monomials.hpp.

References lvar().

Referenced by mmx::CF_positive(), mmx::linear::cpolynom(), binary_sleeve_subdivision< K >::init_pol(), mmx::MCF_positive(), mmx::tensor::reciprocal(), homography< C >::reciprocal_hom(), mmx::univariate::reverse(), mmx::reverse(), mmx::array::reverse(), interval_rep< POL >::reverse_box(), mmx::array::reverse_n(), continued_fraction_subdivision< K >::solve_homography(), swap(), vrestrict(), and mmx::tensor::vswap().

00964   {
00965     MP Result;//("0");
00966     typedef typename MP::monom_t monom_t;
00967     for ( typename MP::const_iterator it = P.begin();
00968           it != P.end(); ++it )
00969       {
00970         monom_t m(it->coeff());
00971         for(int ind=0; ind<(lvar(P)+1); ++ind)
00972           {
00973             if((*it)[ind] !=0 ) {
00974               if (ind == var_i) {
00975                 m*=monom_t(var_j,(*it)[ind]);
00976               } else { 
00977                 if (ind == var_j)
00978                   m*=monom_t(var_i,(*it)[ind]);
00979                 else
00980                   m*= monom_t(ind,(*it)[ind]);
00981               }
00982             }
00983           }
00984         Result+=m;
00985       }
00986     return Result;
00987   }

bool mmx::sparse::with_plus_sign ( const X &  x  )  [inline]

Definition at line 219 of file sparse_dual.hpp.

Referenced by print().

00219 {return x>0;}

Generated on 6 Dec 2012 for realroot by  doxygen 1.6.1