My Project  debian-1:4.1.1-p2+ds-4build4
Data Structures | Macros | Functions
syzextra.cc File Reference

New implementations for the computation of syzygies and resolutions. More...

#include "kernel/mod2.h"
#include <string.h>
#include "syzextra.h"
#include "omalloc/omalloc.h"
#include "misc/intvec.h"
#include "misc/options.h"
#include "coeffs/coeffs.h"
#include "polys/monomials/p_polys.h"
#include "polys/monomials/ring.h"
#include "polys/simpleideals.h"
#include "polys/kbuckets.h"
#include "polys/sbuckets.h"
#include "polys/operations/p_Mult_q.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/polys.h"
#include "kernel/GBEngine/syz.h"
#include "kernel/ideals.h"
#include "kernel/oswrapper/timer.h"
#include "Singular/tok.h"
#include "Singular/ipid.h"
#include "Singular/lists.h"
#include "Singular/attrib.h"
#include "Singular/ipshell.h"
#include <stdio.h>
#include <stdlib.h>

Go to the source code of this file.

Data Structures

class  SBucketWrapper
 
class  CDivisorEnumerator
 TODO: More...
 
class  CDivisorEnumerator2
 TODO: More...
 

Macros

#define _GNU_SOURCE   /*for qsort_r on cygwin, must be before system includes*/
 
#define RTIMER_BENCHMARKING   0
 
#define qsort_my(m, s, ss, r, cmp)   qsort(m, s, ss, cmp)
 

Functions

static FORCE_INLINE poly pp_Add_qq (const poly a, const poly b, const ring R)
 
static FORCE_INLINE poly p_VectorProductLT (poly s, const ideal &L, const ideal &T, const ring &R)
 
static FORCE_INLINE int atGetInt (idhdl rootRingHdl, const char *attribute, long def)
 
static int cmp_c_ds (const void *p1, const void *p2)
 
static FORCE_INLINE poly myp_Head (const poly p, const bool bIgnoreCoeff, const ring r)
 
poly leadmonom (const poly p, const ring r, const bool bSetZeroComp)
 return a new term: leading coeff * leading monomial of p with 0 leading component! More...
 
poly p_Tail (const poly p, const ring r)
 return the tail of a given polynomial or vector returns NULL if input is NULL, otherwise the result is a new polynomial/vector in the ring r More...
 
ideal id_Tail (const ideal id, const ring r)
 return the tail of a given ideal or module returns NULL if input is NULL, otherwise the result is a new ideal/module in the ring r NOTE: the resulting rank is autocorrected More...
 
void Sort_c_ds (const ideal id, const ring r)
 inplace sorting of the module (ideal) id wrt <_(c,ds) More...
 
bool my_p_LmCmp (poly a, poly b, const ring r)
 
static BOOLEAN _p_LmDivisibleByNoComp (const poly a, const poly b, const poly c, const ring r)
 _p_LmDivisibleByNoComp for a | b*c More...
 

Detailed Description

New implementations for the computation of syzygies and resolutions.

ABSTRACT: Computation of Syzygies due to Schreyer

Author
Oleksandr Motsak

Definition in file syzextra.cc.

Macro Definition Documentation

◆ _GNU_SOURCE

#define _GNU_SOURCE   /*for qsort_r on cygwin, must be before system includes*/

Definition at line 18 of file syzextra.cc.

◆ qsort_my

#define qsort_my (   m,
  s,
  ss,
  r,
  cmp 
)    qsort(m, s, ss, cmp)

◆ RTIMER_BENCHMARKING

#define RTIMER_BENCHMARKING   0

Definition at line 61 of file syzextra.cc.

Function Documentation

◆ _p_LmDivisibleByNoComp()

static BOOLEAN _p_LmDivisibleByNoComp ( const poly  a,
const poly  b,
const poly  c,
const ring  r 
)
inlinestatic

_p_LmDivisibleByNoComp for a | b*c

Definition at line 1516 of file syzextra.cc.

1517 {
1518  int i=r->VarL_Size - 1;
1519  unsigned long divmask = r->divmask;
1520  unsigned long la, lb;
1521 
1522  if (r->VarL_LowIndex >= 0)
1523  {
1524  i += r->VarL_LowIndex;
1525  do
1526  {
1527  la = a->exp[i];
1528  lb = b->exp[i] + c->exp[i];
1529  if ((la > lb) ||
1530  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
1531  {
1533  return FALSE;
1534  }
1535  i--;
1536  }
1537  while (i>=r->VarL_LowIndex);
1538  }
1539  else
1540  {
1541  do
1542  {
1543  la = a->exp[r->VarL_Offset[i]];
1544  lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
1545  if ((la > lb) ||
1546  (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
1547  {
1549  return FALSE;
1550  }
1551  i--;
1552  }
1553  while (i>=0);
1554  }
1555 #ifdef HAVE_RINGS
1556  assume( !rField_is_Ring(r) ); // not implemented for rings...!
1557 #endif
1558  return TRUE;
1559 }
#define TRUE
Definition: auxiliary.h:98
#define FALSE
Definition: auxiliary.h:94
int i
Definition: cfEzgcd.cc:125
CanonicalForm b
Definition: cfModGcd.cc:4044
#define assume(x)
Definition: mod2.h:390
BOOLEAN p_DebugLmDivisibleByNoComp(poly a, poly b, ring r)
Definition: pDebug.cc:141
#define pDivAssume(x)
Definition: p_polys.h:1228
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477

◆ atGetInt()

static FORCE_INLINE int atGetInt ( idhdl  rootRingHdl,
const char *  attribute,
long  def 
)
static

Definition at line 158 of file syzextra.cc.

159 {
160  return ((int)(long)(atGet(rootRingHdl, attribute, INT_CMD, (void*)def)));
161 }
void * atGet(idhdl root, const char *name, int t, void *defaultReturnValue)
Definition: attrib.cc:131
@ INT_CMD
Definition: tok.h:96

◆ cmp_c_ds()

static int cmp_c_ds ( const void *  p1,
const void *  p2 
)
static

Definition at line 168 of file syzextra.cc.

168  { void *R = currRing;
169 #endif
170  assume(R != NULL);
171  const int YES = 1;
172  const int NO = -1;
173 
174  const ring r = (const ring) R; // TODO/NOTE: the structure is known: C, lp!!!
175 
176  assume( r == currRing ); // for now...
177 
178  const poly a = *(const poly*)p1;
179  const poly b = *(const poly*)p2;
180 
181  assume( a != NULL );
182  assume( b != NULL );
183 
184  p_LmTest(a, r);
185  p_LmTest(b, r);
186 
187 
188  const signed long iCompDiff = p_GetComp(a, r) - p_GetComp(b, r);
189 
190  // TODO: test this!!!!!!!!!!!!!!!!
191 
192  //return -( compare (c, qsorts) )
193 
194  if( iCompDiff > 0 )
195  return YES;
196 
197  if( iCompDiff < 0 )
198  return NO;
199 
200  assume( iCompDiff == 0 );
201 
202  const signed long iDegDiff = p_Totaldegree(a, r) - p_Totaldegree(b, r);
203 
204  if( iDegDiff > 0 )
205  return YES;
206 
207  if( iDegDiff < 0 )
208  return NO;
209 
210  assume( iDegDiff == 0 );
211 
212  for (int v = rVar(r); v > 0; v--)
213  {
214  assume( v > 0 );
215  assume( v <= rVar(r) );
216 
217  const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
218 
219  if( d > 0 )
220  return YES;
221 
222  if( d < 0 )
223  return NO;
224 
225  assume( d == 0 );
226  }
227 
228  return 0;
229 }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define p_GetComp(p, r)
Definition: monomials.h:71
#define NULL
Definition: omList.c:10
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469
#define p_LmTest(p, r)
Definition: p_polys.h:164
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1453
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
#define R
Definition: sirandom.c:26

◆ id_Tail()

ideal id_Tail ( const ideal  id,
const ring  r 
)

return the tail of a given ideal or module returns NULL if input is NULL, otherwise the result is a new ideal/module in the ring r NOTE: the resulting rank is autocorrected

Definition at line 325 of file syzextra.cc.

326 {
327  if( UNLIKELY(id == NULL) )
328  return NULL;
329 
330  const ideal newid = idInit(IDELEMS(id),id->rank);
331 
332  for (int i=IDELEMS(id) - 1; i >= 0; i--)
333  newid->m[i] = p_Tail( id->m[i], r );
334 
335  newid->rank = id_RankFreeModule(newid, currRing);
336 
337  return newid;
338 }
#define UNLIKELY
Definition: auxiliary.h:422
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
#define IDELEMS(i)
Definition: simpleideals.h:24
poly p_Tail(const poly p, const ring r)
return the tail of a given polynomial or vector returns NULL if input is NULL, otherwise the result i...
Definition: syzextra.cc:316

◆ leadmonom()

poly leadmonom ( const poly  p,
const ring  r,
const bool  bSetZeroComp 
)

return a new term: leading coeff * leading monomial of p with 0 leading component!

Definition at line 288 of file syzextra.cc.

289 {
290  if( UNLIKELY(p == NULL ) )
291  return NULL;
292 
293  assume( p != NULL );
294  p_LmTest(p, r);
295 
296  poly m = p_LmInit(p, r);
297  p_SetCoeff0(m, n_Copy(pGetCoeff(p), r->cf), r);
298 
299  if( bSetZeroComp )
300  p_SetComp(m, 0, r);
301 
302  p_Setm(m, r);
303 
304  assume( m != NULL );
305  assume( pNext(m) == NULL );
306  p_LmTest(m, r);
307 
308  if( bSetZeroComp )
309  assume( p_GetComp(m, r) == 0 );
310 
311  return m;
312 }
int m
Definition: cfEzgcd.cc:121
int p
Definition: cfModGcd.cc:4019
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:452
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:67
#define pNext(p)
Definition: monomials.h:43
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:51
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1281
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:247
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:233

◆ my_p_LmCmp()

bool my_p_LmCmp ( poly  a,
poly  b,
const ring  r 
)

Definition at line 1140 of file syzextra.cc.

1140 { return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1507

◆ myp_Head()

static FORCE_INLINE poly myp_Head ( const poly  p,
const bool  bIgnoreCoeff,
const ring  r 
)
static

Definition at line 271 of file syzextra.cc.

272 {
273  assume( p != NULL ); p_LmCheckPolyRing1(p, r);
274 
275  poly np; omTypeAllocBin(poly, np, r->PolyBin);
276  p_SetRingOfLm(np, r);
277  memcpy(np->exp, p->exp, r->ExpL_Size*sizeof(long));
278  pNext(np) = NULL;
279  pSetCoeff0(np, (bIgnoreCoeff)? NULL : n_Copy(pGetCoeff(p), r->cf));
280 
281  p_LmCheckPolyRing1(np, r);
282  return np;
283 }
#define p_LmCheckPolyRing1(p, r)
Definition: monomials.h:184
#define pSetCoeff0(p, n)
Definition: monomials.h:66
#define p_SetRingOfLm(p, r)
Definition: monomials.h:151
#define omTypeAllocBin(type, addr, bin)
Definition: omAllocDecl.h:203

◆ p_Tail()

poly p_Tail ( const poly  p,
const ring  r 
)

return the tail of a given polynomial or vector returns NULL if input is NULL, otherwise the result is a new polynomial/vector in the ring r

Definition at line 316 of file syzextra.cc.

317 {
318  if( UNLIKELY(p == NULL) )
319  return NULL;
320  else
321  return p_Copy( pNext(p), r );
322 }
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:812

◆ p_VectorProductLT()

static FORCE_INLINE poly p_VectorProductLT ( poly  s,
const ideal &  L,
const ideal &  T,
const ring &  R 
)
static

Definition at line 128 of file syzextra.cc.

129 {
130  assume( IDELEMS(L) == IDELEMS(T) );
131  poly vp = NULL; // resulting vector product
132 
133  while( s != NULL )
134  {
135  const poly nxt = pNext(s);
136  pNext(s) = NULL;
137 
138  if( !n_IsZero( pGetCoeff(s), R->cf) )
139  {
140  const int i = p_GetComp(s, R) - 1;
141  assume( i >= 0 ); assume( i < IDELEMS(L) );
142  p_SetComp(s, 0, R); p_SetmComp(s, R);
143 
144  vp = p_Add_q( vp, pp_Mult_qq( s, L->m[i], R ), R);
145  vp = p_Add_q( vp, pp_Mult_qq( s, T->m[i], R ), R);
146  }
147 
148  p_Delete(&s, R);
149 
150  s = nxt;
151  };
152 
153  assume( s == NULL );
154 
155  return vp;
156 }
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
const CanonicalForm int s
Definition: facAbsFact.cc:55
static jList * T
Definition: janet.cc:31
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:892
#define p_SetmComp
Definition: p_polys.h:244
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:857
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1093

◆ pp_Add_qq()

static FORCE_INLINE poly pp_Add_qq ( const poly  a,
const poly  b,
const ring  R 
)
static

Definition at line 123 of file syzextra.cc.

124 {
125  return p_Add_q( p_Copy(a, R), p_Copy(b, R), R );
126 }

◆ Sort_c_ds()

void Sort_c_ds ( const ideal  id,
const ring  r 
)

inplace sorting of the module (ideal) id wrt <_(c,ds)

Definition at line 342 of file syzextra.cc.

343 {
344  const int sizeNew = IDELEMS(id);
345 
346 #if ( (defined(HAVE_QSORT_R)) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9) )
347 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
348 #elif ( (defined(HAVE_QSORT_R)) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
349 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
350 #else
351 #define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
352 #endif
353 
354  if( sizeNew >= 2 )
355  qsort_my(id->m, sizeNew, sizeof(poly), r, FROM_NAMESPACE(SORT_c_ds, cmp_c_ds));
356 
357 #undef qsort_my
358 
359  id->rank = id_RankFreeModule(id, r);
360 }
#define FROM_NAMESPACE(a, s)
static int cmp_c_ds(const void *p1, const void *p2)
Definition: syzextra.cc:168
#define qsort_my(m, s, ss, r, cmp)