Changeset 052af1 in git


Ignore:
Timestamp:
Sep 29, 2016, 12:08:34 PM (8 years ago)
Author:
Andreas Steenpass <steenpass@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b4f17ed1d25f93d46dbe29e4b499baecc2fd51bb')
Children:
781011ad928c92d557a10b3cd56d83c3b0a0277b
Parents:
d3f9bb894c684ed67a0c0c6ab1ece2e380413a24
git-author:
Andreas Steenpass <steenpass@mathematik.uni-kl.de>2016-09-29 12:08:34+02:00
git-committer:
Andreas Steenpass <steenpass@mathematik.uni-kl.de>2017-12-15 12:17:07+01:00
Message:
chg: move some functions
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/GBEngine/syz4.cc

    rd3f9bb8 r052af1  
    1414#include <vector>
    1515#include <map>
    16 
    17 typedef struct {
    18     poly lt;
    19     unsigned long sev;
    20     unsigned int comp;
    21 } lt_struct;
    22 
    23 typedef std::vector<lt_struct> lts_vector;
    24 typedef std::map<long, lts_vector> lts_hash;
    25 
    26 static void initialize_lts_hash(lts_hash &C, const ideal L)
    27 {
    28     const ring R = currRing;
    29     const unsigned int n_elems = IDELEMS(L);
    30     for (unsigned int k = 0; k < n_elems; k++) {
    31         const poly a = L->m[k];
    32         C[p_GetComp(a, R)].push_back({a, p_GetShortExpVector(a, R), k});
    33     }
    34 }
    35 
    36 #define delete_lts_hash(C) C->clear()
    37 
    38 bool is_divisible(const lts_hash *C, const poly p)
    39 {
    40     const ring R = currRing;
    41     lts_hash::const_iterator itr = C->find(p_GetComp(p, R));
    42     if (itr == C->end()) {
    43         return false;
    44     }
    45     lts_vector::const_iterator v_current = itr->second.begin();
    46     lts_vector::const_iterator v_finish  = itr->second.end();
    47     const unsigned long not_sev = ~p_GetShortExpVector(p, R);
    48     for ( ; v_current != v_finish; ++v_current) {
    49         if (p_LmShortDivisibleByNoComp(v_current->lt, v_current->sev,
    50                 p, not_sev, R)) {
    51             return true;
    52         }
    53     }
    54     return false;
    55 }
    56 
    57 static poly TraverseTail_test(poly multiplier, const int tail,
    58    const ideal previous_module, const std::vector<bool> &variables,
    59    const lts_hash *m_div, const lts_hash *m_checker);
    60 static poly ComputeImage_test(poly multiplier, const int tail,
    61     const ideal previous_module, const std::vector<bool> &variables,
    62     const lts_hash *m_div, const lts_hash *m_checker);
    63 static inline poly ReduceTerm_test(poly multiplier, poly term4reduction,
    64     poly syztermCheck, const ideal previous_module,
    65     const std::vector<bool> &variables, const lts_hash *m_div,
    66     const lts_hash *m_checker);
    67 static poly leadmonom_test(const poly p, const ring r, const bool bSetZeroComp = true);
    6816
    6917static inline void update_variables(std::vector<bool> &variables,
    … …  
    9947}
    10048
    101 static poly TraverseNF_test(const poly a, const ideal previous_module,
     49typedef struct {
     50    poly lt;
     51    unsigned long sev;
     52    unsigned int comp;
     53} lt_struct;
     54
     55typedef std::vector<lt_struct> lts_vector;
     56typedef std::map<long, lts_vector> lts_hash;
     57
     58static void initialize_lts_hash(lts_hash &C, const ideal L)
     59{
     60    const ring R = currRing;
     61    const unsigned int n_elems = IDELEMS(L);
     62    for (unsigned int k = 0; k < n_elems; k++) {
     63        const poly a = L->m[k];
     64        C[p_GetComp(a, R)].push_back({a, p_GetShortExpVector(a, R), k});
     65    }
     66}
     67
     68#define delete_lts_hash(C) C->clear()
     69
     70bool is_divisible(const lts_hash *C, const poly p)
     71{
     72    const ring R = currRing;
     73    lts_hash::const_iterator itr = C->find(p_GetComp(p, R));
     74    if (itr == C->end()) {
     75        return false;
     76    }
     77    lts_vector::const_iterator v_current = itr->second.begin();
     78    lts_vector::const_iterator v_finish  = itr->second.end();
     79    const unsigned long not_sev = ~p_GetShortExpVector(p, R);
     80    for ( ; v_current != v_finish; ++v_current) {
     81        if (p_LmShortDivisibleByNoComp(v_current->lt, v_current->sev,
     82                p, not_sev, R)) {
     83            return true;
     84        }
     85    }
     86    return false;
     87}
     88
     89static poly leadmonom_test(const poly p, const ring r,
     90    const bool bSetZeroComp = true)
     91{
     92  poly m = p_LmInit(p, r);
     93  p_SetCoeff0(m, n_Copy(p_GetCoeff(p, r), r), r);
     94  if( bSetZeroComp )
     95    p_SetComp(m, 0, r);
     96  p_Setm(m, r);
     97  return m;
     98}
     99
     100// _p_LmDivisibleByNoComp for a | b*c
     101static inline BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
     102{
     103  int i=r->VarL_Size - 1;
     104  unsigned long divmask = r->divmask;
     105  unsigned long la, lb;
     106
     107  if (r->VarL_LowIndex >= 0)
     108  {
     109    i += r->VarL_LowIndex;
     110    do
     111    {
     112      la = a->exp[i];
     113      lb = b->exp[i] + c->exp[i];
     114      if ((la > lb) ||
     115          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
     116      {
     117        return FALSE;
     118      }
     119      i--;
     120    }
     121    while (i>=r->VarL_LowIndex);
     122  }
     123  else
     124  {
     125    do
     126    {
     127      la = a->exp[r->VarL_Offset[i]];
     128      lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
     129      if ((la > lb) ||
     130          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
     131      {
     132        return FALSE;
     133      }
     134      i--;
     135    }
     136    while (i>=0);
     137  }
     138  return TRUE;
     139}
     140
     141poly FindReducer(const poly multiplier, const poly t, const poly syzterm,
     142    const lts_hash *syz_checker, const lts_hash *m_div)
     143{
     144  const ring r = currRing;
     145  lts_hash::const_iterator m_itr = m_div->find(p_GetComp(t, currRing));
     146  if (m_itr == m_div->end()) {
     147    return NULL;
     148  }
     149  lts_vector::const_iterator m_current = (m_itr->second).begin();
     150  lts_vector::const_iterator m_finish  = (m_itr->second).end();
     151  if (m_current == m_finish) {
     152    return NULL;
     153  }
     154  const poly q = p_New(r);
     155  pNext(q) = NULL;
     156  const unsigned long m_not_sev = ~p_GetShortExpVector(multiplier, t, r);
     157  for( ; m_current != m_finish; ++m_current) {
     158    if ( (m_current->sev & m_not_sev)
     159        || !(_p_LmDivisibleByNoComp(m_current->lt, multiplier, t, r))) {
     160      continue;
     161    }
     162    const poly p = m_current->lt;
     163    const int k  = m_current->comp;
     164    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t
     165    p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
     166    p_SetComp(q, k + 1, r);
     167    p_Setm(q, r);
     168    // cannot allow something like: a*gen(i) - a*gen(i)
     169    if (syzterm != NULL && (k == p_GetComp(syzterm, r) - 1)
     170        && p_ExpVectorEqual(syzterm, q, r)) {
     171      continue;
     172    }
     173    if (is_divisible(syz_checker, q)) {
     174      continue;
     175    }
     176    number n = n_Mult(p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
     177    p_SetCoeff0(q, n_InpNeg(n, r), r);
     178    return q;
     179  }
     180  p_LmFree(q, r);
     181  return NULL;
     182}
     183
     184static poly TraverseTail_test(poly multiplier, const int tail,
     185   const ideal previous_module, const std::vector<bool> &variables,
     186   const lts_hash *m_div, const lts_hash *m_checker);
     187
     188static inline poly ReduceTerm_test(poly multiplier, poly term4reduction,
     189    poly syztermCheck, const ideal previous_module,
    102190    const std::vector<bool> &variables, const lts_hash *m_div,
    103191    const lts_hash *m_checker)
    104192{
    105   const ring R = currRing;
    106   const int r = p_GetComp(a, R) - 1;
    107   poly aa = leadmonom_test(a, R);
    108   poly t = TraverseTail_test(aa, r, previous_module, variables, m_div,
    109       m_checker);
    110   if (check_variables(variables, aa)) {
    111     t = p_Add_q(t, ReduceTerm_test(aa, previous_module->m[r], a,
    112         previous_module, variables, m_div, m_checker), R);
    113   }
    114   p_Delete(&aa, R);
    115   return t;
     193  const ring r = currRing;
     194  poly s = FindReducer(multiplier, term4reduction, syztermCheck, m_checker,
     195        m_div);
     196  if( s == NULL )
     197  {
     198    return NULL;
     199  }
     200  poly b = leadmonom_test(s, r);
     201  const int c = p_GetComp(s, r) - 1;
     202  const poly t
     203      = TraverseTail_test(b, c, previous_module, variables, m_div, m_checker);
     204  pDelete(&b);
     205  if( t != NULL )
     206    s = p_Add_q(s, t, r);
     207  return s;
     208}
     209
     210static poly ComputeImage_test(poly multiplier, const int t,
     211    const ideal previous_module, const std::vector<bool> &variables,
     212    const lts_hash *m_div, const lts_hash *m_checker)
     213{
     214  const poly tail = previous_module->m[t]->next;
     215  if(tail != NULL)
     216  {
     217    if (!check_variables(variables, multiplier))
     218    {
     219      return NULL;
     220    }
     221    sBucket_pt sum = sBucketCreate(currRing);
     222    for(poly p = tail; p != NULL; p = pNext(p))   // iterate over the tail
     223    {
     224      const poly rt = ReduceTerm_test(multiplier, p, NULL, previous_module,
     225          variables, m_div, m_checker);
     226      sBucket_Add_p(sum, rt, pLength(rt));
     227    }
     228    poly s;
     229    int l;
     230    sBucketClearAdd(sum, &s, &l);
     231    sBucketDestroy(&sum);
     232    return s;
     233  }
     234  return NULL;
    116235}
    117236
    … …  
    240359}
    241360
    242 static poly ComputeImage_test(poly multiplier, const int t,
    243     const ideal previous_module, const std::vector<bool> &variables,
    244     const lts_hash *m_div, const lts_hash *m_checker)
    245 {
    246   const poly tail = previous_module->m[t]->next;
    247   if(tail != NULL)
    248   {
    249     if (!check_variables(variables, multiplier))
    250     {
    251       return NULL;
    252     }
    253     sBucket_pt sum = sBucketCreate(currRing);
    254     for(poly p = tail; p != NULL; p = pNext(p))   // iterate over the tail
    255     {
    256       const poly rt = ReduceTerm_test(multiplier, p, NULL, previous_module,
    257           variables, m_div, m_checker);
    258       sBucket_Add_p(sum, rt, pLength(rt));
    259     }
    260     poly s;
    261     int l;
    262     sBucketClearAdd(sum, &s, &l);
    263     sBucketDestroy(&sum);
    264     return s;
    265   }
    266   return NULL;
    267 }
    268 
    269 static poly leadmonom_test(const poly p, const ring r, const bool bSetZeroComp)
    270 {
    271   poly m = p_LmInit(p, r);
    272   p_SetCoeff0(m, n_Copy(p_GetCoeff(p, r), r), r);
    273   if( bSetZeroComp )
    274     p_SetComp(m, 0, r);
    275   p_Setm(m, r);
    276   return m;
    277 }
    278 
    279 // _p_LmDivisibleByNoComp for a | b*c
    280 static inline BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
    281 {
    282   int i=r->VarL_Size - 1;
    283   unsigned long divmask = r->divmask;
    284   unsigned long la, lb;
    285 
    286   if (r->VarL_LowIndex >= 0)
    287   {
    288     i += r->VarL_LowIndex;
    289     do
    290     {
    291       la = a->exp[i];
    292       lb = b->exp[i] + c->exp[i];
    293       if ((la > lb) ||
    294           (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
    295       {
    296         return FALSE;
    297       }
    298       i--;
    299     }
    300     while (i>=r->VarL_LowIndex);
    301   }
    302   else
    303   {
    304     do
    305     {
    306       la = a->exp[r->VarL_Offset[i]];
    307       lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
    308       if ((la > lb) ||
    309           (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
    310       {
    311         return FALSE;
    312       }
    313       i--;
    314     }
    315     while (i>=0);
    316   }
    317   return TRUE;
    318 }
    319 
    320 poly FindReducer(const poly multiplier, const poly t, const poly syzterm,
    321     const lts_hash *syz_checker, const lts_hash *m_div)
    322 {
    323   const ring r = currRing;
    324   lts_hash::const_iterator m_itr = m_div->find(p_GetComp(t, currRing));
    325   if (m_itr == m_div->end()) {
    326     return NULL;
    327   }
    328   lts_vector::const_iterator m_current = (m_itr->second).begin();
    329   lts_vector::const_iterator m_finish  = (m_itr->second).end();
    330   if (m_current == m_finish) {
    331     return NULL;
    332   }
    333   const poly q = p_New(r);
    334   pNext(q) = NULL;
    335   const unsigned long m_not_sev = ~p_GetShortExpVector(multiplier, t, r);
    336   for( ; m_current != m_finish; ++m_current) {
    337     if ( (m_current->sev & m_not_sev)
    338         || !(_p_LmDivisibleByNoComp(m_current->lt, multiplier, t, r))) {
    339       continue;
    340     }
    341     const poly p = m_current->lt;
    342     const int k  = m_current->comp;
    343     p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t
    344     p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
    345     p_SetComp(q, k + 1, r);
    346     p_Setm(q, r);
    347     // cannot allow something like: a*gen(i) - a*gen(i)
    348     if (syzterm != NULL && (k == p_GetComp(syzterm, r) - 1)
    349         && p_ExpVectorEqual(syzterm, q, r)) {
    350       continue;
    351     }
    352     if (is_divisible(syz_checker, q)) {
    353       continue;
    354     }
    355     number n = n_Mult(p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
    356     p_SetCoeff0(q, n_InpNeg(n, r), r);
    357     return q;
    358   }
    359   p_LmFree(q, r);
    360   return NULL;
    361 }
    362 
    363 static inline poly ReduceTerm_test(poly multiplier, poly term4reduction,
    364     poly syztermCheck, const ideal previous_module,
     361static poly TraverseNF_test(const poly a, const ideal previous_module,
    365362    const std::vector<bool> &variables, const lts_hash *m_div,
    366363    const lts_hash *m_checker)
    367364{
    368   const ring r = currRing;
    369   poly s = FindReducer(multiplier, term4reduction, syztermCheck, m_checker,
    370         m_div);
    371   if( s == NULL )
    372   {
    373     return NULL;
    374   }
    375   poly b = leadmonom_test(s, r);
    376   const int c = p_GetComp(s, r) - 1;
    377   const poly t
    378       = TraverseTail_test(b, c, previous_module, variables, m_div, m_checker);
    379   pDelete(&b);
    380   if( t != NULL )
    381     s = p_Add_q(s, t, r);
    382   return s;
     365  const ring R = currRing;
     366  const int r = p_GetComp(a, R) - 1;
     367  poly aa = leadmonom_test(a, R);
     368  poly t = TraverseTail_test(aa, r, previous_module, variables, m_div,
     369      m_checker);
     370  if (check_variables(variables, aa)) {
     371    t = p_Add_q(t, ReduceTerm_test(aa, previous_module->m[r], a,
     372        previous_module, variables, m_div, m_checker), R);
     373  }
     374  p_Delete(&aa, R);
     375  return t;
    383376}
    384377
Note: See TracChangeset for help on using the changeset viewer.