Macros | Functions
spectrum.cc File Reference
#include <kernel/mod2.h>
#include <misc/mylimits.h>
#include <coeffs/numbers.h>
#include <polys/monomials/p_polys.h>
#include <polys/simpleideals.h>
#include <misc/intvec.h>
#include <polys/monomials/ring.h>
#include <kernel/GBEngine/kstd1.h>
#include <kernel/combinatorics/stairc.h>
#include <kernel/spectrum/multicnt.h>
#include <kernel/spectrum/GMPrat.h>
#include <kernel/spectrum/kmatrix.h>
#include <kernel/spectrum/npolygon.h>
#include <kernel/spectrum/splist.h>
#include <kernel/spectrum/semic.h>

Go to the source code of this file.

Macros

#define SPECTRUM_CC
 

Functions

BOOLEAN hasTermOfDegree (poly h, int d, const ring r)
 
static BOOLEAN hasConstTerm (poly h, const ring r)
 
static BOOLEAN hasLinearTerm (poly h, const ring r)
 
BOOLEAN hasAxis (ideal J, int k, const ring r)
 
int hasOne (ideal J, const ring r)
 
int isMultiple (poly f, poly m, const ring r)
 
poly computeWC (const newtonPolygon &np, Rational max_weight, const ring r)
 
static poly normalFormHC (poly f, poly hc, const ring r)
 
static poly normalFormZ (poly f, poly Z, const ring r)
 
static int isLeadMonomial (poly m, ideal stdJ, const ring r)
 
static void setExp (poly m, int *r, const ring s)
 
static BOOLEAN isWell (const ring r)
 
void computeNF (ideal stdJ, poly hc, poly wc, spectrumPolyList *NF, const ring r)
 
BOOLEAN ringIsLocal (const ring r)
 

Macro Definition Documentation

#define SPECTRUM_CC

Definition at line 8 of file spectrum.cc.

Function Documentation

void computeNF ( ideal  stdJ,
poly  hc,
poly  wc,
spectrumPolyList NF,
const ring  r 
)

Definition at line 309 of file spectrum.cc.

310 {
311  int carry,k;
312  multiCnt C( r->N,0 );
313  poly Z = NULL;
314 
315  int well = isWell(r);
316 
317  do
318  {
319  poly m = p_One(r);
320  setExp( m,C.cnt,r );
321 
322  carry = FALSE;
323 
324  k = isLeadMonomial( m,stdJ,r );
325 
326  if( k < 0 )
327  {
328  // ---------------------------
329  // m is not a lead monomial
330  // ---------------------------
331 
332  NF->insert_node( m,NULL,r );
333  }
334  else if( isMultiple( Z,m,r ) )
335  {
336  // ------------------------------------
337  // m is trivially in the ideal stdJ
338  // ------------------------------------
339 
340  p_Delete( &m,r );
341  carry = TRUE;
342  }
343  else if( p_Cmp( m,hc,r ) < 0 || p_Cmp( m,wc,r ) < 0 )
344  {
345  // -------------------
346  // we do not need m
347  // -------------------
348 
349  p_Delete( &m,r );
350  carry = TRUE;
351  }
352  else
353  {
354  // --------------------------
355  // compute lazy normal form
356  // --------------------------
357 
358  poly multiplicant = p_Divide( m,stdJ->m[k],r );
359  pGetCoeff( multiplicant ) = n_Init(1,r->cf);
360 
361  poly nf = p_Mult_mm( p_Copy( stdJ->m[k],r ), multiplicant,r );
362 
363  p_Delete( &multiplicant,r );
364 
365  nf = normalFormHC( nf,hc,r );
366 
367  if( pNext( nf )==NULL )
368  {
369  // ----------------------------------
370  // normal form of m is m itself
371  // ----------------------------------
372 
373  p_Delete( &nf,r );
374  NF->delete_monomial( m,r );
375  Z = p_Add_q( Z,m,r );
376  carry = TRUE;
377  }
378  else
379  {
380  nf = normalFormZ( nf,Z,r );
381 
382  if( pNext( nf )==NULL )
383  {
384  // ----------------------------------
385  // normal form of m is m itself
386  // ----------------------------------
387 
388  p_Delete( &nf,r );
389  NF->delete_monomial( m,r );
390  Z = p_Add_q( Z,m,r );
391  carry = TRUE;
392  }
393  else
394  {
395  // ------------------------------------
396  // normal form of m is a polynomial
397  // ------------------------------------
398 
399  p_Norm( nf,r );
400  if( well==TRUE )
401  {
402  NF->insert_node( m,nf,r );
403  }
404  else
405  {
406  poly nfhard = kNF( stdJ,(ideal)NULL,pNext( nf ),0,0 );
407  nfhard = normalFormHC( nfhard,hc,r );
408  nfhard = normalFormZ ( nfhard,Z,r );
409 
410  if( nfhard==NULL )
411  {
412  NF->delete_monomial( m,r );
413  Z = p_Add_q( Z,m,r );
414  carry = TRUE;
415  }
416  else
417  {
418  p_Delete( &pNext( nf ),r );
419  pNext( nf ) = nfhard;
420  NF->insert_node( m,nf,r );
421  }
422  }
423  }
424  }
425  }
426  }
427  while( C.inc( carry ) );
428 
429  // delete single monomials
430 
431  BOOLEAN not_finished;
432 
433  do
434  {
435  not_finished = FALSE;
436 
437  spectrumPolyNode *node = NF->root;
438 
439  while( node!=(spectrumPolyNode*)NULL )
440  {
441  if( node->nf!=NULL && pNext( node->nf )==NULL )
442  {
443  NF->delete_monomial( node->nf,r );
444  not_finished = TRUE;
445  node = (spectrumPolyNode*)NULL;
446  }
447  else
448  {
449  node = node->next;
450  }
451  }
452  } while( not_finished );
453 
454  p_Delete( &Z,r );
455 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2819
spectrumPolyNode * next
Definition: splist.h:39
static int p_Cmp(poly p1, poly p2, ring r)
Definition: p_polys.h:1524
#define FALSE
Definition: auxiliary.h:140
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:974
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
#define TRUE
Definition: auxiliary.h:144
int k
Definition: cfEzgcd.cc:93
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3576
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_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:810
Definition: gnumpfl.cc:60
spectrumPolyNode * root
Definition: splist.h:60
const ring r
Definition: syzextra.cc:208
poly p_One(const ring r)
Definition: p_polys.cc:1318
static poly normalFormHC(poly f, poly hc, const ring r)
Definition: spectrum.cc:182
int m
Definition: cfEzgcd.cc:119
poly p_Divide(poly a, poly b, const ring r)
Definition: p_polys.cc:1467
int isMultiple(poly f, poly m, const ring r)
Definition: spectrum.cc:110
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
static BOOLEAN isWell(const ring r)
Definition: spectrum.cc:274
#define NULL
Definition: omList.c:10
void delete_monomial(poly, const ring)
Definition: splist.cc:269
static int isLeadMonomial(poly m, ideal stdJ, const ring r)
Definition: spectrum.cc:234
static void setExp(poly m, int *r, const ring s)
Definition: spectrum.cc:260
#define pNext(p)
Definition: monomials.h:43
static poly normalFormZ(poly f, poly Z, const ring r)
Definition: spectrum.cc:206
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:883
int BOOLEAN
Definition: auxiliary.h:131
void insert_node(poly, poly, const ring)
Definition: splist.cc:184
poly computeWC ( const newtonPolygon np,
Rational  max_weight,
const ring  r 
)

Definition at line 142 of file spectrum.cc.

143 {
144  poly m = p_One(r);
145  poly wc = NULL;
146  int mdegree;
147 
148  for( int i=1; i<=r->N; i++ )
149  {
150  mdegree = 1;
151  p_SetExp( m,i,mdegree,r );
152  // pSetm( m );
153  // np.weight_shift does not need pSetm( m ), postpone it
154 
155  while( np.weight_shift( m,r )<max_weight )
156  {
157  mdegree++;
158  p_SetExp( m,i,mdegree,r );
159  // pSetm( m );
160  // np.weight_shift does not need pSetm( m ), postpone it
161  }
162  p_Setm( m,r );
163 
164  if( i==1 || p_Cmp( m,wc,r )<0 )
165  {
166  p_Delete( &wc,r );
167  wc = p_Head( m,r );
168  }
169 
170  p_SetExp( m,i,0,r );
171  }
172 
173  p_Delete( &m,r );
174 
175  return wc;
176 }
static int p_Cmp(poly p1, poly p2, ring r)
Definition: p_polys.h:1524
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:818
const ring r
Definition: syzextra.cc:208
poly p_One(const ring r)
Definition: p_polys.cc:1318
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
Rational weight_shift(poly, const ring r) const
Definition: npolygon.cc:586
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
#define NULL
Definition: omList.c:10
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
polyrec * poly
Definition: hilb.h:10
BOOLEAN hasAxis ( ideal  J,
int  k,
const ring  r 
)

Definition at line 81 of file spectrum.cc.

82 {
83  int i;
84 
85  for( i=0; i<IDELEMS(J); i++ )
86  {
87  if (p_IsPurePower( J->m[i],r ) == k) return TRUE;
88  }
89  return FALSE;
90 }
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1224
static BOOLEAN hasConstTerm ( poly  h,
const ring  r 
)
inlinestatic

Definition at line 63 of file spectrum.cc.

64 {
65  return hasTermOfDegree(h,0,r);
66 }
BOOLEAN hasTermOfDegree(poly h, int d, const ring r)
Definition: spectrum.cc:46
const ring r
Definition: syzextra.cc:208
static Poly * h
Definition: janet.cc:978
static BOOLEAN hasLinearTerm ( poly  h,
const ring  r 
)
inlinestatic

Definition at line 72 of file spectrum.cc.

73 {
74  return hasTermOfDegree(h,1,r);
75 }
BOOLEAN hasTermOfDegree(poly h, int d, const ring r)
Definition: spectrum.cc:46
const ring r
Definition: syzextra.cc:208
static Poly * h
Definition: janet.cc:978
int hasOne ( ideal  J,
const ring  r 
)

Definition at line 96 of file spectrum.cc.

97 {
98  int i;
99 
100  for( i=0; i<IDELEMS(J); i++ )
101  {
102  if (p_IsConstant(J->m[i],r)) return TRUE;
103  }
104  return FALSE;
105 }
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
const ring r
Definition: syzextra.cc:208
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1785
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
BOOLEAN hasTermOfDegree ( poly  h,
int  d,
const ring  r 
)

Definition at line 46 of file spectrum.cc.

47 {
48  do
49  {
50  if( p_Totaldegree( h,r )== d )
51  return TRUE;
52  pIter(h);
53  }
54  while( h!=NULL );
55 
56  return FALSE;
57 }
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1436
#define pIter(p)
Definition: monomials.h:44
const ring r
Definition: syzextra.cc:208
#define NULL
Definition: omList.c:10
static Poly * h
Definition: janet.cc:978
static int isLeadMonomial ( poly  m,
ideal  stdJ,
const ring  r 
)
inlinestatic

Definition at line 234 of file spectrum.cc.

235 {
236  int length = MAX_INT_VAL;
237  int result = -1;
238 
239  for( int i=0; i<IDELEMS(stdJ); i++ )
240  {
241  if( p_Cmp( stdJ->m[i],m,r )>=0 && p_DivisibleBy( stdJ->m[i],m,r ) )
242  {
243  int tmp = pLength( stdJ->m[i] );
244 
245  if( tmp < length )
246  {
247  length = tmp;
248  result = i;
249  }
250  }
251  }
252 
253  return result;
254 }
static int p_Cmp(poly p1, poly p2, ring r)
Definition: p_polys.h:1524
static int pLength(poly a)
Definition: p_polys.h:189
const ring r
Definition: syzextra.cc:208
const int MAX_INT_VAL
Definition: mylimits.h:12
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1686
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
return result
Definition: facAbsBiFact.cc:76
int isMultiple ( poly  f,
poly  m,
const ring  r 
)

Definition at line 110 of file spectrum.cc.

111 {
112  while( f!=NULL )
113  {
114  // ---------------------------------------------------
115  // for a local order f|m is only possible if f>=m
116  // ---------------------------------------------------
117 
118  if( p_LmCmp( f,m,r )>=0 )
119  {
120  if( p_LmDivisibleByNoComp( f,m,r ) )
121  {
122  return TRUE;
123  }
124  else
125  {
126  pIter( f );
127  }
128  }
129  else
130  {
131  return FALSE;
132  }
133  }
134 
135  return FALSE;
136 }
#define FALSE
Definition: auxiliary.h:140
static BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, const ring r)
Definition: p_polys.h:1663
#define TRUE
Definition: auxiliary.h:144
#define pIter(p)
Definition: monomials.h:44
const ring r
Definition: syzextra.cc:208
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1473
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:7
#define NULL
Definition: omList.c:10
static BOOLEAN isWell ( const ring  r)
static

Definition at line 274 of file spectrum.cc.

275 {
276  int b = rBlocks( r );
277 
278  if( b==3 &&
279  ( r->order[0] == ringorder_ds ||
280  r->order[0] == ringorder_Ds ||
281  r->order[0] == ringorder_ws ||
282  r->order[0] == ringorder_Ws ) )
283  {
284  return TRUE;
285  }
286  else if( b>=3
287  && (( r->order[0] ==ringorder_a
288  && r->block1[0]==r->N )
289  || (r->order[0]==ringorder_M
290  && r->block1[0]==r->N*r->N )))
291  {
292  for( int i=r->N-1; i>=0; i-- )
293  {
294  if( r->wvhdl[0][i]>=0 )
295  {
296  return FALSE;
297  }
298  }
299  return TRUE;
300  }
301 
302  return FALSE;
303 }
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
static int rBlocks(ring r)
Definition: ring.h:513
const ring r
Definition: syzextra.cc:208
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213
static poly normalFormHC ( poly  f,
poly  hc,
const ring  r 
)
inlinestatic

Definition at line 182 of file spectrum.cc.

183 {
184  poly *ptr = &f;
185 
186  while( (*ptr)!=NULL )
187  {
188  if( p_LmCmp( *ptr,hc,r )>=0 )
189  {
190  ptr = &(pNext( *ptr ));
191  }
192  else
193  {
194  p_Delete( ptr,r );
195  return f;
196  }
197  }
198 
199  return f;
200 }
const ring r
Definition: syzextra.cc:208
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1473
FILE * f
Definition: checklibs.c:7
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
polyrec * poly
Definition: hilb.h:10
static poly normalFormZ ( poly  f,
poly  Z,
const ring  r 
)
inlinestatic

Definition at line 206 of file spectrum.cc.

207 {
208  poly *ptr = &f;
209 
210  while( (*ptr)!=NULL )
211  {
212  if( !isMultiple( Z,*ptr,r ) )
213  {
214  ptr = &(pNext( *ptr ));
215  }
216  else
217  {
218  p_LmDelete(ptr,r);
219  }
220  }
221 
222  return f;
223 }
const ring r
Definition: syzextra.cc:208
FILE * f
Definition: checklibs.c:7
int isMultiple(poly f, poly m, const ring r)
Definition: spectrum.cc:110
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:706
polyrec * poly
Definition: hilb.h:10
BOOLEAN ringIsLocal ( const ring  r)

Definition at line 461 of file spectrum.cc.

462 {
463  poly m = p_One(r);
464  poly one = p_One(r);
465  BOOLEAN res=TRUE;
466 
467  for( int i=r->N; i>0; i-- )
468  {
469  p_SetExp( m,i,1,r );
470  p_Setm( m,r );
471 
472  if( p_Cmp( m,one,r )>0 )
473  {
474  res=FALSE;
475  break;
476  }
477  p_SetExp( m,i,0,r );
478  }
479 
480  p_Delete( &m,r );
481  p_Delete( &one,r );
482 
483  return res;
484 }
static int p_Cmp(poly p1, poly p2, ring r)
Definition: p_polys.h:1524
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
poly res
Definition: myNF.cc:322
const ring r
Definition: syzextra.cc:208
poly p_One(const ring r)
Definition: p_polys.cc:1318
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
polyrec * poly
Definition: hilb.h:10
int BOOLEAN
Definition: auxiliary.h:131
static void setExp ( poly  m,
int *  r,
const ring  s 
)
static

Definition at line 260 of file spectrum.cc.

261 {
262  for( int i=s->N; i>0; i-- )
263  {
264  p_SetExp( m,i,r[i-1],s );
265  }
266  p_Setm( m,s );
267 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const ring r
Definition: syzextra.cc:208
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228