realroot_doc 0.1.1
Classes | Functions
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 ( 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().

                                                            {
  add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
}
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().

                                                     {
  add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
}
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  result,
const monomial_seq< C, O, MONOM, REP > &  p1,
const monomial_seq< C, O, MONOM, REP > &  p2 
)

Definition at line 112 of file sparse_monomials.hpp.

References assert, and Scalar.

  {
    assert(&result != &p1); assert(&result != &p2);
    
    typedef typename Polynomial::const_iterator  const_iterator;
    typedef typename Polynomial::iterator        iterator;
    typedef typename Polynomial::value_type      coeff_type;
    typedef typename Polynomial::Scalar          Scalar;

    const_iterator
      b1=p1.begin(),
      e1=p1.end(),
      b2=p2.begin(),
      e2=p2.end();
    result.resize(p1.size()+p2.size());
    iterator i=result.begin();
    while (b1!=e1 && b2!=e2) {
      if(Polynomial::less(*b2,*b1))
        *i++=*b1++;
      else if(Polynomial::less(*b1,*b2))
        *i++=*b2++;
      else {
        coeff_type c=b1->coeff()+ b2->coeff();
        if (c !=(Scalar)0) {
          *i =*b1;
          i->set_coeff(c);
          ++i;
        }
        ++b1;++b2;
      }
    }
    while (b1!=e1) *i++=*b1++;
    while (b2!=e2) *i++=*b2++;
    
    int m=std::distance(result.begin(),i);
    assert(m>=0);
    result.resize(m);
  }
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  p1,
const monomial_seq< C, O, MONOM, REP > &  p2 
)

Inplace addition.

Definition at line 153 of file sparse_monomials.hpp.

References assert, and Scalar.

                                             {
    
    assert(&p1 != &p2);
    typedef typename Polynomial::const_iterator  const_iterator;
    typedef typename Polynomial::iterator        iterator;
    typedef typename Polynomial::value_type      coeff_type;
    
    //    reserve(p1,p1.size()+p2.size());
    iterator        b1=p1.begin();
    const_iterator  b2=p2.begin();
    while (b1!=p1.end() && b2!=p2.end()) {
      if(Polynomial::less(*b2,*b1))
        b1++;
      else if(Polynomial::less(*b1,*b2))
        {
          b1 = p1.insert(b1,*b2); b1++; b2++;
        }
      else
        {
          coeff_type c=b1->coeff() + b2->coeff();
          if (c != (typename Polynomial::Scalar)0) {
            b1->set_coeff(c); ++b1;
          }else{
            b1 = p1.erase(b1);
          }
          ++b2;
        }
    }
    p1.insert(b1,b2,p2.end());
  }
I mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  p1,
I  b1,
J  e1,
const M &  m2 
)

Definition at line 185 of file sparse_monomials.hpp.

                                                   {
    typedef typename Polynomial::value_type::coeff_t coeff_type;
    
    while (b1!=e1) {
      if(Polynomial::less(m2,*b1))
        {
          b1++; //COUNT<M>('i');
        }
      else if(Polynomial::less(*b1,m2))
        {
          b1=p1.insert(b1,m2);
          return b1;
        }
      else
        {
          coeff_type c=b1->coeff() + m2.coeff();
          if (c !=0) {
            b1->set_coeff(c);
          }else
            b1 = p1.erase(b1);
          return(b1);
        }
    }
    b1 = p1.insert(b1,m2);
    return b1;
  }
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  p,
const typename monomial_seq< C, O, MONOM, REP >::monom_t &  m 
)

Definition at line 213 of file sparse_monomials.hpp.

References add(), and Polynomial.

                                                           {
    Polynomial q(m); add(p,q);
  }
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  p,
const C &  c 
)

Definition at line 218 of file sparse_monomials.hpp.

References add(), and Polynomial.

                                  {
    Polynomial m(c); add(p,m);
  }
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  q,
const X &  c 
)

Definition at line 223 of file sparse_monomials.hpp.

References add(), and Polynomial.

                                                       {
    Polynomial m(c); add(r,q,m);
  }
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().

                                                    {
  add((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
}
void mmx::sparse::add ( monomial_seq< C, O, MONOM, REP > &  r,
const C &  c,
const monomial_seq< C, O, MONOM, REP > &  q 
)

Definition at line 228 of file sparse_monomials.hpp.

References add(), and Polynomial.

                                                       {
    Polynomial m(c); add(r,q,m);
  }
void mmx::sparse::coefficients ( Seq< U > &  r,
const monomial_seq< C, O, MONOM, REP > &  f,
int  v 
)

Definition at line 455 of file sparse_monomials.hpp.

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

                                                    {
    unsigned N = degree(f,v)+1;
    r=Seq<U>(N);
    typename Polynomial::monom_t m;
    for(typename Polynomial::const_iterator it=f.begin(); it != f.end(); it++) {
      m=*it;
      if (v<(int)m.size()) m.set_expt(v,0);
      r[(*it)[v]]+= U(m);
    }
  }
void mmx::sparse::coefficients ( Seq< C > &  r,
const monomial_seq< C, O, MONOM, REP > &  f 
)

Definition at line 467 of file sparse_monomials.hpp.

                                               {
    for(typename Polynomial::const_iterator it=f.begin(); it != f.end(); it++) {
      r<<it->coeff();
    }
  }
POL::coeff_t mmx::sparse::coeffof ( const POL &  p,
const typename POL::monom_t &  mono 
)

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

Definition at line 527 of file sparse_monomials.hpp.

  {
    typedef typename POL::coeff_t coeff_t;
    typename POL::const_iterator m;
    for(m = p.begin();  m!= p.end() && !IsComparable((*m),mono); m++) {}
    if(m != p.end())
      {
        return m->coeff();
      }
    else
      {
        return  coeff_t(0);
      }
  }
C mmx::sparse::content ( const monomial_seq< C, O, MONOM, REP > &  P)

Definition at line 1000 of file sparse_monomials.hpp.

References mmx::gcd().

  {
    C d=0;
    for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
      d= gcd(d,i->coeff());
    }
    return d;
  }
MP mmx::sparse::convert ( const MP &  P,
typename MP::coeff_t  x,
typename MP::coeff_t  y,
int  ind 
)

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().

                                                                          {
    typedef typename MP::const_iterator  const_iterator;
    typedef typename MP::coeff_t coeff_t;
    typedef typename MP::monom_t monom_t;
    MP  res;
    int ind1=0;
    int ind2=0;
    for(int i=0;i<=2;i++)
      {
        if(ind!=i) {ind1=i;break;}
      }
    for(int i=0;i<=2;i++)
      {
        if(ind!=i && ind1!=i) {ind2=i;break;}
      }
    for(const_iterator i = P.begin(); i != P.end(); ++i)
      {
        coeff_t  k=i->coeff();
        int puissx=(*i)[ind1];
        int puissy=(*i)[ind2];
        int d=(*i)[ind];
        coeff_t coeff1=pow(x,puissx);
        coeff_t coeff2=pow(y,puissy);
        k*=coeff1;k*=coeff2;
        MP P1=monom_t(k,ind,d);
        res=res+P1;
      }
    return res;
  }
void mmx::sparse::copy ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  a 
)

Copy of @ in @.

Definition at line 614 of file sparse_monomials.hpp.

Referenced by mmx::let::assign(), 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().

  {
    //to be modified when bug fixed in gcc
    //    using dense::reserve;
    reserve(r,a.size());
    std::copy(a.begin(),a.end(),r.begin());
  }
int mmx::sparse::degree ( const R &  p)

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==().

                       {
    if(!p.size())
      return -1;
    else
      {
        int d = 0;
        for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
          d = std::max(d,degree(*it));
        return d;
      }
  }
int mmx::sparse::degree ( const R &  p,
int  i 
)

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

Definition at line 502 of file sparse_monomials.hpp.

References mmx::vctops::max().

                              {
    if(!p.size())
      return -1;
    else
      {
        int d=0;
        for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
          {
            if(i<=it->nvars()) d = std::max(d,(int)(*it)[i]);
          }
        return d;
      }
  }
void mmx::sparse::diff ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
int  i 
)

Derivative of @ with respect to $^{ th}$ variable put in @.

Definition at line 581 of file sparse_monomials.hpp.

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

  {
    typedef typename Polynomial::Monomial Monomial;
    typedef typename Polynomial::Scalar   Scalar;

    assert(&r != &p);
    r= Polynomial((Scalar)0);
    for (typename Polynomial::const_iterator it = p.begin(); it != p.end(); ++it) {
      if((*it)[i]>0){
        Monomial m(*it);
        m*=(typename Polynomial::coeff_t)(*it)[i];
        m.set_expt(i,(*it)[i]-1);
        add(r,m);
      }
    }
  }
void mmx::sparse::div ( monomial_seq< C, O, MONOM, REP > &  q,
const monomial_seq< C, O, MONOM, REP > &  a,
const monomial_seq< C, O, MONOM, REP > &  b 
) [inline]

Definition at line 419 of file sparse_monomials.hpp.

References div_rem(), and Polynomial.

  {
    Polynomial r(a);
    div_rem(q,r,b);
  }
void mmx::sparse::div ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  b 
) [inline]

Definition at line 426 of file sparse_monomials.hpp.

References div(), and Polynomial.

  {
    Polynomial a(r);
    div(r,a,b);
  }
void mmx::sparse::div ( monomial_seq< C, O, MONOM, REP > &  f,
const typename monomial_seq< C, O, MONOM, REP >::Scalar &  c 
) [inline]

Definition at line 433 of file sparse_monomials.hpp.

  {
    for(typename Polynomial::iterator it=f.begin(); it != f.end(); it++) 
      it->coeff()/=c;
  }
void mmx::sparse::div ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const C &  c 
)

Definition at line 441 of file sparse_monomials.hpp.

References div().

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

Definition at line 205 of file sparse_dual.hpp.

Referenced by div().

                              {
  for(typename dual<C,O>::iterator it=f.begin(); it != f.end(); it++) 
    it->coeff()/=c;
}
void mmx::sparse::div ( dual< C, O > &  r,
const dual< C, O > &  p,
const C &  c 
)

Definition at line 212 of file sparse_dual.hpp.

References div().

                                                   {
  r = p; div(r,c);
}
void mmx::sparse::div_rem ( R &  q,
R &  a,
const R &  b0 
)

Divide @ in place by @, concidering all the monomials.

Definition at line 555 of file sparse_monomials.hpp.

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

Referenced by div(), and rem().

                                      {
    //    std::cout <<"---- Begin div-rem sparse -----"<<std::endl;
    typedef typename R::monom_t       monom_t;
    typedef typename monom_t::coeff_t coeff_t;
    q= R((coeff_t)0);

    if(a==0) return;
    
    R b(b0);
    //coeff_t cb =b0.begin()->coeff();
    //  b/=cb;
    monom_t mb = (*b.begin()), m;
    R t;
    while( a != (coeff_t)0 && divide(*a.begin(), mb, m) )
      {
        mul(t,b,m);
        sub(a,t);
        if ( m != 0 )  add(q,m);
        //      print(std::cout,a); std::cout<<std::endl;
      }
    //    std::cout <<"---- End div-rem sparse -----"<<std::endl;
  }
T mmx::sparse::eval ( const MP &  p,
const V &  v 
)

Definition at line 846 of file sparse_monomials.hpp.

References mmx::assign().

                                {
    T r(0);
    for(typename MP::const_iterator it=p.begin(); it!=p.end(); ++it)
      {
        T c; let::assign(c,it->coeff());
        for(unsigned i=0;i< it->size()&&i<v.size();++i)
          for(int k=0;k<(*it)[i];k++)
            {
              c*=v[i];
            }
        r+=c;
      }
    return r;
  }
void mmx::sparse::eval ( R &  r,
const MP &  p,
const V &  v,
unsigned  n 
)

Definition at line 864 of file sparse_monomials.hpp.

References mmx::assign().

                                                  {
    r=R(0);
    for(typename MP::const_iterator it=p.begin(); it!=p.end(); ++it)
      {
        R c; 
        let::assign(c,it->coeff());
        for(unsigned i=0;i< it->size()&&i<n;++i)
          for(int k=0;k<(*it)[i];k++) {
            c*=v[i];
          }
        r+=c;
      }
  }
monomial_seq<C,O,MONOM,REP>::coeff_t mmx::sparse::eval ( const monomial_seq< C, O, MONOM, REP > &  p,
const typename monomial_seq< C, O, MONOM, REP >::coeff_t &  x,
const typename monomial_seq< C, O, MONOM, REP >::coeff_t &  y 
)

Evaluate the polynomial @ for =x@, =y@, and the other xi=1.

Definition at line 624 of file sparse_monomials.hpp.

                                            {
    typename Polynomial::coeff_t r(0);
    for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
      {
        typename Polynomial::coeff_t c(it->coeff());
        //for(unsigned int i=0;i<2;++i)
        for(int k=0;k<(int)(*it)[0];k++)
          c*=x;
        for(int k=0;k<(int)(*it)[1];k++)
          c*=y;
        r+=c;
      }
    return r;
  }
void mmx::sparse::eval ( R &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const X &  x 
) [inline]

Evaluate the polynomial @ for =x@, =y@, and the other xi=1.

Definition at line 661 of file sparse_monomials.hpp.

                                              {
    r=(R)0;
    for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
      {
        R c(it->coeff());
        for(int k=0;k<(int)(*it)[0];k++)
          c*=x;
        r+=(R)c;
      }
  }
void mmx::sparse::eval_at ( R &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const VCT &  x 
)

Definition at line 643 of file sparse_monomials.hpp.

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

                        {
    r=R(0);
    for(typename Polynomial::const_iterator it=p.begin(); it!=p.end(); ++it)
      {
        R c(it->coeff());
        for(unsigned int j=0;j<x.size()&& j<it->nvars();++j)
          for(int k=0;k<(int)(*it)[j];k++)
            c*=x[j];
        r+=c;
      }
    return r;
  }
void mmx::sparse::homogenize ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
int  n,
const monomial_seq< C, O, MONOM, REP > &  v 
) [inline]

Definition at line 686 of file sparse_monomials.hpp.

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

                                                                             {
    Polynomial t;
    int d = degree(p,n);
    for(typename Polynomial::const_iterator it=p.begin();it != p.end();it++) {
      t=*it;
      for (int i=0;i<d-(*it)[n];i++) mul(t,v);
      add(r,t);
    }
  }
void mmx::sparse::homogenize ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const monomial_seq< C, O, MONOM, REP > &  v 
) [inline]

Definition at line 674 of file sparse_monomials.hpp.

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

                                                                      {
    Polynomial t;
    int d = sparse::degree(p);
    for(typename Polynomial::const_iterator it=p.begin();it != p.end();it++) {
      t=*it;
      for (int i=0;i<d-degree(*it);i++) mul(t,v);
      add(r,t);
    }
  }
POL::const_iterator mmx::sparse::last_term ( const POL &  p)

Definition at line 544 of file sparse_monomials.hpp.

References assert.

                          {
    assert(p.size()>0);
    typename POL::const_iterator it=p.end();
    it--;
    return it;
  }
R::coeff_t& mmx::sparse::leadingcoeff ( R &  a)

Definition at line 517 of file sparse_monomials.hpp.

{return a.begin()->coeff();}
R::coeff_t mmx::sparse::leadingcoeff ( const R &  a)

Definition at line 520 of file sparse_monomials.hpp.

{return a.begin()->coeff();}
int mmx::sparse::lvar ( const R &  p)

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().

                                             {
  int v = -1;
  for (typename R::const_iterator it = p.begin(); it != p.end(); ++it)
    v = std::max(v,it->l_variable());
  return v;
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  a,
const typename monomial_seq< C, O, MONOM, 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().

                                                                                {
    mul_ext(r,a,m);
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const typename monomial_seq< C, O, MONOM, REP >::monom_t &  m 
) [inline]

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 324 of file sparse_monomials.hpp.

                                                           {
    typename Polynomial::iterator i=r.begin();
    for(; i!=r.end(); ++i) *i *= m; 
  }
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().

                                                    {
  mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
}
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  a,
const monomial_seq< C, O, MONOM, REP > &  b 
) [inline]

Multiplication of two polynomials.

Definition at line 348 of file sparse_monomials.hpp.

References mul().

  {
    if (a.size()==0) return;
    if (b.size()==0) return;
    if (a.size()<b.size())
      mul(r,a.begin(),a.end(),b);
    else
      mul(r,b.begin(),b.end(),a);
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  a,
const monomial_seq< C, O, MONOM, REP > &  b,
const X &  o 
) [inline]

Specialisation for list.

Definition at line 360 of file sparse_monomials.hpp.

References add(), and mul_ext().

  {
    typedef typename Polynomial::const_iterator const_iterator;
    typedef typename Polynomial::iterator       iterator;
    typedef typename Polynomial::monomt_t       M;

    r.resize(0);
    M m;
    for(const_iterator i=b.begin();i !=b.end();i++)
      {
        if(r.size())
          {
            iterator ip = r.begin();
            for(const_iterator j=a.begin();j != a.end();j++) { 
              m  = *j * *i;
              ip = add(r,ip,r.end(),m);//,O()); 
            }
            //MPOLDST::mul_ext(tmp,a,*i);
            //MPOLDST::add<list<M>,vector<M>,O>(r,tmp);
          }
        else
          mul_ext(r,a,*i);
      }
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p 
) [inline]

Definition at line 413 of file sparse_monomials.hpp.

References mul(), and Polynomial.

  {
    Polynomial s(r); mul(r,s,p); 
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
typename monomial_seq< C, O, MONOM, REP >::const_iterator  b,
typename monomial_seq< C, O, MONOM, REP >::const_iterator  e,
const monomial_seq< C, O, MONOM, REP > &  p 
) [inline]

Definition at line 389 of file sparse_monomials.hpp.

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

                           {

    
    typedef typename Polynomial::const_iterator  const_iterator;
    int n=std::distance(b,e);
    assert(n>=0);
    if (n==0) r.resize(0);
    if (n==1) 
      mul_ext(r,p,*b);
    else {
      const_iterator med=b; // b+(n/2);
      for(int i=0; i<n/2 && med !=e;i++,med++) {}

      Polynomial tmp0((C)0), tmp1((C)0);
      mul(tmp0,b,med,p);
      mul(tmp1,med,e,p);
      add(r,tmp0,tmp1);
    }

  }
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().

                                                            {
  mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
}
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const C &  c 
)

Definition at line 296 of file sparse_monomials.hpp.

References mul().

                                                       {
    r = p; mul(r,c);
  }
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().

                                                    {
  mul((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
}
void mmx::sparse::mul ( dual< C, O > &  res,
const monomial_seq< C, O > &  p,
const dual< C, O > &  l 
)

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().

                                                                    {
  monomial_seq<C,O> t;
  mul(t,p,(monomial_seq<C,O>)l);
  typedef typename dual<C,O>::const_iterator iterator;
  for(iterator it=t.begin();it != t.end();it++)
    {
      bool neg=true;
      for(unsigned j=0;j<it->size() && neg;j++) {
        if((*it)[j]>0) neg=false;
      }
      if(neg) res.push_back(*it);
    }
}
void mmx::sparse::mul ( monomial_seq< C, O > &  res,
const dual< C, O > &  l,
const monomial_seq< C, O > &  p 
)

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().

                                                                            {
  monomial_seq<C,O> t;
  mul(t,(monomial_seq<C,O>)l,p);
  typedef typename dual<C,O>::const_iterator iterator;
  for(iterator it=t.begin();it != t.end();it++)
    {
      bool pos=true;
      for(unsigned j=0;j<it->size() && pos;j++) {
        if((*it)[j]<0) pos=false;
      }
      if(pos) res.push_back(*it);
    }
}
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const X &  c,
const monomial_seq< C, O, MONOM, REP > &  p 
)

Definition at line 302 of file sparse_monomials.hpp.

References mul().

                                                       {
    r = p; mul(r,c);
  }
void mmx::sparse::mul ( monomial_seq< C, O, MONOM, REP > &  r,
const C &  c 
)

Multiplication of a polynomial by a monomial or a scalar.

Definition at line 289 of file sparse_monomials.hpp.

                                  {
    for(typename Polynomial::iterator it=r.begin(); it!=r.end(); ++it) {
      it->coeff()*=c;
    }
  }
void mmx::sparse::mul_ext ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, 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().

                                                           {
    r.resize(a.size());
    typename Polynomial::const_iterator b=a.begin(); 
    typename Polynomial::iterator i=r.begin();
    for(; b!=a.end(); ++i, ++b) *i = (*b) * m; 
     //    VECTOR::apply_mult(r, a, m);
  }
void mmx::sparse::mul_ext_e ( monomial_seq< C, O, MONOM, REP > &  result,
const monomial_seq< C, O, MONOM, REP > &  a,
const M &  m 
) [inline]

Definition at line 330 of file sparse_monomials.hpp.

  {
    typedef typename Polynomial::const_iterator  const_iterator;
    typedef typename Polynomial::iterator        iterator;
    typedef typename Polynomial::monom_t         R;

    result.resize(0);
    iterator i=result.begin();
    R tmp;
    for(const_iterator b=a.begin();b!=a.end(); ++b)
      {
        tmp = (*b) * m;
        (i=result.insert(i,tmp))++;
      }
  }
unsigned mmx::sparse::nbvar ( const R &  p)

Number of variables of a polynomial.

Definition at line 482 of file sparse_monomials.hpp.

                                                   {
    return p.nbvar();
  }
void mmx::sparse::neg_exponent ( dual< C, O > &  p)

Definition at line 70 of file sparse_dual.hpp.

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

{
  typedef typename dual<C,O>::iterator iterator;
  for(iterator it=p.begin();it != p.end();it++)
    {
      for(int j=0;j<(it->nvars()+1);j++)
        {
          it->set_expt(j,-(*it)[j]);
        }
    }
}
OS& mmx::sparse::print ( OS &  os,
const monomial_seq< C, O, MONOM, REP > &  P 
)

Definition at line 767 of file sparse_monomials.hpp.

References variables::default_, and print().

  {
    return print(os,P,variables::default_);
  }
OSTREAM& mmx::sparse::print ( OSTREAM &  os,
const dual< C, O > &  P,
const variables &  V 
)

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().

                                                              {
 if ( P.begin() == P.end() ) {
   os << '0';
   return os;
 }
 typename dual<C,O>::const_iterator i = P.begin();
 while ( i != P.end() ) {
   if ( with_plus_sign(i->coeff()) && i !=P.begin())
     os <<'+';
   print_dual(os,*i++,V);
 }
 return os;
}
void mmx::sparse::print ( const T &  x)

Definition at line 957 of file sparse_monomials.hpp.

{std::cout<<x<<std::endl;}
OS& mmx::sparse::print ( OS &  os,
const monomial_seq< C, O, MONOM, REP > &  P,
const VARIABLES &  V 
)

Definition at line 732 of file sparse_monomials.hpp.

References print().

                                                            {
    if ( P.begin() == P.end() )
      {
        os << '0';
        return os;
      }
    for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
      std::ostringstream sm;
      print(sm,*i,V);
      if(sm.str()[0] != '-' && sm.str()[0] != '+' && i != P.begin())
        os <<'+';
      os<<sm.str();
    }
    return os;
  }
OS& mmx::sparse::print_as_double ( OS &  os,
const monomial_seq< C, O, MONOM, REP > &  P,
const VARIABLES &  V 
)

Definition at line 750 of file sparse_monomials.hpp.

                                                                      {
    if ( P.begin() == P.end() )
      {
        os << '0';
        return os;
      }
    for(typename Polynomial::const_iterator i = P.begin(); i != P.end();i++ ) {
      std::ostringstream sm;
      print_as_double(sm,*i,V);
      if(sm.str()[0] != '-' && sm.str()[0] != '+' && i != P.begin())
        os <<'+';
      os<<sm.str();
    }
    return os;
  }
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().

                                                                 { 
  if (m.coeff() ==0 ) {
    os<<"0"; return os;
  }
  int i=m.size()-1;
  while(i> -1 && m[i]==0) i--;
  if(i<0)
    os <<m.coeff();
  else {
    if(m.coeff() != 1) {
      if(m.coeff()==-1) 
         os << "-"; 
      else {  
        os << m.coeff(); os <<"*"; 
      }
    }
  }
  bool first=true;
  for (unsigned i = 0; i < m.size(); ++i) {
    if (m[i] !=0) {
      if(first)
        first =false;
      else
        os<<'*';
      os << 'd'<<V[i];
      if (m[i] != -1)
        os << '^' <<(-m[i]);
    }
  }
  return os;
}
OS& mmx::sparse::print_verbatim ( OS &  os,
const monomial_seq< C, O, MONOM, REP > &  P 
)

Definition at line 775 of file sparse_monomials.hpp.

  {
    if ( P.begin() == P.end() )
      {
        os << '0';
        return os;
      }
    for( typename Polynomial::const_iterator i=P.begin(); i != P.end();++i)
      {
        os<<" "<<i->coeff()<<" [";
        for(int l=0;l<i->size();l++) os<<(*i)[l]<<" ";
        os<<"]";
      }
    return os;
  }
void mmx::sparse::rem ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  a,
const monomial_seq< C, O, MONOM, REP > &  b 
) [inline]

Definition at line 447 of file sparse_monomials.hpp.

References div_rem(), and Polynomial.

  {
    Polynomial q; r=a;
    div_rem(q,r,b);
  }
POL mmx::sparse::scale ( const POL &  p,
C  a,
int  v 
)

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().

                                   {
    
    typedef typename POL::monom_t monomial;
    
    POL  np(p);
    
    for ( typename POL::const_iterator i = np.begin(); i != np.end(); ++i ) {
      i->coeff()*= pow( a, int( i->operator[]( v ) ) );
    }
    return np;
    
  }
void mmx::sparse::shift ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  p,
const typename monomial_seq< C, O, MONOM, REP >::monom_t &  m 
)

Multiply @ by a monomial @ and put in @.

Definition at line 601 of file sparse_monomials.hpp.

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

  {
    assert(&r != &p);
    typedef typename Polynomial::monom_t Monomial;
    r= Polynomial(0);
    for (typename Polynomial::const_iterator it = p.begin(); it != p.end(); ++it) {
      add(r,*it*m);
    }
  }
POL mmx::sparse::shift ( typename POL::const_iterator  monom,
const C &  a,
int  i 
)

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

                                                             {
    
    POL polynom;
    // Definition du type monome.
    typedef typename POL::monom_t monomial;
    // monomiale temporaire.
    monomial tmpmonomial;
    
    int i0 = i;
    int i1 = (i + 1) % 3;
    int i2 = (i + 2) % 3;
    
    // Si la variable est presente dans le monome.
    if ( (a!=0) && ( monom->operator[](i0) !=0 ) )
      {
        polynom = binomial< POL >(C(1.), i0, monom->operator[](i0), a);
        int expt[3];
        expt[i0] = 0;
        expt[i1] = monom->operator[](i1);
        expt[i2] = monom->operator[](i2);
        
        if ( ( expt[i0] == 0 ) && ( expt[i1] == 0 ) && ( expt[i2] == 0 ) )
          tmpmonomial = monomial( monom->coeff(), 0, 0 );
        else   tmpmonomial = monomial( monom->coeff(), 3, expt );
        
        polynom *= tmpmonomial;
      }
    // Si a = 0 alors le monome reste inchange.
    else polynom = ( *monom );
    
    return polynom;
    
  }
void mmx::sparse::sub ( monomial_seq< C, O, MONOM, REP > &  result,
const monomial_seq< C, O, MONOM, REP > &  p1,
const monomial_seq< C, O, MONOM, REP > &  p2 
)

Definition at line 233 of file sparse_monomials.hpp.

References assert.

  {
    assert(&result != &p1); assert(&result != &p2);
    typedef typename Polynomial::const_iterator  const_iterator;
    typedef typename Polynomial::iterator        iterator;
    typedef typename Polynomial::value_type      coeff_type;
    const_iterator
      b1=p1.begin(),
      e1=p1.end(),
      b2=p2.begin(),
      e2=p2.end();
    result.resize(p1.size()+p2.size());
    iterator i=result.begin();
    while (b1!=e1 && b2!=e2) {
      if(Polynomial::less(*b2,*b1))
        *i++=*b1++;
      else if(Polynomial::less(*b1,*b2))
        {
          *i=*b2++; i->coeff()*= -1; i++;
        }
      else {
        coeff_type c=b1->coeff()- b2->coeff();
        if (c !=0) {
          *i =*b1;
          i->set_coeff(c);
          ++i;
        }
        ++b1;++b2;
      }
    }
    while (b1!=e1) *i++=*b1++;
    while (b2!=e2) {*i=*b2++;i->coeff()*=-1;i++;}
    
    int m=std::distance(result.begin(),i);
    assert(m>=0);
    result.resize(m);
  }
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().

                                                            {
  sub((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,(const monomial_seq<C,O>&)b);
}
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().

                                                    {
  sub((monomial_seq<C,O>&)res,a,(const monomial_seq<C,O>&)b);
}
void mmx::sparse::sub ( monomial_seq< C, O, MONOM, REP > &  r,
const X &  c,
const monomial_seq< C, O, MONOM, REP > &  q 
)

Definition at line 283 of file sparse_monomials.hpp.

References Polynomial, and sub().

                                                       {
    Polynomial m(c); sub(r,m,q);
  }
void mmx::sparse::sub ( monomial_seq< C, O, MONOM, REP > &  p,
const monomial_seq< C, O, MONOM, REP > &  q 
)

Definition at line 272 of file sparse_monomials.hpp.

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

                                           {
    Polynomial m(q); mul(m,(C)-1);
    add(p,m);
  }
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().

                                                    {
  sub((monomial_seq<C,O>&)res,(const monomial_seq<C,O>&)a,b);
}
void mmx::sparse::sub ( monomial_seq< C, O, MONOM, REP > &  r,
const monomial_seq< C, O, MONOM, REP > &  q,
const X &  c 
)

Definition at line 278 of file sparse_monomials.hpp.

References add(), and Polynomial.

                                                       {
    Polynomial m(C(-c)); add(r,q,m);
  }
MP mmx::sparse::subs ( const MP &  P,
char *  x,
typename MP::coeff_t  val 
)

Substitute the variable x by the value val.

Definition at line 948 of file sparse_monomials.hpp.

References subs().

                                                      {
    int xi = MP::var(x);
    if (xi<0)
      return P;
    else
      return subs(P,xi,val);
  }
MP mmx::sparse::subs ( const MP &  P,
int  var,
typename MP::coeff_t  val 
)

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

Definition at line 905 of file sparse_monomials.hpp.

References lvar(), and Monomial.

  {
    MP Result;//("0");
    typedef typename MP::coeff_t coeff_t;
    typedef typename MP::Monomial monom_t;
        //  std::cout<<"Begin subs!!"<<endl;
    coeff_t C=0;
    for ( typename MP::const_iterator it = P.begin();
          it != P.end(); ++it )
      {
        monom_t m(it->coeff());
        for(int ind=0; ind<(lvar(P)+1); ++ind)
          {
            if (ind == var)
              {
                for(int k=0;k<(int)(*it)[ind];k++)
                  m*=val;
              }
            else
              {
                if ((*it)[ind] != 0)
                  {
                    monom_t mon(ind,(*it)[ind]);
                    m*= mon;
                  }
              }
          }
        if (m.nvars() == -1)
          {
            C += m.coeff();
          }
        else if (m != 0)
          Result+= m;
      }
    if (C != 0)
      Result += monom_t(C);
          //std::cout<<"End subs!!"<<endl;
    return Result;
  }
MP mmx::sparse::subs ( unsigned  var,
const X &  val,
const MP &  P 
)

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().

  {
    MP Result;//("0");
    typedef typename MP::coeff_t coeff_t;
    typedef typename MP::Monomial monom_t;
    
    for( typename MP::const_iterator it = P.begin(); it != P.end(); ++it )
      {
        if ( it->size() > var )
          {
            monom_t m (*it);
            X tmp = pow(val,m[var]);
            m.rep()[var] = 0; 
            Result += tmp*m;
          }
        else 
          Result += *it;
        
      }
    return Result;
  }
MP mmx::sparse::swap ( const MP &  P,
char *  x_i,
char *  x_j 
)

Swap the variable x_i and x_j in the polynomial P.

Definition at line 990 of file sparse_monomials.hpp.

References swap().

  {
    typedef typename MP::monom_t monom_t;
    int xi = monom_t::index_of_var(x_i);
    int xj = monom_t::index_of_var(x_j);
    return swap(P,xi,xj);
  }
MP mmx::sparse::swap ( const MP &  P,
int  var_i,
int  var_j 
)

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

Definition at line 961 of file sparse_monomials.hpp.

References lvar().

Referenced by mmx::let::assign(), 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().

  {
    MP Result;//("0");
    typedef typename MP::monom_t monom_t;
    for ( typename MP::const_iterator it = P.begin();
          it != P.end(); ++it )
      {
        monom_t m(it->coeff());
        for(int ind=0; ind<(lvar(P)+1); ++ind)
          {
            if((*it)[ind] !=0 ) {
              if (ind == var_i) {
                m*=monom_t(var_j,(*it)[ind]);
              } else { 
                if (ind == var_j)
                  m*=monom_t(var_i,(*it)[ind]);
                else
                  m*= monom_t(ind,(*it)[ind]);
              }
            }
          }
        Result+=m;
      }
    return Result;
  }
bool mmx::sparse::with_plus_sign ( const X &  x)

Definition at line 219 of file sparse_dual.hpp.

Referenced by print().

{return x>0;}