tgb_internal.h File Reference

#include <omalloc/omalloc.h>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <misc/options.h>
#include <coeffs/modulop.h>
#include <polys/monomials/p_polys.h>
#include <polys/monomials/ring.h>
#include <polys/kbuckets.h>
#include <kernel/ideals.h>
#include <kernel/polys.h>
#include <kernel/GBEngine/kutil.h>
#include <kernel/GBEngine/kInline.h>
#include <kernel/GBEngine/kstd1.h>

Go to the source code of this file.

Data Structures
class	PolySimple
class	DataNoroCacheNode< number_type >
class	MonRedResNP< number_type >
struct	sorted_pair_node
struct	poly_list_node
struct	int_pair_node
struct	monom_poly
struct	mp_array_list
struct	poly_array_list
class	slimgb_alg
class	red_object
class	reduction_step
	makes on each red_object in a region a single_step More...
class	simple_reducer
struct	find_erg
class	NoroCacheNode
class	DenseRow
class	SparseRow< number_type >
class	DataNoroCacheNode< number_type >
class	TermNoroDataNode< number_type >
class	NoroCache< number_type >
class	CoefIdx< number_type >
class	ModPMatrixBackSubstProxyOnArray< number_type >
class	ModPMatrixProxyOnArray< number_type >
class	ModPMatrixBackSubstProxyOnArray< number_type >

Macros
#define	USE_NORO   1
#define	FULLREDUCTIONS
#define	HANS_IDEA
#define	REDTAIL_S
#define	PAR_N   100
#define	PAR_N_F4   5000
#define	AC_NEW_MIN   2
#define	AC_FLATTEN   1
#define	NORO_CACHE   1
#define	NORO_SPARSE_ROWS_PRE   1
#define	NORO_NON_POLY   1
#define	npInit   n_Init
#define	npNeg   n_InpNeg
#define	npInvers   n_Invers
#define	npMult   n_Mult
#define	npIsOne   n_IsOne
#define	npIsZero   n_IsZero
#define	slim_prec_cast(a)   (unsigned int) (unsigned long) (a)
#define	F4mat_to_number_type(a)   (number_type) slim_prec_cast(a)
#define	LIKELY(expression)   (expression)
#define	UNLIKELY(expression)   (expression)

Typedefs
typedef unsigned short	tgb_uint16
typedef unsigned char	tgb_uint8
typedef unsigned int	tgb_uint32

Enumerations
enum	calc_state { UNCALCULATED, HASTREP }

Functions
template<class len_type , class set_type >
int	pos_helper (kStrategy strat, poly p, len_type len, set_type setL, polyset set)
void	free_sorted_pair_node (sorted_pair_node *s, ring r)
ideal	do_t_rep_gb (ring r, 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)
void	clean_top_of_pair_list (slimgb_alg *c)
int	slim_nsize (number n, ring r)
sorted_pair_node *	quick_pop_pair (slimgb_alg *c)
sorted_pair_node *	top_pair (slimgb_alg *c)
sorted_pair_node **	add_to_basis_ideal_quotient (poly h, slimgb_alg *c, int *ip)
sorted_pair_node **	spn_merge (sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
int	kFindDivisibleByInS_easy (kStrategy strat, const red_object &obj)
int	tgb_pair_better_gen2 (const void *ap, const void *bp)
int	kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev)
template<class number_type >
SparseRow< number_type > *	noro_red_to_non_poly_t (poly p, int &len, NoroCache< number_type > *cache, slimgb_alg *c)
template<class number_type >
MonRedResNP< number_type >	noro_red_mon_to_non_poly (poly t, NoroCache< number_type > *cache, slimgb_alg *c)
template<class number_type >
SparseRow< number_type > *	convert_to_sparse_row (number_type *temp_array, int temp_size, int non_zeros)
template<class number_type >
void	add_coef_times_sparse (number_type *const temp_array, int temp_size, SparseRow< number_type > *row, number coef)
template<class number_type >
void	add_coef_times_dense (number_type *const temp_array, int temp_size, const number_type *row, int len, number coef)
template<class number_type >
void	add_dense (number_type *const temp_array, int temp_size, const number_type *row, int len)
template<class number_type >
void	sub_dense (number_type *const temp_array, int temp_size, const number_type *row, int len)
template<class number_type >
void	add_sparse (number_type *const temp_array, int temp_size, SparseRow< number_type > *row)
template<class number_type >
void	sub_sparse (number_type *const temp_array, int temp_size, SparseRow< number_type > *row)
template<class number_type >
SparseRow< number_type > *	noro_red_to_non_poly_dense (MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
template<class number_type >
void	write_coef_times_xx_idx_to_buffer (CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen, const number coef)
template<class number_type >
void	write_coef_times_xx_idx_to_buffer_dense (CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen, const number coef)
template<class number_type >
void	write_coef_idx_to_buffer_dense (CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
template<class number_type >
void	write_minus_coef_idx_to_buffer_dense (CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
template<class number_type >
void	write_coef_idx_to_buffer (CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
template<class number_type >
void	write_minus_coef_idx_to_buffer (CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
template<class number_type >
SparseRow< number_type > *	noro_red_to_non_poly_sparse (MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
wlen_type	pELength (poly p, ring r)
int	terms_sort_crit (const void *a, const void *b)
template<class number_type >
void	write_poly_to_row (number_type *row, poly h, poly *terms, int tn, ring r)
template<class number_type >
poly	row_to_poly (number_type *row, poly *terms, int tn, ring r)
template<class number_type >
int	modP_lastIndexRow (number_type *row, int ncols)
template<class number_type >
int	term_nodes_sort_crit (const void *a, const void *b)
template<class number_type >
void	simplest_gauss_modp (number_type *a, int nrows, int ncols)
template<class number_type >
void	noro_step (poly *p, int &pn, slimgb_alg *c)

---

Data Structure Documentation

struct sorted_pair_node

Definition at line 155 of file tgb_internal.h.

Data Fields
int	deg
wlen_type	expected_length
int	i
int	j
poly	lcm_of_lm

struct poly_list_node

Definition at line 179 of file tgb_internal.h.

Data Fields
poly_list_node *	next
poly	p

struct int_pair_node

Definition at line 185 of file tgb_internal.h.

Data Fields
int	a
int	b
int_pair_node *	next

struct monom_poly

Definition at line 191 of file tgb_internal.h.

Data Fields
poly	f
poly	m

struct mp_array_list

Definition at line 196 of file tgb_internal.h.

Data Fields
monom_poly *	mp
mp_array_list *	next
int	size

struct poly_array_list

Definition at line 204 of file tgb_internal.h.

Data Fields
poly_array_list *	next
poly *	p
int	size

struct find_erg

Definition at line 383 of file tgb_internal.h.

Data Fields
poly	expand
int	expand_length
BOOLEAN	fromS
int	reduce_by
int	to_reduce_l
int	to_reduce_u

class TermNoroDataNode

template<class number_type>
class TermNoroDataNode< number_type >

Definition at line 580 of file tgb_internal.h.

Data Fields
DataNoroCacheNode< number_type > *	node
poly	t

Macro Definition Documentation

#define AC_FLATTEN   1

Definition at line 24 of file tgb_internal.h.

#define AC_NEW_MIN   2

Definition at line 23 of file tgb_internal.h.

#define F4mat_to_number_type

(

a

)

(number_type) slim_prec_cast(a)

Definition at line 425 of file tgb_internal.h.

#define FULLREDUCTIONS

Definition at line 15 of file tgb_internal.h.

#define HANS_IDEA

Definition at line 16 of file tgb_internal.h.

#define LIKELY

(

expression

)

(expression)

Definition at line 837 of file tgb_internal.h.

#define NORO_CACHE   1

Definition at line 30 of file tgb_internal.h.

#define NORO_NON_POLY   1

Definition at line 32 of file tgb_internal.h.

#define NORO_SPARSE_ROWS_PRE   1

Definition at line 31 of file tgb_internal.h.

#define npInit   n_Init

Definition at line 73 of file tgb_internal.h.

#define npInvers   n_Invers

Definition at line 75 of file tgb_internal.h.

#define npIsOne   n_IsOne

Definition at line 77 of file tgb_internal.h.

#define npIsZero   n_IsZero

Definition at line 78 of file tgb_internal.h.

#define npMult   n_Mult

Definition at line 76 of file tgb_internal.h.

#define npNeg   n_InpNeg

Definition at line 74 of file tgb_internal.h.

#define PAR_N   100

Definition at line 21 of file tgb_internal.h.

#define PAR_N_F4   5000

Definition at line 22 of file tgb_internal.h.

#define REDTAIL_S

Definition at line 20 of file tgb_internal.h.

#define slim_prec_cast

(

a

)

(unsigned int) (unsigned long) (a)

Definition at line 424 of file tgb_internal.h.

#define UNLIKELY

(

expression

)

(expression)

Definition at line 838 of file tgb_internal.h.

#define USE_NORO   1

Definition at line 10 of file tgb_internal.h.

Typedef Documentation

typedef unsigned short tgb_uint16

Definition at line 426 of file tgb_internal.h.

typedef unsigned int tgb_uint32

Definition at line 428 of file tgb_internal.h.

typedef unsigned char tgb_uint8

Definition at line 427 of file tgb_internal.h.

Enumeration Type Documentation

enum calc_state

Enumerator
UNCALCULATED
HASTREP

Definition at line 322 of file tgb_internal.h.

  {
    UNCALCULATED,
    HASTREP//,
    //UNIMPORTANT,
    //SOONTREP
  };

Function Documentation

template<class number_type >

void add_coef_times_dense	(	number_type *const	temp_array,
		int	temp_size,
		const number_type *	row,
		int	len,
		number	coef
	)

Definition at line 955 of file tgb_internal.h.

{
  int j;
  const number_type* const coef_array=row;
  //int* const idx_array=row->idx_array;
  //const int len=temp_size;
  tgb_uint32 buffer[256];
  const tgb_uint32 prime=n_GetChar(currRing->cf);
  const tgb_uint32 c=F4mat_to_number_type(coef);
  assume(!(npIsZero(coef,currRing->cf)));
  for(j=0;j<len;j=j+256)
  {
    const int bound=std::min(j+256,len);
    int i;
    int bpos=0;
    for(i=j;i<bound;i++)
    {
      buffer[bpos++]=coef_array[i];
    }
    int bpos_bound=bound-j;
    for(i=0;i<bpos_bound;i++)
    {
       buffer[i]*=c;
     }
    for(i=0;i<bpos_bound;i++)
    {
       buffer[i]=buffer[i]%prime;
    }
    bpos=0;
    for(i=j;i<bound;i++)
    {
      //int idx=idx_array[i];
      assume(bpos<256);
      //assume(!(npIsZero((number) buffer[bpos])));
      STATISTIC(n_Add); temp_array[i]=F4mat_to_number_type(npAddM((number)(long) temp_array[i], (number)(long) buffer[bpos++],currRing->cf));
      assume(i<temp_size);
    }

  }
}

template<class number_type >

void add_coef_times_sparse	(	number_type *const	temp_array,
		int	temp_size,
		SparseRow< number_type > *	row,
		number	coef
	)

Definition at line 909 of file tgb_internal.h.

{
  int j;
  number_type* const coef_array=row->coef_array;
  int* const idx_array=row->idx_array;
  const int len=row->len;
  tgb_uint32 buffer[256];
  const tgb_uint32 prime=n_GetChar(currRing->cf);
  const tgb_uint32 c=F4mat_to_number_type(coef);
  assume(!(npIsZero(coef,currRing->cf)));
  for(j=0;j<len;j=j+256)
  {
    const int bound=std::min(j+256,len);
    int i;
    int bpos=0;
    for(i=j;i<bound;i++)
    {
      buffer[bpos++]=coef_array[i];
    }
    int bpos_bound=bound-j;
    for(i=0;i<bpos_bound;i++)
    {
       buffer[i]*=c;
     }
    for(i=0;i<bpos_bound;i++)
    {
       buffer[i]=buffer[i]%prime;
    }
    bpos=0;
    for(i=j;i<bound;i++)
    {
      int idx=idx_array[i];
      assume(bpos<256);
      assume(!(npIsZero((number)(long) buffer[bpos],currRing->cf)));
      STATISTIC(n_Add); temp_array[idx]=F4mat_to_number_type(npAddM((number)(long) temp_array[idx], (number)(long) buffer[bpos++],currRing->cf));
      assume(idx<temp_size);
    }

  }
}

template<class number_type >

void add_dense	(	number_type *const	temp_array,
		int	temp_size,
		const number_type *	row,
		int	len
	)

Definition at line 1001 of file tgb_internal.h.

{
  //int j;
  //const number_type* const coef_array=row;
  //int* const idx_array=row->idx_array;
  //const int len=temp_size;
  //tgb_uint32 buffer[256];
  //const tgb_uint32 prime=npPrimeM;
  //const tgb_uint32 c=F4mat_to_number_type(coef);

  int i;
  for(i=0;i<len;i++)
  {
      STATISTIC(n_Add); temp_array[i]=F4mat_to_number_type(npAddM((number)(long) temp_array[i], (number)(long) row[i],currRing->cf));
      assume(i<temp_size);
  }

}

template<class number_type >

void add_sparse	(	number_type *const	temp_array,
		int	temp_size,
		SparseRow< number_type > *	row
	)

Definition at line 1050 of file tgb_internal.h.

{
  int j;

          number_type* const coef_array=row->coef_array;
          int* const idx_array=row->idx_array;
          const int len=row->len;
        for(j=0;j<len;j++)
        {
          int idx=idx_array[j];
          STATISTIC(n_Add); temp_array[idx]=F4mat_to_number_type(   (number_type)(long)npAddM((number) (long)temp_array[idx],(number)(long) coef_array[j],currRing->cf));
          assume(idx<temp_size);
        }
}

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;
  }
}

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--;
  }
}

template<class number_type >

SparseRow<number_type>* convert_to_sparse_row	(	number_type *	temp_array,
		int	temp_size,
		int	non_zeros
	)

Definition at line 841 of file tgb_internal.h.

                                                                                                                              {
SparseRow<number_type>* res=new SparseRow<number_type>(non_zeros);
//int pos=0;
//Print("denseness:%f\n",((double) non_zeros/(double) temp_size));
number_type* it_coef=res->coef_array;
int* it_idx=res->idx_array;
#if 0
for(i=0;i<cache->nIrreducibleMonomials;i++){
  if (!(0==temp_array[i])){

    res->idx_array[pos]=i;
    res->coef_array[pos]=temp_array[i];

    pos++;
    non_zeros--;
    if (non_zeros==0) break;
  }

}
#else
int64* start=(int64*) ((void*)temp_array);
int64* end;
const int multiple=sizeof(int64)/sizeof(number_type);
if (temp_size==0) end=start;

else
{
  int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
  assume(temp_size_rounded>=temp_size);
  assume(temp_size_rounded%multiple==0);
  assume(temp_size_rounded<temp_size+multiple);
  number_type* nt_end=temp_array+temp_size_rounded;
  end=(int64*)((void*)nt_end);
}
int64* it=start;
while(it!=end)
{
  if UNLIKELY((*it)!=0)
  {
    int small_i;
    const int temp_index=((number_type*)((void*) it))-temp_array;
    const int bound=temp_index+multiple;
    number_type c;
    for(small_i=temp_index;small_i<bound;small_i++)
    {
      if((c=temp_array[small_i])!=0)
      {
        //res->idx_array[pos]=small_i;
        //res->coef_array[pos]=temp_array[small_i];
        (*(it_idx++))=small_i;
        (*(it_coef++))=c;
        //pos++;
        non_zeros--;

      }
      if UNLIKELY(non_zeros==0) break;
    }

  }
  ++it;
}
#endif
return res;
}

ideal do_t_rep_gb	(	ring	r,
		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);
}

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);
}

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;
}

template<class number_type >

int modP_lastIndexRow	(	number_type *	row,
		int	ncols
	)

Definition at line 1482 of file tgb_internal.h.

{
  int lastIndex;
  const number_type zero=0;//npInit(0);
  for(lastIndex=ncols-1;lastIndex>=0;lastIndex--)
  {
    if (!(row[lastIndex]==zero))
    {
      return lastIndex;
    }
  }
  return -1;
}

template<class number_type >

MonRedResNP<number_type> noro_red_mon_to_non_poly	(	poly	t,
		NoroCache< number_type > *	cache,
		slimgb_alg *	c
	)

Definition at line 755 of file tgb_internal.h.

{
  MonRedResNP<number_type> res_holder;


    DataNoroCacheNode<number_type>* ref=cache->getCacheReference(t);
    if (ref!=NULL)
    {
      res_holder.coef=p_GetCoeff(t,c->r);

      res_holder.ref=ref;
      p_Delete(&t,c->r);
      return res_holder;
    }

  unsigned long sev=p_GetShortExpVector(t,currRing);
  int i=kFindDivisibleByInS_easy(c->strat,t,sev);
  if (i>=0)
  {
    number coef_bak=p_GetCoeff(t,c->r);

    p_SetCoeff(t,npInit(1,c->r->cf),c->r);
    assume(npIsOne(p_GetCoeff(c->strat->S[i],c->r),c->r->cf));
    number coefstrat=p_GetCoeff(c->strat->S[i],c->r);


    poly exp_diff=cache->temp_term;
    p_ExpVectorDiff(exp_diff,t,c->strat->S[i],c->r);
    p_SetCoeff(exp_diff,npNeg(npInvers(coefstrat,c->r->cf),c->r->cf),c->r);
    p_Setm(exp_diff,c->r);
    assume(c->strat->S[i]!=NULL);

    poly res;
    res=pp_Mult_mm(pNext(c->strat->S[i]),exp_diff,c->r);

    int len=c->strat->lenS[i]-1;
    SparseRow<number_type>* srow;
    srow=noro_red_to_non_poly_t<number_type>(res,len,cache,c);
    ref=cache->insert(t,srow);
    p_Delete(&t,c->r);


    res_holder.coef=coef_bak;
    res_holder.ref=ref;
    return res_holder;

  } else {
    number coef_bak=p_GetCoeff(t,c->r);
    number one=npInit(1, c->r->cf);
    p_SetCoeff(t,one,c->r);

    res_holder.ref=cache->insertAndTransferOwnerShip(t,c->r);
    assume(res_holder.ref!=NULL);
    res_holder.coef=coef_bak;

    return res_holder;

  }

}

template<class number_type >

SparseRow<number_type>* noro_red_to_non_poly_dense	(	MonRedResNP< number_type > *	mon,
		int	len,
		NoroCache< number_type > *	cache
	)

Definition at line 1083 of file tgb_internal.h.

{
  size_t temp_size_bytes=cache->nIrreducibleMonomials*sizeof(number_type)+8;//use 8bit int for testing
   assume(sizeof(int64)==8);
   cache->ensureTempBufferSize(temp_size_bytes);
   number_type* temp_array=(number_type*) cache->tempBuffer;//omalloc(cache->nIrreducibleMonomials*sizeof(number_type));
   int temp_size=cache->nIrreducibleMonomials;
   memset(temp_array,0,temp_size_bytes);
   number minus_one=npInit(-1,currRing->cf);
   int i;
   for(i=0;i<len;i++)
   {
     MonRedResNP<number_type> red=mon[i];
     if ( /*(*/ red.ref /*)*/ )
     {
       if (red.ref->row)
       {
         SparseRow<number_type>* row=red.ref->row;
         number coef=red.coef;
         if (row->idx_array)
         {
           if (!((coef==(number)(long) 1)||(coef==minus_one)))
           {
             add_coef_times_sparse(temp_array,temp_size,row,coef);
           }
           else
           {
             if (coef==(number)(long) 1)
             {
               add_sparse(temp_array,temp_size,row);
             }
             else
             {
               sub_sparse(temp_array,temp_size,row);
             }
           }
         }
         else
         //TODO: treat, 1,-1
         if (!((coef==(number)(long) 1)||(coef==minus_one)))
         {
          add_coef_times_dense(temp_array,temp_size,row->coef_array,row->len,coef);
         }
         else
         {
           if (coef==(number)(long)1)
             add_dense(temp_array,temp_size,row->coef_array,row->len);
           else
           {
             assume(coef==minus_one);
             sub_dense(temp_array,temp_size,row->coef_array,row->len);
             //add_coef_times_dense(temp_array,temp_size,row->coef_array,row->len,coef);
           }
         }
       }
       else
       {
         if (red.ref->value_len==NoroCache<number_type>::backLinkCode)
         {
           STATISTIC(n_Add); temp_array[red.ref->term_index]=F4mat_to_number_type( npAddM((number)(long) temp_array[red.ref->term_index],red.coef,currRing->cf));
         }
         else
         {
           //PrintS("third case\n");
         }
       }
     }
   }
   int non_zeros=0;
   for(i=0;i<cache->nIrreducibleMonomials;i++)
   {
     //if (!(temp_array[i]==0)){
     //  non_zeros++;
     //}
     assume(((temp_array[i]!=0)==0)|| (((temp_array[i]!=0)==1)));
     non_zeros+=(temp_array[i]!=0);
   }

   if (non_zeros==0)
   {
     //omfree(mon);
     return NULL;
   }
   SparseRow<number_type>* res=new SparseRow<number_type>(temp_size,temp_array);//convert_to_sparse_row(temp_array,temp_size, non_zeros);

   //omfree(temp_array);


   return res;
}

template<class number_type >

SparseRow<number_type>* noro_red_to_non_poly_sparse	(	MonRedResNP< number_type > *	mon,
		int	len,
		NoroCache< number_type > *	cache
	)

Definition at line 1272 of file tgb_internal.h.

{
  int i;
  int together=0;
  for(i=0;i<len;i++)
  {
    MonRedResNP<number_type> red=mon[i];
    if ((red.ref) &&( red.ref->row))
    {
      together+=red.ref->row->len;
    }
    else
    {
      if ((red.ref) &&(red.ref->value_len==NoroCache<number_type>::backLinkCode))
      together++;
    }
  }
  //PrintS("here\n");
  if (together==0) return 0;
  //PrintS("there\n");
  cache->ensureTempBufferSize(together*sizeof(CoefIdx<number_type>));
  CoefIdx<number_type>* pairs=(CoefIdx<number_type>*) cache->tempBuffer; //omalloc(together*sizeof(CoefIdx<number_type>));
  int pos=0;
  const number one=npInit(1, currRing->cf);
  const number minus_one=npInit(-1, currRing->cf);
  for(i=0;i<len;i++)
  {
    MonRedResNP<number_type> red=mon[i];
    if ((red.ref) &&( red.ref->row))
    {
      //together+=red.ref->row->len;
      int* idx_array=red.ref->row->idx_array;
      number_type* coef_array=red.ref->row->coef_array;
      int rlen=red.ref->row->len;
      number coef=red.coef;
      if (idx_array)
      {
        if ((coef!=one)&&(coef!=minus_one))
        {
          write_coef_times_xx_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen, coef);
        }
        else
        {
          if (coef==one)
          {
            write_coef_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen);
          }
          else
          {
            assume(coef==minus_one);
            write_minus_coef_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen);
          }
        }
      }
      else
      {
        if ((coef!=one)&&(coef!=minus_one))
        {
          write_coef_times_xx_idx_to_buffer_dense(pairs,pos,coef_array,rlen,coef);
        }
        else
        {
          if (coef==one)
            write_coef_idx_to_buffer_dense(pairs,pos,coef_array,rlen);
          else
          {
            assume(coef==minus_one);
            write_minus_coef_idx_to_buffer_dense(pairs,pos,coef_array,rlen);
          }
        }
      }
    }
    else
    {
      if ((red.ref) &&(red.ref->value_len==NoroCache<number_type>::backLinkCode))
      {
        CoefIdx<number_type> ci;
        ci.coef=F4mat_to_number_type(red.coef);
        ci.idx=red.ref->term_index;
        pairs[pos++]=ci;
      }
    }
  }
  assume(pos<=together);
  together=pos;

  std::sort(pairs,pairs+together);

  int act=0;

  assume(pairs[0].coef!=0);
  for(i=1;i<together;i++)
  {
    if (pairs[i].idx!=pairs[act].idx)
    {
      if (pairs[act].coef!=0)
      {
        act=act+1;
      }
      pairs[act]=pairs[i];
    }
    else
    {
      STATISTIC(n_Add); pairs[act].coef=F4mat_to_number_type(npAddM((number)(long)pairs[act].coef,(number)(long)pairs[i].coef,currRing->cf));
    }
  }

  if (pairs[act].coef==0)
  {
    act--;
  }
  int sparse_row_len=act+1;
  //Print("res len:%d",sparse_row_len);
  if (sparse_row_len==0) {return NULL;}
  SparseRow<number_type>* res=new SparseRow<number_type>(sparse_row_len);
  {
    number_type* coef_array=res->coef_array;
    int* idx_array=res->idx_array;
    for(i=0;i<sparse_row_len;i++)
    {
      idx_array[i]=pairs[i].idx;
      coef_array[i]=pairs[i].coef;
    }
  }
  //omfree(pairs);

  return res;
}

template<class number_type >

SparseRow< number_type > * noro_red_to_non_poly_t	(	poly	p,
		int &	len,
		NoroCache< number_type > *	cache,
		slimgb_alg *	c
	)

Definition at line 1400 of file tgb_internal.h.

                                                                                                                                          {
  assume(len==pLength(p));
  if (p==NULL)
  {
    len=0;
    return NULL;
  }

  MonRedResNP<number_type>* mon=(MonRedResNP<number_type>*) omalloc(len*sizeof(MonRedResNP<number_type>));
  int i=0;
  double max_density=0.0;
  while(p!=NULL)
  {
    poly t=p;
    pIter(p);
    pNext(t)=NULL;

    MonRedResNP<number_type> red=noro_red_mon_to_non_poly(t,cache,c);
    if ((red.ref) && (red.ref->row))
    {
      double act_density=(double) red.ref->row->len;
      act_density/=(double) cache->nIrreducibleMonomials;
      max_density=std::max(act_density,max_density);
    }
    mon[i]=red;
    i++;
  }

  assume(i==len);
  len=i;
  bool dense=true;
  if (max_density<0.3) dense=false;
  if (dense){
    SparseRow<number_type>* res=noro_red_to_non_poly_dense(mon,len,cache);
    omfree(mon);
    return res;
  } else   {
      SparseRow<number_type>* res=noro_red_to_non_poly_sparse(mon,len,cache);
      omfree(mon);
      return res;
    }
  //in the loop before nIrreducibleMonomials increases, so position here is important

}

template<class number_type >

void noro_step	(	poly *	p,
		int &	pn,
		slimgb_alg *	c
	)

Definition at line 1779 of file tgb_internal.h.

                                                                         {
  //Print("Input rows %d\n",pn);
  int j;
  if (TEST_OPT_PROT)
  {
    Print("Input rows %d\n",pn);
  }

  NoroCache<number_type> cache;

  SparseRow<number_type> ** srows=(SparseRow<number_type>**) omAlloc(pn*sizeof(SparseRow<number_type>*));
  int non_zeros=0;
  for(j=0;j<pn;j++)
  {
    poly h=p[j];
    int h_len=pLength(h);
    //number coef;
    srows[non_zeros]=noro_red_to_non_poly_t<number_type>(h,h_len,&cache,c);
    if (srows[non_zeros]!=NULL) non_zeros++;
  }
  std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
  cache.collectIrreducibleMonomials(irr_nodes);
  //now can build up terms array
  //Print("historic irred Mon%d\n",cache.nIrreducibleMonomials);
  int n=irr_nodes.size();//cache.countIrreducibleMonomials();
  cache.nIrreducibleMonomials=n;
  if (TEST_OPT_PROT)
  {
    Print("Irred Mon:%d\n",n);
    Print("red Mon:%d\n",cache.nReducibleMonomials);
  }
  TermNoroDataNode<number_type>* term_nodes=(TermNoroDataNode<number_type>*) omalloc(n*sizeof(TermNoroDataNode<number_type>));

  for(j=0;j<n;j++)
  {
    assume(irr_nodes[j]!=NULL);
    assume(irr_nodes[j]->value_len==NoroCache<number_type>::backLinkCode);
    term_nodes[j].t=irr_nodes[j]->value_poly;
    assume(term_nodes[j].t!=NULL);
    term_nodes[j].node=irr_nodes[j];
  }

  qsort(term_nodes,n,sizeof(TermNoroDataNode<number_type>),term_nodes_sort_crit<number_type>);
  poly* terms=(poly*) omalloc(n*sizeof(poly));

  int* old_to_new_indices=(int*) omalloc(cache.nIrreducibleMonomials*sizeof(int));
  for(j=0;j<n;j++)
  {
    old_to_new_indices[term_nodes[j].node->term_index]=j;
    term_nodes[j].node->term_index=j;
    terms[j]=term_nodes[j].t;
  }

  //if (TEST_OPT_PROT)
  //  Print("Evaluate Rows \n");
  pn=non_zeros;
  number_type* number_array=(number_type*) omalloc0(n*pn*sizeof(number_type));

  for(j=0;j<pn;j++)
  {
    int i;
    number_type* row=number_array+n*j;
    /*for(i=0;i<n;i++)
    {
      row[i]=zero;
    }*/

    SparseRow<number_type>* srow=srows[j];

    if (srow)
    {
      int* const idx_array=srow->idx_array;
      number_type* const coef_array=srow->coef_array;
      const int len=srow->len;
      if (srow->idx_array)
      {
        for(i=0;i<len;i++)
        {
         int idx=old_to_new_indices[idx_array[i]];
         row[idx]=F4mat_to_number_type(coef_array[i]);
        }
      }
      else
      {
        for(i=0;i<len;i++)
        {
          row[old_to_new_indices[i]]=F4mat_to_number_type(coef_array[i]);
        }
      }
      delete srow;
    }
  }

  //static int export_n=0;
  //export_mat(number_array,pn,n,"mat%i.py",++export_n);
  simplest_gauss_modp(number_array,pn,n);

  int p_pos=0;
  for(j=0;j<pn;j++){
    poly h=row_to_poly(number_array+j*n,terms,n,c->r);
    if(h!=NULL){
      p[p_pos++]=h;
    }
  }
  pn=p_pos;
  omfree(terms);
  omfree(term_nodes);
  omfree(number_array);
  #ifdef NORO_NON_POLY
  omfree(srows);
  omfree(old_to_new_indices);
  #endif
  //don't forget the rank

}

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;
}

wlen_type pELength	(	poly	p,
		ring	r
	)

template<class len_type , class set_type >

int pos_helper	(	kStrategy	strat,
		poly	p,
		len_type	len,
		set_type	setL,
		polyset	set
	)

Definition at line 394 of file tgb_internal.h.

{
  //Print("POSHELER:%d",sizeof(wlen_type));
  int length=strat->sl;
  int i;
  int an = 0;
  int en= length;

  if ((len>setL[length])
      || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
    return length+1;

  loop
  {
    if (an >= en-1)
    {
      if ((len<setL[an])
          || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an;
      return en;
    }
    i=(an+en) / 2;
    if ((len<setL[i])
        || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
    //else if ((len>setL[i])
    //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
    else an=i;
  }

}

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--]);
}

template<class number_type >

poly row_to_poly	(	number_type *	row,
		poly *	terms,
		int	tn,
		ring	r
	)

Definition at line 1466 of file tgb_internal.h.

                                                                                             {
  poly h=NULL;
  int j;
  number_type zero=0;//;npInit(0);
  for(j=tn-1;j>=0;j--){
    if (!(zero==(row[j]))){
      poly t=terms[j];
      t=p_LmInit(t,r);
      p_SetCoeff(t,(number)(long) row[j],r);
      pNext(t)=h;
      h=t;
    }

  }
  return h;
}

template<class number_type >

void simplest_gauss_modp	(	number_type *	a,
		int	nrows,
		int	ncols
	)

Definition at line 1757 of file tgb_internal.h.

{
  //use memmoves for changing rows
  //if (TEST_OPT_PROT)
  //    PrintS("StartGauss\n");
  ModPMatrixProxyOnArray<number_type> mat(a,nrows,ncols);

  int c=0;
  int r=0;
  while(mat.findPivot(r,c)){
    //int pivot=find_pivot()
      mat.reduceOtherRowsForward(r);
    r++;
    c++;
  }
  ModPMatrixBackSubstProxyOnArray<number_type> backmat(mat);
  backmat.backwardSubstitute();
  //backward substitutions
  //if (TEST_OPT_PROT)
  //PrintS("StopGauss\n");
}

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);
  }
}

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;
}

template<class number_type >

void sub_dense	(	number_type *const	temp_array,
		int	temp_size,
		const number_type *	row,
		int	len
	)

Definition at line 1025 of file tgb_internal.h.

{
  //int j;
  //const number_type* const coef_array=row;
  //int* const idx_array=row->idx_array;
  //const int len=temp_size;
  //tgb_uint32 buffer[256];
  //const tgb_uint32 prime=npPrimeM;
  //const tgb_uint32 c=F4mat_to_number_type(coef);

  int i;
  for(i=0;i<len;i++)
  {

      STATISTIC(n_Sub); temp_array[i]=F4mat_to_number_type(npSubM((number)(long) temp_array[i], (number)(long) row[i],currRing->cf));
      assume(i<temp_size);
  }

}

template<class number_type >

void sub_sparse	(	number_type *const	temp_array,
		int	temp_size,
		SparseRow< number_type > *	row
	)

Definition at line 1068 of file tgb_internal.h.

{
  int j;

          number_type* const coef_array=row->coef_array;
          int* const idx_array=row->idx_array;
          const int len=row->len;
        for(j=0;j<len;j++)
        {
          int idx=idx_array[j];
          STATISTIC(n_Sub); temp_array[idx]=F4mat_to_number_type(  (number_type)(long) npSubM((number) (long)temp_array[idx],(number)(long) coef_array[j],currRing->cf));
          assume(idx<temp_size);
        }
}

template<class number_type >

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

Definition at line 1495 of file tgb_internal.h.

{
  return -pLmCmp(((TermNoroDataNode<number_type>*) a)->t,((TermNoroDataNode<number_type>*) b)->t);
}

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

Definition at line 2068 of file tgb.cc.

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

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]);
}

template<class number_type >

void write_coef_idx_to_buffer	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		int *const	idx_array,
		number_type *const	coef_array,
		const int	rlen
	)

Definition at line 1247 of file tgb_internal.h.

{
  int j;
  for(j=0;j<rlen;j++)
  {
    assume(coef_array[j]!=0);
    CoefIdx<number_type> ci;
    ci.coef=coef_array[j];
    ci.idx=idx_array[j];
    pairs[pos++]=ci;
  }
}

template<class number_type >

void write_coef_idx_to_buffer_dense	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		number_type *const	coef_array,
		const int	rlen
	)

Definition at line 1212 of file tgb_internal.h.

{
  int j;

  for(j=0;j<rlen;j++)
  {
    if (coef_array[j]!=0)
    {
      assume(coef_array[j]!=0);
      CoefIdx<number_type> ci;
      ci.coef=coef_array[j];
      assume(ci.coef!=0);
      ci.idx=j;
      pairs[pos++]=ci;
    }
  }
}

template<class number_type >

void write_coef_times_xx_idx_to_buffer	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		int *const	idx_array,
		number_type *const	coef_array,
		const int	rlen,
		const number	coef
	)

Definition at line 1183 of file tgb_internal.h.

{
  int j;
  for(j=0;j<rlen;j++)
  {
    assume(coef_array[j]!=0);
    CoefIdx<number_type> ci;
    STATISTIC(n_Mult); ci.coef=F4mat_to_number_type(npMultM((number)(long) coef,(number)(long) coef_array[j],currRing->cf));
    ci.idx=idx_array[j];
    pairs[pos++]=ci;
  }
}

template<class number_type >

void write_coef_times_xx_idx_to_buffer_dense	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		number_type *const	coef_array,
		const int	rlen,
		const number	coef
	)

Definition at line 1195 of file tgb_internal.h.

{
  int j;

  for(j=0;j<rlen;j++)
  {
    if (coef_array[j]!=0)
    {
      assume(coef_array[j]!=0);
      CoefIdx<number_type> ci;
      STATISTIC(n_Mult); ci.coef=F4mat_to_number_type(npMultM((number)(long) coef,(number)(long) coef_array[j],currRing->cf));
      assume(ci.coef!=0);
      ci.idx=j;
      pairs[pos++]=ci;
    }
  }
}

template<class number_type >

void write_minus_coef_idx_to_buffer	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		int *const	idx_array,
		number_type *const	coef_array,
		const int	rlen
	)

Definition at line 1260 of file tgb_internal.h.

{
  int j;
  for(j=0;j<rlen;j++)
  {
    assume(coef_array[j]!=0);
    CoefIdx<number_type> ci;
    STATISTIC(n_InpNeg); ci.coef=F4mat_to_number_type(npNegM((number)(unsigned long)coef_array[j],currRing->cf));  // FIXME: inplace negation! // TODO: check if this is not a bug!?
    ci.idx=idx_array[j];
    pairs[pos++]=ci;
  }
}

template<class number_type >

void write_minus_coef_idx_to_buffer_dense	(	CoefIdx< number_type > *const	pairs,
		int &	pos,
		number_type *const	coef_array,
		const int	rlen
	)

Definition at line 1230 of file tgb_internal.h.

{
  int j;

  for(j=0;j<rlen;j++)
  {
    if (coef_array[j]!=0)
    {
      assume(coef_array[j]!=0);
      CoefIdx<number_type> ci;
      STATISTIC(n_InpNeg); ci.coef=F4mat_to_number_type(npNegM((number)(long) coef_array[j],currRing->cf)); // FIXME: inplace negation! // TODO: check if this is not a bug!?
      assume(ci.coef!=0);
      ci.idx=j;
      pairs[pos++]=ci;
    }
  }
}

template<class number_type >

void write_poly_to_row	(	number_type *	row,
		poly	h,
		poly *	terms,
		int	tn,
		ring	r
	)

Definition at line 1453 of file tgb_internal.h.

                                                                                                          {
  //poly* base=row;
  while(h!=NULL){
    //Print("h:%i\n",h);
    number coef=p_GetCoeff(h,r);
    poly* ptr_to_h=(poly*) bsearch(&h,terms,tn,sizeof(poly),terms_sort_crit);
    assume(ptr_to_h!=NULL);
    int pos=ptr_to_h-terms;
    row[pos]=F4mat_to_number_type(coef);
    //number_type_array[base+pos]=coef;
    pIter(h);
  }
}

---

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