include/borderbasix/corealgo.cc

Go to the documentation of this file.

template<typename typP,typename typPk,typename Base>
void Crochetchoix(const typP & P,typPk & Pk, typPk & redspol,int k,
                    Base &b);

template<template<typename> class cont,typename mon, typename T>
cont<pol<mon,T> > Crochet(const cont<pol<mon,T> > &P, int k)
{
  cont<pol<mon,T> > res;
  for(typename cont<pol<mon,T> >::const_iterator iter=P.begin()
        ;iter!=P.end();iter++)
    {
      if(Degree(*iter)==k) res.push_back(*iter);
    }
  return res;
}

template<typename typPk>
void stab(typPk & Pk)
{
  typedef typename typPk::value_type pol;
  for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    {
      pol tmpres=mon(0);
      for(typename pol::iterator iterpol=iter->begin();iterpol!=iter->end();
          iterpol++)
        {
          if(!Iszero(iterpol->GetCoeff()))
            tmpres+=*iterpol;
        }
      *iter=tmpres;
    }
}

template<typename T>
void  my_merge(T &l1,const T &l2)
{
  typename T::const_iterator iter=l2.begin();
  for(;iter!=l2.end();iter++)
    l1.push_back(*iter);
}

template<typename mon>
mon lcm(const mon &m1,const mon &m2)
{
  mon m(1);
  int maxi=max(lvar(m1.rep),lvar(m2.rep));
  for(int i=0;i<=maxi;i++)
    m*=mon(i,max(m1.GetDegree(i),m2.GetDegree(i)));
  return m;
}

template<typename typppcm,typename Base>
int compute_ppcm(typppcm &ppcm,const Base & b)
{
  typedef typename Base::mon mon;
  //typppcm tmpppcm;
  int maxdeg=-1;
  list<mon> list1,list2;
  for(typename Base::const_reverse_iterator iter=b.rbegin()
        ;iter==b.rbegin();iter++)
    {
      for(int i=0;i<iter->taille2;i++)
        for(int j=i+1;j<iter->taille2;j++)
          {
            mon tmpmon=lcm(iter->refuse[i],iter->refuse[j]);
#ifndef oldppcm
            if((!ppcm.count(tmpmon))&& 
               (tmpmon.GetDegree()!=
                (iter->refuse[i].GetDegree()+iter->refuse[j].GetDegree())))
              ppcm[tmpmon]=1;
            //cout<<"ppcm rajoute "<<tmpmon<<" "<<iter->refuse[i]<<" "<<iter->refuse[j]<<endl;
#else
            if((tmpmon.GetDegree()!=
                (iter->refuse[i].GetDegree()+iter->refuse[j].GetDegree())))
              list1.push_back(tmpmon);
#endif  
          }
    }
#ifdef oldppcm  
  for(typename list<mon>::iterator iter1=list1.begin();
      iter1!=list1.end();iter1++)
    list2.push_back(*iter1);
  for(typename list<mon>::iterator iter1=list1.begin();
      iter1!=list1.end();iter1++)
    {
      for(typename list<mon>::iterator iter2=list2.begin();
          iter2!=list2.end();iter2++)
        if(isdivisible(*iter1,*iter2,b))
          list2.erase(iter2--);
    }
  maxdeg=0;
#ifdef DEB
  cout<<"liste2.size "<<list2.size()<<endl;
#endif
  for(typename list<mon>::iterator iter2=list2.begin();
          iter2!=list2.end();iter2++)
    {
      cout<<"je passe ici "<<*iter2<<endl;
      ppcm[*iter2]=1;
      if(iter2->GetDegree()>maxdeg)
        maxdeg=iter2->GetDegree();
    }
#endif
  return maxdeg;
}

template<typename mon,typename Base,typename typppcm>
int goodspol(const mon &m1,const mon &m2, typppcm & ppcm,const Base &b
#ifdef NO_TWICE
  ,const typMk &Spoldejavu)
#else
  )
#endif
{
  //list<mon> ppcm;
  int res=0,comp=0;//,nobplus=1;
  mon m=m1;
  for(int i=0;i<b.nbvar();i++)
    if(m1.GetDegree(i)!=m2.GetDegree(i))
      {
        comp++;
        if (m1.GetDegree(i)-m2.GetDegree(i)==1)
          res+=1;
        if (m1.GetDegree(i)-m2.GetDegree(i)==-1)
          {
            res+=1;
            m*=mon(i,1);
          }
      };
  //compute_ppcm(ppcm,b);
  //if((res==2)&&(comp==2)) 
  //  for(int i=0;i<b.nbvar();i++)
  //    if(m.GetDegree(i)>0)
  //    nobplus=nobplus && !IsinB(my_divmon(m,i,b),b);
   //cout<<"m1 "<<m1<<" m2 "<<m2<<" resultat "<<((res==2)&&(comp==2))<<endl;
   //return ((res==2)&&(comp==2)&&nobplus);
  //cout<<m1<<" < "<<m2<<" res "<<(member(ppcm,m)&&(res==2)&&(comp==2))<<endl;
  #ifdef NO_TWICE
  return (res==2)&&(comp==2)&&ppcm[m]&&!member(Spoldejavu,m);
  #else
  return (res==2)&&(comp==2)&&ppcm[m];
  #endif
//return (res==2)&&(comp==2)&&ppcm.count(m);//&&!member(Spoldejavu,m);
}

template<typename typPk,typename Base>
typPk Spolordsup(typPk Pk,const Base & b
#ifndef NO_TWICE
)
#else
,const typMk & Spoldejavu)
#endif
{
  typedef typename typPk::value_type::monom_t mon;
  //typedef typename typ::order_t O;
#ifdef experiment
  typename typPk::value_type tmp;
#endif
  map<mon,int> ppcm;
  typPk res;
  int maxdeg;
  //cout<<"compute ppcm"<<endl;
  maxdeg=compute_ppcm(ppcm,b);
  //cout<<"test goodspol"<<endl;
  for(typename typPk::iterator iter1=Pk.begin();iter1!=Pk.end();iter1++)
    for(typename typPk::iterator iter2=iter1;iter2!=Pk.end();iter2++)
#ifndef NO_TWICE      
      if (goodspol(iter1->ind,iter2->ind,ppcm,b))
#else
        if (goodspol(iter1->ind,iter2->ind,ppcm,b,Spoldejavu))
#endif
        {
          //cout<<"goospol "<<iter1->ind<<" "<<iter2->ind<<endl;
          res.push_back(*iter1);
          res.push_back(*iter2);
        }
#ifdef experiment
  tmp.ind.SetCoeff(maxdeg);
  res.push_back(tmp);
#endif
  return res;
}
template<typename typP>
int minmaxdegP(typP P,int &maxdeg)
{
  int res=Degree(P.front());
  maxdeg=res;
  for(typename typP::iterator iter=P.begin();iter!=P.end();iter++)
    {
      res=(res>Degree(*iter))?Degree(*iter):res;
      maxdeg=(maxdeg<Degree(*iter))?Degree(*iter):maxdeg;
    }
  return res;
}
template<typename typP>
typP Crochet(const typP &P, int k)
{
  typP res;
  for(typename typP::const_iterator iter=P.begin();iter!=P.end();iter++)
    if(Degree(*iter)==k) res.push_back(*iter);
  return res;
}
template<typename typP, typename Base>
void Setnbvars(const typP &tmpPk,Base& b)
{
  int tmpvar=0;
  for(typename typP::const_iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
    for(typename typP::value_type::const_iterator iterpol=iter->begin();
        iterpol!=iter->end();iterpol++)
      if(tmpvar<lvar(iterpol->rep)) tmpvar=lvar(iterpol->rep);
  b.nbvars=tmpvar+1;
}

template<typename typP, typename typMk, typename Base>
void DoBaseMk(const typP &tmpPk, typMk &Mk, Base &b)
{
  typedef typename typMk::value_type mon;
  typename Base::predicat_t tmp;
  int i=0;
  //int tmpvar=0;
   
  for(typename typP::const_iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
    {
      mon tmp(choice(*iter,b));
      int yes=1;
      //  cout<<"pol dans DoBaseMk "<<endl<<*iter<<endl<<"g choisi "<<tmp<<endl;
      tmp.SetCoeff(1);//*=mon(1/tmp.GetCoeff());
      for(typename typMk::iterator iter=Mk.begin();iter!=Mk.end();iter++)
        if(*iter==tmp) {yes=0;break;};
      if(yes) Mk.push_back(tmp);
    }
  //cout<<"Mk.size()"<<Mk.size()<<endl;
  tmp.taille2=Mk.size();
  tmp.refuse=(mon*)MAC_REV_MALLOC<mon>(tmp.taille2*sizeof(mon));
  tmp.taille1=1;
  tmp.accept=(mon*)MAC_REV_MALLOC<mon>(sizeof(mon));
  tmp.accept[0]=mon(1);
  i=0;//pour en etre bien sur
  for(typename typMk::iterator iter=Mk.begin();iter!=Mk.end();iter++,i++)
    {
      tmp.refuse[i]=*iter;
    };
  if(!b.def.empty())
    {
      typename Base::predicat_t verytmp;
      for(typename Base::iterator iter=b.begin();iter!=b.end();iter++)
        {
          verytmp=*iter;
          MAC_REV_FREE<mon>(verytmp.refuse,verytmp.taille2*sizeof(mon));
          MAC_REV_FREE<mon>(verytmp.accept,verytmp.taille1*sizeof(mon));
        }
      b.erase(b.begin(),b.end());
    }
  b.def.push_back(tmp);
  return;
}

template <typename typPk,typename typMk,typename typmat >
typmat*
MatrixOf(const typPk & L, 
         const typMk & lm,const typmat &mat) 
{
  typedef typename typPk::value_type POL;
  typedef typename typMk::value_type monom_t;  
  typmat *res=NULL;
  map<monom_t,int> index;
  int l=1;
  if (res!=NULL) {delete res;};
  for(typename typMk::const_iterator m = lm.begin(); m!=lm.end(); m++){
    index[*m]=l;
    l++;
  }
  int c;
  res=new typmat(L.size(),lm.size());
  l=0;
  // cout<<"L.size() "<<L.size()<<" lm.size() "<<lm.size()<<endl;
  for(typename typPk::const_iterator pi = L.begin(); pi != L.end(); ++pi){
    for(typename POL::const_iterator m = pi->begin(); m!=pi->end(); m++)
      {
        
        if((index.count(*m))) 
          {
            c=index[*m];
            (*res)(l,c-1,m->GetCoeff());
          }
      }
    l++;
  }
  return res;   
}

template<typename typMat,typename typP,typename typPk,typename typMk, typename Base,typename typdump>
void init_algo(typP &P,int &nouveaumon, int &maxdeg, int & k
               ,typPk &Pk, typMk & Mk, Base & b, typdump & dump)
{
  typedef typename typPk::value_type pol;
  typedef typename pol::coeff_t coeff;
  typedef typename pol::monom_t mon;
  const typename typP::value_type::order_t (tmpord)(const mon,const mon);
  typP tmpPk=P;
  pol debugpol;
  typMat *Mat;
  int *pr,*pc,flag=1;
  setorder(my_ord);
  nouveaumon=1;
  Setnbvars(P,b);
#ifdef unimul
  init_multiple(b.nbvars);
#endif
#ifdef uninf
  init_nf<pol>(b.nbvars);
#endif 
  while(flag)
    {
      Mk.erase(Mk.begin(),Mk.end());
      //cout<<"mindeg"<<endl;
      k=minmaxdegP(tmpPk,maxdeg);
      //cout<<"Crochet"<<endl;
      //tmpPk.push_back(Crochet(P,k).front());
      tmpPk=Crochet(tmpPk,k);
#ifdef DEB
      for(typename typP::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
      cout<<"pol pendant init"<<endl<<*iter<<endl;
#endif 
      DoBaseMk(tmpPk,Mk,b);
      // for(typename typMk::iterator iter=Mk.begin();iter!=Mk.end();iter++)
      //        cout<<*iter<<endl;
      //cout<<"Matrixof"<<endl;
      Mat=MatrixOf(tmpPk,Mk,typMat());
      //affdebug(*Mat);
      //cout<<"solve"<<endl;
      tmpPk=Solve(*Mat,tmpPk,&pr,&pc);
      selectnozero(tmpPk);
      //affdebug(*Mat);
      stab(tmpPk);
      //for(typename typP::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
      //        cout<<"pol pendant init"<<endl<<*iter<<endl;
      //  cout<<"deletemat"<<endl;
      if(my_rank(*Mat)==(int)tmpPk.size()) flag=0;
      Mat->destroystore();
      delete(Mat);
      free(pr);
      free(pc);
    }
  //cout<<"Pk,apres solve"<<endl<<tmpPk.front()<<endl;
  //   cout<<"convertion"<<endl;
  // for(typename typP::value_type::iterator iter=tmpPk.front().begin();
  //   iter!=tmpPk.front().end();iter++)
  // cout<<"*iter "<<*iter<<" IsinB "<<IsinB(*iter,b)<<endl;
  //for(typename typP::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
  //cout<<"pol apres les solve "<<endl<<*iter<<endl;
      for(typename typP::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
        {
          Pk.push_back(convert<pol>(*iter,b));
          //cout<<"le pol apres invconv"<<endl
          //  <<invconv<typename typP::value_type>(*Pk.rbegin())<<endl;
          //  cout<<"le pol original "<<endl<<*iter<<endl;
        }
      //      for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
      //        cout<<"pol apres les solve "<<endl<<iter->ind<<endl;
      debugpol=Pk.front();
      //for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
        //      cout<<"apres convertion "<<endl<<
        //  invconv<typename typP::value_type>(*iter)<<endl;
      //cout<<"size "<<debugpol.size<<endl;
      //cout<<"Dump "<<Pk.front().ind.GetCoeff()<<endl;
      Dump(Pk,dump);
      //cout<<"apres Dump "<<invconv<typename typP::value_type>(Pk.front())<<endl;
      //cout<<"je sort d'init_algo "<<endl;
      //cout<<"k vaut "<<k<<endl;
      //      cout<<" Pk.size() "<<Pk.size()<<endl;
  return ;
}

template<typename pol,typename coeff>
void inline my_plus2(pol &res1, pol & res2,const pol& nf,
                     const coeff &toto1,const coeff &toto2 )
{
  typedef typename pol::monom_t mon;
   unsigned int i=0,stock;;
   unsigned int ttmp;
   unsigned int tmp;
   register coeff *res1nf,*res2nf,*nfnf,*tmpcoeff;
  tmp=nf.size;
  if(res1.size<tmp)
    {
      res1.nf=(coeff*)MAC_REV_REALLOC<coeff>(res1.nf,res1.size*sizeof(coeff)
                                     ,tmp*sizeof(coeff));
      for(i=res1.size;i<tmp;i++)
        res1.nf[i]=0;
      res1.size=tmp;
    }
  if(res2.size<tmp)
    {
      res2.nf=(coeff*)MAC_REV_REALLOC<coeff>(res2.nf,res2.size*sizeof(coeff)
                                             ,tmp*sizeof(coeff));
      for(i=res2.size;i<tmp;i++)
        res2.nf[i]=0;
      res2.size=tmp;
    }
  tmp=nf.size;
  ttmp=(tmp/8)*8;
  tmp=tmp & 7;//15;//16 pourquoi... PARCE QUE!!!!! :-))
  res1nf=res1.nf;
  res2nf=res2.nf;
  nfnf=nf.nf;
  for(i=0;i<ttmp;i+=8)
    {
      //1
      tmpcoeff=nfnf+i;
      res1nf[i]-=*tmpcoeff*toto1;
      res2nf[i]-=*tmpcoeff*toto2;
      //2 
      tmpcoeff=nfnf+i+1;
      res1nf[i+1]-=*tmpcoeff*toto1;
      res2nf[i+1]-=*tmpcoeff*toto2;
      //3
      tmpcoeff=nfnf+i+2;
      res1nf[i+2]-=*tmpcoeff*toto1;
      res2nf[i+2]-=*tmpcoeff*toto2;
      //4
      tmpcoeff=nfnf+i+3;
      res1nf[i+3]-=*tmpcoeff*toto1;
      res2nf[i+3]-=*tmpcoeff*toto2;
      //5
      tmpcoeff=nfnf+i+4;
      res1nf[i+4]-=*tmpcoeff*toto1;
      res2nf[i+4]-=*tmpcoeff*toto2;
      //6
      tmpcoeff=nfnf+i+5;
      res1nf[i+5]-=*tmpcoeff*toto1;
      res2nf[i+5]-=*tmpcoeff*toto2;
      //7
      tmpcoeff=nfnf+i+6;
      res1nf[i+6]-=*tmpcoeff*toto1;
      res2nf[i+6]-=*tmpcoeff*toto2;
      //8
      tmpcoeff=nfnf+i+7;
      res1nf[i+7]-=*tmpcoeff*toto1;
      res2nf[i+7]-=*tmpcoeff*toto2;
#if 0 
     //9
      tmpcoeff=nfnf+i+8;
      res1nf[i+8]-=*tmpcoeff*toto1;
      res2nf[i+8]-=*tmpcoeff*toto2;
      //10
      tmpcoeff=nfnf+i+9;
      res1nf[i+9]-=*tmpcoeff*toto1;
      res2nf[i+9]-=*tmpcoeff*toto2;
      
      //11
      tmpcoeff=nfnf+i+10;
      res1nf[i+10]-=*tmpcoeff*toto1;
      res2nf[i+10]-=*tmpcoeff*toto2;
      
      //12
      tmpcoeff=nfnf+i+11;
      res1nf[i+11]-=*tmpcoeff*toto1;
      res2nf[i+11]-=*tmpcoeff*toto2;

      //13
      tmpcoeff=nfnf+i+12;
      res1nf[i+12]-=*tmpcoeff*toto1;
      res2nf[i+12]-=*tmpcoeff*toto2;
      
      //14
      tmpcoeff=nfnf+i+13;
      res1nf[i+13]-=*tmpcoeff*toto1;
      res2nf[i+13]-=*tmpcoeff*toto2;
      
      //15
      tmpcoeff=nfnf+i+14;
      res1nf[i+14]-=*tmpcoeff*toto1;
      res2nf[i+14]-=*tmpcoeff*toto2;
      
      //16
      tmpcoeff=nfnf+i+15;
      res1nf[i+15]-=*tmpcoeff*toto1;
      res2nf[i+15]-=*tmpcoeff*toto2;

#endif
    }
  for(register unsigned int j=i;j<nf.size;j++)
    {
      res1nf[j]-=nfnf[j]*toto1;
      res2nf[j]-=nfnf[j]*toto2; 
    }
}

template<typename pol,typename coeff>
void inline my_plustmp(pol &res,const pol & nf,const coeff toto)
{
  typedef typename pol::monom_t mon;
  unsigned int i=0,stock;;
  unsigned int ttmp;//=taillequotient/16;
  unsigned int tmp;//=taillequotient % 16;
  // cout<<"nf.size "<<nf.size<<endl;
  //cout<<"nf.ind "<<nf.ind<<endl;
  //cout<<"nf.nf "<<nf.nf<<endl;
  //cout<<"res.nf "<<res.nf<<endl;
  //cout<<"res.size "<<res.size<<endl;
  register coeff *resnf,*nfnf;
  if (toto==0) return;
  if(res.size<nf.size)
    {
      //  cout<<"je realloue res.nf avant "<<res.nf<<endl;
      res.nf=(coeff*)MAC_REV_REALLOC<coeff>(res.nf,res.size*sizeof(coeff)
                                     ,nf.size*sizeof(coeff));
      //cout<<"res.nf apres "<<res.nf<<endl;
      for(i=res.size;i<nf.size;i++)
        res.nf[i]=0;
      res.size=nf.size;
    }
  ttmp=nf.size/16;
  tmp=nf.size & 15;//16 pourquoi... PARCE QUE!!!!! :-))
  resnf=res.nf;
  nfnf=nf.nf;
  for(i=0;i<ttmp;++i)
      {
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
            *resnf++-=*nfnf++*toto;
      }
   for(register unsigned j=0;j<tmp;j++)
    *resnf++-=*nfnf++*toto;
}
//#define DEB
template<typename pol,typename coeff>
void inline my_plus(pol &res,const pol & nf,const coeff toto)
{
#ifdef DEB
  cout<<"dans myplus je calcul"<<endl<<invconv<Poly>(res)<<endl<<
  "toto "<<toto<<endl<<"nf"<<endl<<invconv<Poly>(nf)<<endl;
#endif
  typedef typename pol::monom_t mon;
  register unsigned int i=0;
  register unsigned int ttmp,tmp;//=taillequotient/16;
  register coeff *nfnf=nf.nf,*resnf;
  coeff *ptr1,*ptr2;
  //register unsigned int tmp;//=taillequotient % 16;
  tmp=nf.size;
  if(res.size<tmp)
   {
     res.nf=(coeff*)MAC_REV_REALLOC<coeff>(res.nf,res.size*sizeof(coeff)
                                           ,tmp*sizeof(coeff));
     for(int i=res.size;i<tmp;i++)
       res.nf[i]=0;
     res.size=tmp;
   }
  resnf=res.nf;
  ttmp=(tmp/16)*16;
  ptr1=resnf;
  ptr2=nfnf;
  //resnf=res.nf;
  //tmp=nf.size & 15;//16 pourquoi... PARCE QUE!!!!! :-))
  for(;i<ttmp;i+=16,resnf+=16,nfnf+=16)
    {
      {
        resnf[0]-=nfnf[0]*toto;
        resnf[1]-=nfnf[1]*toto;
        resnf[2]-=nfnf[2]*toto;
        resnf[3]-=nfnf[3]*toto;
        resnf[4]-=nfnf[4]*toto;
        resnf[5]-=nfnf[5]*toto;
        resnf[6]-=nfnf[6]*toto;
        resnf[7]-=nfnf[7]*toto;
        resnf[8]-=nfnf[8]*toto;
        resnf[9]-=nfnf[9]*toto;
        resnf[10]-=nfnf[10]*toto;
        resnf[11]-=nfnf[11]*toto;
        resnf[12]-=nfnf[12]*toto;
        resnf[13]-=nfnf[13]*toto;
        resnf[14]-=nfnf[14]*toto;
        resnf[15]-=nfnf[15]*toto;
      } 
    }
  resnf=ptr1;nfnf=ptr2;
  for(register unsigned int j=i;j<tmp;j++)
    resnf[j]-=nfnf[j]*toto;
#ifdef DEB
     cout<<"les resultat "<<endl<<invconv<Poly>(res)<<endl;
#endif
}
//#undef DEB

template<typename pol>
void inline my_plus(pol &res,const pol & nf)
{
  typedef typename pol::monom_t mon;
  typedef typename pol::coeff_t coeff;
  register unsigned int i=0;
  register unsigned int ttmp,tmp;//=taillequotient/16;
  register coeff *nfnf=nf.nf,*resnf;;
  //register unsigned int tmp;//=taillequotient % 16;
  tmp=nf.size;
  if(res.size<tmp)
   {
     res.nf=(coeff*)MAC_REV_REALLOC<coeff>(res.nf,res.size*sizeof(coeff)
                                           ,tmp*sizeof(coeff));
     for(int i=res.size;i<tmp;i++)
       res.nf[i]=0;
     res.size=tmp;
   }
  ttmp=(tmp/16)*16;
  resnf=res.nf;
  //tmp=nf.size & 15;//16 pourquoi... PARCE QUE!!!!! :-))
  for(;i<ttmp;i+=16)
    {
      {
        resnf[i]-=nfnf[i];
        resnf[i+1]-=nfnf[i+1];
        resnf[i+2]-=nfnf[i+2];
        resnf[i+3]-=nfnf[i+3];
        resnf[i+4]-=nfnf[i+4];
        resnf[i+5]-=nfnf[i+5];
        resnf[i+6]-=nfnf[i+6];
        resnf[i+7]-=nfnf[i+7];
        resnf[i+8]-=nfnf[i+8];
        resnf[i+9]-=nfnf[i+9];
        resnf[i+10]-=nfnf[i+10];
        resnf[i+11]-=nfnf[i+11];
        resnf[i+12]-=nfnf[i+12];
        resnf[i+13]-=nfnf[i+13];
        resnf[i+14]-=nfnf[i+14];
        resnf[i+15]-=nfnf[i+15];
      } 
    }
  for(register unsigned int j=i;j<tmp;j++)
    resnf[j]-=nfnf[j];
}

template<typename pol,typename coeff>
void inline myplus22(pol &res,const pol & nf,const coeff toto, const pol &nf2,const coeff toto2)
{
  typedef typename pol::monom_t mon;
  register unsigned int i=0;
  register unsigned int ttmp;//=taillequotient/16;
  register unsigned int tmp;//=taillequotient % 16;
  register coeff *resnf,*nfnf,*nf2nf;
  coeff tmp1,tmp2;
  int maxsize=max(nf.size,nf2.size);
  if(res.size<maxsize)
   {
     res.nf=(coeff*)MAC_REV_REALLOC<coeff>(res.nf,res.size*sizeof(coeff)
                                           ,maxsize*sizeof(coeff));
     for(int i=res.size;i<maxsize;i++)
       res.nf[i]=0;
     res.size=maxsize;
   }
  resnf=res.nf;
  nfnf=nf.nf;
  nf2nf=nf2.nf;
  if(nf.size<nf2.size)
    {
      ttmp=(nf.size/16)*16;
      tmp=nf.size & 15;//16 pourquoi... PARCE QUE!!!!! :-))
      for(;i<ttmp;i+=16)
        {
          {
            // tmp1=nfnf[i];
//          tmp1*=toto;
//          tmp2=nf2nf[i];
//          tmp2*=toto2;
//          resnf[i]-=tmp1+tmp2;
            resnf[i]-=nfnf[i]*toto+nf2nf[i]*toto2;
//           tmp1=nfnf[i+1];
//          tmp1*=toto;
//          tmp2=nf2nf[i+1];
//          tmp2*=toto2;
//          resnf[i+1]-=tmp1+tmp2;
resnf[i+1]-=nfnf[i+1]*toto+nf2nf[i+1]*toto2;
//          tmp1=nfnf[i+2];
//          tmp1*=toto;
//          tmp2=nf2nf[i+2];
//          tmp2*=toto2;
//          resnf[i+2]-=tmp1+tmp2;
resnf[i+2]-=nfnf[i+2]*toto+nf2nf[i+2]*toto2;
//          tmp1=nfnf[i+3];
//          tmp1*=toto;
//          tmp2=nf2nf[i+3];
//          tmp2*=toto2;
//          resnf[i+3]-=tmp1+tmp2;
resnf[i+3]-=nfnf[i+3]*toto+nf2nf[i+3]*toto2;
//          tmp1=nfnf[i+4];
//          tmp1*=toto;
//          tmp2=nf2nf[i+4];
//          tmp2*=toto2;
//          resnf[i+4]-=tmp1+tmp2;
resnf[i+4]-=nfnf[i+4]*toto+nf2nf[i+4]*toto2;
//          tmp1=nfnf[i+5];
//          tmp1*=toto;
//          tmp2=nf2nf[i+5];
//          tmp2*=toto2;
//          resnf[i+5]-=tmp1+tmp2;
resnf[i+5]-=nfnf[i+5]*toto+nf2nf[i+5]*toto2;
//          tmp1=nfnf[i+6];
//          tmp1*=toto;
//          tmp2=nf2nf[i+6];
//          tmp2*=toto2;
//          resnf[i+6]-=tmp1+tmp2;
resnf[i+6]-=nfnf[i+6]*toto+nf2nf[i+6]*toto2;
//          tmp1=nfnf[i+7];
//          tmp1*=toto;
//          tmp2=nf2nf[i+7];
//          tmp2*=toto2;
//          resnf[i+7]-=tmp1+tmp2;
resnf[i+7]-=nfnf[i+7]*toto+nf2nf[i+7]*toto2;
//          tmp1=nfnf[i+8];
//          tmp1*=toto;
//          tmp2=nf2nf[i+8];
//          tmp2*=toto2;
//          resnf[i+8]-=tmp1+tmp2;
resnf[i+8]-=nfnf[i+8]*toto+nf2nf[i+8]*toto2;
//          tmp1=nfnf[i+9];
//          tmp1*=toto;
//          tmp2=nf2nf[i+9];
//          tmp2*=toto2;
//          resnf[i+9]-=tmp1+tmp2;
resnf[i+9]-=nfnf[i+9]*toto+nf2nf[i+9]*toto2;
//          tmp1=nfnf[i+10];
//          tmp1*=toto;
//          tmp2=nf2nf[i+10];
//          tmp2*=toto2;
//          resnf[i+10]-=tmp1+tmp2;
resnf[i+10]-=nfnf[i+10]*toto+nf2nf[i+10]*toto2;
//          tmp1=nfnf[i+11];
//          tmp1*=toto;
//          tmp2=nf2nf[i+11];
//          tmp2*=toto2;
//          resnf[i+11]-=tmp1+tmp2;
resnf[i+11]-=nfnf[i+11]*toto+nf2nf[i+11]*toto2;
//          tmp1=nfnf[i+12];
//          tmp1*=toto;
//          tmp2=nf2nf[i+12];
//          tmp2*=toto2;
//          resnf[i+12]-=tmp1+tmp2;
resnf[i+12]-=nfnf[i+12]*toto+nf2nf[i+12]*toto2;
//          tmp1=nfnf[i+13];
//          tmp1*=toto;
//          tmp2=nf2nf[i+13];
//          tmp2*=toto2;
//          resnf[i+13]-=tmp1+tmp2;
resnf[i+13]-=nfnf[i+13]*toto+nf2nf[i+13]*toto2;
//          tmp1=nfnf[i+14];
//          tmp1*=toto;
//          tmp2=nf2nf[i+14];
//          tmp2*=toto2;
//          resnf[i+14]-=tmp1+tmp2;
resnf[i+14]-=nfnf[i+14]*toto+nf2nf[i+14]*toto2;
//          tmp1=nfnf[i+15];
//          tmp1*=toto;
//          tmp2=nf2nf[i+15];
//          tmp2*=toto2;
//          resnf[i+15]-=tmp1+tmp2;
            
            resnf[i+15]-=nfnf[i+15]*toto+nf2nf[i+15]*toto2;
          } 
        }
      for(register unsigned int j=i;j<nf.size;j++)
        resnf[j]-=nfnf[j]*toto+nf2nf[j]*toto2;
      for(register unsigned int j=nf.size;j<nf2.size;j++)
        resnf[j]-=nf2nf[j]*toto2;
      
    }
  else
    {
      ttmp=(nf2.size/16)*16;
      tmp=nf2.size & 15;//16 pourquoi... PARCE QUE!!!!! :-))
      for(;i<ttmp;i+=16)
        {
          {
            tmp1=nfnf[i];
            tmp1*=toto;
            tmp2=nf2nf[i];
            tmp2*=toto2;
            resnf[i]-=tmp1+tmp2;
            //      resnf[i]-=nfnf[i]*toto+nf2nf[i]*toto2;
             tmp1=nfnf[i+1];
            tmp1*=toto;
            tmp2=nf2nf[i+1];
            tmp2*=toto2;
            resnf[i+1]-=tmp1+tmp2;
            //      resnf[i+1]-=nfnf[i+1]*toto+nf2nf[i+1]*toto2;
            tmp1=nfnf[i+2];
            tmp1*=toto;
            tmp2=nf2nf[i+2];
            tmp2*=toto2;
            resnf[i+2]-=tmp1+tmp2;
            //      resnf[i+2]-=nfnf[i+2]*toto+nf2nf[i+2]*toto2;
            tmp1=nfnf[i+3];
            tmp1*=toto;
            tmp2=nf2nf[i+3];
            tmp2*=toto2;
            resnf[i+3]-=tmp1+tmp2;
            //      resnf[i+3]-=nfnf[i+3]*toto+nf2nf[i+3]*toto2;
            tmp1=nfnf[i+4];
            tmp1*=toto;
            tmp2=nf2nf[i+4];
            tmp2*=toto2;
            resnf[i+4]-=tmp1+tmp2;
            //      resnf[i+4]-=nfnf[i+4]*toto+nf2nf[i+4]*toto2;
            tmp1=nfnf[i+5];
            tmp1*=toto;
            tmp2=nf2nf[i+5];
            tmp2*=toto2;
            resnf[i+5]-=tmp1+tmp2;
            //      resnf[i+5]-=nfnf[i+5]*toto+nf2nf[i+5]*toto2;
            tmp1=nfnf[i+6];
            tmp1*=toto;
            tmp2=nf2nf[i+6];
            tmp2*=toto2;
            resnf[i+6]-=tmp1+tmp2;
            //      resnf[i+6]-=nfnf[i+6]*toto+nf2nf[i+6]*toto2;
            tmp1=nfnf[i+7];
            tmp1*=toto;
            tmp2=nf2nf[i+7];
            tmp2*=toto2;
            resnf[i+7]-=tmp1+tmp2;
            //      resnf[i+7]-=nfnf[i+7]*toto+nf2nf[i+7]*toto2;
            tmp1=nfnf[i+8];
            tmp1*=toto;
            tmp2=nf2nf[i+8];
            tmp2*=toto2;
            resnf[i+8]-=tmp1+tmp2;
            //      resnf[i+8]-=nfnf[i+8]*toto+nf2nf[i+8]*toto2;
            tmp1=nfnf[i+9];
            tmp1*=toto;
            tmp2=nf2nf[i+9];
            tmp2*=toto2;
            resnf[i+9]-=tmp1+tmp2;
            //      resnf[i+9]-=nfnf[i+9]*toto+nf2nf[i+9]*toto2;
            tmp1=nfnf[i+10];
            tmp1*=toto;
            tmp2=nf2nf[i+10];
            tmp2*=toto2;
            resnf[i+10]-=tmp1+tmp2;
            //      resnf[i+10]-=nfnf[i+10]*toto+nf2nf[i+10]*toto2;
            tmp1=nfnf[i+11];
            tmp1*=toto;
            tmp2=nf2nf[i+11];
            tmp2*=toto2;
            resnf[i+11]-=tmp1+tmp2;
            //      resnf[i+11]-=nfnf[i+11]*toto+nf2nf[i+11]*toto2;
            tmp1=nfnf[i+12];
            tmp1*=toto;
            tmp2=nf2nf[i+12];
            tmp2*=toto2;
            resnf[i+12]-=tmp1+tmp2;
            //      resnf[i+12]-=nfnf[i+12]*toto+nf2nf[i+12]*toto2;
            tmp1=nfnf[i+13];
            tmp1*=toto;
            tmp2=nf2nf[i+13];
            tmp2*=toto2;
            resnf[i+13]-=tmp1+tmp2;
            //      resnf[i+13]-=nfnf[i+13]*toto+nf2nf[i+13]*toto2;
            tmp1=nfnf[i+14];
            tmp1*=toto;
            tmp2=nf2nf[i+14];
            tmp2*=toto2;
            resnf[i+14]-=tmp1+tmp2;
            //      resnf[i+14]-=nfnf[i+14]*toto+nf2nf[i+14]*toto2;
            tmp1=nfnf[i+15];
            tmp1*=toto;
            tmp2=nf2nf[i+15];
            tmp2*=toto2;
            resnf[i+15]-=tmp1+tmp2;
          } 
        }
      for(register unsigned int j=i;j<nf2.size;j++)
        resnf[j]-=nfnf[j]*toto+nf2nf[j]*toto2;
      for(register unsigned int j=nf2.size;j<nf.size;j++)
        resnf[j]-=nfnf[j]*toto;
      
    }
}

template<typename pol,typename coeff>
void inline myplus44(pol &res,const pol & nf,const coeff toto, 
                     const pol &nf2,const coeff toto2,
                     const pol &nf3,const coeff toto3,
                     const pol &nf4,const coeff toto4)
{
  typedef typename pol::monom_t mon;
  register unsigned int i=0;
  register unsigned int ttmp;//=taillequotient/16;
  register unsigned int tmp;//=taillequotient % 16;
  coeff *resnf,*nfnf,*nf2nf,*nf3nf,*nf4nf;
  int maxsize=max(max(nf.size,nf2.size),max(nf3.size,nf4.size));
  int minsize=min(min(nf.size,nf2.size),min(nf3.size,nf4.size));
  if(res.size<maxsize)
   {
     res.nf=(coeff*)MAC_REV_REALLOC<coeff>(res.nf,res.size*sizeof(coeff)
                                           ,maxsize*sizeof(coeff));
     for(int i=res.size;i<maxsize;i++)
       res.nf[i]=0;
     res.size=maxsize;
   }
  resnf=res.nf;
  nfnf=nf.nf;
  nf2nf=nf2.nf;
  nf3nf=nf3.nf;
  nf4nf=nf4.nf;
  ttmp=(minsize/16)*16;
  tmp=minsize & 15;//16 pourquoi... PARCE QUE!!!!! :-))
  for(;i<ttmp;i+=16)
        {
          {
            resnf[i]-=nfnf[i]*toto+nf2nf[i]*toto2
              +nf3nf[i]*toto3+nf4nf[i]*toto4;
            resnf[i+1]-=nfnf[i+1]*toto+nf2nf[i+1]*toto2
              +nf3nf[i+1]*toto3+nf4nf[i+1]*toto4;
            resnf[i+2]-=nfnf[i+2]*toto+nf2nf[i+2]*toto2
                +nf3nf[i+2]*toto3+nf4nf[i+2]*toto4;
            resnf[i+3]-=nfnf[i+3]*toto+nf2nf[i+3]*toto2
                +nf3nf[i+3]*toto3+nf4nf[i+3]*toto4;
            resnf[i+4]-=nfnf[i+4]*toto+nf2nf[i+4]*toto2
                +nf3nf[i+4]*toto3+nf4nf[i+4]*toto4;
            resnf[i+5]-=nfnf[i+5]*toto+nf2nf[i+5]*toto2
                +nf3nf[i+5]*toto3+nf4nf[i+5]*toto4;
            resnf[i+6]-=nfnf[i+6]*toto+nf2nf[i+6]*toto2
                +nf3nf[i+6]*toto3+nf4nf[i+6]*toto4;
            resnf[i+7]-=nfnf[i+7]*toto+nf2nf[i+7]*toto2
                +nf3nf[i+7]*toto3+nf4nf[i+7]*toto4;
            resnf[i+8]-=nfnf[i+8]*toto+nf2nf[i+8]*toto2
                +nf3nf[i+8]*toto3+nf4nf[i+8]*toto4;
            resnf[i+9]-=nfnf[i+9]*toto+nf2nf[i+9]*toto2
                +nf3nf[i+9]*toto3+nf4nf[i+9]*toto4;
            resnf[i+10]-=nfnf[i+10]*toto+nf2nf[i+10]*toto2
                +nf3nf[i+10]*toto3+nf4nf[i+10]*toto4;
            resnf[i+11]-=nfnf[i+11]*toto+nf2nf[i+11]*toto2
                +nf3nf[i+11]*toto3+nf4nf[i+11]*toto4;
            resnf[i+12]-=nfnf[i+12]*toto+nf2nf[i+12]*toto2
                +nf3nf[i+12]*toto3+nf4nf[i+12]*toto4;
            resnf[i+13]-=nfnf[i+13]*toto+nf2nf[i+13]*toto2
                +nf3nf[i+13]*toto3+nf4nf[i+13]*toto4;
            resnf[i+14]-=nfnf[i+14]*toto+nf2nf[i+14]*toto2
                +nf3nf[i+14]*toto3+nf4nf[i+14]*toto4;
            resnf[i+15]-=nfnf[i+15]*toto+nf2nf[i+15]*toto2
              +nf3nf[i+15]*toto3+nf4nf[i+15]*toto4;
          } 
        }
  for(register unsigned int j=i;j<nf.size;j++)
    resnf[j]-=nfnf[j]*toto;
  for(register unsigned int j=i;j<nf2.size;j++)
    resnf[j]-=nf2nf[j]*toto2;
  for(register unsigned int j=i;j<nf3.size;j++)
    resnf[j]-=nf3nf[j]*toto3;
  for(register unsigned int j=i;j<nf4.size;j++)
    resnf[j]-=nf4nf[j]*toto4;
      
}

//renvoit l'indice du monome x_i*m_j
template<typename mon,typename Base>
int indice2(int i,int j,const Base & b)
{
 int res=-1;
 mon tmp;
 int2mon(j,tmp);
 tmp*=mon(i,1);//on suppose qd meme que j correspond a qqchose
 //cout<<"indice2 IsinB("<<mon(i,1)*tmp<<",b) "<<IsinB(mon(i,1)*tmp,b)<<endl;
 if(IsinB(tmp,b))
   {
     res=mon2int(tmp);
     //  cout<<"le monome "<<mon(i,1)*tmp<<" l'indice "<<res<<endl;
   }
 return res;
}

template<typename mon,typename Base>
int indice2(const mon &tmp,const Base & b)
{
 int res=-1;
 if(IsinB(tmp,b))
   {
     res=mon2int(tmp);
     //  cout<<"le monome "<<mon(i,1)*tmp<<" l'indice "<<res<<endl;
   }
 return res;
}

//on lui donne l'ensemble des formes normales, dump, l'indice de b(cf ci dessus)
// le numero de la variable par laquelle on multiplie
//et elle renvoie un pol(cf def du type) sur la forme normale de var*m_{indmon}
#ifndef uninf
template<typename typpol,typename typdump,typename Base>
typpol nf(int var ,int indmon,const typdump &dump,const Base & b)
{
  //on cherche dans dump...
  //a optimiser plus tard
  typedef typename typdump::value_type dumpstruct;
  typedef typpol pol;
  typedef typename pol::monom_t mon;
  pol res;
  res.nf=NULL;
  res.size=-1;
  mon tmpmon;//=mon(1,var)*int2mon<mon>(indmon);
  int deg=0;//=tmpmon.GetDegree()+1;
  typename typdump::const_iterator iter;
  int2mon(indmon,tmpmon);
  deg=tmpmon.GetDegree()+1;
  //cout<<"mon("<<var<<",1) "<<mon(var,1)<<" et deg "<<deg<<endl;
  tmpmon*=mon(var,1);
   for(iter=dump.begin();
       (iter!=dump.end()) && (iter->k!=deg);iter++);
   //    cout<<"iter-k "<<iter->k<<endl;
   // if(iter!=dump.end()) cout<<"iter->k en sortie "<<iter->k<<" et deg "<<deg<<endl;
  //cout<<"valuer a la sortie "<<(--iter)++->k<<endl;
   // cout<<"iter!=dump.end() "<<(iter!=dump.end())
   //   <<" dump.empty() "<<dump.empty()<<endl;
  if(iter!=dump.end())//on cherche pas n'importe quoi qd meme
    {
      int i;
      for(i=0;i<iter->size;i++)
        {
          //  cout<<"dans nf iter->nf[i].ind "<<iter->nf[i].ind<<endl;
          if(iter->nf[i].ind.rep==tmpmon.rep)
            break;
        }
      if(i!=iter->size)
        //Tue Dec  4 16:39:25 MET 2001
        //      densify(iter->nf[i],res);

        res=(iter->nf[i]);
    }
  //cout<<"la gueule de res "<<res<<endl;
  //if (res!=NULL) cout<<"suite de res "<<res->ind<<" "<<res->nf<<endl;
  return res;
}
#endif
 
template<typename typpol,typename typdump,typename Base, typename mon>
typpol nf(const mon &ind,const typdump &dump,const Base & b)
{
  //on cherche dans dump...
  //a optimiser plus tard
  typedef typename typdump::value_type dumpstruct;
  typedef typpol pol;
  pol res;
  res.nf=NULL;
  res.size=-1;
  int deg=0;//=tmpmon.GetDegree()+1;
  typename typdump::const_iterator iter;
  deg=ind.GetDegree();
  for(iter=dump.begin();
      (iter!=dump.end()) && (iter->k!=deg);iter++);
  if(iter!=dump.end())//on cherche pas n'importe quoi qd meme
    {
      int i;
      for(i=0;i<iter->size;i++)
        {
          if(iter->nf[i].ind.rep==ind.rep)
            break;
        }
      if(i!=iter->size)
        res=(iter->nf[i]);
    }
  return res;
}

//effectue la multiplication du pol T par la variable x_i
template<typename typpol,typename typdump,typename Base,typename mon> 
typpol inline mult(int i,const typpol &pol,const typdump &dump,
                   const Base &b,mon **exce,int &exsize)
{
  typedef typename typpol::coeff_t coeff;
  //static const mon monzero=mon(0);
  typpol ret;
  coeff *res=NULL,*polnf;
#ifndef unimul
  mon *stockmontab=(mon*)MAC_REV_MALLOC<mon>(pol.size*sizeof(mon));
#endif 
  ret.nf=res;
  (*exce)=(mon*)MAC_REV_MALLOC<mon>((pol.size+1)*sizeof(mon));
  int *stockindicetab=(int*)malloc(pol.size*sizeof(int)),*tmpptr;
  int noquo=0;
  static int nbmyplus=0;
#ifdef plus2
 int flagplus=0;
 coeff stockcoeffplus;
 typpol stockpolplus;
#endif 
#ifdef plus4
 int flagplus=0;
 coeff stockcoeffplus[4];
 typpol stockpolplus[4];
#endif
 int maxind=0;
  tmpptr=stockindicetab;
  //cout<<"pol.size "<<pol.size<<endl;
  for(int j=0;j<pol.size;++j)
    if (!Iszero(pol.nf[j]))
     {
#ifdef unimul
       int stockindice2=mulind(j,i,b);
       *tmpptr++=stockindice2;
#else
       mon tmpmon;
       int2mon(j,tmpmon);
       tmpmon*=mon(i,1);
       stockmontab[j]=tmpmon;
       int stockindice2=indice2<mon>(tmpmon,b);
       *tmpptr++=stockindice2;
#endif

       //cout<<"stockindice2 "<<stockindice2<<" pol.size "<<
       //pol.size<<" J "<<j<<endl;

       if (maxind<stockindice2)
         maxind=stockindice2;
     }
  //cout<<"maxind "<<maxind<<endl;
  //  maxind=size;
  ret.nf=(coeff*)MAC_REV_MALLOC<coeff>((maxind+1)*sizeof(coeff));
  for(int j=0;j<=maxind;j++)
    ((coeff*)(ret.nf))[j]=0;
  ret.size=maxind+1;
  //ret.nf=res;
  tmpptr=stockindicetab;
  polnf=pol.nf;
  for(int j=0;j<pol.size;++j,polnf++)
    {
      const coeff stockpol=*polnf;
      if (!Iszero(stockpol))//ici introduire les epsilon si on veut gagner un peu..
     {// pas necessaire pour les epsilon parce que ca marche !!
       int stockindice2=*tmpptr++;//indice2<mon>(i,j,b);
      //cout<<"stockindice2 avant le test "<<stockindice2<<endl;
      if (stockindice2>=0) 
        {
          ret.nf[stockindice2]+=stockpol;
          //  cout<<"stocvkindice2 "<<stockindice2<<" pol.size "<<
          //   pol.size<<" J "<<j<<endl;
        }
      else  
        {
          //
          //
          //
          //
          //typename typpol::monom_t tmpmon;
          //cout<<" j vaut dans mult "<<j<<endl;
          // cout<<"et int2mon de ce j vaut "<<tmpmon<<endl;
          //cout<<"je recherche la nf de "<<tmpmon<<endl;
          typpol tmp;
          //tmp.ind=monzero;
#ifdef unimul      
          tmp=nf<typpol>(i,j,dump,b);
#else
          tmp=nf<typpol>(stockmontab[j],dump,b);
#endif    
          //cout<<"tmpind  vaut alors "<<tmp.ind<<endl;
           //
           //
           //
          if (tmp.size!=-1)
          {
#ifdef plus4
            if(flagplus==3)
              {
                flagplus=0;
                myplus44(ret,tmp,stockpol,
                         stockpolplus[0],stockcoeffplus[0],
                         stockpolplus[1],stockcoeffplus[1],
                         stockpolplus[2],stockcoeffplus[2]);
              }
            else
              {
                stockcoeffplus[flagplus]=stockpol;
                stockpolplus[flagplus]=tmp;
                flagplus++;
              }
#endif

#ifdef plus2
            if(flagplus==1)
              {
                flagplus=0;
                myplus22(ret,tmp,stockpol,stockpolplus,stockcoeffplus);
              }
            else
              {
                stockcoeffplus=stockpol;
                stockpolplus=tmp;
                flagplus=1;
              }
#else
            //nbmyplus++;
            //cout<<"tmp "<<tmp<<endl;
            //cout<<"tmp.ind "<<tmp->ind<<endl;
            //cout<<"tmp.nf "<<tmp->nf<<endl;
            my_plus(ret,tmp,stockpol);
            //Tue Dec 4
            //MAC_REV_FREE<mon>(tmp.nf,tmp.size*sizeof(coeff));
            //res=ret.nf;//car my_plus realloc la chose
#endif
          }
          else  
            {
              mon tmpmon;
              (*exce)[noquo]=mon(i,1);
              int2mon(j,tmpmon);
              //cout<<"je rajoute ala fin listes exceed "<<tmpmon*mon(i,1)<<endl;
              (*exce)[noquo]*=tmpmon;//int2mon<mon>(j);
              (*exce)[noquo]*=stockpol;
              ++noquo;
            };
          
          //dans plus qd nf renvois NULL il faut rien faire!!!!
        }
      }
    }
  //(*exce)=(mon*)MAC_REV_REALLOC<mon>((*exce),pol.size*sizeof(mon)
  //                           ,(noquo)*sizeof(mon));
  //cout<<"fin "<<nbmyplus<<endl;
#ifdef plus4
  for(int ii=0;ii<flagplus;ii++)
    my_plus(ret,stockpolplus[ii],stockcoeffplus[ii]);
#endif

#ifdef plus2
  if(flagplus)
    {
      my_plus(ret,stockpolplus,stockcoeffplus);
    }
#endif

  ret.ind=pol.ind;
  ret.ind*=mon(i,1);
  //Fri Nov 16 14:42:34 MET 2001
  (*exce)[noquo++]=ret.ind;
  exsize=noquo;
  (*exce)=(mon*)MAC_REV_REALLOC<mon>((*exce),(pol.size+1)*sizeof(mon)
                               ,(noquo)*sizeof(mon));
   ret.ind.SetCoeff(noquo+1);
#ifndef unimul
   MAC_REV_FREE<mon>(stockmontab,pol.size*sizeof(mon));
#endif 
   free(stockindicetab);
   //   cout<<"ret.size "<<ret.size<<endl;
   // cout<<invconv<Poly>(ret)<<endl;
   //cout<<"-----------------------------------"<<endl;
   return ret;

}

// renvoit mon/x_i .... mais suppose qu'on ne fait pas n'importe quoi
template <typename Mon,typename Base>
Mon my_divmon(const Mon &mon,int i,const Base& b)
{
  Mon res(1);
  for(int j=0;j<b.nbvar();j++)
    if(i==j)
      {
        res*=Mon(j,mon.GetDegree(j)-1);
      }
     else 
       {
         res*=Mon(j,mon.GetDegree(j));
       }
  return res;
}

template<typename typmon,typename Base>
int GoodDir(const typmon &m,int i, const Base & b)
{
  int res=0;
  mon tmpm=m*mon(i,1);
  //cout<<"dans GoodDir les monomes "<<m<<"********"<<typmon(i,1)<<endl;
  //cout<<"b.nbvar() "<<b.nbvar()<<endl;
  for(int j=0;j<b.nbvar();j++)
    {
      if(tmpm.GetDegree(j)>=1)
        if(IsinB(my_divmon(tmpm,j,b),b)) {res=1;break;};
    }
  //cout<<" le verdict de GoodDir "<<res<<endl;
  return res;
}

//fonct\ion adhoc qui merge une liste de polyalp avec une liste de pol
//en cours de calcul cad liste de pol + liste excedentaire 
template<typename typPk,typename typP,typename typexceed,
  typename typsize ,typename Base>
void conv_merge(typPk &Pk,typP &P,typexceed &ex,typsize &sizeex,const Base &b)
{
  typedef typename typP::value_type polalp;
  typedef typename polalp::order_t ord;
  typedef typename polalp::monom_t mon;
  typedef typename typPk::value_type pol;
  typedef typename pol::coeff_t coeff;
  coeff * tabcoeff=NULL;
  int * tabindices=NULL;
  int tabsize=0;
#ifdef DEBUG
  cout<<"entree dans conv_merge"<<endl;
  for(typename Base::const_iterator p=b.begin();p!=b.end();p++)
    {
      for(int i=0;i<p->taille1;i++)
        {
          cout<<"p.accept[i] "<<p->accept[i]<<endl;
        }
      for(int i=0;i<p->taille2;i++)
        {
          cout<<"p.refuse[i] "<<p->refuse[i]<<endl;
        }
    }
  cout<<"p-taille2 "<<b.begin()->taille2<<" "<<b.begin()->taille2-1<<endl;
  cout<<"I=ideal("<<endl;
  {
    typename Base::const_iterator p=b.begin();
    for(int i=0;i<p->taille2-1;i++)
        {
          cout<<p->refuse[i]<<","<<endl;
        }
    if(p->taille2>=1) cout<<p->refuse[p->taille2-1]<<")"<<endl;
  }
#endif //DEBUG
  for(typename typP::iterator iter=P.begin();iter!=P.end();iter++)
    {
      //cout<<"dans for"<<endl;
      pol tmp;
      int max=0;
      tmp.ind=mon(1);
      
      tabcoeff=(coeff*)MAC_REV_REALLOC<coeff>((void*)tabcoeff,
                                              tabsize*sizeof(coeff),
                                              iter->size()*sizeof(coeff));
      tabindices=(int*)realloc((void*)tabindices,iter->size()*sizeof(int));
      tabsize=iter->size();
      //ici il faudrait un type template
      for(int i=0;i<tabsize;i++)
        {
          tabcoeff[i]=0;
        }
      //memset((void*)tabcoeff,0,tabsize*sizeof(coeff));
      //ici aussi
      mon * tmpex=NULL;
      tmpex=(mon*)MAC_REV_REALLOC<mon>((void*)tmpex,0,tabsize*sizeof(mon));
      {
        int comp=0;int i=0;
        for(typename polalp::iterator iterpol=iter->begin();
            iterpol!=iter->end();iterpol++)
          {
            //      cout<<"IsinB("<<*iterpol<<","<<"b)"<<endl;
            if (IsinB(*iterpol,b))
              {
                tabcoeff[i]=iterpol->GetCoeff();
                tabindices[i]=mon2int(*iterpol);
                if(tabindices[i]>max) max=tabindices[i];
                i++;
              }
            else
              { 
                //cout<<"y en a un qu'est pas dans B "<<*iterpol<<endl;
                if(!Iszero(iterpol->GetCoeff()))
                   tmpex[comp++]=*iterpol;
              }
          }
        tmpex=(mon*)MAC_REV_REALLOC<mon>((void*)tmpex,tabsize*sizeof(mon)
                                         ,(comp+1)*sizeof(mon));
        tmp.size=max+1;
        tmp.nf=(coeff*)MAC_REV_MALLOC<coeff>(tmp.size*sizeof(coeff));
        for(int j=0;j<tmp.size;j++)
          tmp.nf[j]=0;
        for(int j=0;j<i;j++)
          tmp.nf[tabindices[j]]=tabcoeff[j];
        tmp.ind=mon(comp+1);
        Pk.push_back(tmp);
        ex.push_back(tmpex);
        sizeex.push_back(comp);
      }
    }
  MAC_REV_FREE<coeff>(tabcoeff,tabsize*sizeof(coeff));
  free(tabindices);
}
//member ne test que les exposant pas les coefficients
template<typename typMk>
int member(const typMk & tmpMk,const typename typMk::value_type mon)
{
  int res=0;
  for(typename typMk::const_iterator iter=tmpMk.begin();
      iter!=tmpMk.end();iter++)
    if(iter->rep==mon.rep) {res=1;break;}
  return res;
}

template<typename typP,typename typPk, typename typMk,typename typexceed
,typename typsize,typename typdump,typename Base>
void putingoodshape(const typP & P,typPk &workvect,const typMk & tmpMk
                    ,typexceed & exceed,typsize & sizeex
                    ,const typdump & dump,const Base & b)
{
  typedef typename typPk::value_type pol;
  typedef typename pol::coeff_t coeff;
  typedef typename typexceed::value_type typex;
  typedef typename typMk::value_type mon;
  typedef typename typP::value_type polyalp;
  typP tobeproj;
  for(typename typPk::iterator iter=workvect.begin();
      iter!=workvect.end();iter++)
    {
      int sizeexceed=0;
      polyalp projpol(0);
      typex tmpex=(mon*)MAC_REV_MALLOC<mon>(sizeof(mon)*tmpMk.size());
      for(unsigned int i=0;i<tmpMk.size();i++)
        tmpex[i]=mon(0);
      //      cout<<"proj pol au debaut "<<projpol<<endl;
      for(int i=0;i<iter->size;i++)
        {
          if(!Iszero(iter->nf[i]))
            {
              mon tmpmon;
              int2mon(i,tmpmon);
              if(!IsinB(tmpmon,b))
                {
                  if(member(tmpMk,tmpmon)) 
                    {
                      tmpex[sizeexceed++]=tmpmon*iter->nf[i];
                      iter->nf[i]=0;
                    }
                  else
                    {
                      projpol+=tmpmon*iter->nf[i];
                      iter->nf[i]=0;
                    };
                }
            }
        }
      if(iter->ind.GetDegree()>0)
        tmpex[sizeexceed++]=iter->ind;
      exceed.push_back(tmpex);
      tobeproj.push_back(projpol);
      //cout<<"tobeproj avant push back "<<endl<<projpol<<endl;
      //cout<<"sizeexced pushbacke "<<sizeexceed<<endl;
      sizeex.push_back(sizeexceed);
    }
  //bon on a isole les monomes a projeter 
  proj(tobeproj,dump,b);
  {
    typename typPk::iterator iter=workvect.begin();
    typename typexceed::iterator iterex=exceed.begin(); 
    typename typsize::iterator itersize=sizeex.begin();
    for(typename typP::iterator iterproj=tobeproj.begin();
        iterproj!=tobeproj.end();iterproj++,iter++,iterex++,itersize++)
      {
        //      cout<<"*itersize "<<(*itersize)<<" et tmpMk.size() "<<tmpMk.size()<<endl;       
        int maxend=iter->size-1;
        for(typename polyalp::iterator iterpol=iterproj->begin();
            iterpol!=iterproj->end();iterpol++)
          {
            if(IsinB(*iterpol,b)&&maxend<mon2int(*iterpol))
              maxend=mon2int(*iterpol);
          }
            iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf
                                                    ,iter->size*sizeof(coeff)
                                                    ,(maxend+1)*sizeof(coeff));
            for(int i=iter->size;i<=maxend;i++)
              iter->nf[i]=0;
            for(typename polyalp::iterator iterpol=iterproj->begin();
                  iterpol!=iterproj->end();iterpol++)
              {
                if(IsinB(*iterpol,b))
                  {
                    iter->nf[mon2int(*iterpol)]+=iterpol->GetCoeff();
                  }
                else
                  {
                    int i=0;
                    
                    for(;(i<(*itersize))&&((*iterex)[i].rep!=iterpol->rep);i++);
                    if(i<(*itersize))
                      {
                        (*iterex)[i]+=*iterpol;
                      }
                    else 
                      {
                        (*iterex)[(*itersize)++]=*iterpol;
                        //      cout<<"rajoute "<<*iterpol<<" a la pos "<<*itersize<<endl;
                      }
                  }
              }
            *iterex=(typex)MAC_REV_REALLOC<mon>(*iterex,tmpMk.size()*sizeof(mon)
                                                ,(*itersize)*sizeof(mon));
        iter->size=maxend+1;
        //cout<<"relecture  itersize "<<*itersize<<endl;
      }
    
  }
}

template<typename typMat,typename typPk,typename typP,
  typename typMk,typename Base,typename typdump,typename typrecall>
int newPkMkMatrixof(typMat &mat,typPk &Pk, typP &P,typMk &Mk,
                    int &k,Base &b, typdump &dump,typrecall &recall
#ifndef NO_TWICE
)
#else
,typMk &Spoldejavu)
#endif
  //template<typename typMat,typename typPk,typename typP,
  // typename typMk,typename Base,typename typdump>
  //int newPkMkMatrixof(typMat &mat,typPk &Pk,const typP &P,typMk &Mk,
  //         int &k,Base &b, typdump &dump)
{
  typedef typename typMk::value_type mon;
  typedef typename typP::value_type::order_t ord;
  typedef typename typPk::value_type pol;
  typedef typename pol::coeff_t coeff;
  typedef typename typP::value_type polyalp;
  typPk tmpPk,workvect;
  typMk tmpMk;
  list<mon *> exceed;
  list<int> sizeexceed;
  int nbproj=0,flagdoplus=1;
  //prise en compte des pol pas encore introduits
  cout<<endl;
  cerr<<"k on entering newpkmkmatrixof "<<k<<endl;
  //cout<<"crochet"<<endl;
  typP ttmpP=Crochet(P,k+1);//
  //typrecall verytmp=Crochet(recall,k+1);//verytmpP 24/08/2001
  //recall.erase(recall.begin(),recall.end());
  //my_merge(ttmpP,verytmpP);//le 24/08/2001
  //nbproj=ttmpP.size();
  //for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
  //   cout<<"ind au debut"<<iter->ind<<endl;
  //for(typename typPk::iterator iter=verytmp.begin();iter!=verytmp.end();iter++)
  // cout<<"ind au debut"<<iter->ind<<endl;
  //    cout<<"pol au debut"<<invconv<typename typP::value_type>(*iter)<<endl; 
  if (!ttmpP.empty()) 
    {
      int tmpdeg;
      // cout<<"proj "<<endl;
      proj(ttmpP,dump,b);
      //  cout<<"selectnozero"<<endl;
      selectnozero(ttmpP);
#ifdef NO_TWICE_FALL
      for(typename typP::iterator iter=P.begin();iter!=P.end();iter++)
        if(Degree(*iter)==k+1) P.erase(iter--);
      for(typename typP::iterator iter=ttmpP.begin()
            ;iter!=ttmpP.end();iter++)
        P.push_back(*iter);
#endif    
//  for(typename typP::iterator iter=P.begin();iter!=P.end();iter++)
      //if(Degree(*iter)==k+1) P.erase(iter--);
      //for(typename typP::iterator iter=ttmpP.begin();iter!=ttmpP.end();iter++)
      //        P.push_back(*iter);
      //        cout<<"pol mal red "<<*iter<<endl;
      //cout<<"passage par ici"<<endl;
      nbproj=ttmpP.size();
      if (!ttmpP.empty())
        {
          //  cout<<"apres select non zero "<<ttmpP.size()<<endl;
          tmpdeg=minmaxdegP(ttmpP,tmpdeg);
          //      cout<<"apres minmax deg "<<tmpdeg<<" "<<k<<endl;
          if(tmpdeg<k+1)
            {
              flagdoplus=0;
              // cout<<"un des pol de pretendu degre le bon se reduit mal"<<endl;
              //en fait a un polynome de degre inferieur
              typPk tmpconv;
              //cout<<"recover"<<endl;
              recover(tmpPk,Mk,dump,tmpdeg);
#ifdef NO_TWICE       
              Listedejafait(Mk,Spoldejavu);
#endif
              // for (typename typPk::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
                //      cout<<"pol ICI "<<invconv<typename typP::value_type>(*iter)<<endl;
                // cout<<"forget "<<tmpdeg<<endl;
              //      recall=verytmp;
              forget(b,dump,tmpdeg,recall);
              compress(tmpPk,dump,b,tmpdeg);
              //verytmp.erase(verytmp.begin(),verytmp.end());


              
              //forget(b,dump,tmpdeg);
              
              ttmpP=Crochet(ttmpP,tmpdeg);
#ifdef NO_TWICE_BUG        
              for(typename typP::iterator iter=P.begin()
                    ;iter!=P.end();iter++)
                if(Degree(*iter)==tmpdeg)
                  P.erase(iter--);
#endif  
              //      for(typename typP::iterator iter=ttmpP.begin()
              //    ;iter!=ttmpP.end();iter++)
              //P.push_back(*iter);
              nbproj=ttmpP.size();
              //for(typename typP::iterator iter=ttmpP.begin();iter!=ttmpP.end();iter++)
              //        tmpconv.push_back(convert<pol>(*iter,b));
              //ttmpP.erase(ttmpP.begin(),ttmpP.end());//samedi 24 aout
              //nbproj=1;//                              samedi 24 aout
              //Crochetchoix(P,Pk,tmpconv,tmpdeg,b);
              //ttmpP.push_back(invconv<typename typP::value_type>(Pk.back()));
              //Pk.pop_back();//on elimine de Pk le pol de proj choisi
              //pour se ramner au cas ou proj != 0 et P ok
              Mk.erase(Mk.begin(),Mk.end());
              for (typename typPk::iterator iterpk=tmpPk.begin();
                   iterpk!=tmpPk.end();iterpk++)
                {
                  // cout<<"iterpk->ind "<<iterpk->ind
                  //    <<"et Isinb(iterpk-ind,b) "<<IsinB(iterpk->ind,b)<<endl;
                  if (IsinB(iterpk->ind,b))
                    {
                      for(typename Base::iterator iterb=b.begin()
                            ;iterb!=b.end();iterb++)
                        {
                          iterb->refuse=(mon*)MAC_REV_REALLOC<mon>
                            (iterb->refuse,(iterb->taille2)*sizeof(mon),
                             (iterb->taille2+1)*sizeof(mon));
                          iterb->refuse[iterb->taille2]=iterpk->ind;
                          iterb->refuse[iterb->taille2].SetCoeff(1);
                          iterb->taille2++;
                        }
                    }
                }
              for(typename typPk::iterator iter=tmpPk.begin()
                    ;iter!=tmpPk.end();iter++)
                {
                  mon *tmp=(mon*)MAC_REV_MALLOC<mon>(sizeof(mon));
                  *tmp=iter->ind;
                  tmpMk.push_back(*tmp);
                  exceed.push_back(tmp);
                  sizeexceed.push_back(1);
                  //      cout<<"pour Mk iter->ind "<<iter->ind<<endl;
                }
              //on vient de chuter de 
              //degre et on a reconstitue les bons mk et pk
              k=tmpdeg-1;
              //Dump(Pk,dump);
            }
        }
    }
  if(flagdoplus)
    {
#ifdef unimul
        reinit_multiple();
#endif      
#ifdef uninf
        reinit_nf<pol>();
#endif 
        map<mon,int,ord> monmember;
      //      int nbmult=0;
      //list<mon> dejavu;
      //consttruction des pol ord sup
      for(int i=0;i<b.nbvar();i++)
        {
          for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
            {
              //cout<<"avant gooddir l'ind "<<iter->ind<<endl;
              if(GoodDir((*iter).ind,i,b))
                {
                  mon tmpmon=iter->ind*mon(i,1);
                  //tmpmon.SetCoeff(1);
                  //if(!member(tmpMk,tmpmon))
                  if(!(monmember).count(tmpmon))
                    {
                      typename typrecall::iterator iterrec;
                      (monmember)[tmpmon]=1;
                      tmpMk.push_back(tmpmon);
#if 0         
                      for(iterrec=verytmp.begin();
                          (iterrec!=verytmp.end())
                            &&(!(iterrec->ind.rep==tmpmon.rep));
                          iterrec++);
                        if(iterrec!=verytmp.end())
                          {
                            //                      cout<<"g un candidat "<<tmpmon<<" son ind "<<iterrec->ind<<"la comparaison "<<(iterrec->ind.rep==tmpmon.rep)<<endl;
                            // putingoodshape(P,workvect,Mk,exceed,sizeex,dump,b);                          
                            workvect.push_back(*iterrec);
                            verytmp.erase(iterrec);
                            continue;
                          }
#endif
                        //cout<<"aprfes gooddir"<<endl;
                      mon * tmp=NULL;
                      int tmpsize;
                      //cout<<"avant mult"<<endl;
                      tmpPk.push_back(mult(i,*iter,dump,b,&tmp,tmpsize));
                      //attention le coefficient de ind est la taille de 
                      // l'exceed correspondant
                      //      cout<<"apres mult"<<endl;
                      exceed.push_back(tmp);
                      sizeexceed.push_back(tmpsize);
#ifdef DEB                  
                      cout<<"coucou"<<endl;
                      for(int j=0;j<tmpsize;j++)
                        cout<<" "<<tmp[j];
                      cout<<endl; 
#endif
                      //              nbmult++;
                    }
                }
            }
        }
      //      recall=verytmp;
      //      cout<<"nbmult "<<nbmult<<endl;
    }

  //  cout<<"tmpPK.size "<<tmpPk.size()<<endl;
  //Constructyion de pol terminee
  //cout<<"ttmpP.size "<<ttmpP.size()<<endl;
  //cout<<"avant conv merge"<<endl;
#if 1
  {  
#if 0
    for(typename typPk::iterator iter=verytmp.begin();iter!=verytmp.end();iter++)
      {
        int good=0;
        for(int i=0;i<b.nbvar();i++)
          {
            if((iter->ind.GetDegree(i)>0)&&(IsinB(my_divmon(iter->ind,i,b),b)))
            {
              good=1;break;
            }
          }
        if(good)
          { 
            //NON il faut virer les ind de B avant de les pushbacker
            if(mon2int(iter->ind)>=iter->size)
              {
                iter->nf=(coeff*)MAC_REV_REALLOC<coeff>(iter->nf,
                                     iter->size*sizeof(coeff)
                                     ,(mon2int(iter->ind)+1)*sizeof(coeff));
                }
            iter->nf[mon2int(iter->ind)]=iter->ind.GetCoeff();
            iter->ind=mon(0);
            workvect.push_back(*iter);
            verytmp.erase(iter--);
          }
      }
#endif
    //recall=verytmp;
    list<mon*> tmpexceed;
    list<int> tmpsizeex;
    putingoodshape(P,workvect,tmpMk,tmpexceed,tmpsizeex,dump,b);
    my_merge(tmpPk,workvect);
    my_merge(exceed,tmpexceed);
    my_merge(sizeexceed,tmpsizeex);
  }
#endif
  conv_merge(tmpPk,ttmpP,exceed,sizeexceed,b);
  //cout<<"apres conv merge"<<endl;
  //cout<<"tmpMK==empty?? "<<tmpMk.empty()<<endl;
  //   for(typename typPk::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
  //   {
  //    cout<<"iter->ind.GetCoeff() "<<iter->ind.GetCoeff()-1
  //        <<" et ind "<<iter->ind<<endl;
  //   }
    //cout<<"tmpPK.size "<<tmpPk.size()<<endl;

  //Tue Nov 27 15:57:25 MET 2001
  /*
   for(typename typPk::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
    
   {
   mon tmp=iter->ind;
   tmp.SetCoeff(1);
   if((iter->ind.GetDegree()!=0)&&(!member(tmpMk,tmp)))
   {
   //cout<<"iter->ind.GetCoeff()"<<iter->ind.GetCoeff()-(coeff)1<<" "
   //    <<tmp<<endl;
   tmpMk.push_back(tmp);
   //tmpMk.back().SetCoeff(1);
   }
   }
  */
  //construction de la matrice maintenant
  //positionnement des pointeurs de matrices pour gagner en tps
   {
     int nnz=0;
     //-----------------
     //for(typename typMk::iterator iter=tmpMk.begin();iter!=tmpMk.end();iter++)
     // cout<<"mon "<<*iter<<endl;
     //-----------------
     //     cout<<"nb proj "<<nbproj<<endl;
     for(list<int>::iterator iter=sizeexceed.begin();iter!=sizeexceed.end()
           ;iter++)
       {
         nnz+=*iter;
         //      cout<<"on a donc de monme pour celui la "<<
         //  (int)((iter->ind).GetCoeff()-1)<<" d'ou nnz "<<nnz<<endl;
       }
     //for(typename typPk::iterator iter=tmpPk.begin();iter!=tmpPk.end();iter++)
     //  {
     //  int tmp=0;
     //  for(;(iter->ind).GetCoeff()>(coeff)tmp;tmp++);
     //  nnz+=tmp-1;
         //      cout<<"on a donc de monme pour celui la "<<
         //  (int)((iter->ind).GetCoeff()-1)<<" d'ou nnz "<<nnz<<endl;
     //       }
     // nnz+=tmpPk.size()-nbproj;//le 10/05/2001 avant: nnz+=tmpMk.size()-nbproj;
     //le -nbproj rajoute le 23/01/2001!!
     //     #define DEBUG
#ifdef DEBUG
     typename typPk::iterator tmpiter=tmpPk.begin();
     list<int>::iterator itersize=sizeexceed.begin();
     for(typename list<mon*>::iterator iter=exceed.begin();iter!=exceed.end()
      ;tmpiter++,iter++,itersize++)
      {
        cout<<"pour un exceeed la taille attendue est "
            <<*itersize<<endl;
        for(int i=0;*itersize>i;i++)//;tmpiter->ind.GetCoeff()>i+1;i++)
           {
             cout<<"le gus que je regarde "<<(*iter)[i]<<endl;
             if(!member(tmpMk,(*iter)[i]))
             {
               cout<<(*iter)[i]<<endl;
               cout<<"dans ce pol "<<invconv<Poly>(*tmpiter)<<endl;
               cout<<"l'ind "<<tmpiter->ind<<endl;
               exit(-10);
             }
           }
     }
#endif
     // #undef DEBUG
     cout<<"nnz of matrix "<<nnz<<endl;
     //en general la matrice est rectangulaire
     void * toto=MAC_REV_MALLOC<coeff>(nnz*sizeof(typename typMat::coeff_t));
     //+nnz*sizeof(int)+((*mat)->ncol+1)*sizeof(int));
     if (mat.nzval!=NULL) MAC_REV_FREE<typename typMat::coeff_t>
                            (mat.nzval,mat.nnz
                             *sizeof(typename typMat::coeff_t));
     mat.nrow=tmpPk.size();
     mat.ncol=tmpMk.size();
     mat.nnz=nnz;
     mat.nzval=toto;
#ifdef DEBUG
     for(int i=0;i<nnz;i++)
       ((typename typMat::coeff_t*)mat.nzval)[i]=(coeff)1000000000000.0;
#endif
     // mstore->rowind=(int*)((double*)toto+nnz);
     if(mat.rowind!=NULL) free(mat.rowind);
     mat.rowind=(int*)malloc(nnz*sizeof(int));
     //mstore->colptr=(int*)(mstore->rowind+nnz);//
     if(mat.colptr!=NULL) free(mat.colptr);
     mat.colptr=(int*)malloc((mat.ncol+1)*sizeof(int));
   }
   cout<<"matrix of size "<<mat.nrow<<"x"<<mat.ncol<<endl;
   //matrice cree rest plus qu'a ecrire dedans ca
   {
     int *ncol=(int*)calloc(mat.ncol,sizeof(int));
     //memset((void*)ncol,0,(*mat)->ncol*sizeof(int));
     map<mon,int,ord> mapint;
     typename typMk::iterator itermk=tmpMk.begin();
     typename typPk::iterator iterpk=tmpPk.begin();
     typename list<mon*>::iterator iterex=exceed.begin();
     list<int>::iterator itersize=sizeexceed.begin();
     int line_num=0;
#ifdef nomap
     int **indmonmk=malloc(b.nbvar()*sizeof(int));
     for(int i=0;i<b.nbvars();i++)
       {
         indmon[i]=malloc(size*sizeof(int));
       }
     for(int i=0;itermk!=tmpMk.end();i++,itermk++)
       {
         for(int j=0;j<b.nbvars;j++)
           {
             mon tmp=my_divmon(*itermk,mon(j,1));
             indmon[mon2int(tmp)]=i;
           }
       } 
#endif
     for(int i=0;itermk!=tmpMk.end();i++,itermk++)
       {
         mapint[*itermk]=i;
       } 
     iterpk=tmpPk.begin();
     for(;iterpk!=tmpPk.end();iterpk++,iterex++,itersize++,line_num++)
       {
         // if(iterpk->ind.GetDegree()>0) 
         //  {
         //    mon tmpmon=iterpk->ind;
         //    tmpmon.SetCoeff(1);
         //   ncol[mapint[tmpmon]]++;
             //      cout<<"on est a la ligne "<<line_num<<" ai augmente "<<mapint[(iterpk->ind*(1/iterpk->ind.GetCoeff()))]<<" a cause de son monome dom "<<endl;
             // cout<<"le voila "<<(iterpk->ind*(1/iterpk->ind.GetCoeff()))<<endl;
         //}
        {
          // coeff tmpcoeff=(iterpk->ind).GetCoeff()-(coeff)1;
#ifdef nomap
          for(int i=0;*itersize>i;i+=2)
            ++ncol[indmon[(*iterex)[i]][(*iterex)[i+1]]]; 
#else    
          for(int i=0;*itersize>i;i++)
            {
             //cout<<"iterpk icici ->GetCoeff()"<<iterpk->ind.GetCoeff()<<endl;
             //     if (mapint.count((*iterex)[i]))
              {
                ++ncol[mapint[(*iterex)[i]]];
                // cout<<" ai augmente "<<mapint[(*iterex)[i]]<<"a cause de iterex "<<endl;
              }
#endif  
           }
        }
       }
     //rajoute le 23/01/2001
     //enleve le 17.05/2001
     //     for(int i=mat.nrow-nbproj;i<mat.nrow;i++)
     // ncol[i]--;
     //fin rajout c pour prendre en compte que lors de 
     //de la proj le monome de tete se trouve dans exceed
     //fin enlevement
     typename typMat::coeff_t* nzval=(typename typMat::coeff_t*)mat.nzval;
     int *rowind=mat.rowind;
     int *colptr=mat.colptr;
    //mise  en place des colptr
    *colptr=0;
    for(int i=0;i<mat.ncol-1;i++)
      {
        colptr[i+1]=colptr[i]+ncol[i];
        //cout<<"nb element colonne "<<i<<" "<<ncol[i]<<endl;
        //cout<<"les valeurs de debut de colonne "<<8*colptr[i+1]<<endl;
      }
    colptr[mat.ncol]=mat.nnz;
    //cout<<"mat.nnz "<<mat.nnz<<" "<<mat.nnz*8<<endl;
    //fin mise en place
    //la on fait des manip symboliques pour savoir ou ecrire 
    //les coeffs de chaques colonnes ca evite d'avoir a les
    //recopier 50000 fois pour construire la matrice 
    //c bcp plus rapide
    itermk=tmpMk.begin();
    iterpk=tmpPk.begin();
    iterex=exceed.begin();
    itersize=sizeexceed.begin();
    line_num=0;
    //cout<<"nbproj "<<nbproj<<endl;
#if 0    
for(;0&&(line_num < (int)(tmpPk.size()-nbproj));
        iterpk++,iterex++,itersize++,line_num++)
      //les polynome projette sont foutut au bout de la liste!!
      //d'ou le tmpPk.size()-nbproj
      {
        mon tmpmon=iterpk->ind;
        tmpmon.SetCoeff(1);
        //const unsigned int tmpplus=line_num+1,tmp=line_num;
        const unsigned int tmpplus
          =mapint[tmpmon]+1,tmp=tmpplus-1;
        //      cout<<"ici line_num"<<line_num<<" le mon dom est col "<<tmp<<endl;
        //ici couille car le ind n'est pas forcement le mon diag
        nzval[colptr[tmpplus]-ncol[tmp]]=1;
        //fin couille changer un truc
        //      cout<<"mat.nnz "<<mat.nnz<<endl;
        //cout<<"colptr[...]"<<colptr[tmpplus]<<endl;
        //cout<<"ncol[....]"<<ncol[tmp]<<endl;
        //cout<<"1 a la pos "<<colptr[tmpplus]-ncol[tmp]<<endl;
        rowind[colptr[tmpplus]-ncol[tmp]]=line_num;
        //cout<<"1 a la ligne "<<rowind[colptr[tmpplus]-ncol[tmp]]<<endl;
        ncol[tmp]--;
        {
          //coeff tmpcoeff=iterpk->ind.GetCoeff()-(coeff)1;
          for(int i=0;*itersize>i;i++)
          {
            const coeff stock=(*iterex)[i].GetCoeff();
            (*iterex)[i].SetCoeff(1);
            const unsigned int tmpplusex=mapint[(*iterex)[i]]+1;
            const unsigned int tmpex=mapint[(*iterex)[i]];
            nzval[colptr[tmpplusex]-ncol[tmpex]]
              =stock;
            rowind[colptr[tmpplusex]-ncol[tmpex]]=line_num; 
            ncol[tmpex]--;
            //    cout<<"valeur de ncol["<<tmpex<<"] "<<ncol[tmpex]<<endl;
          }
        }
        MAC_REV_FREE<mon>(*iterex,*itersize*sizeof(mon));
      }
#endif
    for(;(iterpk!=tmpPk.end());iterpk++,iterex++,itersize++,line_num++)
      {
        //const unsigned int tmpplus=line_num+1,tmp=line_num;
        {
          //coeff tmpcoeff=iterpk->ind.GetCoeff()-(coeff)1;
          for(int i=0;*itersize>i;i++)
          {
            const coeff stock=(*iterex)[i].GetCoeff();
            (*iterex)[i].SetCoeff(1);
            const unsigned int tmpplusex=mapint[(*iterex)[i]]+1;
            const unsigned int tmpex=tmpplusex-1;
            nzval[colptr[tmpplusex]-ncol[tmpex]]
              =stock;
            rowind[colptr[tmpplusex]-ncol[tmpex]]=line_num; 
            ncol[tmpex]--;
          }
        }
        MAC_REV_FREE<mon>(*iterex,*itersize*sizeof(mon));
        //free(*iterex);
      }
    free(ncol);
   }
   for(typename typPk::iterator iterpk=tmpPk.begin()
         ;iterpk!=tmpPk.end();iterpk++)
     iterpk->ind.SetCoeff(1);
     //iterpk->ind*=1/iterpk->ind.GetCoeff();
   //  cout<<"la matrice dans newpkmkmatrixof"<<endl;
   //cout<<" nombre de non zero "<<mat.nnz<<endl;
#ifdef DEB
   affdebug(mat);
#endif
   //cout<<"le colptr "<<endl;
   //for(int i=0;i<mat.ncol;i++)
   // cout<<mat.colptr[i]<<" "<<endl;
   //   cout<<"les indices de lignes et le nnz"<<endl;
   //for(int i=0;i<mat.nnz;i++)
   //  cout<<mat.rowind[i]<<" "<<((typename typMat::coeff_t*)mat.nzval)[i]<<endl;
   //cout<<"fin matrice"<<endl;
   Pk.swap(tmpPk);
   Mk.swap(tmpMk);
   
   //  for(int i=0;i<mat.nnz;i++)
   // cout<<"coeff mat "<<((typename typMat::coeff_t*)mat.nzval)[i]<<" et i "<<i<<endl; 
   return flagdoplus;
}
//newpkmkmatrixof termine reste plus qu'a tester .... ;-(

template<typename typdump,typename mon,typename pol>
void findcorresppol(const mon & m,const typdump &dump,pol &res)
{
  typedef typename pol::monom_t mondump;
  int i,d=m.GetDegree();
  typename typdump::const_iterator iter=dump.begin();
  for(;(iter!=dump.end())&&(iter->k!=d);iter++);
  //localise la dump struct de bon degre
  if(iter!=dump.end())
    {
      for(i=0;(i<iter->size)&&(iter->nf[i].ind.rep!=m.rep);i++);
      //cout<<"monomes passe en revue pour chercher "<<m<<" : "<<iter->nf[i].ind<<endl;;
      //trouve dans la dump struct le pol qui marche
      if (i<iter->size)//estce que je connais?
        //oui super
        {
          //cout<<"g trouve un gus qui convient"<<endl;
          //for(int j=0;j<iter->nf[i].size;j++)
          // cout<<"et ses coeff sont "<<iter->nf[i].nf[j]<<endl;
          //Tue Dec  4 16:12:10 MET 2001
          //densify(iter->nf[i],res);}
          //Tue Dec  4 16:12:10 MET 2001
          res=iter->nf[i];}
      else {
        //non ben alors il se reecrit en lui meme
        res.ind=mondump(0);//m*(1/m.GetCoeff());
        res.size=-1;
        res.nf=NULL;
      }
    }
  return;
}

template<typename iterator, typename mon,typename Base>
void varmult(iterator iter1,iterator iter2,mon &var1, mon &var2,const Base &b)
{
  for(int i=0;i<b.nbvar();i++)
    {
      if(iter1->ind.GetDegree(i)>iter2->ind.GetDegree(i))
        var2=mon(i,1);
      if(iter2->ind.GetDegree(i)>iter1->ind.GetDegree(i))
        var1=mon(i,1);
    }
}

template <typename mon,typename pol, typename typdump,typename Base>
pol halfred(const mon &targetind, const pol & p, const typdump & dump
              , const Base & b)
{
  typedef typename pol::coeff_t coeff;
  static const mon monzero=mon(0);
  static const typename pol::coeff_t zero(0);
  pol res;
  int *place=(int*)MAC_REV_MALLOC<int>(p.size*sizeof(int));
#ifdef uninf
  int varref;
  int flagplus=0;
  pol stockpol;
  coeff stockcoeff;
#else
  mon varref;
  
#endif  
  int maxref=0,i;
  for(i=0;i<b.nbvar();i++)
    {
      if(targetind.GetDegree(i)>p.ind.GetDegree(i))
        break;
    }
#ifdef uninf
  varref=i;
#else
  varref=mon(i,1); 
#endif
#ifdef DEB  
  cout<<"p en entree"<<invconv<Poly>(p)<<endl;
  cout<<"target "<<targetind<<" et ind "<<p.ind<<" et var "<<varref<<endl;
#endif
#ifdef nosize
  maxref=size;
#else
  for(int i=0;i<p.size;i++)
    {
      if(p.nf[i]!=zero)
        {
#ifdef uninf    
          place[i]=mulind(i,varref,b);
          if (place[i]>maxref)
            maxref=place[i];
#else
          int indtmpmon;
          mon tmpmon;
          int2mon(i,tmpmon);
          tmpmon*=varref;
          if(IsinB(tmpmon,b))
            {
              indtmpmon=mon2int(tmpmon);
              if(maxref<indtmpmon) 
                maxref=indtmpmon;
              place[i]=indtmpmon;
            }
          else
            {
              place[i]=-1;
            }
#endif //nored
        }
    }
#endif //nosize
  res.nf=(typename pol::coeff_t*)
    MAC_REV_MALLOC<typename pol::coeff_t>
    ((maxref+1)*sizeof(typename pol::coeff_t));
  for(int i=0;i<=maxref;i++)
    res.nf[i]=0;
  res.size=maxref+1;
  i=0;
  for(;i<p.size;i++)
    {
      if(p.nf[i]!=zero)
        {
#ifdef uninf
          if(place[i]==-1)
            {
              pol stock=nf<pol,typdump,Base>(varref,i,dump,b);
#ifdef plus2          
              if (!flagplus)
                {
                  flagplus=1;
                  stockpol=stock;
                  stockcoeff=p.nf[i];
                }
              else
                {
                  myplus22(res,stockpol,stockcoeff,stock,p.nf[i]);
                  flagplus=0;
                  stockcoeff=0;
                }
#else
              //cout<<" je reduit prr lui"<<endl<<invconv<Poly>(stock)<<endl;
              my_plus(res,stock,p.nf[i]);
#endif
            }
          else
            {
              res.nf[place[i]]+=p.nf[i];
            }
#else
          mon tmpmon;
          int2mon(i,tmpmon);
          tmpmon*=varref;
          
          if(place[i]==-1)
            {
              pol stock;
              //cout<<"halfred "<<varref*tmpmon<<endl;
              findcorresppol(tmpmon,dump,stock);
              //cout<<"en retour "<<invconv<Poly>(stock)<<endl;
              //res*stock.ind.GetCoeff();
              //cout<<"le coeff ici "<<stock.ind.GetCoeff()<<endl;
              my_plus(res,stock,p.nf[i]);
              //Tue Dec  4 17:29:06 MET 2001
              //MAC_REV_FREE<coeff>(stock.nf,stock.size*sizeof(coeff));
              //Tue Dec  4 17:29:06 MET 2001
            }
          else
            {
              res.nf[mon2int(tmpmon)]+=p.nf[i];
            }
#endif
        }
    }
#ifdef uninf
#ifdef plus2
  if(flagplus)
    my_plus(res,stockpol,stockcoeff);
#endif
#endif

  res.ind=monzero;
  MAC_REV_FREE<int>(place,p.size*sizeof(int));
#ifdef DEB
  cout<<" apres reduction "<<invconv<Poly>(res)<<endl;
#endif
  return res;
}

template <typename typPk, typename typdump,typename Base>
void ReduceSpol(typPk &S,const typdump & dump,typPk &redspol,const Base &b)
{
  typedef typename typPk::value_type pol;
  typedef typename pol::monom_t mon;
  typedef typename pol::coeff_t coeff;
  list<mon> leadmon;
  list<typPk> membermon;
  
   cout<<"en entree de RedSpol S.size "<<S.size()/2<<endl;
  for(typename typPk::iterator iterS=S.begin();iterS!=S.end();iterS++,iterS++)
    {
      typename typPk::iterator iterS2=iterS;
      typename list<mon>::iterator itermon=leadmon.begin();
      typename list<typPk>::iterator itermemb=membermon.begin();
      mon var1,var2,tmpleadmon;
      iterS2++;
      varmult(iterS,iterS2,var1,var2,b);
      tmpleadmon=iterS->ind*var1;
      for(;itermon!=leadmon.end()&&itermon->rep!=tmpleadmon.rep;
          itermon++,itermemb++);
      if(itermon!=leadmon.end())
        {
          int yes1=1,yes2=1;
          for(typename typPk::iterator tmpiter=itermemb->begin();
              tmpiter!=itermemb->end();tmpiter++)
            {
              if(tmpiter->ind.rep==iterS->ind.rep) yes1=0;
              if(tmpiter->ind.rep==iterS2->ind.rep) yes2=0;
            }
          if(yes1) itermemb->push_back(*iterS);
          if(yes2) itermemb->push_back(*iterS2);
        }
      else
        {
          typPk verytmp;
          leadmon.push_back(tmpleadmon);
          membermon.push_back(verytmp);
          membermon.back().push_back(*iterS); 
          membermon.back().push_back(*iterS2);
        }
    }
  //maintenant on a mis en place la structure de Redspol
  //reste plus qu'a calculer les bons et a reduire tout ca!!
  { 
    typename list<mon>::iterator itermon=leadmon.begin();
    typename list<typPk>::iterator itermemb=membermon.begin();
    for(;itermon!=leadmon.end();itermon++,itermemb++)
      {
        typename typPk::value_type ref;
        typename typPk::iterator tmpiter=itermemb->begin();
        ref=halfred(*itermon,*tmpiter,dump,b);
        //      cout<<"ref.size "<<ref.size<<endl;
        //cout<<"ref en entier"<<endl<<invconv<Poly>(ref)<<endl;
        tmpiter++;
        for(;tmpiter!=itermemb->end();tmpiter++)
          {
            typename typPk::value_type redcur;
            redcur=halfred(*itermon,*tmpiter,dump,b);
            my_plus(redcur,ref);
            if(!Ispolzero(redcur))
              {
                // cout<<"un redspol pas 0"<<endl<<invconv<Poly>(redcur)<<endl;
//              for(int i=0;i<redcur.size;i++)
//                cout<<int2mon_[i]<<" ";
//              cout<<endl;
                redspol.push_back(redcur);
              }
            else
              {
                MAC_REV_FREE<coeff>(redcur.nf,redcur.size*sizeof(coeff));
              }
          }
        MAC_REV_FREE<coeff>(ref.nf,ref.size*sizeof(coeff));
      }
  }
}

template <typename typPk, typename typdump,typename Base>
void OLD_ReduceSpol(typPk &S,const typdump & dump,typPk &redspol,const Base &b)
{
  typedef typename typPk::value_type pol;
  typedef typename pol::monom_t mon;
  typedef typename pol::coeff_t coeff;
  const coeff  zero(0);
  //cout<<"en entree de RedSpol S.size "<<S.size()/2<<endl;
  for(typename typPk::iterator iterS=S.begin();iterS!=S.end();iterS++,iterS++)
    {
      typename typPk::iterator iterS2=iterS;
      mon var1,var2;
      typename typPk::value_type res;
      int max=0;
      mon tmpmon;
      iterS2++;
      //cout<<"les deux pol sont dans redspol "<<endl;
       //cout<<invconv<Poly>(*iterS)<<endl;
      //cout<<"et"<<endl;
      //cout<<invconv<Poly>(*iterS2)<<endl;
      varmult(iterS,iterS2,var1,var2,b);
      //cout<<"les var mult "<<var1<<" "<<var2<<endl;
      res.ind=mon(zero);
      for(int i=0;i<iterS->size;i++)
        {
          //if(!Iszero(iterS->nf[i]))
          if(iterS->nf[i]!=zero)
            {
              int2mon(i,tmpmon);
              //cout<<"les mon red "<<(var1*tmpmon)<<endl;
              if(IsinB(var1*tmpmon,b))
                if(max<mon2int(var1*tmpmon)) max=mon2int(var1*tmpmon);
          }
        }
      for(int i=0;i<iterS2->size;i++)
        {
          //if(!Iszero(iterS2->nf[i]))
          if(iterS2->nf[i]!=zero)
          {
              int2mon(i,tmpmon);
              //  cout<<"les mon red "<<(var1*tmpmon)<<endl;
              if(IsinB(var2*tmpmon,b))
                if(max<mon2int(var2*tmpmon)) max=mon2int(var2*tmpmon);
            }
        }
      res.nf=(typename typPk::value_type::coeff_t*)
        MAC_REV_MALLOC<typename typPk::value_type::coeff_t>
        ((max+1)*sizeof(typename typPk::value_type::coeff_t));
      for(int i=0;i<=max;i++)
        res.nf[i]=0;
      res.size=max+1;
      for(int i=0;i<iterS->size;i++)
        {
          //if(!Iszero(iterS->nf[i]))
          if(iterS->nf[i]!=zero)
          {
            mon tmpmon;
            int2mon(i,tmpmon);
            if(!IsinB(var1*tmpmon,b))
              {
                pol stock;
                //cout<<"je cheche le monome "<<(var1*tmpmon)<<"  et var1 vaut "
                //   <<var1<<endl;
                findcorresppol(var1*tmpmon,dump,stock);
                //cout<<"stock trouve "<<endl<<invconv<Poly>(stock)<<endl;
                //cout<<"stock.size "<<stock.size<<endl;
                res*stock.ind.GetCoeff();
                my_plus(res,stock,iterS->nf[i]);
              }
          else
            {
         //      cout<<"je rajoute a "<<var1*tmpmon<<" "<<iterS->nf[i]<<endl;
              res.nf[mon2int(var1*tmpmon)]+=iterS->nf[i];
            }
            // cout<<"a ce tour de boucle res vaut"<<endl<<invconv<Poly>(res)<<endl;
          }
        }
      //cout<<"entre deux boucle res vaut"<<endl<<invconv<Poly>(res)<<endl;
      for(int i=0;i<iterS2->size;i++)
        {
          //if (!Iszero(iterS2->nf[i]))
          if(iterS2->nf[i]!=zero)
          {
              mon tmpmon;
              //cout<<"iterS2->size "<<iterS2->size<<endl;
              //cout<<" et i "<<i<<endl;
              int2mon(i,tmpmon);
              //cout<<"mon en cours "<<tmpmon<<" et Is in B "<<
              //        IsinB(var2*tmpmon,b)<<endl;
              if(!IsinB(var2*tmpmon,b))
                {
                  pol stock;
                  findcorresppol(var2*tmpmon,dump,stock);
                  //  cout<<"stock trouve "<<endl<<invconv<Poly>(stock)<<endl;
                  res*stock.ind.GetCoeff();
                  my_plus(res,stock,(coeff)((coeff)(-1)*iterS2->nf[i]));
                }
              else
                {
                  // int toto=mon2int(var2*tmpmon),tutu=mon2int(var2*tmpmon);
                  //cout<<"res.size "<<res.size<<endl;
                  //cout<<"et j'acced a "<<toto
                  //   <<" "<<tutu<<endl;
                  res.nf[mon2int(var2*tmpmon)]-=iterS2->nf[i];
                }
            }
          //cout<<"a ce tour de boucle res vaut"<<endl<<invconv<Poly>(res)<<endl;
        }
      if(!Ispolzero(res))
        {
          //  cout<<"un spol qui se reduiot pas a 0"<<endl;
          //for(int i=0;i<res.size;i++)
          //  cout<<"les coeff du qui se reduit pas a 0 "<<res.nf[i]<<endl;
          // cout<<"invconv<Poly>"<<endl<<invconv<Poly>(res)<<endl;
          redspol.push_back(res);
          //break;//ca c pour pas faire 50 tours 
          //      //qd on cherche juste a extraire 1 seul sopl non 0
        }
      else
        {
          MAC_REV_FREE<coeff>(res.nf,res.size*sizeof(coeff));
          // free(res.nf);
        }
    }
  //cout<<"en sortie redspol.size() "<<redspol.size()<<endl;
}

template<typename typPk>
int mindeg(const typPk &l)
{
  typedef typename typPk::value_type::monom_t mon;
  typedef typename mon::coeff_t coeff;
  int res=-1;
  //  cout<<"dans mindeg res au debut"<<res<<endl;
  for(typename typPk::const_iterator iter=l.begin() ;iter!=l.end();iter++)
   {
     int mmax=-1;
     // cout<<"tour de boucle de mindeg "<<endl;
     for(int i=0;i<iter->size;i++)
       if(!Iszero(iter->nf[i]))
         {
           mon tmpmon;
           int2mon(i,tmpmon);
           mmax=(mmax<tmpmon.GetDegree())?tmpmon.GetDegree():mmax;
         }
     // cout<<"mmax ici "<<mmax<<endl;
     if (iter->ind.GetCoeff()==(coeff)1)
       mmax=(mmax<iter->ind.GetDegree())?iter->ind.GetDegree():mmax;
     //cout<<"les gens que je regarde "<<iter->ind<<endl;
     if(mmax!=-1)
     {
       if(res==-1) res=mmax;
       res=(mmax>res)?res:mmax;
     }
   }
  //cout<<"resultat de mindeg "<<res<<endl;
  return res;
}

template<typename typP,typename typPk,typename typMk,typename Base
,typename typdump>
void Crochetchoix(const typP & P,typPk & Pk, typMk & Mk, typPk & redspol,int k
                    ,typdump & dump, Base &b)
{
  typedef typename typP::value_type polyalp;
  typedef typename polyalp::monom_t mon;
  typedef typename polyalp::coeff_t coeff;
  typPk res=Crochet(redspol,k),tmpres;
  //typename typPk::iterator iter=res.begin();
  //  cout<<"entree dans Crochetchoix et k vaut "<<k<<endl;
  //cout<<"res.size "<<res.size()<<endl;
  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
    {
      for(typename typPk::iterator iterredspol=redspol.begin();
          iterredspol!=redspol.end();iterredspol++)
        if(iter->nf==iterredspol->nf)
          {
            redspol.erase(iterredspol);
            break;
          }
    }
  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
    {
      //  cout<<"un nouveau tour de boucle "<<endl;
      if (!Ispolzero(*iter))
        {
          iter->ind=choice(invconv<polyalp>(*iter),b);
          //cout<<"g choisi dans Crochetchoix "<<iter->ind<<endl;
          //cout<<"a t'il un mon2int ?"<<IsinB(iter->ind,b)<<endl;
          //mon tmp10,tmp11;
          //      int2mon(10,tmp10);int2mon(11,tmp11);
          //cout<<"qu'en est il de int2mon(10) et 11 "<<tmp10<<" "<<tmp11<<endl;
           //     
          //
          //
          //UGLY HACK
          remiseenforme(*iter);
          //SALE HACK
          //
          //
          //
          //
          //
          *iter/=iter->ind.GetCoeff();//pour la "nf"
          iter->ind*=(coeff)1/iter->ind.GetCoeff();//pour l'ind
          iter->nf[mon2int(iter->ind)]=0;
          //      
          //
          //
          //UGLY HACK
          remiseenforme(*iter);
          //SALE HACK
          //
          //
          //
          //
          //

          tmpres.push_back(*iter);
          //on met a 0 le coeff du mon passe en ind
          //maintenant on a une regle en forme comme il faut reste a:
          //-reduire les regles deja existantes par rapport acelle ci
          //-reduire les autres redspol par rapport a celle ci
          for(typename typPk::iterator iterPk=Pk.begin();iterPk!=Pk.end();iterPk++)
            if((mon2int(iter->ind)<iterPk->size)&&
               (iterPk->nf[mon2int(iter->ind)]!=(coeff)0))//test a zero!!!
              {
                //      cout<<"g trouve un gus qui a un coeff du mon choisi "
                //    <<iterPk->nf[mon2int(iter->ind)]<<endl;
                my_plus(*iterPk,*iter,iterPk->nf[mon2int(iter->ind)]);
                iterPk->nf[mon2int(iter->ind)]=0;
                //cout<<"apres plus le coeff vaut "
                //    <<iterPk->nf[mon2int(iter->ind)]<<endl; 
              }
                //attention plus(a,b)==a-coeff_de_ind_b_dans_a*b;
          for(typename typPk::iterator iterredspol=iter;iterredspol!=res.end()
                ;iterredspol++)
            {
              // cout<<"redspol.size() "<<redspol.size()<<endl;
              //cout<<"iterredspol-ind "<<iterredspol->ind<<" "<<iterredspol->nf<<endl;
              if(mon2int(iter->ind)<iterredspol->size && 
                 iterredspol->nf[mon2int(iter->ind)]!=(coeff)0)//test a 0 ici
                {
                  my_plus(*iterredspol,*iter,iterredspol->nf[mon2int(iter->ind)]);
                  iterredspol->nf[mon2int(iter->ind)]=0;
                }
                  //cout<<"coucou je suis ici"<<endl;
            }
              //voila c fait 
          //maintenant on met a jour la Base b.
          for(typename Base::iterator iterb=b.begin();iterb!=b.end();iterb++)
            {
              iterb->refuse=(mon*)MAC_REV_REALLOC<mon>
                (iterb->refuse,(iterb->taille2)*sizeof(mon),
                 (iterb->taille2+1)*sizeof(mon));
              iterb->refuse[iterb->taille2]=iter->ind;
              iterb->refuse[iterb->taille2].SetCoeff(1);
              iterb->taille2++;
            }
          res.erase(iter--);
          break;//comme ca on fait pas 50 tours.
        }
    }
  for (typename typPk::iterator iterpk=Pk.begin();iterpk!=Pk.end();iterpk++)
    {
      //      cout<<"iterpk->ind "<<iterpk->ind<<"et Isinb(iterpk-ind,b) "<<IsinB(iterpk->ind,b)<<endl;
      if (IsinB(iterpk->ind,b))
        {
          for(typename Base::iterator iterb=b.begin();iterb!=b.end();iterb++)
            {
              iterb->refuse=(mon*)MAC_REV_REALLOC<mon>
                (iterb->refuse,(iterb->taille2)*sizeof(mon),
                 (iterb->taille2+1)*sizeof(mon));
              iterb->refuse[iterb->taille2]=iterpk->ind;
              iterb->refuse[iterb->taille2].SetCoeff(1);
              iterb->taille2++;
            }
        }
    }
  my_merge(Pk,tmpres);//les gens dans res\tmpres ne sont pas detruits!!!
  my_merge(redspol,res);
  return;
}
//assomption de Destroy Crochet choix met le "gagnant " a la fin
template<typename typPk>
void Destroyredspol(typPk &redspol,const typPk &Pk)
{
  typename typPk::const_iterator iterpk=--Pk.end(); 
  for(typename typPk::iterator iter=redspol.begin();
      iter!=redspol.end();iter++)
    {
      if(iter->nf!=iterpk->nf)
        MAC_REV_FREE<typename typPk::value_type::coeff_t>(iter->nf
                                                  ,iter->size
                                 *sizeof(typename typPk::value_type::coeff_t));
    }
}
#ifndef NO_TWICE
template<typename typP,typename typPk,typename typMk
         ,typename Base,typename typdump, typename typrecall>
void NewCrochetchoix(typP & P,typPk & Pk,typMk & Mk, typPk & redspol
                     ,int &k,typdump &dump, Base &b, typrecall & recall)
#else
template<typename typP,typename typPk,typename typMk
         ,typename Base,typename typdump, typename typrecall>
void NewCrochetchoix(typP & P,typPk & Pk,typMk & Mk, typPk & redspol
                     ,int &k,typdump &dump, Base &b, typrecall & recall
                     ,typMk &Spoldejavu)
#endif
  //template<typename typP,typename typPk,typename typMk,typename Base,typename typdump>
//void NewCrochetchoix(const typP & P,typPk & Pk,typMk & Mk, typPk & redspol
//                   ,int &k,typdump &dump, Base &b)
  //en cours d'ecriutre inoperationnel ,pour le moment
  //comme le Newdestroystore...
{
  //displaymon();
  typedef typename typP::value_type polyalp;
  typedef typename polyalp::monom_t mon;
  typedef typename polyalp::coeff_t coeff;
  //  for(typename typPk::iterator iter=redspol.begin();iter!=redspol.end();iter++)
  //cout<<"les gens dans redspol "<<endl<<invconv<polyalp>(*iter)<<endl;
  
  typPk res=Crochet(redspol,k),tmpres;
  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
        {
          for(typename typPk::iterator iterredspol=redspol.begin();
              iterredspol!=redspol.end();iterredspol++)
            if(iter->nf==iterredspol->nf)
              {
                redspol.erase(iterredspol);
                break;
              }
        }

  for(typename typPk::iterator iter=res.begin();iter!=res.end();iter++)
    {
      // cout<<"un nouveau tour de boucle "<<endl;
      if (!Ispolzero(*iter))
        {
          //iter->ind=choice(invconv<polyalp>(*iter));
          iter->ind=choice(*iter,b);
          //cout<<"le pol pas zero "<<(invconv<polyalp>(*iter))<<endl;
          if(iter->ind.GetDegree()<k)
            {

              k=iter->ind.GetDegree();
              iter->ind=mon(0);
#ifdef NO_TWICE_FALL
              P.push_back(invconv<polyalp>(*iter));
#endif  
              //cout<<"le pol pas zero "<<(invconv<polyalp>(*iter))<<endl;
              //cout<<"passage par bout de code en plus "<<endl;
              my_merge(res,tmpres);
              my_merge(redspol,res);
              tmpres.erase(tmpres.begin(),tmpres.end());
              res.erase(res.begin(),res.end());
              res=Crochet(redspol,k);
              //cout<<"newres.size "<<res.size()<<endl;
              for(typename typPk::iterator iterres=res.begin()
                    ;iterres!=res.end();iterres++)
                {
                  for(typename typPk::iterator iterredspol=redspol.begin();
                      iterredspol!=redspol.end();iterredspol++)
                    if(iterres->nf==iterredspol->nf)
                      {
                        redspol.erase(iterredspol);
                        break;
                      }
                }
              iter=res.begin();
              //iter->ind=choice(invconv<polyalp>(*iter));
              iter->ind=choice(*iter,b);
              Dump(Pk,dump);//c pour detruire Pk dans forget
              //ca ne respecte pas la structure du dump!!!
              recover(Pk,Mk,dump,k);
#ifdef NO_TWICE       
              Listedejafait(Mk,Spoldejavu);
#endif
              forget(b,dump,k,recall);
              //forget(b,dump,k);
              compress(Pk,redspol,dump,b,k);
              //swap(*iter,*res.rbegin());//on veut ne plus 
              //iter=--res.end();//refaire d'autre tours
            }
          //cout<<"g choisi dans Crochetchoix "<<iter->ind<<endl;
          //cout<<"a t'il un mon2int ?"<<IsinB(iter->ind,b)<<endl;
          //mon tmp10,tmp11;
          //      int2mon(10,tmp10);int2mon(11,tmp11);
          //cout<<"qu'en est il de int2mon(10) et 11 "<<tmp10<<" "<<tmp11<<endl;
          //      
          //
          //
#ifdef UGLY_HACK
          remiseenforme(*iter);
#endif
          //SALE HACK
          //
          //
          //
          //
          //
          *iter/=iter->ind.GetCoeff();//pour la "nf"
          iter->ind*=(coeff)1/iter->ind.GetCoeff();//pour l'ind
          iter->nf[mon2int(iter->ind)]=0;
          //      
          //
              //
#ifdef UGLY_HACK
          remiseenforme(*iter);
#endif    
          //SALE HACK
              //
          //
              //
          //
          //
          
          tmpres.push_back(*iter);
          //on met a 0 le coeff du mon passe en ind
          //maintenant on a une regle en forme comme il faut reste a:
          //-reduire les regles deja existantes par rapport acelle ci
          //-reduire les autres redspol par rapport a celle ci
          for(typename typPk::iterator iterPk=Pk.begin();iterPk!=Pk.end();iterPk++)
            if((mon2int(iter->ind)<iterPk->size)&&
               (iterPk->nf[mon2int(iter->ind)]!=(coeff)0))//test a zero!!!
              {
                //cout<<"g trouve un gus qui a un coeff du mon choisi "<<endl;
                //cout<<"le voila "<<invconv<Poly>(*iterPk)<<endl;
                //<<iterPk->nf[mon2int(iter->ind)]<<endl;
                coeff tmpcoeff=iterPk->nf[mon2int(iter->ind)];
                //cout<<"le coeff "<<tmpcoeff<<" tmpind "<<mon2int(iter->ind)<<endl;
                my_plus(*iterPk,*iter,tmpcoeff);
                iterPk->nf[mon2int(iter->ind)]=0;
                //cout<<"apres plus le coeff vaut "
                //  <<iterPk->nf[mon2int(iter->ind)]<<endl; 
                //cout<<"apres mise a jour"<<endl<<invconv<Poly>(*iterPk)<<endl;
              }
          //attention plus(a,b)==a-coeff_de_ind_b_dans_a*b;
          typename typPk::iterator iterredspol=iter;
          iterredspol++;
          for(;iterredspol!=res.end();iterredspol++)
            {
              //cout<<"redspol.size() "<<redspol.size()<<endl;
              //cout<<"iterredspol-ind "<<iterredspol->ind<<" "<<iterredspol->nf<<endl;
              if(mon2int(iter->ind)<iterredspol->size && 
                 iterredspol->nf[mon2int(iter->ind)]!=(coeff)0)//test a 0 ici
                {
                  coeff tmpcoeff=iterredspol->nf[mon2int(iter->ind)];
              my_plus(*iterredspol,*iter,tmpcoeff);
                  iterredspol->nf[mon2int(iter->ind)]=0;
                  //  cout<<"coucou je suis ici "<<
                  // iterredspol->nf[mon2int(iter->ind)]<<endl;
                }
            }
          //au tour de tmpres...
          for(iterredspol=tmpres.begin();iterredspol!=tmpres.end();iterredspol++)
            {
              //cout<<"redspol.size() "<<redspol.size()<<endl;
              //cout<<"iterredspol-ind "<<iterredspol->ind<<" "<<iterredspol->nf<<endl;
              if(mon2int(iter->ind)<iterredspol->size && 
                 iterredspol->nf[mon2int(iter->ind)]!=(coeff)0)//test a 0 ici
                {
                  coeff tmpcoeff=iterredspol->nf[mon2int(iter->ind)];
                  my_plus(*iterredspol,*iter,tmpcoeff);
                  iterredspol->nf[mon2int(iter->ind)]=0;
                  //  cout<<"coucou je suis ici "<<
                  //  iterredspol->nf[mon2int(iter->ind)]<<endl;
                }
            }
          //voila c fait 
          //maintenant on met a jour la Base b.
          for(typename Base::iterator iterb=b.begin();iterb!=b.end();iterb++)
            {
              int tmptaille1=0;
              mon *tmp=(mon*)MAC_REV_MALLOC<mon>(iterb->taille1*sizeof(mon));
              for(int i=0;i<iterb->taille1;i++)
                if(!isdivisible(iter->ind,iterb->accept[i],b))
                  tmp[tmptaille1++]=iterb->accept[i];
              tmp=(mon*)MAC_REV_REALLOC<mon>(tmp,iterb->taille1*sizeof(mon)
                                             ,tmptaille1*sizeof(mon));
              MAC_REV_FREE<mon>(iterb->accept,iterb->taille1*sizeof(mon));
              iterb->accept=tmp;
              iterb->taille1=tmptaille1;
              if(iterb->taille1==0)
                {
                  MAC_REV_FREE<mon>(iterb->refuse,iterb->taille2*sizeof(mon));
                  b.erase(iterb--);
                  continue;
                }
              iterb->refuse=(mon*)MAC_REV_REALLOC<mon>
                (iterb->refuse,(iterb->taille2)*sizeof(mon),
                 (iterb->taille2+1)*sizeof(mon));
              iterb->refuse[iterb->taille2]=iter->ind;
              // cout<<"reffuse rajoute "<<iter->ind<<endl;
              iterb->refuse[iterb->taille2].SetCoeff(1);
              iterb->taille2++;
            }
          res.erase(iter--);
        }
      //break;//comme ca on fait pas 50 tours.
    }

  for (typename typPk::iterator iterpk=Pk.begin();iterpk!=Pk.end();iterpk++)
    {
      //cout<<"iterpk->ind "<<iterpk->ind<<"et Isinb(iterpk-ind,b) "<<IsinB(iterpk->ind,b)<<endl;
      //cout<<"le pol "<<invconv<Poly>(*iterpk)<<endl;
      if (IsinB(iterpk->ind,b))
        {
          for(typename Base::iterator iterb=b.begin();iterb!=b.end();iterb++)
            {
              iterb->refuse=(mon*)MAC_REV_REALLOC<mon>
                (iterb->refuse,(iterb->taille2)*sizeof(mon),
                 (iterb->taille2+1)*sizeof(mon));
              iterb->refuse[iterb->taille2]=iterpk->ind;
              iterb->refuse[iterb->taille2].SetCoeff(1);
              iterb->taille2++;
            }
        }
    }
#ifdef NO_TWICE_FALL_CHOICE
  for(typename typPk::iterator iter=tmpres.begin();iter!=tmpres.end();iter++)
    P.push_back(invconv<polyalp>(*iter));
#endif  
  my_merge(Pk,tmpres);//les gens dans res\tmpres ne sont pas detruits ici!!
  my_merge(redspol,res);
  //displaymon();
  return;
}

template<typename typPk>
void NewDestroyredspol(typPk &redspol,const typPk &Pk)
{
  //  typename typPk::const_iterator iterpk=--Pk.end(); 
  for(typename typPk::iterator iter=redspol.begin();
      iter!=redspol.end();iter++)
    {
      //    if(iter->nf!=iterpk->nf)
        MAC_REV_FREE<typename typPk::value_type::coeff_t>(iter->nf,iter->size*sizeof(typename typPk::value_type::coeff_t));
    }
}

template<typename typMk>
void Listedejafait(const typMk &Mk,typMk &Spoldejavu)
{
  Spoldejavu.erase(Spoldejavu.begin(),Spoldejavu.end());
  for(typename typMk::const_iterator iter1=Mk.begin();iter1!=Mk.end();
      iter1++)
    for(typename typMk::const_iterator iter2=iter1;iter2!=Mk.end();
      iter2++)
      {
        typename typMk::value_type tmp=lcm(*iter1,*iter2);
        if (tmp.GetDegree()==iter1->GetDegree()+1)
          Spoldejavu.push_back(tmp);
      }
}

template<typename typP,typename typPk,typename typdump,typename Base
, template<typename  T> class tmptypmat >
void algo(typP P,typdump &dump,Base &b)
{
  // int toto=0;
  typedef list<typename typPk::value_type::monom_t> typMk;
  typedef typename typMk::value_type mon;
  typMk Mk;
  typMk Spoldejavu;
  typPk Pk,S;
  //typP recall 
  typPk recall;
  //Base b;
  int go_on=1;
  typedef tmptypmat<typename typP::value_type::coeff_t> typMat;
  typMat Mat;
  int nouveaumon,allpolused=0,maxdeg,k,*pr,*pc;
  //cout<<"avant init"<<endl;
  init_algo<typMat>(P,nouveaumon,maxdeg,k,Pk,Mk,b,dump);
  //cout<<"apres init"<<endl;
#ifdef dimpos
  go_on=stop_degree(b);
  cout<<"je m'arrete a ce degre "<<go_on<<endl;
  while((nouveaumon||(k<=maxdeg))&& ((go_on>=k)||(k<=maxdeg)))
#else
  while((nouveaumon||(k<=maxdeg)))
#endif 
    {
    //    if (toto>=3) {exit(10);}
    //toto++;
    int killspol;
    //  for(typename Base::const_iterator p=b.begin();p!=b.end();p++)
//        {

//      for(int i=0;i<p->taille1;i++)
//        {
//          cout<<"p.accept[i] "<<p->accept[i]<<endl;
//        }
//      for(int i=0;i<p->taille2;i++)
//        {
//          cout<<"p.refuse[i] "<<p->refuse[i]<<endl;
//        }
//        }
//#define DEB
#ifdef DEB
    cout<<"poly a la fin de la boulcle de l'algo"<<endl;
    for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
       //cout<<"les sizes "<<iter->size<<endl;
    cout<<invconv<typename typP::value_type>(*iter)<<endl;       
#endif
    //#undef DEB
    //cout<<"Spolordsup"<<endl;
#ifdef NO_TWICE    
    S=Spolordsup(Pk,b,Spoldejavu);
#else
    S=Spolordsup(Pk,b);
#endif

#ifdef experiment
    cout<<"S.back().ind.GetCoeff().rep "<<S.back().ind.GetCoeff().rep<<" k "<<k<<endl;
    if((S.back().ind.GetCoeff().rep<k) && (k>=maxdeg))
      {go_on=0;continue;}
    S.pop_back();
#endif 
    //cout<<"newpkmkmatrixof"<<endl;
    //cout<<"Pk.size() "<<Pk.size()<<endl;
#ifdef NO_TWICE
    killspol=!newPkMkMatrixof(Mat,Pk,P,Mk,k,b,dump,recall,Spoldejavu);
#else    
    killspol=!newPkMkMatrixof(Mat,Pk,P,Mk,k,b,dump,recall);
#endif    
    // killspol=!newPkMkMatrixof(Mat,Pk,P,Mk,k,b,dump);
    if(killspol) S.erase(S.begin(),S.end());
    if (k+1>=maxdeg) allpolused=1;
    if(Mk.size()==0) nouveaumon=0;
    //cout<<"j'en suis a k="<<k<<endl;
    //cout<<"Ici dans algo Mat"<<endl;
    //affdebug(Mat);
    //Solve affecte a Mat la valeur U
    //cout<<"solve"<<endl;
    //for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    //  cout<<"avant solve les ind "<<iter->ind<<endl;
    //for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    //  cout<<"avant solve les pol "<<invconv<Poly>(*iter)<<endl;
    //if(k==3) exit(-10);
    //for(typename typMk::iterator iter=Mk.begin();iter!=Mk.end();iter++)
    //  cout<<"monomes dans Mk "<<*iter<<endl;
    if (Mat.ncol!=0)
      {
        Solve(Mat,Pk,&pr,&pc);
        //for(int kk=0;kk<Mk.size();kk++)
        //  cout<<"permc "<<kk<<" "<<pc[kk]<<endl;
        inverse(pc,Mk.size());
        Dopermu(Mk,pc);
        {
          //ici on remet les ind a la bonne valuer 
          //a inclure dans une petite fonction inline apres
          int j=0;
          typename typMk::iterator itermon=Mk.begin();
          typename typPk::iterator iter;
          for(iter=Pk.begin();
              itermon!=Mk.end();iter++,itermon++,j++)
            {
              if(!Iszero(Mat(j,j)))
                {
                  //              cout<<"ligne "<<j<<" je mets le monome "<<*itermon<<endl;
                  iter->ind=*itermon*(iter->ind.GetCoeff());
                }
              else
                {
                  iter->ind=mon(0);
                }
            }
          //for(;itermon!=Mk.end();iter++,itermon++)
          //  iter->ind=mon(0);
        }
        free(pr);
        free(pc);
      }
    
 //appliquer les permutation a MK!!!!!!!!
    // for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
      //  cout<<"apres solve les ind "<<iter->ind<<endl;
    //for(typename typPk::iterator iter=Pk.begin();iter!=Pk.end();iter++)
    // cout<<"apres solve les pol "<<invconv<Poly>(*iter)<<endl;
    //
    //
    //APPLIQUER LES PERMUTYATIONS A MK!!
    //
    //
    //
    //
    if ((unsigned)my_rank(Mat)==Mk.size())
      //matrice de rang plein
      {
        typPk redspol,secd=secondmembre(Mat,Pk);;
        //secondmembre2(Mat,Pk,secd);
        //typename typPk::iterator iter=Pk.begin();
        cout<<"matrice de rang plein "<<endl;
        //for(unsigned int i=0;i<Mk.size();i++,iter++);
        //Pk.erase(iter,Pk.end());
        //cout<<"Dump "<<endl;
        Dump(Pk,dump);
        //cout<<"Reduce Spol "<<endl;
        ReduceSpol(S,dump,redspol,b);
        //cout<<"secd.size() "<<secd.size()<<endl;
        my_merge(redspol,secd);
        if(redspol.size()==0)
          {
            //a voir....    Dump(Pk,dump);
            k++;
            continue;
            //la matrice a rang plein 
            //ET les Spol\secondmembre de ce niveau se ,reduisent a 0
          }
        else
          {
            //on a des spol\secondmembre qui se reduisent pas a 0
            //cad un defaut de commuatation
            nouveaumon=1;
            cout<<"redspol.size() "<<redspol.size()<<endl;
            //cout<<invconv<typename typP::value_type>(redspol.front())<<endl;
            k=mindeg(redspol);
            //cout<<"le mindeg ici vaut "<<k<<endl;
            //cout<<"Pk.size() avant recover "<<Pk.size()<<endl;
            recover(Pk,Mk,dump,k);
#ifdef NO_TWICE
            Listedejafait(Mk,Spoldejavu);
#endif
            //cout<<"Pk.size() apres recover "<<Pk.size()<<endl;
            forget(b,dump,k,recall);
            //forget(b,dump,k);
            //cout<<"Pk.size() avant Crochetchoix "<<Pk.size()<<endl;
#ifdef NO_TWICE
            NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b,recall,Spoldejavu);
#else    
            NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b,recall);
#endif      
            //NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b);
            //cout<<"Pk.size apres Crochetchoix "<<Pk.size()<<" et k "<<k<<endl;
            NewDestroyredspol(redspol,Pk);
            compress(Pk,dump,b,k);
            Dump(Pk,dump);
            //misa jour de B dans crochet choix!!
#ifdef dimpos
            go_on=stop_degree(b);
            cout<<"go on ici vaut "<<go_on<<endl;
#endif

            continue;
          }
      }
    else
      //la matrice n'est pas de rang plein
      {
        cout<<"matrice de rang pas plein "<<endl;
        typPk secd;
        AddB(Mat,Pk,Mk,dump,b);
        //
        //secondmembre supprime des trucs dans Pk!!
        //
        secd=secondmembre(Mat,Pk);
        rajoute_voisins(Pk,Mk,dump,b);
        //ne selectionne que les non nuls
       if(secd.size()==0)
         {
           typPk redspol;
           //for(int i=Pk.size();i>rank(Mat);i--)
           //{
           //  if(Pk.back().size!=0)
           // MAC_REV_FREE<typename typMat::coeff_t>(Pk.rbegin()->nf
           //    ,Pk.rbegin()->size*sizeof(typename typMat::coeff_t));
           //  Pk.pop_back();
           //}//on vire les 0 avant de dumper
           //      AddB(Mat,Pk,Mk,dump,b);
           Dump(Pk,dump);
           ReduceSpol(S,dump,redspol,b);
           if(redspol.size()==0)
             {
               // forget(b,dump,k);
               //AddB(Mat,Pk,Mk,b);
               //Dump(Pk,dump);
               //ici on modifie Pk dans AddB 
               //<=> forget(b,dump,k) AddB(..) Dump(Pk,dump);
               k++;
#ifdef dimpos
               go_on=stop_degree(b);
               cout<<"go on ici vaut "<<go_on<<endl;
#endif

               continue;
               //la matrice a pas rang plein second membre =0 
               //ET les Spol de ce niveau se ,reduisent a 0
             }
           else
             {
               //on a des spol qui se reduisent pas a 0
               //cad un defaut de commutation 
               k=mindeg(redspol);
               recover(Pk,Mk,dump,k);
#ifdef NO_TWICE
               Listedejafait(Mk,Spoldejavu);
#endif         
               forget(b,dump,k,recall);
               //forget(b,dump,k);
               cout<<"il ya un passage par mat rang pas"
                   <<"plein et pol non zero"<<endl;
#ifdef NO_TWICE
               NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b,recall,Spoldejavu);
#else          
               NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b,recall);
#endif         
               //NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b);
               NewDestroyredspol(redspol,Pk);
               compress(Pk,dump,b,k);
               Dump(Pk,dump); 
#ifdef dimpos
               go_on=stop_degree(b);
               cout<<"go on ici vaut "<<go_on<<endl;
#endif

               continue;
             }
         }
       else
         {
           //on a des pol qui se reduisent pas a 0
           //cad un defaut de commuatation dans les coins
           typPk redspol;
           //for(int i=Pk.size();i>rank(Mat);i--)
           //  Pk.pop_back();
           //cout<<"PK. size "<<Pk.size()<<" Mat.nbcol "<<Mat.ncol<<endl;
           //cout<<"rank(Mat) "<<rank(Mat)<<endl;
           //int j=0;
           //cout<<"avant recover et meme avant le dump "<<endl;
           //for(typename typPk::iterator iter = secd.begin();iter!=secd.end()
           //    ;iter++,j++)
           // cout<<"pol de secd num "<<j<<endl<<invconv<Poly>(*iter)<<endl;
           //      AddB(Mat,Pk,Mk,b);
           //cout<<"apres ADDB le dump "<<endl;
           //for(typename typPk::iterator iter = Pk.begin();iter!=Pk.end()
           //    ;iter++)
           // cout<<invconv<Poly>(*iter)<<endl;
           Dump(Pk,dump);
           //cout<<"secd.size()" <<secd.size()<<endl;
           ReduceSpol(S,dump,redspol,b);
           my_merge(secd,redspol);
           k=mindeg(secd);
           recover(Pk,Mk,dump,k);
#ifdef NO_TWICE    
           Listedejafait(Mk,Spoldejavu);
#endif
           //cout<<"apres recover"<<endl;
           //      for(typename typPk::iterator iter = Pk.begin();iter!=Pk.end()
           //    ;iter++)
           //  cout<<invconv<Poly>(*iter)<<endl;
           //cout<<"les Spol non reduits"<<endl;
           //for(typename typPk::iterator iter = secd.begin();iter!=secd.end()
           //    ;iter++)
           //  cout<<invconv<Poly>(*iter)<<endl;
           forget(b,dump,k,recall);
           //forget(b,dump,k);
           //cout<<"il ya un passage par mat pas rang plein et Spol non zero"<<endl;
           //for(typename typPk::iterator iter = secd.begin();iter!=secd.end()
           //    ;iter++)
           // cout<<invconv<Poly>(*iter)<<endl;
#ifdef NO_TWICE    
           NewCrochetchoix(P,Pk,Mk,redspol,k,dump,b,recall,Spoldejavu);
#else      
           NewCrochetchoix(P,Pk,Mk,secd,k,dump,b,recall);
#endif     
           //NewCrochetchoix(P,Pk,Mk,secd,k,dump,b);
           NewDestroyredspol(secd,Pk);
           //for(typename typPk::iterator iter = Pk.begin();iter!=Pk.end()
           //    ;iter++)
           // cout<<invconv<Poly>(*iter)<<endl;
           compress(Pk,dump,b,k);
           Dump(Pk,dump);
#ifdef dimpos
       go_on=stop_degree(b);
       cout<<"go on ici vaut "<<go_on<<endl;
#endif
           
           continue;
         }
      }
  }
  
  Mat.destroystore();
  //while nouveau mon etc...
  // Pk=recomposePk(dump);
  //return Pk;
  //  return;
#ifdef DEBUG
  for(typename Base::const_iterator p=b.begin();p!=b.end();p++)
    {
      for(int i=0;i<p->taille1;i++)
        {
          cout<<"p.accept[i] "<<p->accept[i]<<endl;
        }
      for(int i=0;i<p->taille2;i++)
        {
          cout<<"p.refuse[i] "<<p->refuse[i]<<endl;
        }
    }
#endif
  cout<<"sortie d'algo flash"<<endl;
  return ;//dump;
  //comme ca on conserve le tri par degre des formes normales et 
  //donc la construction des operateurs de multiplication se 
  //fait plus vite.. :-)

}

---