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 210 of file tgb_internal.h.

Constructor & Destructor Documentation

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

Definition at line 3178 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 != 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));
#ifdef HEAD_BIN
  HeadBin = omGetSpecBin (POLYSIZE + (currRing->ExpL_Size) * sizeof (long));
#endif
  /* 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 = 0;
  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) <= 32003));
  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) <= 32003));
  }
#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 ( )

virtual

Definition at line 3366 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);
  if(c->T_deg_full)
    omfree (c->T_deg_full);

  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

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

Definition at line 3797 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(!rField_is_Zp (r))
        {
          p_Cleardenom (h, r);
          //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
}

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

Definition at line 3142 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);
}

unsigned long slimgb_alg::pTotaldegree ( poly  p )

inline

Definition at line 286 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);
  }

int slimgb_alg::pTotaldegree_full ( poly  p )

inline

Definition at line 294 of file tgb_internal.h.

  {
    int rr=0;
    while(p)
    {
      int d=this->pTotaldegree(p);
      rr=si_max(rr,d);
      pIter(p);
    }
    return rr;
  }

Field Documentation

ideal slimgb_alg::add_later

Definition at line 226 of file tgb_internal.h.

sorted_pair_node** slimgb_alg::apairs

Definition at line 241 of file tgb_internal.h.

int slimgb_alg::array_lengths

Definition at line 261 of file tgb_internal.h.

int slimgb_alg::average_length

Definition at line 270 of file tgb_internal.h.

BOOLEAN slimgb_alg::completed

Definition at line 277 of file tgb_internal.h.

int slimgb_alg::current_degree

Definition at line 263 of file tgb_internal.h.

int slimgb_alg::deg_pos

Definition at line 273 of file tgb_internal.h.

int slimgb_alg::easy_product_crit

Definition at line 268 of file tgb_internal.h.

BOOLEAN slimgb_alg::eliminationProblem

Definition at line 280 of file tgb_internal.h.

poly* slimgb_alg::expandS

Definition at line 238 of file tgb_internal.h.

int slimgb_alg::extended_product_crit

Definition at line 269 of file tgb_internal.h.

mp_array_list* slimgb_alg::F

Definition at line 250 of file tgb_internal.h.

BOOLEAN slimgb_alg::F4_mode

Definition at line 281 of file tgb_internal.h.

poly_array_list* slimgb_alg::F_minus

Definition at line 251 of file tgb_internal.h.

poly* slimgb_alg::gcd_of_terms

Definition at line 239 of file tgb_internal.h.

BOOLEAN slimgb_alg::is_homog

Definition at line 278 of file tgb_internal.h.

BOOLEAN slimgb_alg::isDifficultField

Definition at line 276 of file tgb_internal.h.

int slimgb_alg::last_index

Definition at line 265 of file tgb_internal.h.

int slimgb_alg::lastCleanedDeg

Definition at line 272 of file tgb_internal.h.

int slimgb_alg::lastDpBlockStart

Definition at line 271 of file tgb_internal.h.

int* slimgb_alg::lengths

Definition at line 229 of file tgb_internal.h.

int slimgb_alg::max_pairs

Definition at line 266 of file tgb_internal.h.

int slimgb_alg::n

Definition at line 258 of file tgb_internal.h.

BOOLEAN slimgb_alg::nc

Definition at line 282 of file tgb_internal.h.

int slimgb_alg::normal_forms

Definition at line 262 of file tgb_internal.h.

int slimgb_alg::pair_top

Definition at line 267 of file tgb_internal.h.

ring slimgb_alg::r

Definition at line 228 of file tgb_internal.h.

int slimgb_alg::Rcounter

Definition at line 264 of file tgb_internal.h.

unsigned int slimgb_alg::reduction_steps

Definition at line 257 of file tgb_internal.h.

ideal slimgb_alg::S

Definition at line 227 of file tgb_internal.h.

long* slimgb_alg::short_Exps

Definition at line 231 of file tgb_internal.h.

int_pair_node* slimgb_alg::soon_free

Definition at line 240 of file tgb_internal.h.

char** slimgb_alg::states

Definition at line 221 of file tgb_internal.h.

kStrategy slimgb_alg::strat

Definition at line 232 of file tgb_internal.h.

int slimgb_alg::syz_comp

array_lengths should be greater equal n;

Definition at line 260 of file tgb_internal.h.

int* slimgb_alg::T_deg

Definition at line 233 of file tgb_internal.h.

int* slimgb_alg::T_deg_full

Definition at line 234 of file tgb_internal.h.

BOOLEAN slimgb_alg::tailReductions

Definition at line 279 of file tgb_internal.h.

poly slimgb_alg::tmp_lm

Definition at line 235 of file tgb_internal.h.

poly* slimgb_alg::tmp_pair_lm

Definition at line 236 of file tgb_internal.h.

sorted_pair_node** slimgb_alg::tmp_spn

Definition at line 237 of file tgb_internal.h.

poly_list_node* slimgb_alg::to_destroy

Definition at line 248 of file tgb_internal.h.

BOOLEAN slimgb_alg::use_noro

Definition at line 274 of file tgb_internal.h.

BOOLEAN slimgb_alg::use_noro_last_block

Definition at line 275 of file tgb_internal.h.

wlen_type* slimgb_alg::weighted_lengths

Definition at line 230 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