slimgb_alg Class Reference

#include <tgb_internal.h>

Public Member Functions
	slimgb_alg (ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
void	introduceDelayedPairs (poly *pa, int s)
virtual	~slimgb_alg ()
void	cleanDegs (int lower, int upper)
unsigned long	pTotaldegree (poly p)
int	pTotaldegree_full (poly p)

Data Fields
char **	states
ideal	add_later
ideal	S
ring	r
int *	lengths
wlen_type *	weighted_lengths
long *	short_Exps
kStrategy	strat
int *	T_deg
int *	T_deg_full
poly	tmp_lm
poly *	tmp_pair_lm
sorted_pair_node **	tmp_spn
poly *	expandS
poly *	gcd_of_terms
int_pair_node *	soon_free
sorted_pair_node **	apairs
poly_list_node *	to_destroy
mp_array_list *	F
poly_array_list *	F_minus
unsigned int	reduction_steps
int	n
int	syz_comp
	array_lengths should be greater equal n; More...
int	array_lengths
int	normal_forms
int	current_degree
int	Rcounter
int	last_index
int	max_pairs
int	pair_top
int	easy_product_crit
int	extended_product_crit
int	average_length
int	lastDpBlockStart
int	lastCleanedDeg
int	deg_pos
BOOLEAN	use_noro
BOOLEAN	use_noro_last_block
BOOLEAN	isDifficultField
BOOLEAN	completed
BOOLEAN	is_homog
BOOLEAN	tailReductions
BOOLEAN	eliminationProblem
BOOLEAN	F4_mode
BOOLEAN	nc

Detailed Description

Definition at line 198 of file tgb_internal.h.

Constructor & Destructor Documentation

slimgb_alg()

slimgb_alg::slimgb_alg	(	ideal	I,
		int	syz_comp,
		BOOLEAN	F4,
		int	deg_pos
	)

Definition at line 3192 of file tgb.cc.

{
  this->deg_pos = deg_pos;
  lastCleanedDeg = -1;
  completed = FALSE;
  this->syz_comp = syz_comp;
  r = currRing;
  nc = rIsPluralRing (r);
  this->lastDpBlockStart = get_last_dp_block_start (r);
  //Print("last dp Block start: %i\n", this->lastDpBlockStart);
  is_homog = TRUE;
  {
    int hzz;
    for(hzz = 0; hzz < IDELEMS (I); hzz++)
    {
      assume (I->m[hzz] != NULL);
      int d = this->pTotaldegree (I->m[hzz]);
      poly t = I->m[hzz]->next;
      while(t)
      {
        if(d != (int)this->pTotaldegree (t))
        {
          is_homog = FALSE;
          break;
        }
        t = t->next;
      }
      if(!(is_homog))
        break;
    }
  }
  eliminationProblem = ((!(is_homog)) && ((currRing->pLexOrder) || (I->rank > 1)));
  tailReductions = ((is_homog) || ((TEST_OPT_REDTAIL) && (!(I->rank > 1))));
  //  Print("is homog:%d",c->is_homog);
  void *h;
  int i;
  to_destroy = NULL;
  easy_product_crit = 0;
  extended_product_crit = 0;
  if(rField_is_Zp (r))
    isDifficultField = FALSE;
  else
    isDifficultField = TRUE;
  //not fully correct
  //(rChar()==0);
  F4_mode = F4;
 
  reduction_steps = 0;
  last_index = -1;
 
  F = NULL;
  F_minus = NULL;
 
  Rcounter = 0;
 
  soon_free = NULL;
 
  tmp_lm = pOne ();
 
  normal_forms = 0;
  current_degree = 1;
 
  max_pairs = 5 * IDELEMS (I);
 
  apairs =
    (sorted_pair_node **) omAlloc (sizeof (sorted_pair_node *) * max_pairs);
  pair_top = -1;
 
  int n = IDELEMS (I);
  array_lengths = n;
 
 
  i = 0;
  this->n = 0;
  T_deg = (int *) omAlloc (n * sizeof (int));
  if(eliminationProblem)
    T_deg_full = (int *) omAlloc (n * sizeof (int));
  else
    T_deg_full = NULL;
  tmp_pair_lm = (poly *) omAlloc (n * sizeof (poly));
  tmp_spn = (sorted_pair_node **) omAlloc (n * sizeof (sorted_pair_node *));
  lm_bin = omGetSpecBin (POLYSIZE + (r->ExpL_Size) * sizeof (long));
  /* omUnGetSpecBin(&(c->HeadBin)); */
#ifndef HAVE_BOOST
#ifdef USE_STDVECBOOL
#else
  h = omAlloc (n * sizeof (char *));
 
  states = (char **) h;
#endif
#endif
  h = omAlloc (n * sizeof (int));
  lengths = (int *) h;
  weighted_lengths = (wlen_type *) omAllocAligned (n * sizeof (wlen_type));
  gcd_of_terms = (poly *) omAlloc (n * sizeof (poly));
 
  short_Exps = (long *) omAlloc (n * sizeof (long));
  if(F4_mode)
    S = idInit (n, I->rank);
  else
    S = idInit (1, I->rank);
  strat = new skStrategy;
  if(eliminationProblem)
    strat->honey = TRUE;
  strat->syzComp = syz_comp;
  initBuchMoraCrit (strat);
  initBuchMoraPos (strat);
  strat->initEcart = initEcartBBA;
  strat->tailRing = r;
  strat->enterS = enterSBba;
  strat->sl = -1;
  i = n;
  i = 1;                        //some strange bug else
  /* initS(c->S,NULL,c->strat); */
  /* intS start: */
  // i=((i+IDELEMS(c->S)+15)/16)*16;
  strat->ecartS = (intset) omAlloc (i * sizeof (int));  /*initec(i); */
  strat->sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long));
  /*initsevS(i); */
  strat->S_2_R = (int *) omAlloc0 (i * sizeof (int));   /*initS_2_R(i); */
  strat->fromQ = NULL;
  strat->Shdl = idInit (1, 1);
  strat->S = strat->Shdl->m;
  strat->lenS = (int *) omAlloc0 (i * sizeof (int));
  if((isDifficultField) || (eliminationProblem))
    strat->lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type));
  else
    strat->lenSw = NULL;
  assume (n > 0);
  add_to_basis_ideal_quotient (I->m[0], this, NULL);
 
  assume (strat->sl == IDELEMS (strat->Shdl) - 1);
  if(!(F4_mode))
  {
    poly *array_arg = I->m;
    array_arg++;
    introduceDelayedPairs (array_arg, n - 1);
    /*
       for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
       {
       //     add_to_basis(I->m[i],-1,-1,c);
       si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
       si->i=-1;
       si->j=-2;
       si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
       si->deg=pTotaldegree(I->m[i]);
       if (!rField_is_Zp(r))
       {
       p_Cleardenom(I->m[i], r);
       }
       si->lcm_of_lm=I->m[i];
 
       //      c->apairs[n-1-i]=si;
       apairs[n-i-1]=si;
       ++(pair_top);
       } */
  }
  else
  {
    for(i = 1; i < n; i++)      //the 1 is wanted, because first element is added to basis
      add_to_basis_ideal_quotient (I->m[i], this, NULL);
  }
  for(i = 0; i < IDELEMS (I); i++)
  {
    I->m[i] = NULL;
  }
  idDelete (&I);
  add_later = idInit (ADD_LATER_SIZE, S->rank);
#ifdef USE_NORO
  use_noro = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
              && (!(eliminationProblem)) && (n_GetChar(currRing->cf) <= NV_MAX_PRIME));
  use_noro_last_block = false;
  if((!(use_noro)) && (lastDpBlockStart <= (currRing->N)))
  {
    use_noro_last_block = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
                           && (n_GetChar(currRing->cf) <= NV_MAX_PRIME));
  }
#else
  use_noro = false;
  use_noro_last_block = false;
#endif
  //Print("NORO last block %i",use_noro_last_block);
  memset (add_later->m, 0, ADD_LATER_SIZE * sizeof (poly));
}

~slimgb_alg()

slimgb_alg::~slimgb_alg ( )

virtual

Definition at line 3377 of file tgb.cc.

{
 
  if(!(completed))
  {
    poly *add = (poly *) omAlloc ((pair_top + 2) * sizeof (poly));
    int piter;
    int pos = 0;
    for(piter = 0; piter <= pair_top; piter++)
    {
      sorted_pair_node *s = apairs[piter];
      if(s->i < 0)
      {
        //delayed element
        if(s->lcm_of_lm != NULL)
        {
          add[pos] = s->lcm_of_lm;
          pos++;
        }
      }
      free_sorted_pair_node (s, r);
      apairs[piter] = NULL;
    }
    pair_top = -1;
    add[pos] = NULL;
    pos = 0;
    while(add[pos] != NULL)
    {
      add_to_basis_ideal_quotient (add[pos], this, NULL);
      pos++;
    }
    for(piter = 0; piter <= pair_top; piter++)
    {
      sorted_pair_node *s = apairs[piter];
      assume (s->i >= 0);
      free_sorted_pair_node (s, r);
      apairs[piter] = NULL;
    }
    pair_top = -1;
  }
  id_Delete (&add_later, r);
  int i, j;
  slimgb_alg *c = this;
  while(c->to_destroy)
  {
    pDelete (&(c->to_destroy->p));
    poly_list_node *old = c->to_destroy;
    c->to_destroy = c->to_destroy->next;
    omFree (old);
  }
  while(c->F)
  {
    for(i = 0; i < c->F->size; i++)
    {
      pDelete (&(c->F->mp[i].m));
    }
    omFree (c->F->mp);
    c->F->mp = NULL;
    mp_array_list *old = c->F;
    c->F = c->F->next;
    omFree (old);
  }
  while(c->F_minus)
  {
    for(i = 0; i < c->F_minus->size; i++)
    {
      pDelete (&(c->F_minus->p[i]));
    }
    omFree (c->F_minus->p);
    c->F_minus->p = NULL;
    poly_array_list *old = c->F_minus;
    c->F_minus = c->F_minus->next;
    omFree (old);
  }
#ifndef HAVE_BOOST
#ifndef USE_STDVECBOOL
  for(int z = 1 /* zero length at 0 */ ; z < c->n; z++)
  {
    omFree (c->states[z]);
  }
  omFree (c->states);
#endif
#endif
 
  omFree (c->lengths);
  omFree (c->weighted_lengths);
  for(int z = 0; z < c->n; z++)
  {
    pDelete (&c->tmp_pair_lm[z]);
    omFree (c->tmp_spn[z]);
  }
  omFree (c->tmp_pair_lm);
  omFree (c->tmp_spn);
 
  omFree (c->T_deg);
  omfree (c->T_deg_full); /*c->T_deg_full my be NULL*/
 
  omFree (c->strat->ecartS);
  omFree (c->strat->sevS);
//   initsevS(i);
  omFree (c->strat->S_2_R);
 
 
  omFree (c->strat->lenS);
 
  if(c->strat->lenSw)
    omFree (c->strat->lenSw);
 
  for(i = 0; i < c->n; i++)
  {
    if(c->gcd_of_terms[i])
      pDelete (&(c->gcd_of_terms[i]));
  }
  omFree (c->gcd_of_terms);
 
  omFree (c->apairs);
  if(TEST_OPT_PROT)
  {
    //Print("calculated %d NFs\n",c->normal_forms);
    Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n",
           c->normal_forms, c->easy_product_crit, c->extended_product_crit);
  }
 
  for(i = 0; i <= c->strat->sl; i++)
  {
    if(!c->strat->S[i])
      continue;
    BOOLEAN found = FALSE;
    for(j = 0; j < c->n; j++)
    {
      if(c->S->m[j] == c->strat->S[i])
      {
        found = TRUE;
        break;
      }
    }
    if(!found)
      pDelete (&c->strat->S[i]);
  }
//   for(i=0;i<c->n;i++)
//   {
//     if (c->rep[i]!=i)
//     {
// //       for(j=0;j<=c->strat->sl;j++)
// {
// //   if(c->strat->S[j]==c->S->m[i])
// {
// //     c->strat->S[j]=NULL;
// //     break;
// //   }
// //       }
// //      PrintS("R_delete");
//       pDelete(&c->S->m[i]);
//     }
//   }
 
  if(completed)
  {
    for(i = 0; i < c->n; i++)
    {
      assume (c->S->m[i] != NULL);
      if(p_GetComp (c->S->m[i], currRing) > this->syz_comp)
        continue;
      for(j = 0; j < c->n; j++)
      {
        if((c->S->m[j] == NULL) || (i == j))
          continue;
        assume (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
                                      c->S->m[i], ~c->short_Exps[i],
                                      c->r) == p_LmDivisibleBy (c->S->m[j],
                                                                c->S->m[i],
                                                                c->r));
        if(p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
                                 c->S->m[i], ~c->short_Exps[i], c->r))
        {
          pDelete (&c->S->m[i]);
          break;
        }
      }
    }
  }
  omFree (c->short_Exps);
 
  ideal I = c->S;
  IDELEMS (I) = c->n;
  idSkipZeroes (I);
  for(i = 0; i <= c->strat->sl; i++)
    c->strat->S[i] = NULL;
  id_Delete (&c->strat->Shdl, c->r);
  pDelete (&c->tmp_lm);
  omUnGetSpecBin (&lm_bin);
  delete c->strat;
}

Member Function Documentation

cleanDegs()

void slimgb_alg::cleanDegs	(	int	lower,
		int	upper
	)

Definition at line 3794 of file tgb.cc.

{
  assume (is_homog);
  int deg;
  if(TEST_OPT_PROT)
  {
    PrintS ("C");
  }
  for(deg = lower; deg <= upper; deg++)
  {
    int i;
    for(i = 0; i < n; i++)
    {
      if(T_deg[i] == deg)
      {
        poly h;
        h = S->m[i];
        h = redNFTail (h, strat->sl, strat, lengths[i]);
        if(TEST_OPT_INTSTRATEGY)
        {
          p_Cleardenom (h, r); //includes p_Content(h,r);
        }
        else
          pNorm (h);
        //TODO:GCD of TERMS
        poly got =::gcd_of_terms (h, r);
        p_Delete (&gcd_of_terms[i], r);
        gcd_of_terms[i] = got;
        int len = pLength (h);
        wlen_type wlen = pQuality (h, this, len);
        if(weighted_lengths)
          weighted_lengths[i] = wlen;
        lengths[i] = len;
        assume (h == S->m[i]);
        int j;
        for(j = 0; j <= strat->sl; j++)
        {
          if(h == strat->S[j])
          {
            int new_pos = simple_posInS (strat, h, len, wlen);
            if(strat->lenS)
            {
              strat->lenS[j] = len;
            }
            if(strat->lenSw)
            {
              strat->lenSw[j] = wlen;
            }
            if(new_pos < j)
            {
              move_forward_in_S (j, new_pos, strat);
            }
            else
            {
              if(new_pos > j)
                new_pos = new_pos - 1;  //is identical with one element
              if(new_pos > j)
                move_backward_in_S (j, new_pos, strat);
            }
            break;
          }
        }
      }
    }
  }
  {
    int i, j;
    for(i = 0; i < this->n; i++)
    {
      for(j = 0; j < i; j++)
      {
        if(T_deg[i] + T_deg[j] <= upper)
        {
          now_t_rep (i, j, this);
        }
      }
    }
  }
  //TODO resort and update strat->S,strat->lenSw
  //TODO mark pairs
}

introduceDelayedPairs()

void slimgb_alg::introduceDelayedPairs	(	poly *	pa,
		int	s
	)

Definition at line 3156 of file tgb.cc.

{
  if(s == 0)
    return;
  sorted_pair_node **si_array =
    (sorted_pair_node **) omAlloc (s * sizeof (sorted_pair_node *));
 
  for(int i = 0; i < s; i++)
  {
    sorted_pair_node *si =
      (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
    si->i = -1;
    si->j = -2;
    poly p = pa[i];
    simplify_poly (p, r);
    si->expected_length = pQuality (p, this, pLength (p));
    p_Test (p, r);
    si->deg = this->pTotaldegree_full (p);
    /*if (!rField_is_Zp(r))
       {
       p_Content(p,r);
       p_Cleardenom(p,r);
       } */
 
    si->lcm_of_lm = p;
 
    //      c->apairs[n-1-i]=si;
    si_array[i] = si;
  }
 
  qsort (si_array, s, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
  apairs = spn_merge (apairs, pair_top + 1, si_array, s, this);
  pair_top += s;
  omFree (si_array);
}

pTotaldegree()

unsigned long slimgb_alg::pTotaldegree ( poly  p )

inline

Definition at line 271 of file tgb_internal.h.

  {
      pTest(p);
      //assume(pDeg(p,r)==::p_Totaldegree(p,r));
      assume(((unsigned long)::p_Totaldegree(p,r))==p->exp[deg_pos]);
      return p->exp[deg_pos];
      //return ::pTotaldegree(p,this->r);
  }

pTotaldegree_full()

int slimgb_alg::pTotaldegree_full ( poly  p )

inline

Definition at line 279 of file tgb_internal.h.

  {
    int rr=0;
    while(p!=NULL)
    {
      int d=this->pTotaldegree(p);
      if (d>rr) rr=d;
      pIter(p);
    }
    return rr;
  }

Field Documentation

add_later

ideal slimgb_alg::add_later

Definition at line 214 of file tgb_internal.h.

apairs

sorted_pair_node** slimgb_alg::apairs

Definition at line 229 of file tgb_internal.h.

array_lengths

int slimgb_alg::array_lengths

Definition at line 246 of file tgb_internal.h.

average_length

int slimgb_alg::average_length

Definition at line 255 of file tgb_internal.h.

completed

BOOLEAN slimgb_alg::completed

Definition at line 262 of file tgb_internal.h.

current_degree

int slimgb_alg::current_degree

Definition at line 248 of file tgb_internal.h.

deg_pos

int slimgb_alg::deg_pos

Definition at line 258 of file tgb_internal.h.

easy_product_crit

int slimgb_alg::easy_product_crit

Definition at line 253 of file tgb_internal.h.

eliminationProblem

BOOLEAN slimgb_alg::eliminationProblem

Definition at line 265 of file tgb_internal.h.

expandS

poly* slimgb_alg::expandS

Definition at line 226 of file tgb_internal.h.

extended_product_crit

int slimgb_alg::extended_product_crit

Definition at line 254 of file tgb_internal.h.

F

mp_array_list* slimgb_alg::F

Definition at line 238 of file tgb_internal.h.

F4_mode

BOOLEAN slimgb_alg::F4_mode

Definition at line 266 of file tgb_internal.h.

F_minus

poly_array_list* slimgb_alg::F_minus

Definition at line 239 of file tgb_internal.h.

gcd_of_terms

poly* slimgb_alg::gcd_of_terms

Definition at line 227 of file tgb_internal.h.

is_homog

BOOLEAN slimgb_alg::is_homog

Definition at line 263 of file tgb_internal.h.

isDifficultField

BOOLEAN slimgb_alg::isDifficultField

Definition at line 261 of file tgb_internal.h.

last_index

int slimgb_alg::last_index

Definition at line 250 of file tgb_internal.h.

lastCleanedDeg

int slimgb_alg::lastCleanedDeg

Definition at line 257 of file tgb_internal.h.

lastDpBlockStart

int slimgb_alg::lastDpBlockStart

Definition at line 256 of file tgb_internal.h.

lengths

int* slimgb_alg::lengths

Definition at line 217 of file tgb_internal.h.

max_pairs

int slimgb_alg::max_pairs

Definition at line 251 of file tgb_internal.h.

n

int slimgb_alg::n

Definition at line 243 of file tgb_internal.h.

nc

BOOLEAN slimgb_alg::nc

Definition at line 267 of file tgb_internal.h.

normal_forms

int slimgb_alg::normal_forms

Definition at line 247 of file tgb_internal.h.

pair_top

int slimgb_alg::pair_top

Definition at line 252 of file tgb_internal.h.

r

ring slimgb_alg::r

Definition at line 216 of file tgb_internal.h.

Rcounter

int slimgb_alg::Rcounter

Definition at line 249 of file tgb_internal.h.

reduction_steps

unsigned int slimgb_alg::reduction_steps

Definition at line 242 of file tgb_internal.h.

S

ideal slimgb_alg::S

Definition at line 215 of file tgb_internal.h.

short_Exps

long* slimgb_alg::short_Exps

Definition at line 219 of file tgb_internal.h.

soon_free

int_pair_node* slimgb_alg::soon_free

Definition at line 228 of file tgb_internal.h.

states

char** slimgb_alg::states

Definition at line 209 of file tgb_internal.h.

strat

kStrategy slimgb_alg::strat

Definition at line 220 of file tgb_internal.h.

syz_comp

int slimgb_alg::syz_comp

array_lengths should be greater equal n;

Definition at line 245 of file tgb_internal.h.

T_deg

int* slimgb_alg::T_deg

Definition at line 221 of file tgb_internal.h.

T_deg_full

int* slimgb_alg::T_deg_full

Definition at line 222 of file tgb_internal.h.

tailReductions

BOOLEAN slimgb_alg::tailReductions

Definition at line 264 of file tgb_internal.h.

tmp_lm

poly slimgb_alg::tmp_lm

Definition at line 223 of file tgb_internal.h.

tmp_pair_lm

poly* slimgb_alg::tmp_pair_lm

Definition at line 224 of file tgb_internal.h.

tmp_spn

sorted_pair_node** slimgb_alg::tmp_spn

Definition at line 225 of file tgb_internal.h.

to_destroy

poly_list_node* slimgb_alg::to_destroy

Definition at line 236 of file tgb_internal.h.

use_noro

BOOLEAN slimgb_alg::use_noro

Definition at line 259 of file tgb_internal.h.

use_noro_last_block

BOOLEAN slimgb_alg::use_noro_last_block

Definition at line 260 of file tgb_internal.h.

weighted_lengths

wlen_type* slimgb_alg::weighted_lengths

Definition at line 218 of file tgb_internal.h.

---

The documentation for this class was generated from the following files:

• kernel/GBEngine/tgb_internal.h
• kernel/GBEngine/tgb.cc