Changeset 5ac8e5 in git for kernel/tgb_internal.h


Ignore:
Timestamp:
Feb 23, 2007, 2:17:55 PM (16 years ago)
Author:
Michael Brickenstein <bricken@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
Children:
95692a4585e51835c9345c4556e2361edfa16182
Parents:
abce2eb6b4be7725a8a5bc3b6feeb4821927af5b
Message:
*bricken: fully templated noro


git-svn-id: file:///usr/local/Singular/svn/trunk@9889 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/tgb_internal.h

    rabce2e r5ac8e5  
    55*  Computer Algebra System SINGULAR     *
    66****************************************/
    7 /* $Id: tgb_internal.h,v 1.59 2007-02-23 09:07:41 bricken Exp $ */
     7/* $Id: tgb_internal.h,v 1.60 2007-02-23 13:17:55 bricken Exp $ */
    88/*
    99 * ABSTRACT: tgb internal .h file
    … …  
    9797 
    9898};
    99 class DataNoroCacheNode;
    100 class MonRedRes{
     99template<class number_type> class DataNoroCacheNode;
     100/*class MonRedRes{
    101101public:
    102102  poly p;
    … …  
    116116    p=NULL;
    117117  }
    118 };
    119 class MonRedResNP{
     118};*/
     119template <class number_type> class MonRedResNP{
    120120public:
    121121  number coef;
    122122
    123123
    124   DataNoroCacheNode* ref;
     124  DataNoroCacheNode<number_type>* ref;
    125125  MonRedResNP(){
    126126    ref=NULL;
    … …  
    137137 
    138138};
    139 
    140 
     139#ifdef NORO_CACHE
     140#ifndef NORO_NON_POLY
    141141class NoroPlaceHolder{
    142142public:
    … …  
    144144  number coef;
    145145};
    146 
     146#endif
     147#endif
    147148//static ideal debug_Ideal;
    148149
    … …  
    392393}
    393394#ifdef NORO_CACHE
     395#define slim_prec_cast(a) (unsigned int) (a)
     396#define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
    394397typedef unsigned short tgb_uint16;
    395398typedef unsigned char tgb_uint8;
    … …  
    461464  }
    462465};
    463 class SparseRow{
     466template <class number_type> class SparseRow{
    464467public:
    465468  int* idx_array;
    466   number* coef_array;
     469  number_type* coef_array;
    467470  int len;
    468471  SparseRow(){
    … …  
    471474    coef_array=NULL;
    472475  }
    473   SparseRow(int n){
     476  SparseRow<number_type>(int n){
    474477    len=n;
    475478    idx_array=(int*) omalloc(n*sizeof(int));
    476     coef_array=(number*) omalloc(n*sizeof(number));
    477   }
    478   ~SparseRow(){
     479    coef_array=(number_type*) omalloc(n*sizeof(number_type));
     480  }
     481  ~SparseRow<number_type>(){
    479482    omfree(idx_array);
    480483    omfree(coef_array);
    … …  
    482485};
    483486
    484 class DataNoroCacheNode:public NoroCacheNode{
     487template <class number_type> class DataNoroCacheNode:public NoroCacheNode{
    485488public:
    486489 
    … …  
    488491  poly value_poly;
    489492  #ifdef NORO_SPARSE_ROWS_PRE
    490   SparseRow* row;
     493  SparseRow<number_type>* row;
    491494  #else
    492495  DenseRow* row;
    … …  
    500503  }
    501504  #ifdef NORO_SPARSE_ROWS_PRE
    502   DataNoroCacheNode(SparseRow* row){
     505  DataNoroCacheNode(SparseRow<number_type>* row){
    503506    if (row!=NULL)
    504507      value_len=row->len;
    … …  
    516519  }
    517520};
    518 class TermNoroDataNode{
     521template <class number_type> class TermNoroDataNode{
    519522public:
    520   DataNoroCacheNode* node;
     523  DataNoroCacheNode<number_type>* node;
    521524  poly t;
    522525};
    523 class NoroCache{
     526
     527template <class number_type> class NoroCache{
    524528public:
    525529  poly temp_term;
     530#ifndef NORO_NON_POLY
    526531  void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
    527   void collectIrreducibleMonomials( std::vector<DataNoroCacheNode*>& res);
    528   void collectIrreducibleMonomials(int level,  NoroCacheNode* node, std::vector<DataNoroCacheNode*>& res);
    529532  void evaluateRows();
    530533  void evaluateRows(int level, NoroCacheNode* node);
     534#endif
     535  void collectIrreducibleMonomials( std::vector<DataNoroCacheNode<number_type>* >& res);
     536  void collectIrreducibleMonomials(int level,  NoroCacheNode* node, std::vector<DataNoroCacheNode<number_type>* >& res);
     537
    531538#ifdef NORO_RED_ARRAY_RESERVER
    532539  int reserved;
    … …  
    534541#endif
    535542  static const int backLinkCode=-222;
    536   DataNoroCacheNode* insert(poly term, poly nf, int len){
     543  DataNoroCacheNode<number_type>* insert(poly term, poly nf, int len){
    537544    //assume(impl.find(p_Copy(term,currRing))==impl.end());
    538545    //assume(len==pLength(nf));
    … …  
    559566  }
    560567  #ifdef NORO_SPARSE_ROWS_PRE
    561   DataNoroCacheNode* insert(poly term, SparseRow* srow){
     568  DataNoroCacheNode<number_type>* insert(poly term, SparseRow<number_type>* srow){
    562569    //assume(impl.find(p_Copy(term,currRing))==impl.end());
    563570    //assume(len==pLength(nf));
    … …  
    569576  }
    570577  #endif
    571   DataNoroCacheNode* insertAndTransferOwnerShip(poly t, ring r){
     578  DataNoroCacheNode<number_type>* insertAndTransferOwnerShip(poly t, ring r){
    572579   
    573580    ressources.push_back(t);
    574     DataNoroCacheNode* res=treeInsertBackLink(t);
     581    DataNoroCacheNode<number_type>* res=treeInsertBackLink(t);
    575582    res->term_index=nIrreducibleMonomials;
    576583    nIrreducibleMonomials++;
    … …  
    578585  }
    579586  poly lookup(poly term, BOOLEAN& succ, int & len);
    580   DataNoroCacheNode* getCacheReference(poly term);
     587  DataNoroCacheNode<number_type>* getCacheReference(poly term);
    581588  NoroCache(){
    582589    buffer=NULL;
    … …  
    626633  size_t tempBufferSize;
    627634protected:
    628   DataNoroCacheNode* treeInsert(poly term,poly nf,int len){
     635  DataNoroCacheNode<number_type>* treeInsert(poly term,poly nf,int len){
    629636    int i;
    630637    nReducibleMonomials++;
    … …  
    634641      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    635642    }
    636     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(nf,len));
     643    return (DataNoroCacheNode<number_type>*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode<number_type>(nf,len));
    637644  }
    638645  #ifdef NORO_SPARSE_ROWS_PRE
    639   DataNoroCacheNode* treeInsert(poly term,SparseRow* srow){
     646  DataNoroCacheNode<number_type>* treeInsert(poly term,SparseRow<number_type>* srow){
    640647    int i;
    641648    nReducibleMonomials++;
    … …  
    645652      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    646653    }
    647     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(srow));
     654    return (DataNoroCacheNode<number_type>*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode<number_type>(srow));
    648655  }
    649656  #endif
    650   DataNoroCacheNode* treeInsertBackLink(poly term){
     657  DataNoroCacheNode<number_type>* treeInsertBackLink(poly term){
    651658    int i;
    652659    int nvars=pVariables;
    … …  
    655662      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    656663    }
    657     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(term,backLinkCode));
     664    return (DataNoroCacheNode<number_type>*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode<number_type>(term,backLinkCode));
    658665  }
    659666 
    … …  
    666673  number* buffer;
    667674};
    668 MonRedResNP noro_red_mon_to_non_poly(poly t,  NoroCache* cache,slimgb_alg* c);
    669 template<class storage_type> SparseRow* noro_red_to_non_poly_t(poly p, int &len, NoroCache* cache,slimgb_alg* c){
     675template<class number_type> SparseRow<number_type> * noro_red_to_non_poly_t(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c);
     676template<class number_type> MonRedResNP<number_type> noro_red_mon_to_non_poly(poly t,  NoroCache<number_type> * cache,slimgb_alg* c)
     677{
     678  MonRedResNP<number_type> res_holder;
     679
     680
     681    DataNoroCacheNode<number_type>* ref=cache->getCacheReference(t);
     682    if (ref!=NULL){
     683
     684
     685      res_holder.coef=p_GetCoeff(t,c->r);
     686     
     687      res_holder.ref=ref;
     688      p_Delete(&t,c->r);
     689      return res_holder;
     690    }
     691 
     692  unsigned long sev=p_GetShortExpVector(t,currRing);
     693  int i=kFindDivisibleByInS_easy(c->strat,t,sev);
     694  if (i>=0){
     695    number coef_bak=p_GetCoeff(t,c->r);
     696
     697    p_SetCoeff(t,npInit(1),c->r);
     698    assume(npIsOne(p_GetCoeff(c->strat->S[i],c->r)));
     699    number coefstrat=p_GetCoeff(c->strat->S[i],c->r);
     700
     701
     702    poly exp_diff=cache->temp_term;
     703    p_ExpVectorDiff(exp_diff,t,c->strat->S[i],c->r);
     704    p_SetCoeff(exp_diff,npNeg(npInvers(coefstrat)),c->r);
     705    p_Setm(exp_diff,c->r);
     706    assume(c->strat->S[i]!=NULL);
     707
     708    poly res;
     709    res=pp_Mult_mm(pNext(c->strat->S[i]),exp_diff,c->r);
     710
     711    int len=c->strat->lenS[i]-1;
     712    SparseRow<number_type>* srow;
     713    srow=noro_red_to_non_poly_t<number_type>(res,len,cache,c);
     714    ref=cache->insert(t,srow);
     715    p_Delete(&t,c->r);
     716
     717
     718    res_holder.coef=coef_bak;
     719    res_holder.ref=ref;
     720    return res_holder;
     721
     722  } else {
     723    number coef_bak=p_GetCoeff(t,c->r);
     724    number one=npInit(1);
     725    p_SetCoeff(t,one,c->r);
     726 
     727    res_holder.ref=cache->insertAndTransferOwnerShip(t,c->r);
     728    assume(res_holder.ref!=NULL);
     729    res_holder.coef=coef_bak;
     730   
     731    return res_holder;
     732   
     733  }
     734
     735}
     736/*
     737poly tree_add(poly* a,int begin, int end,ring r){
     738  int d=end-begin;
     739  switch(d){
     740    case 0:
     741      return NULL;
     742    case 1:
     743      return a[begin];
     744    case 2:
     745      return p_Add_q(a[begin],a[begin+1],r);
     746    default:
     747      int s=d/2;
     748      return p_Add_q(tree_add(a,begin,begin+s,r),tree_add(a,begin+s,end,r),r);
     749  }
     750}
     751*/
     752template<class number_type> SparseRow<number_type> * noro_red_to_non_poly_t(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c){
    670753  assume(len==pLength(p));
    671754  poly orig_p=p;
    … …  
    676759 
    677760  number zero=npInit(0);
    678   MonRedResNP* mon=(MonRedResNP*) omalloc(len*sizeof(MonRedResNP));
     761  MonRedResNP<number_type>* mon=(MonRedResNP<number_type>*) omalloc(len*sizeof(MonRedResNP<number_type>));
    679762  int i=0;
    680763
    … …  
    688771    number coef_debug=p_GetCoeff(t,currRing);
    689772#endif
    690     MonRedResNP red=noro_red_mon_to_non_poly(t,cache,c);
     773    MonRedResNP<number_type> red=noro_red_mon_to_non_poly(t,cache,c);
    691774    mon[i]=red;
    692775    i++;
    … …  
    696779  len=i;
    697780  //in the loop before nIrreducibleMonomials increases, so position here is important
    698   size_t temp_size_bytes=cache->nIrreducibleMonomials*sizeof(storage_type);
     781  size_t temp_size_bytes=cache->nIrreducibleMonomials*sizeof(number_type)+8;//use 8bit int for testing
     782  assume(sizeof(int64)==8);
    699783  cache->ensureTempBufferSize(temp_size_bytes);
    700   storage_type* temp_array=(storage_type*) cache->tempBuffer;//omalloc(cache->nIrreducibleMonomials*sizeof(storage_type));
     784  number_type* temp_array=(number_type*) cache->tempBuffer;//omalloc(cache->nIrreducibleMonomials*sizeof(number_type));
    701785  int temp_size=cache->nIrreducibleMonomials;
    702786  memset(temp_array,0,temp_size_bytes);
    703787  for(i=0;i<len;i++){
    704     MonRedResNP red=mon[i];
     788    MonRedResNP<number_type> red=mon[i];
    705789    if ((red.ref)){
    706790      if (red.ref->row){
    707         SparseRow* row=red.ref->row;
     791        SparseRow<number_type>* row=red.ref->row;
    708792        number coef=red.coef;
    709793        int j;
    … …  
    712796          int idx=row->idx_array[j];
    713797          assume(!(npIsZero(coef)));
    714           assume(!(npIsZero(row->coef_array[j])));
    715           temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],npMultM(row->coef_array[j],coef));
     798          assume(!(npIsZero((number) row->coef_array[j])));
     799          temp_array[idx]=F4mat_to_number_type(npAddM((number) temp_array[idx],npMultM((number) row->coef_array[j],coef)));
    716800          assume(idx<temp_size);
    717801        }}else{
    718802          for(j=0;j<row->len;j++){
    719803            int idx=row->idx_array[j];
    720             temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],row->coef_array[j]);
     804            temp_array[idx]=F4mat_to_number_type(   npAddM((number) temp_array[idx],(number) row->coef_array[j]));
    721805            assume(idx<temp_size);
    722806          }
    … …  
    724808      }
    725809      else{
    726         if (red.ref->value_len==NoroCache::backLinkCode){
    727           temp_array[red.ref->term_index]=(storage_type) (unsigned int) npAddM((number) temp_array[red.ref->term_index],red.coef);
     810        if (red.ref->value_len==NoroCache<number_type>::backLinkCode){
     811          temp_array[red.ref->term_index]=(number_type) (unsigned int) npAddM((number) temp_array[red.ref->term_index],red.coef);
    728812        } else {
    729813          //PrintS("third case\n");
    … …  
    745829    return NULL;
    746830  }
    747   SparseRow* res=new SparseRow(non_zeros);
     831  SparseRow<number_type>* res=new SparseRow<number_type>(non_zeros);
    748832  int pos=0;
     833  #if 0
    749834  for(i=0;i<cache->nIrreducibleMonomials;i++){
    750835    if (!(0==temp_array[i])){
    751836   
    752837      res->idx_array[pos]=i;
    753       res->coef_array[pos]=(number) temp_array[i];
     838      res->coef_array[pos]=temp_array[i];
    754839
    755840      pos++;
    … …  
    759844   
    760845  }
     846  #else
     847  int64* start=(int64*) ((void*)temp_array);
     848  int64* end;
     849  const int multiple=sizeof(int64)/sizeof(number_type);
     850  if (temp_size==0) end=start;
     851 
     852  else
     853  {
     854    int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
     855    assume(temp_size_rounded>=temp_size);
     856    assume(temp_size_rounded%multiple==0);
     857    assume(temp_size_rounded<temp_size+multiple);
     858    number_type* nt_end=temp_array+temp_size_rounded;
     859    end=(int64*)((void*)nt_end);
     860  }
     861  int64* it=start;
     862  while(it!=end){
     863    if ((*it)!=0){
     864      int small_i;
     865      const int temp_index=((number_type*)((void*) it))-temp_array;
     866      const int bound=temp_index+multiple;
     867      for(small_i=temp_index;small_i<bound;small_i++){
     868        if(temp_array[small_i]!=0){
     869          res->idx_array[pos]=small_i;
     870          res->coef_array[pos]=temp_array[small_i];
     871
     872          pos++;
     873          non_zeros--;
     874         
     875        }
     876        if (non_zeros==0) break;
     877      }
     878     
     879    }
     880    ++it;
     881  }
     882  #endif
    761883  //omfree(temp_array);
    762884
    … …  
    772894// assume: field is Zp
    773895#ifdef USE_NORO
    774 #define slim_prec_cast(a) (unsigned int) (a)
    775 #define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
     896
    776897
    777898template <class number_type > void write_poly_to_row(number_type* row, poly h, poly*terms, int tn, ring r){
    … …  
    814935  return -1;
    815936}
     937template <class number_type> int term_nodes_sort_crit(const void* a, const void* b){
     938  return -pLmCmp(((TermNoroDataNode<number_type>*) a)->t,((TermNoroDataNode<number_type>*) b)->t);
     939}
     940
    816941template <class number_type>class ModPMatrixBackSubstProxyOnArray;
    817942template <class number_type > class ModPMatrixProxyOnArray{
    … …  
    10441169    PrintS("StopGauss\n");
    10451170}
    1046 int term_nodes_sort_crit(const void* a, const void* b);
     1171//int term_nodes_sort_crit(const void* a, const void* b);
    10471172template <class number_type> void noro_step(poly*p,int &pn,slimgb_alg* c){
    10481173  //Print("Input rows %d\n",pn);
    … …  
    10521177  }
    10531178
    1054   NoroCache cache;
    1055 
    1056   SparseRow** srows=(SparseRow**) omalloc(pn*sizeof(SparseRow*));
     1179  NoroCache<number_type> cache;
     1180
     1181  SparseRow<number_type> ** srows=(SparseRow<number_type>**) omalloc(pn*sizeof(SparseRow<number_type>*));
    10571182  int non_zeros=0;
    10581183  for(j=0;j<pn;j++){
    … …  
    10671192    if (srows[non_zeros]!=NULL) non_zeros++;
    10681193  }
    1069   std::vector<DataNoroCacheNode*> irr_nodes;
     1194  std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
    10701195  cache.collectIrreducibleMonomials(irr_nodes);
    10711196  //now can build up terms array
    … …  
    10771202    Print("red Mon:%d\n",cache.nReducibleMonomials);
    10781203  }
    1079   TermNoroDataNode* term_nodes=(TermNoroDataNode*) omalloc(n*sizeof(TermNoroDataNode));
     1204  TermNoroDataNode<number_type>* term_nodes=(TermNoroDataNode<number_type>*) omalloc(n*sizeof(TermNoroDataNode<number_type>));
    10801205 
    10811206  for(j=0;j<n;j++){
    10821207    assume(irr_nodes[j]!=NULL);
    1083     assume(irr_nodes[j]->value_len==NoroCache::backLinkCode);
     1208    assume(irr_nodes[j]->value_len==NoroCache<number_type>::backLinkCode);
    10841209    term_nodes[j].t=irr_nodes[j]->value_poly;
    10851210    assume(term_nodes[j].t!=NULL);
    … …  
    10881213 
    10891214 
    1090   qsort(term_nodes,n,sizeof(TermNoroDataNode),term_nodes_sort_crit);
     1215  qsort(term_nodes,n,sizeof(TermNoroDataNode<number_type>),term_nodes_sort_crit<number_type>);
    10911216  poly* terms=(poly*) omalloc(n*sizeof(poly));
    10921217
    … …  
    11121237    }*/
    11131238
    1114     SparseRow* srow=srows[j];
     1239    SparseRow<number_type>* srow=srows[j];
    11151240    if (srow){
    11161241    for(i=0;i<srow->len;i++){
    … …  
    11441269 
    11451270}
    1146 #endif
    1147 
    1148 #endif
     1271
     1272template <class number_type> void NoroCache<number_type>::collectIrreducibleMonomials( std::vector<DataNoroCacheNode<number_type> *>& res){
     1273  int i;
     1274  for(i=0;i<root.branches_len;i++){
     1275    collectIrreducibleMonomials(1,root.branches[i],res);
     1276  }
     1277}
     1278template <class number_type> void NoroCache<number_type>::collectIrreducibleMonomials(int level, NoroCacheNode* node, std::vector<DataNoroCacheNode<number_type>*>& res){
     1279  assume(level>=0);
     1280  if (node==NULL) return;
     1281  if (level<pVariables){
     1282    int i,sum;
     1283    for(i=0;i<node->branches_len;i++){
     1284      collectIrreducibleMonomials(level+1,node->branches[i],res);
     1285    }
     1286  } else {
     1287    DataNoroCacheNode<number_type>* dn=(DataNoroCacheNode<number_type>*) node;
     1288    if (dn->value_len==backLinkCode){
     1289      res.push_back(dn);
     1290    }
     1291  }
     1292}
     1293
     1294template<class number_type> DataNoroCacheNode<number_type>* NoroCache<number_type>::getCacheReference(poly term){
     1295  int i;
     1296  NoroCacheNode* parent=&root;
     1297  for(i=1;i<pVariables;i++){
     1298    parent=parent->getBranch(p_GetExp(term,i,currRing));
     1299    if (!(parent)){
     1300      return NULL;
     1301    }
     1302  }
     1303  DataNoroCacheNode<number_type>* res_holder=(DataNoroCacheNode<number_type>*) parent->getBranch(p_GetExp(term,i,currRing));
     1304  return res_holder;
     1305}
     1306template<class number_type> poly NoroCache<number_type>::lookup(poly term, BOOLEAN& succ, int & len){
     1307  int i;
     1308  NoroCacheNode* parent=&root;
     1309  for(i=1;i<pVariables;i++){
     1310    parent=parent->getBranch(p_GetExp(term,i,currRing));
     1311    if (!(parent)){
     1312      succ=FALSE;
     1313      return NULL;
     1314    }
     1315  }
     1316  DataNoroCacheNode<number_type>* res_holder=(DataNoroCacheNode<number_type>*) parent->getBranch(p_GetExp(term,i,currRing));
     1317  if (res_holder){
     1318    succ=TRUE;
     1319    if ((res_holder->value_len==backLinkCode)){
     1320      len=1;
     1321      return term;
     1322    }
     1323    len=res_holder->value_len;
     1324    return res_holder->value_poly;
     1325  } else {
     1326    succ=FALSE;
     1327    return NULL;
     1328  }
     1329}
     1330#endif
     1331
     1332#endif
Note: See TracChangeset for help on using the changeset viewer.