tgb.cc File Reference

#include <kernel/mod2.h>
#include <kernel/GBEngine/tgb.h>
#include <kernel/GBEngine/tgb_internal.h>
#include <kernel/GBEngine/tgbgauss.h>
#include <misc/options.h>
#include <kernel/digitech.h>
#include <polys/nc/nc.h>
#include <polys/nc/sca.h>
#include <polys/prCopy.h>
#include <coeffs/longrat.h>
#include <stdlib.h>
#include <stdio.h>
#include <queue>

Go to the source code of this file.

Data Structures
class	poly_tree_node
class	exp_number_builder
struct	int_poly_pair
	obsolete More...

Macros
#define	BUCKETS_FOR_NORO_RED   1
	: delay nur auf Sugarvergr?erung : grade aus ecartS, setze dazu strat->honey; und nutze p.ecart : no tail reductions in syz comp More...
#define	SR_HDL(A)   ((long)(A))
#define	ADD_LATER_SIZE   500
#define	LEN_VAR3
#define	degbound(p)   assume(pTotaldegree(p)<10)
#define	ENLARGE(pointer, type)   pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))
#define	ENLARGE_ALIGN(pointer, type)

Functions
static int	add_to_reductors (slimgb_alg *c, poly h, int len, int ecart, BOOLEAN simplified=FALSE)
static void	multi_reduction (red_object *los, int &losl, slimgb_alg *c)
static void	multi_reduce_step (find_erg &erg, red_object *r, slimgb_alg *c)
static BOOLEAN	extended_product_criterion (poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg *c)
static poly	gcd_of_terms (poly p, ring r)
static int	tgb_pair_better_gen (const void *ap, const void *bp)
static BOOLEAN	pair_better (sorted_pair_node *a, sorted_pair_node *b, slimgb_alg *c=NULL)
static BOOLEAN	state_is (calc_state state, const int &i, const int &j, slimgb_alg *c)
static void	super_clean_top_of_pair_list (slimgb_alg *c)
static int	simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen)
static int *	make_connections (int from, int to, poly bound, slimgb_alg *c)
static BOOLEAN	has_t_rep (const int &arg_i, const int &arg_j, slimgb_alg *state)
static void	shorten_tails (slimgb_alg *c, poly monom)
static poly	redNF2 (poly h, slimgb_alg *c, int &len, number &m, int n=0)
static poly	redNFTail (poly h, const int sl, kStrategy strat, int len)
static int	bucket_guess (kBucket *bucket)
static void	simplify_poly (poly p, ring r)
int	slim_nsize (number n, ring r)
static BOOLEAN	monomial_root (poly m, ring r)
static BOOLEAN	polynomial_root (poly h, ring r)
static poly	p_Init_Special (const ring r)
static poly	pOne_Special (const ring r=currRing)
static wlen_type	pSLength (poly p, int l)
wlen_type	kSBucketLength (kBucket *b, poly lm=NULL)
	TODO CoefBuckets bercksichtigen. More...
static BOOLEAN	elength_is_normal_length (poly p, slimgb_alg *c)
static BOOLEAN	lies_in_last_dp_block (poly p, slimgb_alg *c)
static int	get_last_dp_block_start (ring r)
static wlen_type	do_pELength (poly p, slimgb_alg *c, int dlm=-1)
wlen_type	pELength (poly p, slimgb_alg *c, ring)
wlen_type	kEBucketLength (kBucket *b, poly lm, slimgb_alg *ca)
static int	pELength (poly p, slimgb_alg *c, int l)
static wlen_type	pQuality (poly p, slimgb_alg *c, int l=-1)
static int	pTotaldegree_full (poly p)
static int	red_object_better_gen (const void *ap, const void *bp)
int	tgb_pair_better_gen2 (const void *ap, const void *bp)
int	kFindDivisibleByInS_easy (kStrategy strat, const red_object &obj)
int	kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev)
static int	posInPairs (sorted_pair_node **p, int pn, sorted_pair_node *qe, slimgb_alg *c, int an=0)
static BOOLEAN	ascending (int *i, int top)
sorted_pair_node **	spn_merge (sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
static BOOLEAN	trivial_syzygie (int pos1, int pos2, poly bound, slimgb_alg *c)
int	find_best (red_object *r, int l, int u, wlen_type &w, slimgb_alg *c)
	returns position sets w as weight More...
BOOLEAN	good_has_t_rep (int i, int j, slimgb_alg *c)
BOOLEAN	lenS_correct (kStrategy strat)
static void	cleanS (kStrategy strat, slimgb_alg *c)
static void	length_one_crit (slimgb_alg *c, int pos, int len)
static void	move_forward_in_S (int old_pos, int new_pos, kStrategy strat)
static void	move_backward_in_S (int old_pos, int new_pos, kStrategy strat)
static void	replace_pair (int &i, int &j, slimgb_alg *c)
static void	add_later (poly p, const char *prot, slimgb_alg *c)
static void	clearS (poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
static int	iq_crit (const void *ap, const void *bp)
static wlen_type	coeff_mult_size_estimate (int s1, int s2, ring r)
static wlen_type	pair_weighted_length (int i, int j, slimgb_alg *c)
sorted_pair_node **	add_to_basis_ideal_quotient (poly h, slimgb_alg *c, int *ip)
static poly	redTailShort (poly h, kStrategy strat)
static void	line_of_extended_prod (int fixpos, slimgb_alg *c)
static void	c_S_element_changed_hook (int pos, slimgb_alg *c)
void	t2ippa_rec (poly *ip, int *ia, poly_tree_node *k, int &offset)
	obsolete More...
void	t2ippa (poly *ip, int *ia, exp_number_builder &e)
	obsolete More...
int	anti_poly_order (const void *a, const void *b)
BOOLEAN	is_valid_ro (red_object &ro)
int	terms_sort_crit (const void *a, const void *b)
static void	mass_add (poly *p, int pn, slimgb_alg *c)
static void	go_on (slimgb_alg *c)
void	init_with_mac_poly (tgb_sparse_matrix *mat, int row, mac_poly m)
poly	free_row_to_poly (tgb_sparse_matrix *mat, int row, poly *monoms, int monom_index)
static int	poly_crit (const void *ap1, const void *ap2)
ideal	t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
ideal	do_t_rep_gb (ring, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
void	now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg *c)
sorted_pair_node *	top_pair (slimgb_alg *c)
sorted_pair_node *	quick_pop_pair (slimgb_alg *c)
void	clean_top_of_pair_list (slimgb_alg *c)
void	free_sorted_pair_node (sorted_pair_node *s, ring r)
static BOOLEAN	pHasNotCFExtended (poly p1, poly p2, poly m)
static wlen_type	quality_of_pos_in_strat_S (int pos, slimgb_alg *c)
static wlen_type	quality_of_pos_in_strat_S_mult_high (int pos, poly high, slimgb_alg *c)
static void	multi_reduction_lls_trick (red_object *los, int, slimgb_alg *c, find_erg &erg)
static int	fwbw (red_object *los, int i)
static void	canonicalize_region (red_object *los, int l, int u, slimgb_alg *)
static void	multi_reduction_find (red_object *los, int losl, slimgb_alg *c, int startf, find_erg &erg)
static int	multi_reduction_clear_zeroes (red_object *los, int losl, int l, int u)
int	search_red_object_pos (red_object *a, int top, red_object *key)
static void	sort_region_down (red_object *los, int l, int u, slimgb_alg *)

Variables
static const int	bundle_size = 100
static const int	bundle_size_noro = 10000
static const int	delay_factor = 3
static omBin	lm_bin = NULL

---

Data Structure Documentation

struct int_poly_pair

obsolete

Definition at line 2025 of file tgb.cc.

Data Fields
int	n
poly	p

Macro Definition Documentation

#define ADD_LATER_SIZE   500

Definition at line 39 of file tgb.cc.

#define BUCKETS_FOR_NORO_RED   1

: delay nur auf Sugarvergr?erung : grade aus ecartS, setze dazu strat->honey; und nutze p.ecart : no tail reductions in syz comp

Definition at line 34 of file tgb.cc.

#define degbound

(

p

)

assume(pTotaldegree(p)<10)

Definition at line 153 of file tgb.cc.

#define ENLARGE	(		pointer,
			type
	)		pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))

#define ENLARGE_ALIGN	(		pointer,
			type
	)

Value:

{if(pointer)\
         pointer=(type*)omReallocAligned(pointer, c->array_lengths*sizeof(type));\
         else pointer=(type*)omAllocAligned(c->array_lengths*sizeof(type));}

#define LEN_VAR3

Definition at line 152 of file tgb.cc.

#define SR_HDL

(

A

)

((long)(A))

Definition at line 35 of file tgb.cc.

Function Documentation

static void add_later ( poly  p, const char *  prot, slimgb_alg *  c  )

static

Definition at line 1294 of file tgb.cc.

{
  int i = 0;
  //check, if it is already in the queue

  while(c->add_later->m[i] != NULL)
  {
    if(p_LmEqual (c->add_later->m[i], p, c->r))
      return;
    i++;
  }
  if(TEST_OPT_PROT)
    PrintS (prot);
  c->add_later->m[i] = p;
}

sorted_pair_node** add_to_basis_ideal_quotient	(	poly	h,
		slimgb_alg *	c,
		int *	ip
	)

Definition at line 1428 of file tgb.cc.

{
  p_Test (h, c->r);
  assume (h != NULL);
  poly got = gcd_of_terms (h, c->r);
  if((got != NULL) && (TEST_V_UPTORADICAL))
  {
    poly copy = p_Copy (got, c->r);
    //p_wrp(got,c->r);
    BOOLEAN changed = monomial_root (got, c->r);
    if(changed)
    {
      poly div_by = pDivide (copy, got);
      poly iter = h;
      while(iter)
      {
        pExpVectorSub (iter, div_by);
        pIter (iter);
      }
      p_Delete (&div_by, c->r);
      PrintS ("U");
    }
    p_Delete (&copy, c->r);
  }

#define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))

#define ENLARGE_ALIGN(pointer, type) {if(pointer)\
         pointer=(type*)omReallocAligned(pointer, c->array_lengths*sizeof(type));\
         else pointer=(type*)omAllocAligned(c->array_lengths*sizeof(type));}
//  BOOLEAN corr=lenS_correct(c->strat);
  int sugar;
  int ecart = 0;
  ++(c->n);
  ++(c->S->ncols);
  int i, j;
  i = c->n - 1;
  sorted_pair_node **nodes =
    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
  int spc = 0;
  if(c->n > c->array_lengths)
  {
    c->array_lengths = c->array_lengths * 2;
    assume (c->array_lengths >= c->n);
    ENLARGE (c->T_deg, int);
    ENLARGE_ALIGN (c->tmp_pair_lm, poly);
    ENLARGE_ALIGN (c->tmp_spn, sorted_pair_node *);

    ENLARGE_ALIGN (c->short_Exps, long);
    ENLARGE (c->lengths, int);
#ifndef HAVE_BOOST
#ifndef USE_STDVECBOOL

    ENLARGE_ALIGN (c->states, char *);
#endif
#endif
    ENLARGE_ALIGN (c->gcd_of_terms, poly);
    //if (c->weighted_lengths!=NULL) {
    ENLARGE_ALIGN (c->weighted_lengths, wlen_type);
    //}
    //ENLARGE_ALIGN(c->S->m,poly);
  }
  pEnlargeSet (&c->S->m, c->n - 1, 1);
  if(c->T_deg_full)
    ENLARGE (c->T_deg_full, int);
  sugar = c->T_deg[i] = c->pTotaldegree (h);
  if(c->T_deg_full)
  {
    sugar = c->T_deg_full[i] = c->pTotaldegree_full (h);
    ecart = sugar - c->T_deg[i];
    assume (ecart >= 0);
  }
  c->tmp_pair_lm[i] = pOne_Special (c->r);

  c->tmp_spn[i] = (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));

  c->lengths[i] = pLength (h);

  //necessary for correct weighted length

  if(!rField_is_Zp (c->r))
  {
    p_Cleardenom (h, c->r);
    //p_Content(h,c->r); //is a duplicate call, but belongs here
  }
  else
    pNorm (h);
  pNormalize (h);

  c->weighted_lengths[i] = pQuality (h, c, c->lengths[i]);
  c->gcd_of_terms[i] = got;
#ifdef HAVE_BOOST
  c->states.push_back (dynamic_bitset <> (i));

#else
#ifdef USE_STDVECBOOL

  c->states.push_back (vector < bool > (i));

#else
  if(i > 0)
    c->states[i] = (char *) omAlloc (i * sizeof (char));
  else
    c->states[i] = NULL;
#endif
#endif

  c->S->m[i] = h;
  c->short_Exps[i] = p_GetShortExpVector (h, c->r);

#undef ENLARGE
#undef ENLARGE_ALIGN
  if(p_GetComp (h, currRing) <= c->syz_comp)
  {
    for(j = 0; j < i; j++)
    {


#ifndef HAVE_BOOST
      c->states[i][j] = UNCALCULATED;
#endif
      assume (p_LmDivisibleBy (c->S->m[i], c->S->m[j], c->r) ==
              p_LmShortDivisibleBy (c->S->m[i], c->short_Exps[i], c->S->m[j],
                                    ~(c->short_Exps[j]), c->r));

      if(__p_GetComp (c->S->m[i], c->r) != __p_GetComp (c->S->m[j], c->r))
      {
        //c->states[i][j]=UNCALCULATED;
        //WARNUNG: be careful
        continue;
      }
      else if((!c->nc) && (c->lengths[i] == 1) && (c->lengths[j] == 1))
      {
        c->states[i][j] = HASTREP;
      }
      else if(((!c->nc) || (c->is_homog && rIsSCA (c->r)))
              && (pHasNotCF (c->S->m[i], c->S->m[j])))
//     else if ((!(c->nc)) &&  (pHasNotCF(c->S->m[i],c->S->m[j])))
      {
        c->easy_product_crit++;
        c->states[i][j] = HASTREP;
        continue;
      }
      else
        if(extended_product_criterion
           (c->S->m[i], c->gcd_of_terms[i], c->S->m[j], c->gcd_of_terms[j],
            c))
      {
        c->states[i][j] = HASTREP;
        c->extended_product_crit++;
        //PrintS("E");
      }
      //  if (c->states[i][j]==UNCALCULATED)
      //  {

      if((TEST_V_FINDMONOM) && (!c->nc))
      {
        //PrintS("COMMU");
        //  if (c->lengths[i]==c->lengths[j])
        //  {
//             poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
//             if (short_s==NULL)
//             {
//                 c->states[i][j]=HASTREP;
//             }
//             else
//             {
//                 p_Delete(&short_s, currRing);
//             }
//         }
        if(c->lengths[i] + c->lengths[j] == 3)
        {


          poly short_s = ksCreateShortSpoly (c->S->m[i], c->S->m[j], c->r);
          if(short_s == NULL)
          {
            c->states[i][j] = HASTREP;
          }
          else
          {
            assume (pLength (short_s) == 1);
            if(TEST_V_UPTORADICAL)
              monomial_root (short_s, c->r);
            int iS = kFindDivisibleByInS_easy (c->strat, short_s,
                                               p_GetShortExpVector (short_s,
                                                                    c->r));
            if(iS < 0)
            {
              //PrintS("N");
              if(TRUE)
              {
                c->states[i][j] = HASTREP;
                add_later (short_s, "N", c);
              }
              else
                p_Delete (&short_s, currRing);
            }
            else
            {
              if(c->strat->lenS[iS] > 1)
              {
                //PrintS("O");
                if(TRUE)
                {
                  c->states[i][j] = HASTREP;
                  add_later (short_s, "O", c);
                }
                else
                  p_Delete (&short_s, currRing);
              }
              else
                p_Delete (&short_s, currRing);
              c->states[i][j] = HASTREP;
            }


          }
        }
      }
      //    if (short_s)
      //    {
      assume (spc <= j);
      sorted_pair_node *s = c->tmp_spn[spc];    //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
      s->i = si_max (i, j);
      s->j = si_min (i, j);
      assume (s->j == j);
      s->expected_length = pair_weighted_length (i, j, c);      //c->lengths[i]+c->lengths[j]-2;

      poly lm = c->tmp_pair_lm[spc];    //=pOne_Special();

      pLcm (c->S->m[i], c->S->m[j], lm);
      pSetm (lm);
      p_Test (lm, c->r);
      s->deg = c->pTotaldegree (lm);

      if(c->T_deg_full)         //Sugar
      {
        int t_i = c->T_deg_full[s->i] - c->T_deg[s->i];
        int t_j = c->T_deg_full[s->j] - c->T_deg[s->j];
        s->deg += si_max (t_i, t_j);
        //Print("\n max: %d\n",max(t_i,t_j));
      }
      p_Test (lm, c->r);
      s->lcm_of_lm = lm;
      //          pDelete(&short_s);
      //assume(lm!=NULL);
      nodes[spc] = s;
      spc++;

      // }
      //else
      //{
      //c->states[i][j]=HASTREP;
      //}
    }
  }                             //if syz_comp end

  assume (spc <= i);
  //now ideal quotient crit
  qsort (nodes, spc, sizeof (sorted_pair_node *), iq_crit);

  sorted_pair_node **nodes_final =
    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
  int spc_final = 0;
  j = 0;
  while(j < spc)
  {
    int lower = j;
    int upper;
    BOOLEAN has = FALSE;
    for(upper = lower + 1; upper < spc; upper++)
    {
      if(!pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm))
      {
        break;
      }
      if(has_t_rep (nodes[upper]->i, nodes[upper]->j, c))
        has = TRUE;
    }
    upper = upper - 1;
    int z;
    assume (spc_final <= j);
    for(z = 0; z < spc_final; z++)
    {
      if(p_LmDivisibleBy
         (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->r))
      {
        has = TRUE;
        break;
      }
    }

    if(has)
    {
      for(; lower <= upper; lower++)
      {
        //free_sorted_pair_node(nodes[lower],c->r);
        //omfree(nodes[lower]);
        nodes[lower] = NULL;
      }
      j = upper + 1;
      continue;
    }
    else
    {
      p_Test (nodes[lower]->lcm_of_lm, c->r);
      nodes[lower]->lcm_of_lm = pCopy (nodes[lower]->lcm_of_lm);
      assume (__p_GetComp (c->S->m[nodes[lower]->i], c->r) ==
              __p_GetComp (c->S->m[nodes[lower]->j], c->r));
      nodes_final[spc_final] =
        (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));

      *(nodes_final[spc_final++]) = *(nodes[lower]);
      //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
      nodes[lower] = NULL;
      for(lower = lower + 1; lower <= upper; lower++)
      {
        //  free_sorted_pair_node(nodes[lower],c->r);
        //omfree(nodes[lower]);
        nodes[lower] = NULL;
      }
      j = upper + 1;
      continue;
    }
  }

  //  Print("i:%d,spc_final:%d",i,spc_final);

  assume (spc_final <= spc);
  omfree (nodes);
  nodes = NULL;

  add_to_reductors (c, h, c->lengths[c->n - 1], ecart, TRUE);
  //i=posInS(c->strat,c->strat->sl,h,0 ecart);
  if(!(c->nc))
  {
    if(c->lengths[c->n - 1] == 1)
      shorten_tails (c, c->S->m[c->n - 1]);
  }
  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths

  //for(i=c->strat->sl; i>0;i--)
  //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
  if(c->Rcounter > 50)
  {
    c->Rcounter = 0;
    cleanS (c->strat, c);
  }

#ifdef HAVE_PLURAL
  // for SCA:
  // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg-1]
  if(rIsSCA (c->r))
  {
    const poly pNext = pNext (h);

    if(pNext != NULL)
    {
      // for additional polynomials
      const unsigned int m_iFirstAltVar = scaFirstAltVar (c->r);
      const unsigned int m_iLastAltVar = scaLastAltVar (c->r);

      int N =                   // c->r->N;
        m_iLastAltVar - m_iFirstAltVar + 1;     // should be enough
      // TODO: but we may also use got = gcd({m}_{m\in f}))!

      poly *array_arg = (poly *) omalloc (N * sizeof (poly));   // !
      int j = 0;


      for(unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++)
        // for all x_v | Ann(lm(h))
        if(p_GetExp (h, v, c->r))       // TODO: use 'got' here!
        {
          assume (p_GetExp (h, v, c->r) == 1);

          poly p = sca_pp_Mult_xi_pp (v, pNext, c->r);  // x_v * h;

          if(p != NULL)         // if (x_v * h != 0)
            array_arg[j++] = p;
        }                       // for all x_v | Ann(lm(h))

      c->introduceDelayedPairs (array_arg, j);

      omFree (array_arg);       // !!!
    }
//     PrintS("Saturation - done!!!\n");
  }
#endif // if SCAlgebra


  if(!ip)
  {
    qsort (nodes_final, spc_final, sizeof (sorted_pair_node *),
           tgb_pair_better_gen2);


    c->apairs =
      spn_merge (c->apairs, c->pair_top + 1, nodes_final, spc_final, c);
    c->pair_top += spc_final;
    clean_top_of_pair_list (c);
    omfree (nodes_final);
    return NULL;
  }
  {
    *ip = spc_final;
    return nodes_final;
  }
}

static int add_to_reductors ( slimgb_alg *  c, poly  h, int  len, int  ecart, BOOLEAN  simplified = FALSE  )

static

Definition at line 965 of file tgb.cc.

{
  //inDebug(h);
  assume (lenS_correct (c->strat));
  assume (len == pLength (h));
  int i;
//   if (c->isDifficultField)
//        i=simple_posInS(c->strat,h,pSLength(h,len),c->isDifficultField);
//   else
//     i=simple_posInS(c->strat,h,len,c->isDifficultField);

  LObject P;
  memset (&P, 0, sizeof (P));
  P.tailRing = c->r;
  P.p = h;                      /*p_Copy(h,c->r); */
  P.ecart = ecart;
  P.FDeg = c->r->pFDeg (P.p, c->r);
  if(!(simplified))
  {
    if(!rField_is_Zp (c->r))
    {
      p_Cleardenom (P.p, c->r);
      //p_Content(P.p,c->r ); //is a duplicate call, but belongs here

    }
    else
      pNorm (P.p);
    pNormalize (P.p);
  }
  wlen_type pq = pQuality (h, c, len);
  i = simple_posInS (c->strat, h, len, pq);
  c->strat->enterS (P, i, c->strat, -1);

  c->strat->lenS[i] = len;
  assume (pLength (c->strat->S[i]) == c->strat->lenS[i]);
  if(c->strat->lenSw != NULL)
    c->strat->lenSw[i] = pq;

  return i;
}

int anti_poly_order	(	const void *	a,
		const void *	b
	)

Definition at line 2054 of file tgb.cc.

{
  return -pLmCmp (((int_poly_pair *) a)->p, ((int_poly_pair *) b)->p);
}

static BOOLEAN ascending ( int *  i, int  top  )

static

Definition at line 742 of file tgb.cc.

{
  if(top < 1)
    return TRUE;
  if(i[top] < i[top - 1])
    return FALSE;
  return ascending (i, top - 1);
}

static int bucket_guess ( kBucket *  bucket )

static

Definition at line 952 of file tgb.cc.

{
  int sum = 0;
  int i;
  for(i = bucket->buckets_used; i >= 0; i--)
  {
    if(bucket->buckets[i])
      sum += bucket->buckets_length[i];
  }
  return sum;
}

static void c_S_element_changed_hook ( int  pos, slimgb_alg *  c  )

static

Definition at line 1974 of file tgb.cc.

{
  length_one_crit (c, pos, c->lengths[pos]);
  if(!c->nc)
    line_of_extended_prod (pos, c);
}

static void canonicalize_region ( red_object *  los, int  l, int  u, slimgb_alg *    )

static

Definition at line 4487 of file tgb.cc.

{
  assume (l <= u + 1);
  int i;
  for(i = l; i <= u; i++)
  {
    kBucketCanonicalize (los[i].bucket);
  }
}

void clean_top_of_pair_list

(

slimgb_alg *

c

)

Definition at line 3925 of file tgb.cc.

{
  while((c->pair_top >= 0) && (c->apairs[c->pair_top]->i >= 0)
        &&
        (!state_is
         (UNCALCULATED, c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,
          c)))
  {
    free_sorted_pair_node (c->apairs[c->pair_top], c->r);
    c->pair_top--;
  }
}

static void cleanS ( kStrategy  strat, slimgb_alg *  c  )

static

Definition at line 919 of file tgb.cc.

{
  int i = 0;
  LObject P;
  while(i <= strat->sl)
  {
    P.p = strat->S[i];
    P.sev = strat->sevS[i];
    //int dummy=strat->sl;
    //if(kFindDivisibleByInS(strat,&dummy,&P)!=i)
    if(kFindDivisibleByInS_easy (strat, P.p, P.sev) != i)
    {
      deleteInS (i, strat);
      //remember destroying poly
      BOOLEAN found = FALSE;
      int j;
      for(j = 0; j < c->n; j++)
      {
        if(c->S->m[j] == P.p)
        {
          found = TRUE;
          break;
        }
      }
      if(!found)
        pDelete (&P.p);
      //remember additional reductors
    }
    else
      i++;
  }
}

static void clearS ( poly  p, unsigned long  p_sev, int  l, int *  at, int *  k, kStrategy  strat  )

inlinestatic

Definition at line 1325 of file tgb.cc.

{
  assume (p_sev == pGetShortExpVector (p));
  if(!pLmShortDivisibleBy (p, p_sev, strat->S[*at], ~strat->sevS[*at]))
    return;
  if(l >= strat->lenS[*at])
    return;
  if(TEST_OPT_PROT)
    PrintS ("!");
  mflush ();
  //pDelete(&strat->S[*at]);
  deleteInS ((*at), strat);
  (*at)--;
  (*k)--;
//  assume(lenS_correct(strat));
}

static wlen_type coeff_mult_size_estimate ( int  s1, int  s2, ring  r  )

static

Definition at line 1367 of file tgb.cc.

{
  if(rField_is_Q (r))
    return s1 + s2;
  else
    return s1 * s2;
}

static wlen_type do_pELength ( poly  p, slimgb_alg *  c, int  dlm = -1  )

static

Definition at line 446 of file tgb.cc.

{
  if(p == NULL)
    return 0;
  wlen_type s = 0;
  poly pi = p;
  if(dlm < 0)
  {
    dlm = c->pTotaldegree (p);
    s = 1;
    pi = p->next;
  }

  while(pi)
  {
    int d = c->pTotaldegree (pi);
    if(d > dlm)
      s += 1 + d - dlm;
    else
      ++s;
    pi = pi->next;
  }
  return s;
}

ideal do_t_rep_gb	(	ring	,
		ideal	arg_I,
		int	syz_comp,
		BOOLEAN	F4_mode,
		int	deg_pos
	)

Definition at line 3609 of file tgb.cc.

{
  //  Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(-2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(-2)),QlogSize(nlInit(5)));

  if(TEST_OPT_PROT)
    if(F4_mode)
      PrintS ("F4 Modus \n");

  //debug_Ideal=arg_debug_Ideal;
  //if (debug_Ideal) PrintS("DebugIdeal received\n");
  // Print("Idelems %i \n----------\n",IDELEMS(arg_I));
  ideal I = arg_I;
  id_Compactify (I,currRing);
  if(idIs0 (I))
    return I;
  int i;
  for(i = 0; i < IDELEMS (I); i++)
  {
    assume (I->m[i] != NULL);
    simplify_poly (I->m[i], currRing);
  }

  qsort (I->m, IDELEMS (I), sizeof (poly), poly_crit);
  //Print("Idelems %i \n----------\n",IDELEMS(I));
  //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg));
  //int syz_comp=arg_I->rank;
  slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos);

  while((c->pair_top >= 0)
        && ((!(TEST_OPT_DEGBOUND))
            || (c->apairs[c->pair_top]->deg <= Kstd1_deg)))
  {
#ifdef HAVE_F4
    if(F4_mode)
      go_on_F4 (c);
    else
#endif
      go_on (c);
  }
  if(c->pair_top < 0)
    c->completed = TRUE;
  I = c->S;
  delete c;
  if(TEST_OPT_REDSB)
  {
    ideal erg = kInterRed (I, NULL);
    assume (I != erg);
    id_Delete (&I, currRing);
    return erg;
  }
  //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func);
  assume (I->rank >= id_RankFreeModule (I,currRing));
  return (I);
}

static BOOLEAN elength_is_normal_length ( poly  p, slimgb_alg *  c  )

static

Definition at line 371 of file tgb.cc.

{
  ring r = c->r;
  if(p_GetComp (p, r) != 0)
    return FALSE;
  if(c->lastDpBlockStart <= (currRing->N))
  {
    int i;
    for(i = 1; i < c->lastDpBlockStart; i++)
    {
      if(p_GetExp (p, i, r) != 0)
      {
        break;
      }
    }
    if(i >= c->lastDpBlockStart)
    {
      //wrp(p);
      //PrintS("\n");
      return TRUE;
    }
    else
      return FALSE;
  }
  else
    return FALSE;
}

static BOOLEAN extended_product_criterion ( poly  p1, poly  gcd1, poly  p2, poly  gcd2, slimgb_alg *  c  )

inlinestatic

Definition at line 4084 of file tgb.cc.

{
  if(c->nc)
    return FALSE;
  if(gcd1 == NULL)
    return FALSE;
  if(gcd2 == NULL)
    return FALSE;
  gcd1->next = gcd2;            //may ordered incorrect
  poly m = gcd_of_terms (gcd1, c->r);
  gcd1->next = NULL;
  if(m == NULL)
    return FALSE;

  BOOLEAN erg = pHasNotCFExtended (p1, p2, m);
  pDelete (&m);
  return erg;
}

int find_best	(	red_object *	r,
		int	l,
		int	u,
		wlen_type &	w,
		slimgb_alg *	c
	)

returns position sets w as weight

Definition at line 854 of file tgb.cc.

{
  int best = l;
  int i;
  w = r[l].guess_quality (c);
  for(i = l + 1; i <= u; i++)
  {
    wlen_type w2 = r[i].guess_quality (c);
    if(w2 < w)
    {
      w = w2;
      best = i;
    }
  }
  return best;
}

poly free_row_to_poly	(	tgb_sparse_matrix *	mat,
		int	row,
		poly *	monoms,
		int	monom_index
	)

Definition at line 3104 of file tgb.cc.

{
  poly p = NULL;
  poly *set_this = &p;
  mac_poly r = mat->mp[row];
  mat->mp[row] = NULL;
  while(r)
  {
    (*set_this) = pLmInit (monoms[monom_index - 1 - r->exp]);
    pSetCoeff ((*set_this), r->coef);
    set_this = &((*set_this)->next);
    mac_poly old = r;
    r = r->next;
    delete old;

  }
  return p;
}

void free_sorted_pair_node	(	sorted_pair_node *	s,
		ring	r
	)

Definition at line 3958 of file tgb.cc.

{
  if(s->i >= 0)
    p_Delete (&s->lcm_of_lm, r);
  omfree (s);
}

static int fwbw ( red_object *  los, int  i  )

static

Definition at line 4429 of file tgb.cc.

{
  int i2 = i;
  int step = 1;

  BOOLEAN bw = FALSE;
  BOOLEAN incr = TRUE;

  while(1)
  {
    if(!bw)
    {
      step = si_min (i2, step);
      if(step == 0)
        break;
      i2 -= step;

      if(!pLmEqual (los[i].p, los[i2].p))
      {
        bw = TRUE;
        incr = FALSE;
      }
      else
      {
        if((!incr) && (step == 1))
          break;
      }
    }
    else
    {
      step = si_min (i - i2, step);
      if(step == 0)
        break;
      i2 += step;
      if(pLmEqual (los[i].p, los[i2].p))
      {
        if(step == 1)
          break;
        else
        {
          bw = FALSE;
        }
      }
    }
    if(incr)
      step *= 2;
    else
    {
      if(step % 2 == 1)
        step = (step + 1) / 2;
      else
        step /= 2;
    }
  }
  return i2;
}

static poly gcd_of_terms ( poly  p, ring  r  )

static

Definition at line 4025 of file tgb.cc.

{
  int max_g_0 = 0;
  assume (p != NULL);
  int i;
  poly m = pOne ();
  poly t;
  for(i = (currRing->N); i; i--)
  {
    pSetExp (m, i, pGetExp (p, i));
    if(max_g_0 == 0)
      if(pGetExp (m, i) > 0)
        max_g_0 = i;
  }

  t = p->next;
  while(t != NULL)
  {
    if(max_g_0 == 0)
      break;
    for(i = max_g_0; i; i--)
    {
      pSetExp (m, i, si_min (pGetExp (t, i), pGetExp (m, i)));
      if(max_g_0 == i)
        if(pGetExp (m, i) == 0)
          max_g_0 = 0;
      if((max_g_0 == 0) && (pGetExp (m, i) > 0))
      {
        max_g_0 = i;
      }
    }
    t = t->next;
  }
  p_Setm (m, r);
  if(max_g_0 > 0)
    return m;
  pDelete (&m);
  return NULL;
}

static int get_last_dp_block_start ( ring  r )

static

Definition at line 427 of file tgb.cc.

{
  //ring r=c->r;
  int last_block;

  if(rRing_has_CompLastBlock (r))
  {
    last_block = rBlocks (r) - 3;
  }
  else
  {
    last_block = rBlocks (r) - 2;
  }
  assume (last_block >= 0);
  if(r->order[last_block] == ringorder_dp)
    return r->block0[last_block];
  return (currRing->N) + 1;
}

static void go_on ( slimgb_alg *  c )

static

Definition at line 2716 of file tgb.cc.

{
  //set limit of 1000 for multireductions, at the moment for
  //programming reasons
#ifdef USE_NORO
  //Print("module rank%d\n",c->S->rank);
  const BOOLEAN use_noro = c->use_noro;
#else
  const BOOLEAN use_noro = FALSE;
#endif
  int i = 0;
  c->average_length = 0;
  for(i = 0; i < c->n; i++)
  {
    c->average_length += c->lengths[i];
  }
  c->average_length = c->average_length / c->n;
  i = 0;
  int max_pairs = bundle_size;

#ifdef USE_NORO
  if((use_noro) || (c->use_noro_last_block))
    max_pairs = bundle_size_noro;
#endif
  poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); //nullterminated

  int curr_deg = -1;
  while(i < max_pairs)
  {
    sorted_pair_node *s = top_pair (c); //here is actually chain criterium done

    if(!s)
      break;

    if(curr_deg >= 0)
    {
      if(s->deg > curr_deg)
        break;
    }

    else
      curr_deg = s->deg;
    quick_pop_pair (c);
    if(s->i >= 0)
    {
      //be careful replace_pair use createShortSpoly which is not noncommutative
      now_t_rep (s->i, s->j, c);
      replace_pair (s->i, s->j, c);

      if(s->i == s->j)
      {
        free_sorted_pair_node (s, c->r);
        continue;
      }
      now_t_rep (s->i, s->j, c);
    }
    poly h;
    if(s->i >= 0)
    {
#ifdef HAVE_PLURAL
      if(c->nc)
      {
        h = nc_CreateSpoly (c->S->m[s->i], c->S->m[s->j] /*, NULL */ , c->r);

        if(h != NULL)
          p_Cleardenom (h, c->r);
      }
      else
#endif
        h = ksOldCreateSpoly (c->S->m[s->i], c->S->m[s->j], NULL, c->r);
      p_Test (h, c->r);
    }
    else
    {
      h = s->lcm_of_lm;
      p_Test (h, c->r);
    }
    // if(s->i>=0)
//       now_t_rep(s->j,s->i,c);
    number coef;
    int mlen = pLength (h);
    p_Test (h, c->r);
    if((!c->nc) & (!(use_noro)))
    {
      h = redNF2 (h, c, mlen, coef, 2);
      redTailShort (h, c->strat);
      nDelete (&coef);
    }
    p_Test (h, c->r);
    free_sorted_pair_node (s, c->r);
    if(!h)
      continue;
    p[i] = h;
    i++;
  }
  p[i] = NULL;
//  pre_comp(p,i,c);
  if(i == 0)
  {
    omfree (p);
    return;
  }
#ifdef TGB_RESORT_PAIRS
  c->replaced = new bool[c->n];
  c->used_b = FALSE;
#endif

  c->normal_forms += i;
  int j;
#ifdef USE_NORO
  //if ((!(c->nc))&&(rField_is_Zp(c->r)))
  //{
  if(use_noro)
  {
    int pn = i;
    if(pn == 0)
    {
      omfree (p);
      return;
    }
    {
      if(n_GetChar(currRing->cf) < 255)
      {
        noro_step < tgb_uint8 > (p, pn, c);
      }
      else
      {
        if(n_GetChar(currRing->cf) < 65000)
        {
          noro_step < tgb_uint16 > (p, pn, c);
        }
        else
        {
          noro_step < tgb_uint32 > (p, pn, c);
        }
      }
    }

    //if (TEST_OPT_PROT)
    //{
    //  Print("reported rank:%i\n",pn);
    //}
    mass_add (p, pn, c);
    omfree (p);
    return;
    /*if (TEST_OPT_PROT)
       for(j=0;j<pn;j++)
       {
       p_wrp(p[j],c->r);
       } */
  }
#endif
  red_object *buf = (red_object *) omalloc (i * sizeof (red_object));
  for(j = 0; j < i; j++)
  {
    p_Test (p[j], c->r);
    buf[j].p = p[j];
    buf[j].sev = pGetShortExpVector (p[j]);
    buf[j].bucket = kBucketCreate (currRing);
    p_Test (p[j], c->r);
    int len = pLength (p[j]);
    kBucketInit (buf[j].bucket, buf[j].p, len);
    buf[j].initial_quality = buf[j].guess_quality (c);
    assume (buf[j].initial_quality >= 0);
  }
  omfree (p);
  qsort (buf, i, sizeof (red_object), red_object_better_gen);
//    Print("\ncurr_deg:%i\n",curr_deg);
  if(TEST_OPT_PROT)
  {
    Print ("%dM[%d,", curr_deg, i);
  }

  multi_reduction (buf, i, c);
#ifdef TGB_RESORT_PAIRS
  if(c->used_b)
  {
    if(TEST_OPT_PROT)
      PrintS ("B");
    int e;
    for(e = 0; e <= c->pair_top; e++)
    {
      if(c->apairs[e]->i < 0)
        continue;
      assume (c->apairs[e]->j >= 0);
      if((c->replaced[c->apairs[e]->i]) || (c->replaced[c->apairs[e]->j]))
      {
        sorted_pair_node *s = c->apairs[e];
        s->expected_length = pair_weighted_length (s->i, s->j, c);
      }
    }
    qsort (c->apairs, c->pair_top + 1, sizeof (sorted_pair_node *),
           tgb_pair_better_gen2);
  }
#endif
#ifdef TGB_DEBUG
  {
    int k;
    for(k = 0; k < i; k++)
    {
      assume (kFindDivisibleByInS_easy (c->strat, buf[k]) < 0);
      int k2;
      for(k2 = 0; k2 < i; k2++)
      {
        if(k == k2)
          continue;
        assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c->r)))
                || (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2),
                    wrp (buf[k2].p), FALSE));
      }
    }
  }
#endif
  //resort S

  if(TEST_OPT_PROT)
    Print ("%i]", i);

  poly *add_those = (poly *) omalloc (i * sizeof (poly));
  for(j = 0; j < i; j++)
  {
    int len;
    poly p;
    buf[j].flatten ();
    kBucketClear (buf[j].bucket, &p, &len);
    kBucketDestroy (&buf[j].bucket);
    p_Test (p, c->r);
    //if (!c->nc) {
    if((c->tailReductions) || (lies_in_last_dp_block (p, c)))
    {
      p = redNFTail (p, c->strat->sl, c->strat, 0);
    }
    else
    {
      p = redTailShort (p, c->strat);
    }
    //}
    p_Test (p, c->r);
    add_those[j] = p;

    //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
  }
  mass_add (add_those, i, c);
  omfree (add_those);
  omfree (buf);

  if(TEST_OPT_PROT)
    Print ("(%d)", c->pair_top + 1);
  //TODO: implement that while(!(idIs0(c->add_later)))
#ifdef TGB_RESORT_PAIRS
  delete c->replaced;
  c->replaced = NULL;
  c->used_b = FALSE;
#endif
  return;
}

BOOLEAN good_has_t_rep	(	int	i,
		int	j,
		slimgb_alg *	c
	)

Definition at line 876 of file tgb.cc.

{
  assume (i >= 0);
  assume (j >= 0);
  if(has_t_rep (i, j, c))
    return TRUE;
  //poly lm=pOne();
  assume (c->tmp_lm != NULL);
  poly lm = c->tmp_lm;

  pLcm (c->S->m[i], c->S->m[j], lm);
  pSetm (lm);
  assume (lm != NULL);
  //int deciding_deg= pTotaldegree(lm);
  int *i_con = make_connections (i, j, lm, c);
  //p_Delete(&lm,c->r);

  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
  {
    if(i_con[n] == j)
    {
      now_t_rep (i, j, c);
      omFree (i_con);
      return TRUE;
    }
  }
  omfree (i_con);

  return FALSE;
}

static BOOLEAN has_t_rep ( const int &  arg_i, const int &  arg_j, slimgb_alg *  state  )

static

Definition at line 3685 of file tgb.cc.

{
  assume (0 <= arg_i);
  assume (0 <= arg_j);
  assume (arg_i < state->n);
  assume (arg_j < state->n);
  if(arg_i == arg_j)
  {
    return (TRUE);
  }
  if(arg_i > arg_j)
  {
    return (state->states[arg_i][arg_j] == HASTREP);
  }
  else
  {
    return (state->states[arg_j][arg_i] == HASTREP);
  }
}

void init_with_mac_poly	(	tgb_sparse_matrix *	mat,
		int	row,
		mac_poly	m
	)

Definition at line 3089 of file tgb.cc.

{
  assume (mat->mp[row] == NULL);
  mat->mp[row] = m;
#ifdef TGB_DEBUG
  mac_poly r = m;
  while(r)
  {
    assume (r->exp < mat->columns);
    r = r->next;
  }
#endif
}

static int iq_crit ( const void *  ap, const void *  bp  )

static

Definition at line 1342 of file tgb.cc.

{
  sorted_pair_node *a = *((sorted_pair_node **) ap);
  sorted_pair_node *b = *((sorted_pair_node **) bp);
  assume (a->i > a->j);
  assume (b->i > b->j);

  if(a->deg < b->deg)
    return -1;
  if(a->deg > b->deg)
    return 1;
  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
  if(comp != 0)
    return comp;
  if(a->expected_length < b->expected_length)
    return -1;
  if(a->expected_length > b->expected_length)
    return 1;
  if(a->j > b->j)
    return 1;
  if(a->j < b->j)
    return -1;
  return 0;
}

BOOLEAN is_valid_ro

(

red_object &

ro

)

Definition at line 2059 of file tgb.cc.

{
  red_object r2 = ro;
  ro.validate ();
  if((r2.p != ro.p) || (r2.sev != ro.sev))
    return FALSE;
  return TRUE;
}

wlen_type kEBucketLength	(	kBucket *	b,
		poly	lm,
		slimgb_alg *	ca
	)

Definition at line 494 of file tgb.cc.

{
  wlen_type s = 0;
  if(lm == NULL)
  {
    lm = kBucketGetLm (b);
  }
  if(lm == NULL)
    return 0;
  if(elength_is_normal_length (lm, ca))
  {
    return bucket_guess (b);
  }
  int d = ca->pTotaldegree (lm);
#if 0
  assume (sugar >= d);
  s = 1 + (bucket_guess (b) - 1) * (sugar - d + 1);
  return s;
#else

  //int d=pTotaldegree(lm,ca->r);
  int i;
  for(i = b->buckets_used; i >= 0; i--)
  {
    if(b->buckets[i] == NULL)
      continue;

    if((ca->pTotaldegree (b->buckets[i]) <= d)
       && (elength_is_normal_length (b->buckets[i], ca)))
    {
      s += b->buckets_length[i];
    }
    else
    {
      s += do_pELength (b->buckets[i], ca, d);
    }
  }
  return s;
#endif
}

int kFindDivisibleByInS_easy	(	kStrategy	strat,
		const red_object &	obj
	)

Definition at line 685 of file tgb.cc.

{
  int i;
  long not_sev = ~obj.sev;
  poly p = obj.p;
  for(i = 0; i <= strat->sl; i++)
  {
    if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
      return i;
  }
  return -1;
}

int kFindDivisibleByInS_easy	(	kStrategy	strat,
		poly	p,
		long	sev
	)

Definition at line 698 of file tgb.cc.

{
  int i;
  long not_sev = ~sev;
  for(i = 0; i <= strat->sl; i++)
  {
    if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
      return i;
  }
  return -1;
}

wlen_type kSBucketLength	(	kBucket *	b,
		poly	lm = NULL
	)

TODO CoefBuckets bercksichtigen.

Definition at line 221 of file tgb.cc.

{
  int s = 0;
  wlen_type c;
  number coef;
  if(lm == NULL)
    coef = pGetCoeff (kBucketGetLm (b));
  //c=nSize(pGetCoeff(kBucketGetLm(b)));
  else
    coef = pGetCoeff (lm);
  //c=nSize(pGetCoeff(lm));
  if(rField_is_Q (currRing))
  {
    c = nlQlogSize (coef, currRing->cf);
  }
  else
    c = nSize (coef);

  int i;
  for(i = b->buckets_used; i >= 0; i--)
  {
    assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
    s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
  }
#ifdef HAVE_COEF_BUCKETS
  assume (b->buckets[0] == kBucketGetLm (b));
  if(b->coef[0] != NULL)
  {
    if(rField_is_Q (currRing))
    {
      int modifier = nlQlogSize (pGetCoeff (b->coef[0]), currRing->cf);
      c += modifier;
    }
    else
    {
      int modifier = nSize (pGetCoeff (b->coef[0]));
      c *= modifier;
    }
  }
#endif
  if(!(TEST_V_COEFSTRAT))
  {
    return s * c;
  }
  else
  {
    wlen_type res = s;
    res *= c;
    res *= c;
    return res;
  }
}

static void length_one_crit ( slimgb_alg *  c, int  pos, int  len  )

static

Definition at line 1007 of file tgb.cc.

{
  if(c->nc)
    return;
  if(len == 1)
  {
    int i;
    for(i = 0; i < pos; i++)
    {
      if(c->lengths[i] == 1)
        c->states[pos][i] = HASTREP;
    }
    for(i = pos + 1; i < c->n; i++)
    {
      if(c->lengths[i] == 1)
        c->states[i][pos] = HASTREP;
    }
    if(!c->nc)
      shorten_tails (c, c->S->m[pos]);
  }
}

BOOLEAN lenS_correct

(

kStrategy

strat

)

Definition at line 907 of file tgb.cc.

{
  int i;
  for(i = 0; i <= strat->sl; i++)
  {
    if(strat->lenS[i] != pLength (strat->S[i]))
      return FALSE;
  }
  return TRUE;
}

static BOOLEAN lies_in_last_dp_block ( poly  p, slimgb_alg *  c  )

static

Definition at line 399 of file tgb.cc.

{
  ring r = c->r;
  if(p_GetComp (p, r) != 0)
    return FALSE;
  if(c->lastDpBlockStart <= (currRing->N))
  {
    int i;
    for(i = 1; i < c->lastDpBlockStart; i++)
    {
      if(p_GetExp (p, i, r) != 0)
      {
        break;
      }
    }
    if(i >= c->lastDpBlockStart)
    {
      //wrp(p);
      //PrintS("\n");
      return TRUE;
    }
    else
      return FALSE;
  }
  else
    return FALSE;
}

static void line_of_extended_prod ( int  fixpos, slimgb_alg *  c  )

static

Definition at line 1942 of file tgb.cc.

{
  if(c->gcd_of_terms[fixpos] == NULL)
  {
    c->gcd_of_terms[fixpos] = gcd_of_terms (c->S->m[fixpos], c->r);
    if(c->gcd_of_terms[fixpos])
    {
      int i;
      for(i = 0; i < fixpos; i++)
        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)))
        {
          c->states[fixpos][i] = HASTREP;
          c->extended_product_crit++;
        }
      for(i = fixpos + 1; i < c->n; i++)
        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)))
        {
          c->states[i][fixpos] = HASTREP;
          c->extended_product_crit++;
        }
    }
  }
}

static int * make_connections ( int  from, int  to, poly  bound, slimgb_alg *  c  )

static

Definition at line 1103 of file tgb.cc.

{
  ideal I = c->S;
  int *cans = (int *) omAlloc (c->n * sizeof (int));
  int *connected = (int *) omAlloc (c->n * sizeof (int));
  cans[0] = to;
  int cans_length = 1;
  connected[0] = from;
  int last_cans_pos = -1;
  int connected_length = 1;
  long neg_bounds_short = ~p_GetShortExpVector (bound, c->r);

  int not_yet_found = cans_length;
  int con_checked = 0;
  int pos;

  while(TRUE)
  {
    if((con_checked < connected_length) && (not_yet_found > 0))
    {
      pos = connected[con_checked];
      for(int i = 0; i < cans_length; i++)
      {
        if(cans[i] < 0)
          continue;
        //FIXME: triv. syz. does not hold on noncommutative, check it for modules
        if((has_t_rep (pos, cans[i], c))
           || ((!rIsPluralRing (c->r))
               && (trivial_syzygie (pos, cans[i], bound, c))))
        {
          connected[connected_length] = cans[i];
          connected_length++;
          cans[i] = -1;
          --not_yet_found;

          if(connected[connected_length - 1] == to)
          {
            if(connected_length < c->n)
            {
              connected[connected_length] = -1;
            }
            omFree (cans);
            return connected;
          }
        }
      }
      con_checked++;
    }
    else
    {
      for(last_cans_pos++; last_cans_pos <= c->n; last_cans_pos++)
      {
        if(last_cans_pos == c->n)
        {
          if(connected_length < c->n)
          {
            connected[connected_length] = -1;
          }
          omfree (cans);
          return connected;
        }
        if((last_cans_pos == from) || (last_cans_pos == to))
          continue;
        if(p_LmShortDivisibleBy
           (I->m[last_cans_pos], c->short_Exps[last_cans_pos], bound,
            neg_bounds_short, c->r))
        {
          cans[cans_length] = last_cans_pos;
          cans_length++;
          break;
        }
      }
      not_yet_found++;
      for(int i = 0; i < con_checked; i++)
      {
        if(has_t_rep (connected[i], last_cans_pos, c))
        {
          connected[connected_length] = last_cans_pos;
          connected_length++;
          cans[cans_length - 1] = -1;
          --not_yet_found;
          if(connected[connected_length - 1] == to)
          {
            if(connected_length < c->n)
            {
              connected[connected_length] = -1;
            }
            omFree (cans);
            return connected;
          }
          break;
        }
      }
    }
  }
  if(connected_length < c->n)
  {
    connected[connected_length] = -1;
  }
  omfree (cans);
  return connected;
}

static void mass_add ( poly *  p, int  pn, slimgb_alg *  c  )

static

Definition at line 2183 of file tgb.cc.

{
  int j;
  int *ibuf = (int *) omalloc (pn * sizeof (int));
  sorted_pair_node ***sbuf =
    (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **));
  for(j = 0; j < pn; j++)
  {
    p_Test (p[j], c->r);
    sbuf[j] = add_to_basis_ideal_quotient (p[j], c, ibuf + j);
  }
  int sum = 0;
  for(j = 0; j < pn; j++)
  {
    sum += ibuf[j];
  }
  sorted_pair_node **big_sbuf =
    (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *));
  int partsum = 0;
  for(j = 0; j < pn; j++)
  {
    memmove (big_sbuf + partsum, sbuf[j],
             ibuf[j] * sizeof (sorted_pair_node *));
    omFree (sbuf[j]);
    partsum += ibuf[j];
  }

  qsort (big_sbuf, sum, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
  c->apairs = spn_merge (c->apairs, c->pair_top + 1, big_sbuf, sum, c);
  c->pair_top += sum;
  clean_top_of_pair_list (c);
  omfree (big_sbuf);
  omfree (sbuf);
  omfree (ibuf);
  //omfree(buf);
#ifdef TGB_DEBUG
  int z;
  for(z = 1; z <= c->pair_top; z++)
  {
    assume (pair_better (c->apairs[z], c->apairs[z - 1], c));
  }
#endif

}

static BOOLEAN monomial_root ( poly  m, ring  r  )

static

Definition at line 89 of file tgb.cc.

{
  BOOLEAN changed = FALSE;
  int i;
  for(i = 1; i <= rVar (r); i++)
  {
    int e = p_GetExp (m, i, r);
    if(e > 1)
    {
      p_SetExp (m, i, 1, r);
      changed = TRUE;
    }
  }
  if(changed)
  {
    p_Setm (m, r);
  }
  return changed;
}

static void move_backward_in_S ( int  old_pos, int  new_pos, kStrategy  strat  )

static

Definition at line 1066 of file tgb.cc.

{
  assume (old_pos <= new_pos);
  poly p = strat->S[old_pos];
  int ecart = strat->ecartS[old_pos];
  long sev = strat->sevS[old_pos];
  int s_2_r = strat->S_2_R[old_pos];
  int length = strat->lenS[old_pos];
  assume (length == pLength (strat->S[old_pos]));
  wlen_type length_w;
  if(strat->lenSw != NULL)
    length_w = strat->lenSw[old_pos];
  int i;
  for(i = old_pos; i < new_pos; i++)
  {
    strat->S[i] = strat->S[i + 1];
    strat->ecartS[i] = strat->ecartS[i + 1];
    strat->sevS[i] = strat->sevS[i + 1];
    strat->S_2_R[i] = strat->S_2_R[i + 1];
  }
  if(strat->lenS != NULL)
    for(i = old_pos; i < new_pos; i++)
      strat->lenS[i] = strat->lenS[i + 1];
  if(strat->lenSw != NULL)
    for(i = old_pos; i < new_pos; i++)
      strat->lenSw[i] = strat->lenSw[i + 1];

  strat->S[new_pos] = p;
  strat->ecartS[new_pos] = ecart;
  strat->sevS[new_pos] = sev;
  strat->S_2_R[new_pos] = s_2_r;
  strat->lenS[new_pos] = length;
  if(strat->lenSw != NULL)
    strat->lenSw[new_pos] = length_w;
  //assume(lenS_correct(strat));
}

static void move_forward_in_S ( int  old_pos, int  new_pos, kStrategy  strat  )

static

Definition at line 1029 of file tgb.cc.

{
  assume (old_pos >= new_pos);
  poly p = strat->S[old_pos];
  int ecart = strat->ecartS[old_pos];
  long sev = strat->sevS[old_pos];
  int s_2_r = strat->S_2_R[old_pos];
  int length = strat->lenS[old_pos];
  assume (length == pLength (strat->S[old_pos]));
  wlen_type length_w;
  if(strat->lenSw != NULL)
    length_w = strat->lenSw[old_pos];
  int i;
  for(i = old_pos; i > new_pos; i--)
  {
    strat->S[i] = strat->S[i - 1];
    strat->ecartS[i] = strat->ecartS[i - 1];
    strat->sevS[i] = strat->sevS[i - 1];
    strat->S_2_R[i] = strat->S_2_R[i - 1];
  }
  if(strat->lenS != NULL)
    for(i = old_pos; i > new_pos; i--)
      strat->lenS[i] = strat->lenS[i - 1];
  if(strat->lenSw != NULL)
    for(i = old_pos; i > new_pos; i--)
      strat->lenSw[i] = strat->lenSw[i - 1];

  strat->S[new_pos] = p;
  strat->ecartS[new_pos] = ecart;
  strat->sevS[new_pos] = sev;
  strat->S_2_R[new_pos] = s_2_r;
  strat->lenS[new_pos] = length;
  if(strat->lenSw != NULL)
    strat->lenSw[new_pos] = length_w;
  //assume(lenS_correct(strat));
}

void multi_reduce_step ( find_erg &  erg, red_object *  r, slimgb_alg *  c  )

static

Definition at line 4932 of file tgb.cc.

{
  static int id = 0;
  id++;
  unsigned long sev;
  BOOLEAN lt_changed = FALSE;
  int rn = erg.reduce_by;
  poly red;
  int red_len;
  simple_reducer *pointer;
  BOOLEAN work_on_copy = FALSE;
  if(erg.fromS)
  {
    red = c->strat->S[rn];
    red_len = c->strat->lenS[rn];
    assume (red_len == pLength (red));
  }
  else
  {
    r[rn].flatten ();
    kBucketClear (r[rn].bucket, &red, &red_len);

    if(!rField_is_Zp (c->r))
    {
      p_Cleardenom (red, c->r); //should be unnecessary
      //p_Content(red, c->r);
    }
    pNormalize (red);

    if((!(erg.fromS)) && (TEST_V_UPTORADICAL))
    {
      if(polynomial_root (red, c->r))
        lt_changed = TRUE;
      sev = p_GetShortExpVector (red, c->r);
    }
    red_len = pLength (red);
  }
  if(((TEST_V_MODPSOLVSB) && (red_len > 1))
     || ((c->nc) || (erg.to_reduce_u - erg.to_reduce_l > 5)))
  {
    work_on_copy = TRUE;
    // poly m=pOne();
    poly m = c->tmp_lm;
    pSetCoeff (m, nInit (1));
    pSetComp (m, 0);
    for(int i = 1; i <= (currRing->N); i++)
      pSetExp (m, i, (pGetExp (r[erg.to_reduce_l].p, i) - pGetExp (red, i)));
    pSetm (m);
    poly red_cp;
#ifdef HAVE_PLURAL
    if(c->nc)
      red_cp = nc_mm_Mult_pp (m, red, c->r);
    else
#endif
      red_cp = ppMult_mm (red, m);
    if(!erg.fromS)
    {
      kBucketInit (r[rn].bucket, red, red_len);
    }
    //now reduce the copy
    //static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n)

    if(!c->nc)
      redTailShort (red_cp, c->strat);
    //number mul;
    // red_len--;
//     red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length);
//     pSetCoeff(red_cp,nMult(red_cp->coef,mul));
//     nDelete(&mul);
//     red_len++;
    red = red_cp;
    red_len = pLength (red);
    // pDelete(&m);
  }

  assume (red_len == pLength (red));

  int reducer_deg = 0;
  if(c->eliminationProblem)
  {
    int lm_deg = c->pTotaldegree (r[erg.to_reduce_l].p);
    int ecart;
    if(erg.fromS)
    {
      ecart = c->strat->ecartS[erg.reduce_by];
    }
    else
    {
      ecart = c->pTotaldegree_full (red) - lm_deg;
    }
    reducer_deg = lm_deg + ecart;
  }
  pointer = new simple_reducer (red, red_len, reducer_deg, c);

  if((!work_on_copy) && (!erg.fromS))
    pointer->fill_back = r[rn].bucket;
  else
    pointer->fill_back = NULL;
  pointer->reduction_id = id;
  pointer->c = c;

  pointer->reduce (r, erg.to_reduce_l, erg.to_reduce_u);
  if(work_on_copy)
    pDelete (&pointer->p);
  delete pointer;
  if(lt_changed)
  {
    assume (!erg.fromS);
    r[erg.reduce_by].sev = sev;
  }
}

static void multi_reduction ( red_object *  los, int &  losl, slimgb_alg *  c  )

static

Definition at line 4674 of file tgb.cc.

{
  poly *delay = (poly *) omalloc (losl * sizeof (poly));
  int delay_s = 0;
  //initialize;
  assume (c->strat->sl >= 0);
  assume (losl > 0);
  int i;
  wlen_type max_initial_quality = 0;

  for(i = 0; i < losl; i++)
  {
    los[i].sev = pGetShortExpVector (los[i].p);
//SetShortExpVector();
    los[i].p = kBucketGetLm (los[i].bucket);
    if(los[i].initial_quality > max_initial_quality)
      max_initial_quality = los[i].initial_quality;
    // else
//         Print("init2_qal=%lld;", los[i].initial_quality);
//     Print("initial_quality=%lld;",max_initial_quality);
  }

  int curr_pos = losl - 1;

//  nicht reduzierbare eintr�e in ergebnisliste schreiben
  // nullen loeschen
  while(curr_pos >= 0)
  {
    if((c->use_noro_last_block)
       && (lies_in_last_dp_block (los[curr_pos].p, c)))
    {
      int pn_noro = curr_pos + 1;
      poly *p_noro = (poly *) omalloc (pn_noro * sizeof (poly));
      for(i = 0; i < pn_noro; i++)
      {
        int dummy_len;
        poly p;
        los[i].p = NULL;
        kBucketClear (los[i].bucket, &p, &dummy_len);
        p_noro[i] = p;
      }
      if(n_GetChar(currRing->cf) < 255)
      {
        noro_step < tgb_uint8 > (p_noro, pn_noro, c);
      }
      else
      {
        if(n_GetChar(currRing->cf) < 65000)
        {
          noro_step < tgb_uint16 > (p_noro, pn_noro, c);
        }
        else
        {
          noro_step < tgb_uint32 > (p_noro, pn_noro, c);
        }
      }
      for(i = 0; i < pn_noro; i++)
      {
        los[i].p = p_noro[i];
        los[i].sev = pGetShortExpVector (los[i].p);
        //ignore quality
        kBucketInit (los[i].bucket, los[i].p, pLength (los[i].p));
      }
      qsort (los, pn_noro, sizeof (red_object), red_object_better_gen);
      int deleted =
        multi_reduction_clear_zeroes (los, losl, pn_noro, curr_pos);
      losl -= deleted;
      curr_pos -= deleted;
      break;
    }
    find_erg erg;

    multi_reduction_find (los, losl, c, curr_pos, erg); //last argument should be curr_pos
    if(erg.reduce_by < 0)
      break;

    erg.expand = NULL;

    multi_reduction_lls_trick (los, losl, c, erg);

    int i;
    //    wrp(los[erg.to_reduce_u].p);
    //PrintLn();
    multi_reduce_step (erg, los, c);


    if(!TEST_OPT_REDTHROUGH)
    {
      for(i = erg.to_reduce_l; i <= erg.to_reduce_u; i++)
      {
        if(los[i].p != NULL)    //the check (los[i].p!=NULL) might be invalid
        {
          //
          assume (los[i].initial_quality > 0);
          if(los[i].guess_quality (c)
             > 1.5 * delay_factor * max_initial_quality)
          {
            if(TEST_OPT_PROT)
              PrintS ("v");
            los[i].canonicalize ();
            if(los[i].guess_quality (c) > delay_factor * max_initial_quality)
            {
              if(TEST_OPT_PROT)
                PrintS (".");
              los[i].clear_to_poly ();
              //delay.push_back(los[i].p);
              delay[delay_s] = los[i].p;
              delay_s++;
              los[i].p = NULL;
            }
          }
        }
      }
    }
    int deleted = multi_reduction_clear_zeroes (los, losl, erg.to_reduce_l,
                                                erg.to_reduce_u);
    if(erg.fromS == FALSE)
      curr_pos = si_max (erg.to_reduce_u, erg.reduce_by);
    else
      curr_pos = erg.to_reduce_u;
    losl -= deleted;
    curr_pos -= deleted;

    //Print("deleted %i \n",deleted);
    if((TEST_V_UPTORADICAL) && (!(erg.fromS)))
      sort_region_down (los, si_min (erg.to_reduce_l, erg.reduce_by),
                        (si_max (erg.to_reduce_u, erg.reduce_by)) - deleted,
                        c);
    else
      sort_region_down (los, erg.to_reduce_l, erg.to_reduce_u - deleted, c);

    if(erg.expand)
    {
#ifdef FIND_DETERMINISTIC
      int i;
      for(i = 0; c->expandS[i]; i++) ;
      c->expandS = (poly *) omrealloc (c->expandS, (i + 2) * sizeof (poly));
      c->expandS[i] = erg.expand;
      c->expandS[i + 1] = NULL;
#else
      int ecart = 0;
      if(c->eliminationProblem)
      {
        ecart =
          c->pTotaldegree_full (erg.expand) - c->pTotaldegree (erg.expand);
      }
      add_to_reductors (c, erg.expand, erg.expand_length, ecart);
#endif
    }
  }

  //sorted_pair_node** pairs=(sorted_pair_node**)
  //  omalloc(delay_s*sizeof(sorted_pair_node*));
  c->introduceDelayedPairs (delay, delay_s);
  /*
     for(i=0;i<delay_s;i++)
     {
     poly p=delay[i];
     //if (rPar(c->r)==0)
     simplify_poly(p,c->r);
     sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
     si->i=-1;
     si->j=-1;
     if (!rField_is_Zp(c->r))
     {
     if (!c->nc)
     p=redTailShort(p, c->strat);
     p_Cleardenom(p, c->r);
     p_Content(p, c->r);
     }
     si->expected_length=pQuality(p,c,pLength(p));
     si->deg=pTotaldegree(p);
     si->lcm_of_lm=p;
     pairs[i]=si;
     }
     qsort(pairs,delay_s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
     c->apairs=spn_merge(c->apairs,c->pair_top+1,pairs,delay_s,c);
     c->pair_top+=delay_s; */
  omfree (delay);
  //omfree(pairs);
  return;
}

static int multi_reduction_clear_zeroes ( red_object *  los, int  losl, int  l, int  u  )

static

Definition at line 4565 of file tgb.cc.

{
  int deleted = 0;
  int i = l;
  int last = -1;
  while(i <= u)
  {
    if(los[i].p == NULL)
    {
      kBucketDestroy (&los[i].bucket);
//      delete los[i];//here we assume los are constructed with new
      //destroy resources, must be added here
      if(last >= 0)
      {
        memmove (los + (int) (last + 1 - deleted), los + (last + 1),
                 sizeof (red_object) * (i - 1 - last));
      }
      last = i;
      deleted++;
    }
    i++;
  }
  if((last >= 0) && (last != losl - 1))
    memmove (los + (int) (last + 1 - deleted), los + last + 1,
             sizeof (red_object) * (losl - 1 - last));
  return deleted;
}

static void multi_reduction_find ( red_object *  los, int  losl, slimgb_alg *  c, int  startf, find_erg &  erg  )

static

Definition at line 4503 of file tgb.cc.

{
  kStrategy strat = c->strat;

  assume (startf <= losl);
  assume ((startf == losl - 1)
          || (pLmCmp (los[startf].p, los[startf + 1].p) == -1));
  int i = startf;

  int j;
  while(i >= 0)
  {
    assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) <= 0));
    assume (is_valid_ro (los[i]));
    j = kFindDivisibleByInS_easy (strat, los[i]);
    if(j >= 0)
    {
      erg.to_reduce_u = i;
      erg.reduce_by = j;
      erg.fromS = TRUE;
      int i2 = fwbw (los, i);
      assume (pLmEqual (los[i].p, los[i2].p));
      assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
      assume (i >= i2);

      erg.to_reduce_l = i2;
      assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
      canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
      return;
    }
    if(j < 0)
    {
      //not reduceable, try to use this for reducing higher terms
      int i2 = fwbw (los, i);
      assume (pLmEqual (los[i].p, los[i2].p));
      assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
      assume (i >= i2);
      if(i2 != i)
      {
        erg.to_reduce_u = i - 1;
        erg.to_reduce_l = i2;
        erg.reduce_by = i;
        erg.fromS = FALSE;
        assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
        canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
        return;
      }
      i--;
    }
  }
  erg.reduce_by = -1;           //error code
  return;
}

static void multi_reduction_lls_trick ( red_object *  los, int  , slimgb_alg *  c, find_erg &  erg  )

static

Definition at line 4169 of file tgb.cc.

{
  erg.expand = NULL;
  BOOLEAN swap_roles;           //from reduce_by, to_reduce_u if fromS
  if(erg.fromS)
  {
    if(pLmEqual (c->strat->S[erg.reduce_by], los[erg.to_reduce_u].p))
    {
      wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
      int best = erg.to_reduce_u + 1;
/*
      for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--)
      {
  int qc=los[i].guess_quality(c);
  if (qc<quality_a)
  {
    best=i;
    quality_a=qc;
  }
      }
      if(best!=erg.to_reduce_u+1)
      {*/
      wlen_type qc;
      best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
      if(qc < quality_a)
      {
        los[best].flatten ();
        int b_pos = kBucketCanonicalize (los[best].bucket);
        los[best].p = los[best].bucket->buckets[b_pos];
        qc = pQuality (los[best].bucket->buckets[b_pos], c);
        if(qc < quality_a)
        {
          red_object h = los[erg.to_reduce_u];
          los[erg.to_reduce_u] = los[best];
          los[best] = h;
          swap_roles = TRUE;
        }
        else
          swap_roles = FALSE;
      }
      else
      {
        swap_roles = FALSE;
      }
    }
    else
    {
      if(erg.to_reduce_u > erg.to_reduce_l)
      {
        wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
#ifdef HAVE_PLURAL
        if((c->nc) && (!(rIsSCA (c->r))))
          quality_a =
            quality_of_pos_in_strat_S_mult_high (erg.reduce_by,
                                                 los[erg.to_reduce_u].p, c);
#endif
        int best = erg.to_reduce_u + 1;
        wlen_type qc;
        best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
        assume (qc == los[best].guess_quality (c));
        if(qc < quality_a)
        {
          los[best].flatten ();
          int b_pos = kBucketCanonicalize (los[best].bucket);
          los[best].p = los[best].bucket->buckets[b_pos];
          qc = pQuality (los[best].bucket->buckets[b_pos], c);
          //(best!=erg.to_reduce_u+1)
          if(qc < quality_a)
          {
            red_object h = los[erg.to_reduce_u];
            los[erg.to_reduce_u] = los[best];
            los[best] = h;
            erg.reduce_by = erg.to_reduce_u;
            erg.fromS = FALSE;
            erg.to_reduce_u--;
          }
        }
      }
      else
      {
        assume (erg.to_reduce_u == erg.to_reduce_l);
        wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
        wlen_type qc = los[erg.to_reduce_u].guess_quality (c);
        if(qc < 0)
          PrintS ("Wrong wlen_type");
        if(qc < quality_a)
        {
          int best = erg.to_reduce_u;
          los[best].flatten ();
          int b_pos = kBucketCanonicalize (los[best].bucket);
          los[best].p = los[best].bucket->buckets[b_pos];
          qc = pQuality (los[best].bucket->buckets[b_pos], c);
          assume (qc >= 0);
          if(qc < quality_a)
          {
            BOOLEAN exp = FALSE;
            if(qc <= 2)
            {
              //Print("\n qc is %lld \n",qc);
              exp = TRUE;
            }
            else
            {
              if(qc < quality_a / 2)
                exp = TRUE;
              else if(erg.reduce_by < c->n / 4)
                exp = TRUE;
            }
            if(exp)
            {
              poly clear_into;
              los[erg.to_reduce_u].flatten ();
              kBucketClear (los[erg.to_reduce_u].bucket, &clear_into,
                            &erg.expand_length);
              erg.expand = pCopy (clear_into);
              kBucketInit (los[erg.to_reduce_u].bucket, clear_into,
                           erg.expand_length);
              if(TEST_OPT_PROT)
                PrintS ("e");
            }
          }
        }
      }

      swap_roles = FALSE;
      return;
    }
  }
  else
  {
    if(erg.reduce_by > erg.to_reduce_u)
    {
      //then lm(rb)>= lm(tru) so =
      assume (erg.reduce_by == erg.to_reduce_u + 1);
      int best = erg.reduce_by;
      wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
      wlen_type qc;
      best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);

      if(qc < quality_a)
      {
        red_object h = los[erg.reduce_by];
        los[erg.reduce_by] = los[best];
        los[best] = h;
      }
      swap_roles = FALSE;
      return;
    }
    else
    {
      assume (!pLmEqual (los[erg.reduce_by].p, los[erg.to_reduce_l].p));
      assume (erg.to_reduce_u == erg.to_reduce_l);
      //further assume, that reduce_by is the above all other polys
      //with same leading term
      int il = erg.reduce_by;
      wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
      wlen_type qc;
      while((il > 0) && pLmEqual (los[il - 1].p, los[il].p))
      {
        il--;
        qc = los[il].guess_quality (c);
        if(qc < quality_a)
        {
          quality_a = qc;
          erg.reduce_by = il;
        }
      }
      swap_roles = FALSE;
    }
  }
  if(swap_roles)
  {
    if(TEST_OPT_PROT)
      PrintS ("b");
    poly clear_into;
    int new_length;
    int bp = erg.to_reduce_u;   //bucket_positon
    //kBucketClear(los[bp].bucket,&clear_into,&new_length);
    new_length = los[bp].clear_to_poly ();
    clear_into = los[bp].p;
    poly p = c->strat->S[erg.reduce_by];
    int j = erg.reduce_by;
    int old_length = c->strat->lenS[j]; // in view of S
    los[bp].p = p;
    kBucketInit (los[bp].bucket, p, old_length);
    wlen_type qal = pQuality (clear_into, c, new_length);
    int pos_in_c = -1;
    int z;
    int new_pos;
    new_pos = simple_posInS (c->strat, clear_into, new_length, qal);
    assume (new_pos <= j);
    for(z = c->n; z; z--)
    {
      if(p == c->S->m[z - 1])
      {
        pos_in_c = z - 1;
        break;
      }
    }

    int tdeg_full = -1;
    int tdeg = -1;
    if(pos_in_c >= 0)
    {
#ifdef TGB_RESORT_PAIRS
      c->used_b = TRUE;
      c->replaced[pos_in_c] = TRUE;
#endif
      tdeg = c->T_deg[pos_in_c];
      c->S->m[pos_in_c] = clear_into;
      c->lengths[pos_in_c] = new_length;
      c->weighted_lengths[pos_in_c] = qal;
      if(c->gcd_of_terms[pos_in_c] == NULL)
        c->gcd_of_terms[pos_in_c] = gcd_of_terms (clear_into, c->r);
      if(c->T_deg_full)
        tdeg_full = c->T_deg_full[pos_in_c] =
          c->pTotaldegree_full (clear_into);
      else
        tdeg_full = tdeg;
      c_S_element_changed_hook (pos_in_c, c);
    }
    else
    {
      if(c->eliminationProblem)
      {
        tdeg_full = c->pTotaldegree_full (clear_into);
        tdeg = c->pTotaldegree (clear_into);
      }
    }
    c->strat->S[j] = clear_into;
    c->strat->lenS[j] = new_length;

    assume (pLength (clear_into) == new_length);
    if(c->strat->lenSw != NULL)
      c->strat->lenSw[j] = qal;
    if(!rField_is_Zp (c->r))
    {
      p_Cleardenom (clear_into, c->r);  //should be unnecessary
      //p_Content(clear_into, c->r);
    }
    else
      pNorm (clear_into);
#ifdef FIND_DETERMINISTIC
    erg.reduce_by = j;
    //resort later see diploma thesis, find_in_S must be deterministic
    //during multireduction if spolys are only in the span of the
    //input polys
#else
    if(new_pos < j)
    {
      if(c->strat->honey)
        c->strat->ecartS[j] = tdeg_full - tdeg;
      move_forward_in_S (j, new_pos, c->strat);
      erg.reduce_by = new_pos;
    }
#endif
  }
}

void now_t_rep	(	const int &	arg_i,
		const int &	arg_j,
		slimgb_alg *	c
	)

Definition at line 3664 of file tgb.cc.

{
  int i, j;
  if(arg_i == arg_j)
  {
    return;
  }
  if(arg_i > arg_j)
  {
    i = arg_j;
    j = arg_i;
  }
  else
  {
    i = arg_i;
    j = arg_j;
  }
  c->states[j][i] = HASTREP;
}

static poly p_Init_Special ( const ring  r )

inlinestatic

Definition at line 137 of file tgb.cc.

{
  return p_Init (r, lm_bin);
}

static BOOLEAN pair_better ( sorted_pair_node *  a, sorted_pair_node *  b, slimgb_alg *  c = NULL  )

static

Definition at line 3966 of file tgb.cc.

{
  if(a->deg < b->deg)
    return TRUE;
  if(a->deg > b->deg)
    return FALSE;

  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
  if(comp == 1)
    return FALSE;
  if(-1 == comp)
    return TRUE;
  if(a->expected_length < b->expected_length)
    return TRUE;
  if(a->expected_length > b->expected_length)
    return FALSE;
  if(a->i + a->j < b->i + b->j)
    return TRUE;
  if(a->i + a->j > b->i + b->j)
    return FALSE;
  if(a->i < b->i)
    return TRUE;
  if(a->i > b->i)
    return FALSE;
  return TRUE;
}

static wlen_type pair_weighted_length ( int  i, int  j, slimgb_alg *  c  )

static

Definition at line 1375 of file tgb.cc.

{
  if((c->isDifficultField) && (c->eliminationProblem))
  {
    int c1 = slim_nsize (p_GetCoeff (c->S->m[i], c->r), c->r);
    int c2 = slim_nsize (p_GetCoeff (c->S->m[j], c->r), c->r);
    wlen_type el1 = c->weighted_lengths[i] / c1;
    assume (el1 != 0);
    assume (c->weighted_lengths[i] % c1 == 0);
    wlen_type el2 = c->weighted_lengths[j] / c2;
    assume (el2 != 0);
    //assume (c->weighted_lengths[j] % c2 == 0); // fails in Tst/Plural/dmod_lib.tst
    //should be * for function fields
    //return (c1+c2) * (el1+el2-2);
    wlen_type res = coeff_mult_size_estimate (c1, c2, c->r);
    res *= el1 + el2 - 2;
    return res;

  }
  if(c->isDifficultField)
  {
    //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
    //    slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
    if(!(TEST_V_COEFSTRAT))
    {
      wlen_type cs =
        coeff_mult_size_estimate (slim_nsize
                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
                                              c->r), c->r);
      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
    }
    else
    {

      wlen_type cs =
        coeff_mult_size_estimate (slim_nsize
                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
                                              c->r), c->r);
      cs *= cs;
      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
    }
  }
  if(c->eliminationProblem)
  {

    return (c->weighted_lengths[i] + c->weighted_lengths[j] - 2);
  }
  return c->lengths[i] + c->lengths[j] - 2;

}

wlen_type pELength	(	poly	p,
		slimgb_alg *	c,
		ring
	)

Definition at line 471 of file tgb.cc.

{
  if(p == NULL)
    return 0;
  wlen_type s = 0;
  poly pi = p;
  int dlm;
  dlm = c->pTotaldegree (p);
  s = 1;
  pi = p->next;

  while(pi)
  {
    int d = c->pTotaldegree (pi);
    if(d > dlm)
      s += 1 + d - dlm;
    else
      ++s;
    pi = pi->next;
  }
  return s;
}

static int pELength ( poly  p, slimgb_alg *  c, int  l  )

inlinestatic

Definition at line 535 of file tgb.cc.

{
  if(p == NULL)
    return 0;
  if((l > 0) && (elength_is_normal_length (p, c)))
    return l;
  return do_pELength (p, c);
}

static BOOLEAN pHasNotCFExtended ( poly  p1, poly  p2, poly  m  )

inlinestatic

Definition at line 4065 of file tgb.cc.

{

  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
    return FALSE;
  int i = 1;
  loop
  {
    if((pGetExp (p1, i) - pGetExp (m, i) > 0)
       && (pGetExp (p2, i) - pGetExp (m, i) > 0))
      return FALSE;
    if(i == (currRing->N))
      return TRUE;
    i++;
  }
}

static int poly_crit ( const void *  ap1, const void *  ap2  )

static

Definition at line 3124 of file tgb.cc.

{
  poly p1, p2;
  p1 = *((poly *) ap1);
  p2 = *((poly *) ap2);

  int c = pLmCmp (p1, p2);
  if(c != 0)
    return c;
  int l1 = pLength (p1);
  int l2 = pLength (p2);
  if(l1 < l2)
    return -1;
  if(l1 > l2)
    return 1;
  return 0;
}

static BOOLEAN polynomial_root ( poly  h, ring  r  )

static

Definition at line 109 of file tgb.cc.

{
  poly got = gcd_of_terms (h, r);
  BOOLEAN changed = FALSE;
  if((got != NULL) && (TEST_V_UPTORADICAL))
  {
    poly copy = p_Copy (got, r);
    //p_wrp(got,c->r);
    changed = monomial_root (got, r);
    if(changed)
    {
      poly div_by = pDivide (copy, got);
      poly iter = h;
      while(iter)
      {
        pExpVectorSub (iter, div_by);
        pIter (iter);
      }
      p_Delete (&div_by, r);
      if(TEST_OPT_PROT)
        PrintS ("U");
    }
    p_Delete (&copy, r);
  }
  p_Delete (&got, r);
  return changed;
}

static poly pOne_Special ( const ring  r = currRing )

inlinestatic

Definition at line 142 of file tgb.cc.

{
  poly rc = p_Init_Special (r);
  pSetCoeff0 (rc, n_Init (1, r));
  return rc;
}

static int posInPairs ( sorted_pair_node **  p, int  pn, sorted_pair_node *  qe, slimgb_alg *  c, int  an = 0  )

static

Definition at line 711 of file tgb.cc.

{
  if(pn == 0)
    return 0;

  int length = pn - 1;
  int i;
  //int an = 0;
  int en = length;

  if(pair_better (qe, p[en], c))
    return length + 1;

  while(1)
  {
    //if (an >= en-1)
    if(en - 1 <= an)
    {
      if(pair_better (p[an], qe, c))
        return an;
      return en;
    }
    i = (an + en) / 2;
    if(pair_better (p[i], qe, c))
      en = i;
    else
      an = i;
  }
}

static wlen_type pQuality ( poly  p, slimgb_alg *  c, int  l = -1  )

inlinestatic

Definition at line 544 of file tgb.cc.

{
  if(l < 0)
    l = pLength (p);
  if(c->isDifficultField)
  {
    if(c->eliminationProblem)
    {
      wlen_type cs;
      number coef = pGetCoeff (p);
      if(rField_is_Q (currRing))
      {
        cs = nlQlogSize (coef, currRing->cf);
      }
      else
        cs = nSize (coef);
      wlen_type erg = cs;
      if(TEST_V_COEFSTRAT)
        erg *= cs;
      //erg*=cs;//for quadratic
      erg *= pELength (p, c, l);
      //FIXME: not quadratic coeff size
      //return cs*pELength(p,c,l);
      return erg;
    }
    //PrintS("I am here");
    wlen_type r = pSLength (p, l);
    assume (r >= 0);
    return r;
  }
  if(c->eliminationProblem)
    return pELength (p, c, l);
  return l;
}

static wlen_type pSLength ( poly  p, int  l  )

inlinestatic

Definition at line 197 of file tgb.cc.

{
  wlen_type c;
  number coef = pGetCoeff (p);
  if(rField_is_Q (currRing))
  {
    c = nlQlogSize (coef, currRing->cf);
  }
  else
    c = nSize (coef);
  if(!(TEST_V_COEFSTRAT))
  {
    return (wlen_type) c *(wlen_type) l /*pLength(p) */ ;
  }
  else
  {
    wlen_type res = l;
    res *= c;
    res *= c;
    return res;
  }
}

static int pTotaldegree_full ( poly  p )

inlinestatic

Definition at line 579 of file tgb.cc.

{
  int r = 0;
  while(p)
  {
    int d = pTotaldegree (p);
    r = si_max (r, d);
    pIter (p);
  }
  return r;
}

static wlen_type quality_of_pos_in_strat_S ( int  pos, slimgb_alg *  c  )

inlinestatic

Definition at line 4146 of file tgb.cc.

{
  if(c->strat->lenSw != NULL)
    return c->strat->lenSw[pos];
  return c->strat->lenS[pos];
}

static wlen_type quality_of_pos_in_strat_S_mult_high ( int  pos, poly  high, slimgb_alg *  c  )

inlinestatic

Definition at line 4155 of file tgb.cc.

{
  poly m = pOne ();
  pExpVectorDiff (m, high, c->strat->S[pos]);
  poly product = nc_mm_Mult_pp (m, c->strat->S[pos], c->r);
  wlen_type erg = pQuality (product, c);
  pDelete (&m);
  pDelete (&product);
  return erg;
}

sorted_pair_node* quick_pop_pair

(

slimgb_alg *

c

)

Definition at line 3904 of file tgb.cc.

{
  if(c->pair_top < 0)
    return NULL;
  else
    return (c->apairs[c->pair_top--]);
}

static int red_object_better_gen ( const void *  ap, const void *  bp  )

static

Definition at line 665 of file tgb.cc.

{
  return (pLmCmp (((red_object *) ap)->p, ((red_object *) bp)->p));
}

static poly redNF2 ( poly  h, slimgb_alg *  c, int &  len, number &  m, int  n = 0  )

static

Definition at line 1840 of file tgb.cc.

{
  m = nInit (1);
  if(h == NULL)
    return NULL;

  assume (len == pLength (h));
  kStrategy strat = c->strat;
  if(0 > strat->sl)
  {
    return h;
  }
  int j;

  LObject P (h);
  P.SetShortExpVector ();
  P.bucket = kBucketCreate (currRing);
  // BOOLEAN corr=lenS_correct(strat);
  kBucketInit (P.bucket, P.p, len /*pLength(P.p) */ );
  //wlen_set lenSw=(wlen_set) c->strat->lenS;
  //FIXME: plainly wrong
  //strat->lenS;
  //if (strat->lenSw!=NULL)
  //  lenSw=strat->lenSw;
  //int max_pos=simple_posInS(strat,P.p);
  loop
  {
    //int dummy=strat->sl;
    j = kFindDivisibleByInS_easy (strat, P.p, P.sev);
    //j=kFindDivisibleByInS(strat,&dummy,&P);
    if((j >= 0) && ((!n) ||
                    ((strat->lenS[j] <= n) &&
                     ((strat->lenSw == NULL) || (strat->lenSw[j] <= n)))))
    {
      nNormalize (pGetCoeff (P.p));
#ifdef KDEBUG
      if(TEST_OPT_DEBUG)
      {
        PrintS ("red:");
        wrp (h);
        PrintS (" with ");
        wrp (strat->S[j]);
      }
#endif

      number coef = kBucketPolyRed (P.bucket, strat->S[j],
                                    strat->lenS[j] /*pLength(strat->S[j]) */ ,
                                    strat->kNoether);
      number m2 = nMult (m, coef);
      nDelete (&m);
      m = m2;
      nDelete (&coef);
      h = kBucketGetLm (P.bucket);

      if(h == NULL)
      {
        len = 0;
        kBucketDestroy (&P.bucket);
        return NULL;
      }
      P.p = h;
      P.t_p = NULL;
      P.SetShortExpVector ();
#ifdef KDEBUG
      if(TEST_OPT_DEBUG)
      {
        PrintS ("\nto:");
        wrp (h);
        PrintLn ();
      }
#endif
    }
    else
    {
      kBucketClear (P.bucket, &(P.p), &len);
      kBucketDestroy (&P.bucket);
      pNormalize (P.p);
      assume (len == (pLength (P.p)));
      return P.p;
    }
  }
}

static poly redNFTail ( poly  h, const int  sl, kStrategy  strat, int  len  )

static

Definition at line 2975 of file tgb.cc.

{
  BOOLEAN nc = rIsPluralRing (currRing);
  if(h == NULL)
    return NULL;
  pTest (h);
  if(0 > sl)
    return h;
  if(pNext (h) == NULL)
    return h;

  int j;
  poly res = h;
  poly act = res;
  LObject P (pNext (h));
  pNext (res) = NULL;
  P.bucket = kBucketCreate (currRing);
  len--;
  h = P.p;
  if(len <= 0)
    len = pLength (h);
  kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ );
  pTest (h);
  loop
  {
    P.p = h;
    P.t_p = NULL;
    P.SetShortExpVector ();
    loop
    {
      //int dummy=strat->sl;
      j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P);
      if(j >= 0)
      {
#ifdef REDTAIL_PROT
        PrintS ("r");
#endif
        nNormalize (pGetCoeff (P.p));
#ifdef KDEBUG
        if(TEST_OPT_DEBUG)
        {
          PrintS ("red tail:");
          wrp (h);
          PrintS (" with ");
          wrp (strat->S[j]);
        }
#endif
        number coef;
        pTest (strat->S[j]);
#ifdef HAVE_PLURAL
        if(nc)
        {
          nc_BucketPolyRed_Z (P.bucket, strat->S[j], &coef);
        }
        else
#endif
          coef = kBucketPolyRed (P.bucket, strat->S[j],
                                 strat->lenS[j] /*pLength(strat->S[j]) */ ,
                                 strat->kNoether);
        pMult_nn (res, coef);
        nDelete (&coef);
        h = kBucketGetLm (P.bucket);
        pTest (h);
        if(h == NULL)
        {
#ifdef REDTAIL_PROT
          PrintS (" ");
#endif
          kBucketDestroy (&P.bucket);
          return res;
        }
        pTest (h);
        P.p = h;
        P.t_p = NULL;
        P.SetShortExpVector ();
#ifdef KDEBUG
        if(TEST_OPT_DEBUG)
        {
          PrintS ("\nto tail:");
          wrp (h);
          PrintLn ();
        }
#endif
      }
      else
      {
#ifdef REDTAIL_PROT
        PrintS ("n");
#endif
        break;
      }
    }                           /* end loop current mon */
    //   poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
    //act->next=tmp;pIter(act);
    act->next = kBucketExtractLm (P.bucket);
    pIter (act);
    h = kBucketGetLm (P.bucket);
    if(h == NULL)
    {
#ifdef REDTAIL_PROT
      PrintS (" ");
#endif
      kBucketDestroy (&P.bucket);
      return res;
    }
    pTest (h);
  }
}

static poly redTailShort ( poly  h, kStrategy  strat  )

static

Definition at line 1923 of file tgb.cc.

{
  if(h == NULL)
    return NULL;                //n_Init(1,currRing);
  if(TEST_V_MODPSOLVSB)
  {
    bit_reduce (pNext (h), strat->tailRing);
  }
  int i;
  int len = pLength (h);
  for(i = 0; i <= strat->sl; i++)
  {
    if((strat->lenS[i] > 2)
       || ((strat->lenSw != NULL) && (strat->lenSw[i] > 2)))
      break;
  }
  return (redNFTail (h, i - 1, strat, len));
}

static void replace_pair ( int &  i, int &  j, slimgb_alg *  c  )

static

Definition at line 1217 of file tgb.cc.

{
  if(i < 0)
    return;
  c->soon_free = NULL;
  int syz_deg;
  poly lm = pOne ();

  pLcm (c->S->m[i], c->S->m[j], lm);
  pSetm (lm);

  int *i_con = make_connections (i, j, lm, c);

  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
  {
    if(i_con[n] == j)
    {
      now_t_rep (i, j, c);
      omFree (i_con);
      p_Delete (&lm, c->r);
      return;
    }
  }

  int *j_con = make_connections (j, i, lm, c);

//   if(c->n>1)
//   {
//     if (i_con[1]>=0)
//       i=i_con[1];
//     else
//     {
//       if (j_con[1]>=0)
//         j=j_con[1];
//     }
  // }

  int sugar = syz_deg = c->pTotaldegree (lm);

  p_Delete (&lm, c->r);
  if(c->T_deg_full)             //Sugar
  {
    int t_i = c->T_deg_full[i] - c->T_deg[i];
    int t_j = c->T_deg_full[j] - c->T_deg[j];
    sugar += si_max (t_i, t_j);
    //Print("\n max: %d\n",max(t_i,t_j));
  }

  for(int m = 0; ((m < c->n) && (i_con[m] >= 0)); m++)
  {
    if(c->T_deg_full != NULL)
    {
      int s1 = c->T_deg_full[i_con[m]] + syz_deg - c->T_deg[i_con[m]];
      if(s1 > sugar)
        continue;
    }
    if(c->weighted_lengths[i_con[m]] < c->weighted_lengths[i])
      i = i_con[m];
  }
  for(int m = 0; ((m < c->n) && (j_con[m] >= 0)); m++)
  {
    if(c->T_deg_full != NULL)
    {
      int s1 = c->T_deg_full[j_con[m]] + syz_deg - c->T_deg[j_con[m]];
      if(s1 > sugar)
        continue;
    }
    if(c->weighted_lengths[j_con[m]] < c->weighted_lengths[j])
      j = j_con[m];
  }

  //can also try dependend search
  omfree (i_con);
  omfree (j_con);
  return;
}

int search_red_object_pos	(	red_object *	a,
		int	top,
		red_object *	key
	)

Definition at line 4593 of file tgb.cc.

{
  int an = 0;
  int en = top;
  if(top == -1)
    return 0;
  if(pLmCmp (key->p, a[top].p) == 1)
    return top + 1;
  int i;
  loop
  {
    if(an >= en - 1)
    {
      if(pLmCmp (key->p, a[an].p) == -1)
        return an;
      return en;
    }
    i = (an + en) / 2;
    if(pLmCmp (key->p, a[i].p) == -1)
      en = i;
    else
      an = i;
  }
}

static void shorten_tails ( slimgb_alg *  c, poly  monom  )

static

Definition at line 3718 of file tgb.cc.

{
  return;
// BOOLEAN corr=lenS_correct(c->strat);
  for(int i = 0; i < c->n; i++)
  {
    //enter tail

    if(c->S->m[i] == NULL)
      continue;
    poly tail = c->S->m[i]->next;
    poly prev = c->S->m[i];
    BOOLEAN did_something = FALSE;
    while((tail != NULL) && (pLmCmp (tail, monom) >= 0))
    {
      if(p_LmDivisibleBy (monom, tail, c->r))
      {
        did_something = TRUE;
        prev->next = tail->next;
        tail->next = NULL;
        p_Delete (&tail, c->r);
        tail = prev;
        //PrintS("Shortened");
        c->lengths[i]--;
      }
      prev = tail;
      tail = tail->next;
    }
    if(did_something)
    {
      int new_pos;
      wlen_type q;
      q = pQuality (c->S->m[i], c, c->lengths[i]);
      new_pos = simple_posInS (c->strat, c->S->m[i], c->lengths[i], q);

      int old_pos = -1;
      //assume new_pos<old_pos
      for(int z = 0; z <= c->strat->sl; z++)
      {
        if(c->strat->S[z] == c->S->m[i])
        {
          old_pos = z;
          break;
        }
      }
      if(old_pos == -1)
        for(int z = new_pos - 1; z >= 0; z--)
        {
          if(c->strat->S[z] == c->S->m[i])
          {
            old_pos = z;
            break;
          }
        }
      assume (old_pos >= 0);
      assume (new_pos <= old_pos);
      assume (pLength (c->strat->S[old_pos]) == c->lengths[i]);
      c->strat->lenS[old_pos] = c->lengths[i];
      if(c->strat->lenSw)
        c->strat->lenSw[old_pos] = q;
      if(new_pos < old_pos)
        move_forward_in_S (old_pos, new_pos, c->strat);
      length_one_crit (c, i, c->lengths[i]);
    }
  }
}

static int simple_posInS ( kStrategy  strat, poly  p, int  len, wlen_type  wlen  )

static

Definition at line 1310 of file tgb.cc.

{
  if(strat->sl == -1)
    return 0;
  if(strat->lenSw)
    return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat->lenSw,
                       strat->S);
  return pos_helper (strat, p, len, strat->lenS, strat->S);
}

static void simplify_poly ( poly  p, ring  r  )

static

Definition at line 59 of file tgb.cc.

{
  assume (r == currRing);
  if(!rField_is_Zp (r))
  {
    p_Cleardenom (p, r);
    //p_Content(p,r); //is a duplicate call, but belongs here
  }
  else
    pNorm (p);
}

int slim_nsize	(	number	n,
		ring	r
	)

Definition at line 73 of file tgb.cc.

{
  if(rField_is_Zp (r))
  {
    return 1;
  }
  if(rField_is_Q (r))
  {
    return nlQlogSize (n, r->cf);
  }
  else
  {
    return n_Size (n, r);
  }
}

static void sort_region_down ( red_object *  los, int  l, int  u, slimgb_alg *    )

static

Definition at line 4618 of file tgb.cc.

{
  int r_size = u - l + 1;
  qsort (los + l, r_size, sizeof (red_object), red_object_better_gen);
  int i;
  int *new_indices = (int *) omalloc ((r_size) * sizeof (int));
  int bound = 0;
  BOOLEAN at_end = FALSE;
  for(i = l; i <= u; i++)
  {
    if(!(at_end))
    {
      bound = new_indices[i - l] =
        bound + search_red_object_pos (los + bound, l - bound - 1, los + i);
      if(bound == l)
        at_end = TRUE;
    }
    else
    {
      new_indices[i - l] = l;
    }
  }
  red_object *los_region =
    (red_object *) omalloc (sizeof (red_object) * (u - l + 1));
  for(int i = 0; i < r_size; i++)
  {
    new_indices[i] += i;
    los_region[i] = los[l + i];
    assume ((i == 0) || (new_indices[i] > new_indices[i - 1]));
  }

  i = r_size - 1;
  int j = u;
  int j2 = l - 1;
  while(i >= 0)
  {
    if(new_indices[i] == j)
    {
      los[j] = los_region[i];
      i--;
      j--;
    }
    else
    {
      assume (new_indices[i] < j);
      los[j] = los[j2];
      assume (j2 >= 0);
      j2--;
      j--;
    }
  }
  omfree (los_region);
  omfree (new_indices);
}

sorted_pair_node** spn_merge	(	sorted_pair_node **	p,
		int	pn,
		sorted_pair_node **	q,
		int	qn,
		slimgb_alg *	c
	)

Definition at line 751 of file tgb.cc.

{
  int i;
  int *a = (int *) omalloc (qn * sizeof (int));
//   int mc;
//   PrintS("Debug\n");
//   for(mc=0;mc<qn;mc++)
// {
//     wrp(q[mc]->lcm_of_lm);
//     PrintS("\n");
// }
//    PrintS("Debug they are in\n");
//   for(mc=0;mc<pn;mc++)
// {
//     wrp(p[mc]->lcm_of_lm);
//     PrintS("\n");
// }
  int lastpos = 0;
  for(i = 0; i < qn; i++)
  {
    lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos - 1, 0));
    //   cout<<lastpos<<"\n";
    a[i] = lastpos;
  }
  if((pn + qn) > c->max_pairs)
  {
    p =
      (sorted_pair_node **) omrealloc (p,
                                       2 * (pn +
                                            qn) *
                                       sizeof (sorted_pair_node *));
    c->max_pairs = 2 * (pn + qn);
  }
  for(i = qn - 1; i >= 0; i--)
  {
    size_t size;
    if(qn - 1 > i)
      size = (a[i + 1] - a[i]) * sizeof (sorted_pair_node *);
    else
      size = (pn - a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0
    memmove (p + a[i] + (1 + i), p + a[i], size);
    p[a[i] + i] = q[i];
  }
  omfree (a);
  return p;
}

static BOOLEAN state_is ( calc_state  state, const int &  i, const int &  j, slimgb_alg *  c  )

static

Definition at line 3939 of file tgb.cc.

{
  assume (0 <= arg_i);
  assume (0 <= arg_j);
  assume (arg_i < c->n);
  assume (arg_j < c->n);
  if(arg_i == arg_j)
  {
    return (TRUE);
  }
  if(arg_i > arg_j)
  {
    return (c->states[arg_i][arg_j] == state);
  }
  else
    return (c->states[arg_j][arg_i] == state);
}

static void super_clean_top_of_pair_list ( slimgb_alg *  c )

static

Definition at line 3912 of file tgb.cc.

{
  while((c->pair_top >= 0)
        && (c->apairs[c->pair_top]->i >= 0)
        &&
        (good_has_t_rep
         (c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, c)))
  {
    free_sorted_pair_node (c->apairs[c->pair_top], c->r);
    c->pair_top--;
  }
}

void t2ippa	(	poly *	ip,
		int *	ia,
		exp_number_builder &	e
	)

obsolete

Definition at line 2047 of file tgb.cc.

{

  int o = 0;
  t2ippa_rec (ip, ia, e.top_level, o);
}

void t2ippa_rec	(	poly *	ip,
		int *	ia,
		poly_tree_node *	k,
		int &	offset
	)

obsolete

Definition at line 2033 of file tgb.cc.

{
  if(!k)
    return;
  t2ippa_rec (ip, ia, k->l, offset);
  ip[offset] = k->p;
  ia[k->n] = offset;
  ++offset;

  t2ippa_rec (ip, ia, k->r, offset);
  delete k;
}

ideal t_rep_gb	(	ring	r,
		ideal	arg_I,
		int	syz_comp,
		BOOLEAN	F4_mode
	)

Definition at line 3561 of file tgb.cc.

{
  assume (r == currRing);
  ring orig_ring = r;
  int pos;
  ring new_ring = rAssure_TDeg (orig_ring, 1, rVar (orig_ring), pos);
  ideal s_h;
  if(orig_ring != new_ring)
  {
    rChangeCurrRing (new_ring);
    s_h = idrCopyR_NoSort (arg_I, orig_ring, new_ring);
    idTest (s_h);
    /*int i;
       for(i=0;i<IDELEMS(s_h);i++)
       {
       poly p=s_h->m[i];
       while(p)
       {
       p_Setm(p,new_ring);
       pIter(p);
       }
       } */
  }
  else
  {
    s_h = id_Copy (arg_I, orig_ring);
  }

  ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos);
  ideal result;
  if(orig_ring != new_ring)
  {
    idTest (s_result);
    rChangeCurrRing (orig_ring);
    result = idrMoveR_NoSort (s_result, new_ring, orig_ring);

    idTest (result);
    //rChangeCurrRing(new_ring);
    rDelete(new_ring);
    //rChangeCurrRing(orig_ring);
  }
  else
    result = s_result;
  idTest (result);
  return result;
}

int terms_sort_crit	(	const void *	a,
		const void *	b
	)

Definition at line 2068 of file tgb.cc.

{
  return -pLmCmp (*((poly *) a), *((poly *) b));
}

static int tgb_pair_better_gen ( const void *  ap, const void *  bp  )

static

Definition at line 3993 of file tgb.cc.

{
  sorted_pair_node *a = *((sorted_pair_node **) ap);
  sorted_pair_node *b = *((sorted_pair_node **) bp);
  assume ((a->i > a->j) || (a->i < 0));
  assume ((b->i > b->j) || (b->i < 0));
  if(a->deg < b->deg)
    return -1;
  if(a->deg > b->deg)
    return 1;

  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);

  if(comp == 1)
    return 1;
  if(-1 == comp)
    return -1;
  if(a->expected_length < b->expected_length)
    return -1;
  if(a->expected_length > b->expected_length)
    return 1;
  if(a->i + a->j < b->i + b->j)
    return -1;
  if(a->i + a->j > b->i + b->j)
    return 1;
  if(a->i < b->i)
    return -1;
  if(a->i > b->i)
    return 1;
  return 0;
}

int tgb_pair_better_gen2	(	const void *	ap,
		const void *	bp
	)

Definition at line 680 of file tgb.cc.

{
  return (-tgb_pair_better_gen (ap, bp));
}

sorted_pair_node* top_pair

(

slimgb_alg *

c

)

Definition at line 3880 of file tgb.cc.

{
  while(c->pair_top >= 0)
  {
    super_clean_top_of_pair_list (c);   //yeah, I know, it's odd that I use a different proc here
    if((c->is_homog) && (c->pair_top >= 0)
       && (c->apairs[c->pair_top]->deg >= c->lastCleanedDeg + 2))
    {
      int upper = c->apairs[c->pair_top]->deg - 1;
      c->cleanDegs (c->lastCleanedDeg + 1, upper);
      c->lastCleanedDeg = upper;
    }
    else
    {
      break;
    }
  }

  if(c->pair_top < 0)
    return NULL;
  else
    return (c->apairs[c->pair_top]);
}

static BOOLEAN trivial_syzygie ( int  pos1, int  pos2, poly  bound, slimgb_alg *  c  )

static

Definition at line 800 of file tgb.cc.

{
  poly p1 = c->S->m[pos1];
  poly p2 = c->S->m[pos2];

  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
    return FALSE;
  int i = 1;
  poly m = NULL;
  poly gcd1 = c->gcd_of_terms[pos1];
  poly gcd2 = c->gcd_of_terms[pos2];

  if((gcd1 != NULL) && (gcd2 != NULL))
  {
    gcd1->next = gcd2;          //may ordered incorrect
    m = gcd_of_terms (gcd1, c->r);
    gcd1->next = NULL;
  }
  if(m == NULL)
  {
    loop
    {
      if(pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i))
        return FALSE;
      if(i == (currRing->N))
      {
        //PrintS("trivial");
        return TRUE;
      }
      i++;
    }
  }
  else
  {
    loop
    {
      if(pGetExp (p1, i) - pGetExp (m, i) + pGetExp (p2, i) >
         pGetExp (bound, i))
      {
        pDelete (&m);
        return FALSE;
      }
      if(i == (currRing->N))
      {
        pDelete (&m);
        //PrintS("trivial");
        return TRUE;
      }
      i++;
    }
  }
}

Variable Documentation

const int bundle_size = 100

static

Definition at line 36 of file tgb.cc.

const int bundle_size_noro = 10000

static

Definition at line 37 of file tgb.cc.

const int delay_factor = 3

static

Definition at line 38 of file tgb.cc.

omBin lm_bin = NULL

static

Definition at line 41 of file tgb.cc.

---

Generated on Mon Aug 3 2015 12:41:07 by   doxygen 1.8.9.1 for Singular a9b8ed0|M