My Project
Loading...
Searching...
No Matches
spectrum.cc File Reference

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

◆ SPECTRUM_CC

#define SPECTRUM_CC

Definition at line 8 of file spectrum.cc.

Function Documentation

◆ computeNF()

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_MDivide( 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}
int BOOLEAN
Definition auxiliary.h:88
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
int m
Definition cfEzgcd.cc:128
int k
Definition cfEzgcd.cc:99
void delete_monomial(poly, const ring)
Definition splist.cc:269
spectrumPolyNode * root
Definition splist.h:60
void insert_node(poly, poly, const ring)
Definition splist.cc:184
spectrumPolyNode * next
Definition splist.h:39
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
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3224
#define pNext(p)
Definition monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
#define NULL
Definition omList.c:12
poly p_MDivide(poly a, poly b, const ring r)
Definition p_polys.cc:1493
void p_Norm(poly p1, const ring r)
Definition p_polys.cc:3799
poly p_One(const ring r)
Definition p_polys.cc:1314
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
static int p_Cmp(poly p1, poly p2, ring r)
Definition p_polys.h:1743
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1053
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848
static poly normalFormHC(poly f, poly hc, const ring r)
Definition spectrum.cc:182
static void setExp(poly m, int *r, const ring s)
Definition spectrum.cc:260
static BOOLEAN isWell(const ring r)
Definition spectrum.cc:274
int isMultiple(poly f, poly m, const ring r)
Definition spectrum.cc:110
static poly normalFormZ(poly f, poly Z, const ring r)
Definition spectrum.cc:206
static int isLeadMonomial(poly m, ideal stdJ, const ring r)
Definition spectrum.cc:234
Definition gnumpfl.cc:25

◆ computeWC()

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}
int i
Definition cfEzgcd.cc:132
Rational weight_shift(poly, const ring r) const
Definition npolygon.cc:585
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:490
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:862

◆ hasAxis()

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}
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition p_polys.cc:1227
#define IDELEMS(i)

◆ hasConstTerm()

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}
STATIC_VAR Poly * h
Definition janet.cc:971
BOOLEAN hasTermOfDegree(poly h, int d, const ring r)
Definition spectrum.cc:46

◆ hasLinearTerm()

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}

◆ hasOne()

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}
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition p_polys.h:1980

◆ hasTermOfDegree()

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 pIter(p)
Definition monomials.h:37
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1523

◆ isLeadMonomial()

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}
return result
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
const int MAX_INT_VAL
Definition mylimits.h:12
static int pLength(poly a)
Definition p_polys.h:190
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1916

◆ isMultiple()

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}
FILE * f
Definition checklibs.c:9
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1596
static BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, const ring r)
Definition p_polys.h:1893

◆ isWell()

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}
CanonicalForm b
Definition cfModGcd.cc:4111
static int rBlocks(const ring r)
Definition ring.h:574
@ ringorder_a
Definition ring.h:71
@ ringorder_ds
Definition ring.h:86
@ ringorder_Ds
Definition ring.h:87
@ ringorder_ws
Definition ring.h:88
@ ringorder_Ws
Definition ring.h:89
@ ringorder_M
Definition ring.h:75

◆ normalFormHC()

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}

◆ normalFormZ()

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}
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725

◆ ringIsLocal()

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);
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}
CanonicalForm res
Definition facAbsFact.cc:60

◆ setExp()

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:51