Changeset f3b78d in git


Ignore:
Timestamp:
Feb 5, 2003, 6:01:48 PM (21 years ago)
Author:
Michael Brickenstein <bricken@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
07100c2bf0e9614230a892fda7b9192889d6f8e4
Parents:
d713d78830adcab82fa3ce5686817d1dbdbe140a
Message:
*bricken: extendend product criterion


git-svn-id: file:///usr/local/Singular/svn/trunk@6473 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • Singular/tgb.cc

    rd713d7 rf3b78d  
    55
    66#include "tgb.h"
    7 
    8 
    9 #define LEN_VAR3
     7#define OM_KEEP 0
     8#define LEN_VAR1
    109
    1110#ifdef LEN_VAR1
    … …  
    911910  poly hp;
    912911  int i,j;
     912  c->easy_product_crit=0;
     913  c->extended_product_crit=0;
    913914  c->is_char0=(rChar()==0);
    914915  c->reduction_steps=0;
    … …  
    954955  c->lengths=(int*) h;
    955956  h=omalloc(n*sizeof(int));
     957        c->gcd_of_terms=(poly*) omalloc(n*sizeof(poly));
    956958  c->rep=(int*) h;
    957959  c->short_Exps=(long*) omalloc(n*sizeof(long));
    … …  
    10011003   }
    10021004}
     1005//very important: ILM
    10031006
    10041007//len should be weighted length in char 0
    … …  
    10851088  c->lengths[i]=pLength(h);
    10861089  hp=omrealloc(c->states, c->n * sizeof(char*));
    1087   if (hp!=NULL){
     1090 
    10881091    c->states=(char**) hp;
    1089   } else {
    1090     exit(1);
    1091   }
     1092  c->gcd_of_terms=(poly*) omrealloc(c->gcd_of_terms, c->n *sizeof(poly));
     1093  c->gcd_of_terms[i]=gcd_of_terms(h,c->r);
    10921094  c->deg=(int**) omrealloc(c->deg, c->n * sizeof(int*));
    10931095  c->rep[i]=i;
    … …  
    11421144    if ((c->lengths[i]==1) && (c->lengths[j]==1))
    11431145      c->states[i][j]=HASTREP;
    1144     else if (pHasNotCF(c->S->m[i],c->S->m[j]))
     1146    else if (pHasNotCF(c->S->m[i],c->S->m[j])){
     1147      c->easy_product_crit++;
    11451148      c->states[i][j]=HASTREP;
     1149    }
     1150                        else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)){
     1151                                        c->states[i][j]=HASTREP;
     1152                                        c->extended_product_crit++;
     1153                                        //PrintS("E");
     1154                        }
    11461155    if (c->states[i][j]==UNCALCULATED){
    11471156//      sort_pair_in(i,j,c);
     1157     
    11481158      poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
    11491159      if (short_s)
    … …  
    13481358            {
    13491359              PrintS("e");
    1350               int dummy_len;
     1360              int dummy_len;
    13511361              kBucketClear(P.bucket,&sec_copy,&dummy_len);
    13521362              kBucketInit(P.bucket,pCopy(sec_copy),dummy_len
    1353                                                   /*pLength(sec_copy)*/);
     1363                                                  /*pLength(sec_copy)*/);
    13541364              must_expand=TRUE;
    13551365            }
    … …  
    13841394          len_upper_bound=new_length +strat->lenS[j]-2;//old entries length
    13851395          int new_pos;
    1386           if(c->is_char0)
    1387             new_pos=simple_posInS(c->strat,sec_copy,
    1388                                   pSLength(sec_copy,new_length),
    1389                                   c->is_char0);//hac
    1390           else
    1391             new_pos=simple_posInS(c->strat,sec_copy,new_length,c->is_char0);//hack
    1392           assume(new_pos<=j);
     1396          if(c->is_char0)
     1397            new_pos=simple_posInS(c->strat,sec_copy,
     1398                                  pSLength(sec_copy,new_length),
     1399                                  c->is_char0);//hac
     1400          else
     1401            new_pos=simple_posInS(c->strat,sec_copy,new_length,c->is_char0);//hack
     1402          assume(new_pos<=j);
    13931403//          p=NULL;
    13941404          for (z=c->n;z;z--)
    … …  
    14301440
    14311441              c->strat->lenS[old_pos]=new_length;
    1432               if(c->strat->lenSw)
    1433                 c->strat->lenS[old_pos]=pSLength(sec_copy,new_length);
     1442              if(c->strat->lenSw)
     1443                c->strat->lenS[old_pos]=pSLength(sec_copy,new_length);
    14341444              int i=0;
    14351445              for(i=new_pos;i<old_pos;i++){
    … …  
    15021512}
    15031513
    1504 
     1514static void line_of_extended_prod(int fixpos,calc_dat* c){
     1515    if (c->gcd_of_terms[fixpos]==NULL)
     1516  {
     1517    c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r);
     1518    if (c->gcd_of_terms[fixpos])
     1519    {
     1520      int i;
     1521      for(i=0;i<fixpos;i++)
     1522        if((c->states[fixpos][i]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c)))
     1523{
     1524          c->states[fixpos][i]=HASTREP;
     1525          c->extended_product_crit++;
     1526}     
     1527      for(i=fixpos+1;i<c->n;i++)
     1528        if((c->states[i][fixpos]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c)))
     1529        {        c->states[i][fixpos]=HASTREP;
     1530        c->extended_product_crit++;
     1531        }
     1532    }
     1533  }
     1534}
     1535static void c_S_element_changed_hook(int pos, calc_dat* c){
     1536  length_one_crit(c,pos, c->lengths[pos]);
     1537  line_of_extended_prod(pos,c);
     1538}
    15051539
    15061540static BOOLEAN redNF2_n_steps (redNF_inf* obj,calc_dat* c, int n)
    … …  
    15151549  int j;
    15161550  kStrategy strat=c->strat;
    1517   assume(strat->sl<50000);
     1551
    15181552  if (0 > strat->sl)
    15191553  {
    … …  
    15451579      {
    15461580        poly sec_copy=NULL;
    1547         if (c->is_char0) wlen_upper=kSBucketLength(obj->P->bucket);
     1581        if (c->is_char0) wlen_upper=kSBucketLength(obj->P->bucket);
    15481582        BOOLEAN must_expand=FALSE;
    15491583        BOOLEAN must_replace_in_basis;
    1550         if(c->is_char0)
    1551           must_replace_in_basis=(wlen_upper<strat->lenSw[j]);//first test
    1552         else
    1553           must_replace_in_basis=(obj->len_upper_bound<strat->lenS[j]);//first test
     1584        if(c->is_char0)
     1585          must_replace_in_basis=(wlen_upper<strat->lenSw[j]);//first test
     1586        else
     1587          must_replace_in_basis=(obj->len_upper_bound<strat->lenS[j]);//first test
    15541588        if (must_replace_in_basis)
    15551589        {
    … …  
    15571591          if (pLmEqual(obj->P->p,strat->S[j]))
    15581592          {
    1559             int dummy_len;
     1593            int dummy_len;
    15601594            PrintS("b");
    15611595            kBucketClear(obj->P->bucket,&sec_copy,&dummy_len);
    15621596            kBucketInit(obj->P->bucket,pCopy(sec_copy),dummy_len
    1563                                                          /*pLength(sec_copy)*/);
     1597                                                         /*pLength(sec_copy)*/);
    15641598          }
    15651599          else
    … …  
    15691603                ||(obj->len_upper_bound==2)
    15701604                ||(obj->len_upper_bound<strat->lenS[j]/2)
    1571                 ||
    1572                 (c->is_char0 && (wlen_upper<strat->lenSw[j]/100))
     1605                ||
     1606                (c->is_char0 && (wlen_upper<strat->lenSw[j]/100))
    15731607)
    15741608            {
    1575               int dummy_len;
     1609              int dummy_len;
    15761610              PrintS("e");
    15771611              kBucketClear(obj->P->bucket,&sec_copy,&dummy_len);
    15781612              kBucketInit(obj->P->bucket,pCopy(sec_copy),dummy_len
    1579                                                          /*pLength(sec_copy)*/);
     1613                                                         /*pLength(sec_copy)*/);
    15801614              must_expand=TRUE;
    15811615            }
    … …  
    15931627        }
    15941628#endif
     1629        if ((!must_replace_in_basis) && (pLmEqual(obj->P->p,c->strat->S[j]))){
     1630          obj->need_std_rep=TRUE;
     1631          int is;
     1632          for(is=0;is<c->n;is++)
     1633            if(c->S->m[is]==c->strat->S[j])
     1634              break;
     1635          if (is!=c->n){
     1636            if (c->gcd_of_terms[is]==NULL) {
     1637              poly m=kBucketGcd(obj->P->bucket,c->r);
     1638              if (m!=NULL){
     1639              pDelete(&m);
     1640              kBucketCanonicalize(obj->P->bucket);
     1641              m=kBucketGcd(obj->P->bucket,c->r);
     1642              c->gcd_of_terms[is]=m;
     1643              line_of_extended_prod(is,c);
     1644              PrintS("C");
     1645              }
     1646             
     1647            }
     1648          }
     1649        }
     1650
    15951651        obj->len_upper_bound=obj->len_upper_bound+strat->lenS[j]-2;
    15961652        number coef=kBucketPolyRed(obj->P->bucket,strat->S[j],
    … …  
    15991655        nDelete(&coef);
    16001656        h = kBucketGetLm(obj->P->bucket);
    1601 
     1657                   
     1658     
    16021659        if (must_replace_in_basis){
    16031660          obj->need_std_rep=TRUE;
    … …  
    16101667          obj->len_upper_bound=new_length +strat->lenS[j]-2;//old entries length
    16111668
    1612                     int new_pos;
    1613           if(c->is_char0)
    1614             new_pos=simple_posInS(c->strat,sec_copy,
    1615                                   pSLength(sec_copy,new_length),
    1616                                   c->is_char0);//hac
    1617           else
    1618             new_pos=simple_posInS(c->strat,sec_copy,new_length,c->is_char0);//hack
     1669                    int new_pos;
     1670          if(c->is_char0)
     1671            new_pos=simple_posInS(c->strat,sec_copy,
     1672                                  pSLength(sec_copy,new_length),
     1673                                  c->is_char0);//hac
     1674          else
     1675            new_pos=simple_posInS(c->strat,sec_copy,new_length,c->is_char0);//hack
    16191676//          p=NULL;
    1620           assume(new_pos<=j);
     1677          assume(new_pos<=j);
    16211678          for (z=c->n;z;z--)
    16221679          {
    … …  
    16321689            deleteInS(j,c->strat);
    16331690            add_to_reductors(c,sec_copy,pLength(sec_copy));
    1634             pDelete(&p);
     1691            pDelete(&p);
    16351692          }
    16361693          else {
    … …  
    16471704              assume(new_pos<=old_pos);
    16481705              c->strat->lenS[old_pos]=new_length;
    1649               if(c->strat->lenSw)
    1650                 c->strat->lenS[old_pos]=pSLength(sec_copy,new_length);
     1706              if(c->strat->lenSw)
     1707                c->strat->lenS[old_pos]=pSLength(sec_copy,new_length);
    16511708              int i=0;
    16521709              for(i=new_pos;i<old_pos;i++){
    … …  
    16561713                  break;
    16571714              }
    1658               assume(new_pos<=old_pos);
     1715              assume(new_pos<=old_pos);
    16591716              if (new_pos<old_pos)
    16601717                move_forward_in_S(old_pos,new_pos,c->strat,c->is_char0);
    1661               assume(0<=pos_in_c);
    1662               assume(c->n>pos_in_c);
     1718              assume(0<=pos_in_c);
     1719              assume(c->n>pos_in_c);
    16631720              c->S->m[pos_in_c]=sec_copy;
    16641721
    16651722              c->lengths[pos_in_c]=new_length;
    1666               length_one_crit(c,pos_in_c, new_length);
     1723              c_S_element_changed_hook(pos_in_c,c);
     1724             
    16671725
    16681726            }
    … …  
    20072065          {
    20082066            c->misses_series=0;
    2009             if(c->is_char0)
    2010               pContent(hr);
     2067            if(c->is_char0)
     2068              pContent(hr);
    20112069#ifdef HEAD_BIN
    20122070            hr=p_MoveHead(hr,c->HeadBin);
    20132071#endif
    2014            
     2072           
    20152073            add_to_basis(hr, c->work_on[i].i,c->work_on[i].j,c);
    20162074
    … …  
    21172175  omfree(c->lengths);
    21182176  printf("calculated %d NFs\n",c->normal_forms);
     2177  printf("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit);
    21192178  I=c->S;
    21202179  IDELEMS(I)=c->n;
    … …  
    22202279      int new_pos;
    22212280      if (c->is_char0)
    2222         simple_posInS(c->strat,c->S->m[i],pSLength(c->S->m[i],c->lengths[i]),c->is_char0);
    2223       else     
    2224         simple_posInS(c->strat,c->S->m[i],c->lengths[i],c->is_char0);
     2281        simple_posInS(c->strat,c->S->m[i],pSLength(c->S->m[i],c->lengths[i]),c->is_char0);
     2282      else     
     2283        simple_posInS(c->strat,c->S->m[i],c->lengths[i],c->is_char0);
    22252284      int old_pos=-1;
    22262285      //assume new_pos<old_pos
    … …  
    22472306      c->strat->lenS[old_pos]=c->lengths[i];
    22482307      if (c->strat->lenSw)
    2249         c->strat->lenSw[old_pos]=pSLength(c->S->m[i],c->lengths[i]);
     2308        c->strat->lenSw[old_pos]=pSLength(c->S->m[i],c->lengths[i]);
    22502309
    22512310      if (new_pos<old_pos)
    … …  
    23632422  }
    23642423}
     2424poly gcd_of_terms(poly p, ring r){
     2425  int max_g_0=0;
     2426  assume(p!=NULL);
     2427  int i;
     2428  poly m=pOne();
     2429  poly t;
     2430  for (i=pVariables; i; i--)
     2431  {
     2432      pSetExp(m,i, pGetExp(p,i));
     2433      if (max_g_0==0)
     2434        if (pGetExp(m,i)>0)
     2435          max_g_0=i;
     2436  }
     2437 
     2438  t=p->next;
     2439  while (t!=NULL){
     2440   
     2441    if (max_g_0==0) break;
     2442    for (i=pVariables; i; i--)
     2443    {
     2444      pSetExp(m,i, min(pGetExp(t,i),pGetExp(m,i)));
     2445      if (max_g_0==i)
     2446        if (pGetExp(m,i)==0)
     2447          max_g_0=0;
     2448      if ((max_g_0==0) && (pGetExp(m,i)>0)){
     2449        max_g_0=i;
     2450      }
     2451    }
     2452                t=t->next;
     2453  }
     2454        for (i=pVariables;i;i--)
     2455        {
     2456                if(pGetExp(m,i)>0)
     2457                        return m;
     2458  }
     2459        pDelete(&m);
     2460  return NULL;
     2461}
     2462BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m)
     2463{
     2464
     2465  if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
     2466    return FALSE;
     2467  int i = 1;
     2468  loop
     2469  {
     2470    if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0))   return FALSE;
     2471    if (i == pVariables)                                return TRUE;
     2472    i++;
     2473  }
     2474}
     2475
     2476
     2477//for impl reasons may return false if the the normal product criterion matches
     2478BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c){
     2479  if(gcd1==NULL) return FALSE;
     2480        if(gcd2==NULL) return FALSE;
     2481        gcd1->next=gcd2; //may ordered incorrect
     2482        poly m=gcd_of_terms(gcd1,c->r);
     2483        gcd1->next=NULL;
     2484        if (m==NULL) return FALSE;
     2485
     2486        BOOLEAN erg=pHasNotCFExtended(p1,p2,m);
     2487        pDelete(&m);
     2488        return erg;
     2489}
     2490static poly kBucketGcd(kBucket* b, ring r)
     2491{
     2492  int s=0;
     2493  int i;
     2494  poly m, n;
     2495  BOOLEAN initialized=FALSE;
     2496  for (i=MAX_BUCKET-1;i>=0;i--)
     2497  {
     2498    if (b->buckets[i]!=NULL){
     2499      if (!initialized){
     2500        m=gcd_of_terms(b->buckets[i],r);
     2501        initialized=TRUE;
     2502        if (m==NULL) return NULL;
     2503      }
     2504      else
     2505        {
     2506          n=gcd_of_terms(b->buckets[i],r);
     2507          if (n==NULL) {
     2508            pDelete(&m);
     2509            return NULL;   
     2510          }
     2511          n->next=m;
     2512          poly t=gcd_of_terms(n,r);
     2513          n->next=NULL;
     2514          pDelete(&m);
     2515          pDelete(&n);
     2516          m=t;
     2517          if (m==NULL) return NULL;
     2518         
     2519        }
     2520    }
     2521  }
     2522  return m;
     2523}

  • Singular/tgb.h

    rd713d7 rf3b78d  
    7676  int* T_deg;
    7777  int* misses;
     78        poly* gcd_of_terms;
    7879  int_pair_node* soon_free;
    7980  sorted_pair_node* pairs;
    … …  
    100101  int max_pairs;
    101102  int pair_top;
     103  int easy_product_crit;
     104  int extended_product_crit;
    102105  BOOLEAN is_char0;
    103106};
    … …  
    128131static int pair_better_gen(const void* ap,const void* bp);
    129132static poly redTailShort(poly h, kStrategy strat);
     133poly gcd_of_terms(poly p, ring r);
     134BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c);
     135static poly kBucketGcd(kBucket* b, ring r);
    130136#endif
Note: See TracChangeset for help on using the changeset viewer.