syzextra.cc File Reference

#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.

{
  int i=r->VarL_Size - 1;
  unsigned long divmask = r->divmask;
  unsigned long la, lb;
 
  if (r->VarL_LowIndex >= 0)
  {
    i += r->VarL_LowIndex;
    do
    {
      la = a->exp[i];
      lb = b->exp[i] + c->exp[i];
      if ((la > lb) ||
          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
      {
        pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE);
        return FALSE;
      }
      i--;
    }
    while (i>=r->VarL_LowIndex);
  }
  else
  {
    do
    {
      la = a->exp[r->VarL_Offset[i]];
      lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
      if ((la > lb) ||
          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
      {
        pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE);
        return FALSE;
      }
      i--;
    }
    while (i>=0);
  }
#ifdef HAVE_RINGS
  assume( !rField_is_Ring(r) ); // not implemented for rings...!
#endif
  return TRUE;
}

atGetInt()

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

static

Definition at line 158 of file syzextra.cc.

{
  return ((int)(long)(atGet(rootRingHdl, attribute, INT_CMD, (void*)def)));
}

cmp_c_ds()

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

static

Definition at line 168 of file syzextra.cc.

                                                   { void *R = currRing;
#endif
  assume(R != NULL);
  const int YES = 1;
  const int NO = -1;
 
  const ring r =  (const ring) R; // TODO/NOTE: the structure is known: C, lp!!!
 
  assume( r == currRing ); // for now...
 
  const poly a = *(const poly*)p1;
  const poly b = *(const poly*)p2;
 
  assume( a != NULL );
  assume( b != NULL );
 
  p_LmTest(a, r);
  p_LmTest(b, r);
 
 
  const signed long iCompDiff = p_GetComp(a, r) - p_GetComp(b, r);
 
  // TODO: test this!!!!!!!!!!!!!!!!
 
  //return -( compare (c, qsorts) )
 
  if( iCompDiff > 0 )
    return YES;
 
  if( iCompDiff < 0 )
    return  NO;
 
  assume( iCompDiff == 0 );
 
  const signed long iDegDiff = p_Totaldegree(a, r) - p_Totaldegree(b, r);
 
  if( iDegDiff > 0 )
    return YES;
 
  if( iDegDiff < 0 )
    return  NO;
 
  assume( iDegDiff == 0 );
 
  for (int v = rVar(r); v > 0; v--)
  {
    assume( v > 0 );
    assume( v <= rVar(r) );
 
    const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
 
    if( d > 0 )
      return YES;
 
    if( d < 0 )
      return NO;
 
    assume( d == 0 );
  }
 
  return 0;
}

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.

{
  if( UNLIKELY(id == NULL) )
    return NULL;
 
  const ideal newid = idInit(IDELEMS(id),id->rank);
 
  for (int i=IDELEMS(id) - 1; i >= 0; i--)
    newid->m[i] = p_Tail( id->m[i], r );
 
  newid->rank = id_RankFreeModule(newid, currRing);
 
  return newid;
}

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.

{
  if( UNLIKELY(p == NULL ) )
     return NULL;
 
    assume( p != NULL );
    p_LmTest(p, r);
 
    poly m = p_LmInit(p, r);
    p_SetCoeff0(m, n_Copy(pGetCoeff(p), r->cf), r);
 
    if( bSetZeroComp )
      p_SetComp(m, 0, r);
 
    p_Setm(m, r);
 
    assume( m != NULL );
    assume( pNext(m) == NULL );
    p_LmTest(m, r);
 
    if( bSetZeroComp )
      assume( p_GetComp(m, r) == 0 );
 
  return m;
}

my_p_LmCmp()

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

Definition at line 1140 of file syzextra.cc.

{ return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!

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.

{
  assume( p != NULL ); p_LmCheckPolyRing1(p, r);
 
  poly np; omTypeAllocBin(poly, np, r->PolyBin);
  p_SetRingOfLm(np, r);
  memcpy(np->exp, p->exp, r->ExpL_Size*sizeof(long));
  pNext(np) = NULL;
  pSetCoeff0(np, (bIgnoreCoeff)? NULL : n_Copy(pGetCoeff(p), r->cf));
 
  p_LmCheckPolyRing1(np, r);
  return np;
}

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.

{
  if( UNLIKELY(p == NULL) )
    return NULL;
  else
    return p_Copy( pNext(p), r );
}

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.

{
  assume( IDELEMS(L) == IDELEMS(T) );
  poly vp = NULL; // resulting vector product
 
  while( s != NULL )
  {
    const poly nxt = pNext(s);
    pNext(s) = NULL;
 
    if( !n_IsZero( pGetCoeff(s), R->cf) )
    {
      const int i = p_GetComp(s, R) - 1;
      assume( i >= 0 ); assume( i < IDELEMS(L) );
      p_SetComp(s, 0, R); p_SetmComp(s, R);
 
      vp = p_Add_q( vp, pp_Mult_qq( s, L->m[i], R ), R);
      vp = p_Add_q( vp, pp_Mult_qq( s, T->m[i], R ), R);
    }
 
    p_Delete(&s, R);
 
    s = nxt;
  };
 
  assume( s == NULL );
 
  return vp;
}

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.

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

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.

{
  const int sizeNew = IDELEMS(id);
 
#if ( (defined(HAVE_QSORT_R)) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9) )
#define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
#elif ( (defined(HAVE_QSORT_R)) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
#define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
#else
#define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
#endif
 
  if( sizeNew >= 2 )
    qsort_my(id->m, sizeNew, sizeof(poly), r, FROM_NAMESPACE(SORT_c_ds, cmp_c_ds));
 
#undef qsort_my
 
  id->rank = id_RankFreeModule(id, r);
}