My Project
Functions | Variables
simpleideals.cc File Reference
#include "misc/auxiliary.h"
#include "misc/options.h"
#include "misc/intvec.h"
#include "matpol.h"
#include "monomials/p_polys.h"
#include "weight.h"
#include "sbuckets.h"
#include "clapsing.h"
#include "simpleideals.h"

Go to the source code of this file.

Functions

ideal idInit (int idsize, int rank)
 initialise an ideal / module More...
 
void idShow (const ideal id, const ring lmRing, const ring tailRing, const int debugPrint)
 
int id_PosConstant (ideal id, const ring r)
 index of generator with leading term in ground ring (if any); otherwise -1 More...
 
ideal id_MaxIdeal (const ring r)
 initialise the maximal ideal (at 0) More...
 
void id_Delete (ideal *h, ring r)
 deletes an ideal/module/matrix More...
 
void id_ShallowDelete (ideal *h, ring r)
 Shallowdeletes an ideal/matrix. More...
 
void idSkipZeroes (ideal ide)
 gives an ideal/module the minimal possible size More...
 
ideal id_CopyFirstK (const ideal ide, const int k, const ring r)
 copies the first k (>= 1) entries of the given ideal/module and returns these as a new ideal/module (Note that the copied entries may be zero.) More...
 
void id_Norm (ideal id, const ring r)
 ideal id = (id[i]), result is leadcoeff(id[i]) = 1 More...
 
void id_DelMultiples (ideal id, const ring r)
 ideal id = (id[i]), c any unit if id[i] = c*id[j] then id[j] is deleted for j > i More...
 
void id_DelEquals (ideal id, const ring r)
 ideal id = (id[i]) if id[i] = id[j] then id[j] is deleted for j > i More...
 
void id_DelLmEquals (ideal id, const ring r)
 Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i. More...
 
static void id_DelDiv_SEV (ideal id, int k, const ring r)
 delete id[j], if LT(j) == coeff*mon*LT(i) More...
 
void id_DelDiv (ideal id, const ring r)
 delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*LT(j) More...
 
BOOLEAN id_IsConstant (ideal id, const ring r)
 test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant More...
 
ideal id_Copy (ideal h1, const ring r)
 copy an ideal More...
 
void id_DBTest (ideal h1, int level, const char *f, const int l, const ring r, const ring tailRing)
 Internal verification for ideals/modules and dense matrices! More...
 
void id_DBLmTest (ideal h1, int level, const char *f, const int l, const ring r)
 Internal verification for ideals/modules and dense matrices! More...
 
static int p_Comp_RevLex (poly a, poly b, BOOLEAN nolex, const ring R)
 for idSort: compare a and b revlex inclusive module comp. More...
 
intvecid_Sort (const ideal id, const BOOLEAN nolex, const ring r)
 sorts the ideal w.r.t. the actual ringordering uses lex-ordering when nolex = FALSE More...
 
ideal id_SimpleAdd (ideal h1, ideal h2, const ring R)
 concat the lists h1 and h2 without zeros More...
 
BOOLEAN idInsertPoly (ideal h1, poly h2)
 insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted More...
 
BOOLEAN idInsertPolyOnPos (ideal I, poly p, int pos)
 insert p into I on position pos More...
 
BOOLEAN id_InsertPolyWithTests (ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk, const ring r)
 insert h2 into h1 depending on the two boolean parameters: More...
 
ideal id_Add (ideal h1, ideal h2, const ring r)
 h1 + h2 More...
 
ideal id_Mult (ideal h1, ideal h2, const ring R)
 h1 * h2 one h_i must be an ideal (with at least one column) the other h_i may be a module (with no columns at all) More...
 
BOOLEAN idIs0 (ideal h)
 returns true if h is the zero ideal More...
 
long id_RankFreeModule (ideal s, ring lmRing, ring tailRing)
 return the maximal component number found in any polynomial in s More...
 
BOOLEAN id_HomIdeal (ideal id, ideal Q, const ring r)
 
BOOLEAN id_HomIdealW (ideal id, ideal Q, const intvec *w, const ring r)
 
BOOLEAN id_HomModuleW (ideal id, ideal Q, const intvec *w, const intvec *module_w, const ring r)
 
void idInitChoise (int r, int beg, int end, BOOLEAN *endch, int *choise)
 
void idGetNextChoise (int r, int end, BOOLEAN *endch, int *choise)
 
int idGetNumberOfChoise (int t, int d, int begin, int end, int *choise)
 
int binom (int n, int r)
 
ideal id_FreeModule (int i, const ring r)
 the free module of rank i More...
 
static void makemonoms (int vars, int actvar, int deg, int monomdeg, const ring r)
 
static void lpmakemonoms (int vars, int deg, const ring r)
 
ideal id_MaxIdeal (int deg, const ring r)
 
static void id_NextPotence (ideal given, ideal result, int begin, int end, int deg, int restdeg, poly ap, const ring r)
 
ideal id_Power (ideal given, int exp, const ring r)
 
void id_Compactify (ideal id, const ring r)
 
ideal id_Head (ideal h, const ring r)
 returns the ideals of initial terms More...
 
ideal id_Homogen (ideal h, int varnum, const ring r)
 
ideal id_Vec2Ideal (poly vec, const ring R)
 
poly id_Array2Vector (poly *m, unsigned n, const ring R)
 for julia: convert an array of poly to vector More...
 
ideal id_Matrix2Module (matrix mat, const ring R)
 converts mat to module, destroys mat More...
 
matrix id_Module2Matrix (ideal mod, const ring R)
 
matrix id_Module2formatedMatrix (ideal mod, int rows, int cols, const ring R)
 
ideal id_ResizeModule (ideal mod, int rows, int cols, const ring R)
 
ideal id_Subst (ideal id, int n, poly e, const ring r)
 
BOOLEAN id_HomModule (ideal m, ideal Q, intvec **w, const ring R)
 
ideal id_Jet (const ideal i, int d, const ring R)
 
ideal id_JetW (const ideal i, int d, intvec *iv, const ring R)
 
int id_ReadOutPivot (ideal arg, int *comp, const ring r)
 
intvecid_QHomWeight (ideal id, const ring r)
 
BOOLEAN id_IsZeroDim (ideal I, const ring r)
 
void id_Normalize (ideal I, const ring r)
 normialize all polys in id More...
 
int id_MinDegW (ideal M, intvec *w, const ring r)
 
ideal id_Transp (ideal a, const ring rRing)
 transpose a module More...
 
ideal id_TensorModuleMult (const int m, const ideal M, const ring rRing)
 
ideal id_ChineseRemainder (ideal *xx, number *q, int rl, const ring r)
 
void id_Shift (ideal M, int s, const ring r)
 
ideal id_Delete_Pos (const ideal I, const int p, const ring r)
 

Variables

VAR omBin sip_sideal_bin = omGetSpecBin(sizeof(sip_sideal))
 
STATIC_VAR poly * idpower
 
STATIC_VAR int idpowerpoint
 

Function Documentation

◆ binom()

int binom ( int  n,
int  r 
)

Definition at line 1106 of file simpleideals.cc.

1107 {
1108  int i;
1109  int64 result;
1110 
1111  if (r==0) return 1;
1112  if (n-r<r) return binom(n,n-r);
1113  result = n-r+1;
1114  for (i=2;i<=r;i++)
1115  {
1116  result *= n-r+i;
1117  result /= i;
1118  }
1119  if (result>MAX_INT_VAL)
1120  {
1121  WarnS("overflow in binomials");
1122  result=0;
1123  }
1124  return (int)result;
1125 }
long int64
Definition: auxiliary.h:68
int i
Definition: cfEzgcd.cc:132
#define WarnS
Definition: emacs.cc:78
return result
Definition: facAbsBiFact.cc:75
const int MAX_INT_VAL
Definition: mylimits.h:12
int binom(int n, int r)

◆ id_Add()

ideal id_Add ( ideal  h1,
ideal  h2,
const ring  r 
)

h1 + h2

Definition at line 863 of file simpleideals.cc.

864 {
865  id_Test(h1, r);
866  id_Test(h2, r);
867 
868  ideal result = id_SimpleAdd(h1,h2,r);
870  return result;
871 }
ideal id_SimpleAdd(ideal h1, ideal h2, const ring R)
concat the lists h1 and h2 without zeros
void id_Compactify(ideal id, const ring r)
#define id_Test(A, lR)
Definition: simpleideals.h:87

◆ id_Array2Vector()

poly id_Array2Vector ( poly *  m,
unsigned  n,
const ring  R 
)

for julia: convert an array of poly to vector

Definition at line 1419 of file simpleideals.cc.

1420 {
1421  poly h;
1422  int l;
1423  sBucket_pt bucket = sBucketCreate(R);
1424 
1425  for(unsigned j=0;j<n ;j++)
1426  {
1427  h = m[j];
1428  if (h!=NULL)
1429  {
1430  h=p_Copy(h, R);
1431  l=pLength(h);
1432  p_SetCompP(h,j+1, R);
1433  sBucket_Merge_p(bucket, h, l);
1434  }
1435  }
1436  sBucketClearMerge(bucket, &h, &l);
1437  sBucketDestroy(&bucket);
1438  return h;
1439 }
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int j
Definition: facHensel.cc:110
STATIC_VAR Poly * h
Definition: janet.cc:971
#define NULL
Definition: omList.c:12
static int pLength(poly a)
Definition: p_polys.h:188
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:252
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:237
void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!
Definition: sbuckets.cc:148
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:103
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96
#define R
Definition: sirandom.c:27

◆ id_ChineseRemainder()

ideal id_ChineseRemainder ( ideal *  xx,
number *  q,
int  rl,
const ring  r 
)

Definition at line 2072 of file simpleideals.cc.

2073 {
2074  int cnt=0;int rw=0; int cl=0;
2075  int i,j;
2076  // find max. size of xx[.]:
2077  for(j=rl-1;j>=0;j--)
2078  {
2079  i=IDELEMS(xx[j])*xx[j]->nrows;
2080  if (i>cnt) cnt=i;
2081  if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
2082  if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
2083  }
2084  if (rw*cl !=cnt)
2085  {
2086  WerrorS("format mismatch in CRT");
2087  return NULL;
2088  }
2089  ideal result=idInit(cnt,xx[0]->rank);
2090  result->nrows=rw; // for lifting matrices
2091  result->ncols=cl; // for lifting matrices
2092  number *x=(number *)omAlloc(rl*sizeof(number));
2093  poly *p=(poly *)omAlloc(rl*sizeof(poly));
2094  CFArray inv_cache(rl);
2095  EXTERN_VAR int n_SwitchChinRem; //TEST
2096  int save_n_SwitchChinRem=n_SwitchChinRem;
2097  n_SwitchChinRem=1;
2098  for(i=cnt-1;i>=0;i--)
2099  {
2100  for(j=rl-1;j>=0;j--)
2101  {
2102  if(i>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
2103  p[j]=NULL;
2104  else
2105  p[j]=xx[j]->m[i];
2106  }
2107  result->m[i]=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
2108  for(j=rl-1;j>=0;j--)
2109  {
2110  if(i<IDELEMS(xx[j])*xx[j]->nrows) xx[j]->m[i]=p[j];
2111  }
2112  }
2113  n_SwitchChinRem=save_n_SwitchChinRem;
2114  omFreeSize(p,rl*sizeof(poly));
2115  omFreeSize(x,rl*sizeof(number));
2116  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]),r);
2117  omFreeSize(xx,rl*sizeof(ideal));
2118  return result;
2119 }
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
cl
Definition: cfModGcd.cc:4100
int int ncols
Definition: cf_linsys.cc:32
int nrows
Definition: cf_linsys.cc:32
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define EXTERN_VAR
Definition: globaldefs.h:6
poly p_ChineseRemainder(poly *xx, mpz_ptr *x, mpz_ptr *q, int rl, mpz_ptr *C, const ring R)
VAR int n_SwitchChinRem
Definition: longrat.cc:3094
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define IDELEMS(i)
Definition: simpleideals.h:23

◆ id_Compactify()

void id_Compactify ( ideal  id,
const ring  r 
)

Definition at line 1353 of file simpleideals.cc.

1354 {
1355  int i;
1356  BOOLEAN b=FALSE;
1357 
1358  i = IDELEMS(id)-1;
1359  while ((! b) && (i>=0))
1360  {
1361  b=p_IsUnit(id->m[i],r);
1362  i--;
1363  }
1364  if (b)
1365  {
1366  for(i=IDELEMS(id)-1;i>=0;i--) p_Delete(&id->m[i],r);
1367  id->m[0]=p_One(r);
1368  }
1369  else
1370  {
1371  id_DelMultiples(id,r);
1372  }
1373  idSkipZeroes(id);
1374 }
int BOOLEAN
Definition: auxiliary.h:87
#define FALSE
Definition: auxiliary.h:96
CanonicalForm b
Definition: cfModGcd.cc:4103
poly p_One(const ring r)
Definition: p_polys.cc:1313
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static BOOLEAN p_IsUnit(const poly p, const ring r)
Definition: p_polys.h:1989
void id_DelMultiples(ideal id, const ring r)
ideal id = (id[i]), c any unit if id[i] = c*id[j] then id[j] is deleted for j > i
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size

◆ id_Copy()

ideal id_Copy ( ideal  h1,
const ring  r 
)

copy an ideal

Definition at line 499 of file simpleideals.cc.

500 {
501  id_Test(h1, r);
502 
503  ideal h2 = idInit(IDELEMS(h1), h1->rank);
504  for (int i=IDELEMS(h1)-1; i>=0; i--)
505  h2->m[i] = p_Copy(h1->m[i],r);
506  return h2;
507 }

◆ id_CopyFirstK()

ideal id_CopyFirstK ( const ideal  ide,
const int  k,
const ring  r 
)

copies the first k (>= 1) entries of the given ideal/module and returns these as a new ideal/module (Note that the copied entries may be zero.)

Definition at line 223 of file simpleideals.cc.

224 {
225  id_Test(ide, r);
226 
227  assume( ide != NULL );
228  assume( k <= IDELEMS(ide) );
229 
230  ideal newI = idInit(k, ide->rank);
231 
232  for (int i = 0; i < k; i++)
233  newI->m[i] = p_Copy(ide->m[i],r);
234 
235  return newI;
236 }
int k
Definition: cfEzgcd.cc:99
#define assume(x)
Definition: mod2.h:389

◆ id_DBLmTest()

void id_DBLmTest ( ideal  h1,
int  level,
const char *  f,
const int  l,
const ring  r 
)

Internal verification for ideals/modules and dense matrices!

Definition at line 562 of file simpleideals.cc.

563 {
564  if (h1 != NULL)
565  {
566  // assume(IDELEMS(h1) > 0); for ideal/module, does not apply to matrix
567  omCheckAddrSize(h1,sizeof(*h1));
568 
569  assume( h1->ncols >= 0 );
570  assume( h1->nrows >= 0 ); // matrix case!
571 
572  assume( h1->rank >= 0 );
573 
574  const long n = ((long)h1->ncols * (long)h1->nrows);
575 
576  assume( !( n > 0 && h1->m == NULL) );
577 
578  if( h1->m != NULL && n > 0 )
579  omdebugAddrSize(h1->m, n * sizeof(poly));
580 
581  long new_rk = 0; // inlining id_RankFreeModule(h1, r, tailRing);
582 
583  /* to be able to test matrices: */
584  for (long i=n - 1; i >= 0; i--)
585  {
586  if (h1->m[i]!=NULL)
587  {
588  _p_LmTest(h1->m[i], r, level);
589  const long k = p_GetComp(h1->m[i], r);
590  if (k > new_rk) new_rk = k;
591  }
592  }
593 
594  // dense matrices only contain polynomials:
595  // h1->nrows == h1->rank > 1 && new_rk == 0!
596  assume( !( h1->nrows == h1->rank && h1->nrows > 1 && new_rk > 0 ) ); //
597 
598  if(new_rk > h1->rank)
599  {
600  dReportError("wrong rank %d (should be %d) in %s:%d\n",
601  h1->rank, new_rk, f,l);
602  omPrintAddrInfo(stderr, h1, " for ideal");
603  h1->rank = new_rk;
604  }
605  }
606  else
607  {
608  Print("error: ideal==NULL in %s:%d\n",f,l);
609  assume( h1 != NULL );
610  }
611 }
int level(const CanonicalForm &f)
FILE * f
Definition: checklibs.c:9
#define Print
Definition: emacs.cc:80
int dReportError(const char *fmt,...)
Definition: dError.cc:44
#define p_GetComp(p, r)
Definition: monomials.h:64
#define omdebugAddrSize(addr, size)
Definition: omAllocDecl.h:315
#define omCheckAddrSize(addr, size)
Definition: omAllocDecl.h:327
BOOLEAN _p_LmTest(poly p, ring r, int level)
Definition: pDebug.cc:323
#define omPrintAddrInfo(A, B, C)
Definition: xalloc.h:270

◆ id_DBTest()

void id_DBTest ( ideal  h1,
int  level,
const char *  f,
const int  l,
const ring  r,
const ring  tailRing 
)

Internal verification for ideals/modules and dense matrices!

Definition at line 511 of file simpleideals.cc.

512 {
513  if (h1 != NULL)
514  {
515  // assume(IDELEMS(h1) > 0); for ideal/module, does not apply to matrix
516  omCheckAddrSize(h1,sizeof(*h1));
517 
518  assume( h1->ncols >= 0 );
519  assume( h1->nrows >= 0 ); // matrix case!
520 
521  assume( h1->rank >= 0 );
522 
523  const long n = ((long)h1->ncols * (long)h1->nrows);
524 
525  assume( !( n > 0 && h1->m == NULL) );
526 
527  if( h1->m != NULL && n > 0 )
528  omdebugAddrSize(h1->m, n * sizeof(poly));
529 
530  long new_rk = 0; // inlining id_RankFreeModule(h1, r, tailRing);
531 
532  /* to be able to test matrices: */
533  for (long i=n - 1; i >= 0; i--)
534  {
535  _pp_Test(h1->m[i], r, tailRing, level);
536  const long k = p_MaxComp(h1->m[i], r, tailRing);
537  if (k > new_rk) new_rk = k;
538  }
539 
540  // dense matrices only contain polynomials:
541  // h1->nrows == h1->rank > 1 && new_rk == 0!
542  assume( !( h1->nrows == h1->rank && h1->nrows > 1 && new_rk > 0 ) ); //
543 
544  if(new_rk > h1->rank)
545  {
546  dReportError("wrong rank %d (should be %d) in %s:%d\n",
547  h1->rank, new_rk, f,l);
548  omPrintAddrInfo(stderr, h1, " for ideal");
549  h1->rank = new_rk;
550  }
551  }
552  else
553  {
554  Print("error: ideal==NULL in %s:%d\n",f,l);
555  assume( h1 != NULL );
556  }
557 }
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:290
BOOLEAN _pp_Test(poly p, ring lmRing, ring tailRing, int level)
Definition: pDebug.cc:333

◆ id_DelDiv()

void id_DelDiv ( ideal  id,
const ring  r 
)

delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*LT(j)

Definition at line 420 of file simpleideals.cc.

421 {
422  id_Test(id, r);
423 
424  int i, j;
425  int k = IDELEMS(id)-1;
426 #ifdef HAVE_RINGS
427  if (rField_is_Ring(r))
428  {
429  for (i=k-1; i>=0; i--)
430  {
431  if (id->m[i] != NULL)
432  {
433  for (j=k; j>i; j--)
434  {
435  if (id->m[j]!=NULL)
436  {
437  if (p_DivisibleByRingCase(id->m[i], id->m[j],r))
438  {
439  p_Delete(&id->m[j],r);
440  }
441  else if (p_DivisibleByRingCase(id->m[j], id->m[i],r))
442  {
443  p_Delete(&id->m[i],r);
444  break;
445  }
446  }
447  }
448  }
449  }
450  }
451  else
452 #endif
453  {
454  /* the case of a coefficient field: */
455  if (k>9)
456  {
457  id_DelDiv_SEV(id,k,r);
458  return;
459  }
460  for (i=k-1; i>=0; i--)
461  {
462  if (id->m[i] != NULL)
463  {
464  for (j=k; j>i; j--)
465  {
466  if (id->m[j]!=NULL)
467  {
468  if (p_LmDivisibleBy(id->m[i], id->m[j],r))
469  {
470  p_Delete(&id->m[j],r);
471  }
472  else if (p_LmDivisibleBy(id->m[j], id->m[i],r))
473  {
474  p_Delete(&id->m[i],r);
475  break;
476  }
477  }
478  }
479  }
480  }
481  }
482 }
BOOLEAN p_DivisibleByRingCase(poly f, poly g, const ring r)
divisibility check over ground ring (which may contain zero divisors); TRUE iff LT(f) divides LT(g),...
Definition: p_polys.cc:1638
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1889
#define rField_is_Ring(R)
Definition: ring.h:485
static void id_DelDiv_SEV(ideal id, int k, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i)

◆ id_DelDiv_SEV()

static void id_DelDiv_SEV ( ideal  id,
int  k,
const ring  r 
)
static

delete id[j], if LT(j) == coeff*mon*LT(i)

Definition at line 338 of file simpleideals.cc.

339 {
340  int kk = k+1;
341  long *sev=(long*)omAlloc0(kk*sizeof(long));
342  while(id->m[k]==NULL) k--;
343  BOOLEAN only_lm=r->cf->has_simple_Alloc;
344  if (only_lm)
345  {
346  for (int i=k; i>=0; i--)
347  {
348  if((id->m[i]!=NULL) && (pNext(id->m[i])!=NULL))
349  {
350  only_lm=FALSE;
351  break;
352  }
353  }
354  }
355  for (int i=k; i>=0; i--)
356  {
357  if(id->m[i]!=NULL)
358  {
359  sev[i]=p_GetShortExpVector(id->m[i],r);
360  }
361  }
362  if (only_lm)
363  {
364  for (int i=0; i<k; i++)
365  {
366  if (id->m[i] != NULL)
367  {
368  poly m_i=id->m[i];
369  long sev_i=sev[i];
370  for (int j=i+1; j<=k; j++)
371  {
372  if (id->m[j]!=NULL)
373  {
374  if (p_LmShortDivisibleBy(m_i, sev_i,id->m[j],~sev[j],r))
375  {
376  p_LmFree(&id->m[j],r);
377  }
378  else if (p_LmShortDivisibleBy(id->m[j],sev[j], m_i,~sev_i,r))
379  {
380  p_LmFree(&id->m[i],r);
381  break;
382  }
383  }
384  }
385  }
386  }
387  }
388  else
389  {
390  for (int i=0; i<k; i++)
391  {
392  if (id->m[i] != NULL)
393  {
394  poly m_i=id->m[i];
395  long sev_i=sev[i];
396  for (int j=i+1; j<=k; j++)
397  {
398  if (id->m[j]!=NULL)
399  {
400  if (p_LmShortDivisibleBy(m_i, sev_i, id->m[j],~sev[j],r))
401  {
402  p_Delete(&id->m[j],r);
403  }
404  else if (p_LmShortDivisibleBy(id->m[j],sev[j], m_i,~sev_i,r))
405  {
406  p_Delete(&id->m[i],r);
407  break;
408  }
409  }
410  }
411  }
412  }
413  }
414  omFreeSize(sev,kk*sizeof(long));
415 }
#define pNext(p)
Definition: monomials.h:36
#define omAlloc0(size)
Definition: omAllocDecl.h:211
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4776
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1908
static void p_LmFree(poly p, ring)
Definition: p_polys.h:681

◆ id_DelEquals()

void id_DelEquals ( ideal  id,
const ring  r 
)

ideal id = (id[i]) if id[i] = id[j] then id[j] is deleted for j > i

Definition at line 288 of file simpleideals.cc.

289 {
290  id_Test(id, r);
291 
292  int i, j;
293  int k = IDELEMS(id)-1;
294  for (i=k; i>=0; i--)
295  {
296  if (id->m[i]!=NULL)
297  {
298  for (j=k; j>i; j--)
299  {
300  if ((id->m[j]!=NULL)
301  && (p_EqualPolys(id->m[i], id->m[j],r)))
302  {
303  p_Delete(&id->m[j],r);
304  }
305  }
306  }
307  }
308 }
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4508

◆ id_Delete()

void id_Delete ( ideal *  h,
ring  r 
)

deletes an ideal/module/matrix

Definition at line 123 of file simpleideals.cc.

124 {
125  if (*h == NULL)
126  return;
127 
128  id_Test(*h, r);
129 
130  const long elems = (long)(*h)->nrows * (long)(*h)->ncols;
131 
132  if ( elems > 0 )
133  {
134  assume( (*h)->m != NULL );
135 
136  if (r!=NULL)
137  {
138  long j = elems;
139  do
140  {
141  j--;
142  poly pp=((*h)->m[j]);
143  if (pp!=NULL) p_Delete(&pp, r);
144  }
145  while (j>0);
146  }
147 
148  omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
149  }
150 
152  *h=NULL;
153 }
void * ADDRESS
Definition: auxiliary.h:119
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:27

◆ id_Delete_Pos()

ideal id_Delete_Pos ( const ideal  I,
const int  p,
const ring  r 
)

Definition at line 2135 of file simpleideals.cc.

2136 {
2137  if ((p<0)||(p>=IDELEMS(I))) return NULL;
2138  ideal ret=idInit(IDELEMS(I)-1,I->rank);
2139  for(int i=0;i<p;i++) ret->m[i]=p_Copy(I->m[i],r);
2140  for(int i=p+1;i<IDELEMS(I);i++) ret->m[i-1]=p_Copy(I->m[i],r);
2141  return ret;
2142 }

◆ id_DelLmEquals()

void id_DelLmEquals ( ideal  id,
const ring  r 
)

Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i.

Definition at line 311 of file simpleideals.cc.

312 {
313  id_Test(id, r);
314 
315  int i, j;
316  int k = IDELEMS(id)-1;
317  for (i=k; i>=0; i--)
318  {
319  if (id->m[i] != NULL)
320  {
321  for (j=k; j>i; j--)
322  {
323  if ((id->m[j] != NULL)
324  && p_LmEqual(id->m[i], id->m[j],r)
325 #ifdef HAVE_RINGS
326  && n_IsUnit(pGetCoeff(id->m[i]),r->cf) && n_IsUnit(pGetCoeff(id->m[j]),r->cf)
327 #endif
328  )
329  {
330  p_Delete(&id->m[j],r);
331  }
332  }
333  }
334  }
335 }
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:512
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 p_LmEqual(p1, p2, r)
Definition: p_polys.h:1721

◆ id_DelMultiples()

void id_DelMultiples ( ideal  id,
const ring  r 
)

ideal id = (id[i]), c any unit if id[i] = c*id[j] then id[j] is deleted for j > i

Definition at line 253 of file simpleideals.cc.

254 {
255  id_Test(id, r);
256 
257  int i, j;
258  int k = IDELEMS(id)-1;
259  for (i=k; i>=0; i--)
260  {
261  if (id->m[i]!=NULL)
262  {
263  for (j=k; j>i; j--)
264  {
265  if (id->m[j]!=NULL)
266  {
267  if (rField_is_Ring(r))
268  {
269  /* if id[j] = c*id[i] then delete id[j].
270  In the below cases of a ground field, we
271  check whether id[i] = c*id[j] and, if so,
272  delete id[j] for historical reasons (so
273  that previous output does not change) */
274  if (p_ComparePolys(id->m[j], id->m[i],r)) p_Delete(&id->m[j],r);
275  }
276  else
277  {
278  if (p_ComparePolys(id->m[i], id->m[j],r)) p_Delete(&id->m[j],r);
279  }
280  }
281  }
282  }
283  }
284 }
BOOLEAN p_ComparePolys(poly p1, poly p2, const ring r)
returns TRUE if p1 is a skalar multiple of p2 assume p1 != NULL and p2 != NULL
Definition: p_polys.cc:4572

◆ id_FreeModule()

ideal id_FreeModule ( int  i,
const ring  r 
)

the free module of rank i

Definition at line 1129 of file simpleideals.cc.

1130 {
1131  assume(i >= 0);
1132  if (r->isLPring)
1133  {
1134  PrintS("In order to address bimodules, the command freeAlgebra should be used.");
1135  }
1136  ideal h = idInit(i, i);
1137 
1138  for (int j=0; j<i; j++)
1139  {
1140  h->m[j] = p_One(r);
1141  p_SetComp(h->m[j],j+1,r);
1142  p_SetmComp(h->m[j],r);
1143  }
1144 
1145  return h;
1146 }
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:245
#define p_SetmComp
Definition: p_polys.h:242
void PrintS(const char *s)
Definition: reporter.cc:284

◆ id_Head()

ideal id_Head ( ideal  h,
const ring  r 
)

returns the ideals of initial terms

Definition at line 1377 of file simpleideals.cc.

1378 {
1379  ideal m = idInit(IDELEMS(h),h->rank);
1380 
1381  if (r->cf->has_simple_Alloc)
1382  {
1383  for (int i=IDELEMS(h)-1;i>=0; i--)
1384  if (h->m[i]!=NULL)
1385  m->m[i]=p_CopyPowerProduct0(h->m[i],pGetCoeff(h->m[i]),r);
1386  }
1387  else
1388  {
1389  for (int i=IDELEMS(h)-1;i>=0; i--)
1390  if (h->m[i]!=NULL)
1391  m->m[i]=p_Head(h->m[i],r);
1392  }
1393 
1394  return m;
1395 }
poly p_CopyPowerProduct0(const poly p, number n, const ring r)
like p_Head, but with coefficient n
Definition: p_polys.cc:4917
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:858

◆ id_HomIdeal()

BOOLEAN id_HomIdeal ( ideal  id,
ideal  Q,
const ring  r 
)

Definition at line 953 of file simpleideals.cc.

954 {
955  int i;
956  BOOLEAN b;
957  i = 0;
958  b = TRUE;
959  while ((i < IDELEMS(id)) && b)
960  {
961  b = p_IsHomogeneous(id->m[i],r);
962  i++;
963  }
964  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
965  {
966  i=0;
967  while ((i < IDELEMS(Q)) && b)
968  {
969  b = p_IsHomogeneous(Q->m[i],r);
970  i++;
971  }
972  }
973  return b;
974 }
#define TRUE
Definition: auxiliary.h:100
STATIC_VAR jList * Q
Definition: janet.cc:30
BOOLEAN p_IsHomogeneous(poly p, const ring r)
Definition: p_polys.cc:3315

◆ id_HomIdealW()

BOOLEAN id_HomIdealW ( ideal  id,
ideal  Q,
const intvec w,
const ring  r 
)

Definition at line 976 of file simpleideals.cc.

977 {
978  int i;
979  BOOLEAN b;
980  i = 0;
981  b = TRUE;
982  while ((i < IDELEMS(id)) && b)
983  {
984  b = p_IsHomogeneousW(id->m[i],w,r);
985  i++;
986  }
987  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
988  {
989  i=0;
990  while ((i < IDELEMS(Q)) && b)
991  {
992  b = p_IsHomogeneousW(Q->m[i],w,r);
993  i++;
994  }
995  }
996  return b;
997 }
const CanonicalForm & w
Definition: facAbsFact.cc:51
BOOLEAN p_IsHomogeneousW(poly p, const intvec *w, const ring r)
Definition: p_polys.cc:3339

◆ id_HomModule()

BOOLEAN id_HomModule ( ideal  m,
ideal  Q,
intvec **  w,
const ring  R 
)

Definition at line 1606 of file simpleideals.cc.

1607 {
1608  if (w!=NULL) *w=NULL;
1609  if ((Q!=NULL) && (!id_HomIdeal(Q,NULL,R))) return FALSE;
1610  if (idIs0(m))
1611  {
1612  if (w!=NULL) (*w)=new intvec(m->rank);
1613  return TRUE;
1614  }
1615 
1616  long cmax=1,order=0,ord,* diff,diffmin=32000;
1617  int *iscom;
1618  int i;
1619  poly p=NULL;
1620  pFDegProc d;
1621  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1622  d=p_Totaldegree;
1623  else
1624  d=R->pFDeg;
1625  int length=IDELEMS(m);
1626  poly* P=m->m;
1627  poly* F=(poly*)omAlloc(length*sizeof(poly));
1628  for (i=length-1;i>=0;i--)
1629  {
1630  p=F[i]=P[i];
1631  cmax=si_max(cmax,p_MaxComp(p,R));
1632  }
1633  cmax++;
1634  diff = (long *)omAlloc0(cmax*sizeof(long));
1635  if (w!=NULL) *w=new intvec(cmax-1);
1636  iscom = (int *)omAlloc0(cmax*sizeof(int));
1637  i=0;
1638  while (i<=length)
1639  {
1640  if (i<length)
1641  {
1642  p=F[i];
1643  while ((p!=NULL) && (iscom[__p_GetComp(p,R)]==0)) pIter(p);
1644  }
1645  if ((p==NULL) && (i<length))
1646  {
1647  i++;
1648  }
1649  else
1650  {
1651  if (p==NULL) /* && (i==length) */
1652  {
1653  i=0;
1654  while ((i<length) && (F[i]==NULL)) i++;
1655  if (i>=length) break;
1656  p = F[i];
1657  }
1658  //if (pLexOrder && (currRing->order[0]==ringorder_lp))
1659  // order=pTotaldegree(p);
1660  //else
1661  // order = p->order;
1662  // order = pFDeg(p,currRing);
1663  order = d(p,R) +diff[__p_GetComp(p,R)];
1664  //order += diff[pGetComp(p)];
1665  p = F[i];
1666 //Print("Actual p=F[%d]: ",i);pWrite(p);
1667  F[i] = NULL;
1668  i=0;
1669  }
1670  while (p!=NULL)
1671  {
1672  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1673  ord=p_Totaldegree(p,R);
1674  else
1675  // ord = p->order;
1676  ord = R->pFDeg(p,R);
1677  if (iscom[__p_GetComp(p,R)]==0)
1678  {
1679  diff[__p_GetComp(p,R)] = order-ord;
1680  iscom[__p_GetComp(p,R)] = 1;
1681 /*
1682 *PrintS("new diff: ");
1683 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1684 *PrintLn();
1685 *PrintS("new iscom: ");
1686 *for (j=0;j<cmax;j++) Print("%d ",iscom[j]);
1687 *PrintLn();
1688 *Print("new set %d, order %d, ord %d, diff %d\n",pGetComp(p),order,ord,diff[pGetComp(p)]);
1689 */
1690  }
1691  else
1692  {
1693 /*
1694 *PrintS("new diff: ");
1695 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1696 *PrintLn();
1697 *Print("order %d, ord %d, diff %d\n",order,ord,diff[pGetComp(p)]);
1698 */
1699  if (order != (ord+diff[__p_GetComp(p,R)]))
1700  {
1701  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1702  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1703  omFreeSize((ADDRESS) F,length*sizeof(poly));
1704  delete *w;*w=NULL;
1705  return FALSE;
1706  }
1707  }
1708  pIter(p);
1709  }
1710  }
1711  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1712  omFreeSize((ADDRESS) F,length*sizeof(poly));
1713  for (i=1;i<cmax;i++) (**w)[i-1]=(int)(diff[i]);
1714  for (i=1;i<cmax;i++)
1715  {
1716  if (diff[i]<diffmin) diffmin=diff[i];
1717  }
1718  if (w!=NULL)
1719  {
1720  for (i=1;i<cmax;i++)
1721  {
1722  (**w)[i-1]=(int)(diff[i]-diffmin);
1723  }
1724  }
1725  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1726  return TRUE;
1727 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
Definition: intvec.h:23
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define pIter(p)
Definition: monomials.h:37
#define __p_GetComp(p, r)
Definition: monomials.h:63
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1505
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:38
@ ringorder_lp
Definition: ring.h:77
BOOLEAN id_HomIdeal(ideal id, ideal Q, const ring r)
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal

◆ id_HomModuleW()

BOOLEAN id_HomModuleW ( ideal  id,
ideal  Q,
const intvec w,
const intvec module_w,
const ring  r 
)

Definition at line 999 of file simpleideals.cc.

1000 {
1001  int i;
1002  BOOLEAN b;
1003  i = 0;
1004  b = TRUE;
1005  while ((i < IDELEMS(id)) && b)
1006  {
1007  b = p_IsHomogeneousW(id->m[i],w,module_w,r);
1008  i++;
1009  }
1010  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1011  {
1012  i=0;
1013  while ((i < IDELEMS(Q)) && b)
1014  {
1015  b = p_IsHomogeneousW(Q->m[i],w,r);
1016  i++;
1017  }
1018  }
1019  return b;
1020 }

◆ id_Homogen()

ideal id_Homogen ( ideal  h,
int  varnum,
const ring  r 
)

Definition at line 1397 of file simpleideals.cc.

1398 {
1399  ideal m = idInit(IDELEMS(h),h->rank);
1400  int i;
1401 
1402  for (i=IDELEMS(h)-1;i>=0; i--)
1403  {
1404  m->m[i]=p_Homogen(h->m[i],varnum,r);
1405  }
1406  return m;
1407 }
poly p_Homogen(poly p, int varnum, const ring r)
Definition: p_polys.cc:3266

◆ id_InsertPolyWithTests()

BOOLEAN id_InsertPolyWithTests ( ideal  h1,
const int  validEntries,
const poly  h2,
const bool  zeroOk,
const bool  duplicateOk,
const ring  r 
)

insert h2 into h1 depending on the two boolean parameters:

  • if zeroOk is true, then h2 will also be inserted when it is zero
  • if duplicateOk is true, then h2 will also be inserted when it is already present in h1 return TRUE iff h2 was indeed inserted

Definition at line 835 of file simpleideals.cc.

837 {
838  id_Test(h1, r);
839  p_Test(h2, r);
840 
841  if ((!zeroOk) && (h2 == NULL)) return FALSE;
842  if (!duplicateOk)
843  {
844  bool h2FoundInH1 = false;
845  int i = 0;
846  while ((i < validEntries) && (!h2FoundInH1))
847  {
848  h2FoundInH1 = p_EqualPolys(h1->m[i], h2,r);
849  i++;
850  }
851  if (h2FoundInH1) return FALSE;
852  }
853  if (validEntries == IDELEMS(h1))
854  {
855  pEnlargeSet(&(h1->m), IDELEMS(h1), 16);
856  IDELEMS(h1) += 16;
857  }
858  h1->m[validEntries] = h2;
859  return TRUE;
860 }
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3692
#define p_Test(p, r)
Definition: p_polys.h:159

◆ id_IsConstant()

BOOLEAN id_IsConstant ( ideal  id,
const ring  r 
)

test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant

Definition at line 486 of file simpleideals.cc.

487 {
488  id_Test(id, r);
489 
490  for (int k = IDELEMS(id)-1; k>=0; k--)
491  {
492  if (!p_IsConstantPoly(id->m[k],r))
493  return FALSE;
494  }
495  return TRUE;
496 }
static BOOLEAN p_IsConstantPoly(const poly p, const ring r)
Definition: p_polys.h:1976

◆ id_IsZeroDim()

BOOLEAN id_IsZeroDim ( ideal  I,
const ring  r 
)

Definition at line 1890 of file simpleideals.cc.

1891 {
1892  BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(rVar(r)*sizeof(BOOLEAN));
1893  int i,n;
1894  poly po;
1895  BOOLEAN res=TRUE;
1896  for(i=IDELEMS(I)-1;i>=0;i--)
1897  {
1898  po=I->m[i];
1899  if ((po!=NULL) &&((n=p_IsPurePower(po,r))!=0)) UsedAxis[n-1]=TRUE;
1900  }
1901  for(i=rVar(r)-1;i>=0;i--)
1902  {
1903  if(UsedAxis[i]==FALSE) {res=FALSE; break;} // not zero-dim.
1904  }
1905  omFreeSize(UsedAxis,rVar(r)*sizeof(BOOLEAN));
1906  return res;
1907 }
CanonicalForm res
Definition: facAbsFact.cc:60
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1226
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592

◆ id_Jet()

ideal id_Jet ( const ideal  i,
int  d,
const ring  R 
)

Definition at line 1729 of file simpleideals.cc.

1730 {
1731  ideal r=idInit((i->nrows)*(i->ncols),i->rank);
1732  r->nrows = i-> nrows;
1733  r->ncols = i-> ncols;
1734  //r->rank = i-> rank;
1735 
1736  for(long k=((long)(i->nrows))*((long)(i->ncols))-1;k>=0; k--)
1737  r->m[k]=pp_Jet(i->m[k],d,R);
1738 
1739  return r;
1740 }
poly pp_Jet(poly p, int m, const ring R)
Definition: p_polys.cc:4354

◆ id_JetW()

ideal id_JetW ( const ideal  i,
int  d,
intvec iv,
const ring  R 
)

Definition at line 1742 of file simpleideals.cc.

1743 {
1744  ideal r=idInit(IDELEMS(i),i->rank);
1745  if (ecartWeights!=NULL)
1746  {
1747  WerrorS("cannot compute weighted jets now");
1748  }
1749  else
1750  {
1751  int *w=iv2array(iv,R);
1752  int k;
1753  for(k=0; k<IDELEMS(i); k++)
1754  {
1755  r->m[k]=pp_JetW(i->m[k],d,w,R);
1756  }
1757  omFreeSize((ADDRESS)w,(rVar(R)+1)*sizeof(int));
1758  }
1759  return r;
1760 }
poly pp_JetW(poly p, int m, int *w, const ring R)
Definition: p_polys.cc:4399
int * iv2array(intvec *iv, const ring R)
Definition: weight.cc:200
EXTERN_VAR short * ecartWeights
Definition: weight.h:12

◆ id_Matrix2Module()

ideal id_Matrix2Module ( matrix  mat,
const ring  R 
)

converts mat to module, destroys mat

Definition at line 1442 of file simpleideals.cc.

1443 {
1444  int mc=MATCOLS(mat);
1445  int mr=MATROWS(mat);
1446  ideal result = idInit(mc,mr);
1447  int i,j,l;
1448  poly h;
1449  sBucket_pt bucket = sBucketCreate(R);
1450 
1451  for(j=0;j<mc /*MATCOLS(mat)*/;j++) /* j is also index in result->m */
1452  {
1453  for (i=0;i<mr /*MATROWS(mat)*/;i++)
1454  {
1455  h = MATELEM0(mat,i,j);
1456  if (h!=NULL)
1457  {
1458  l=pLength(h);
1459  MATELEM0(mat,i,j)=NULL;
1460  p_SetCompP(h,i+1, R);
1461  sBucket_Merge_p(bucket, h, l);
1462  }
1463  }
1464  sBucketClearMerge(bucket, &(result->m[j]), &l);
1465  }
1466  sBucketDestroy(&bucket);
1467 
1468  // obachman: need to clean this up
1469  id_Delete((ideal*) &mat,R);
1470  return result;
1471 }
#define MATELEM0(mat, i, j)
0-based access to matrix
Definition: matpol.h:31
#define MATROWS(i)
Definition: matpol.h:26
#define MATCOLS(i)
Definition: matpol.h:27

◆ id_MaxIdeal() [1/2]

ideal id_MaxIdeal ( const ring  r)

initialise the maximal ideal (at 0)

Definition at line 98 of file simpleideals.cc.

99 {
100  int nvars;
101 #ifdef HAVE_SHIFTBBA
102  if (r->isLPring)
103  {
104  nvars = r->isLPring;
105  }
106  else
107 #endif
108  {
109  nvars = rVar(r);
110  }
111  ideal hh = idInit(nvars, 1);
112  for (int l=nvars-1; l>=0; l--)
113  {
114  hh->m[l] = p_One(r);
115  p_SetExp(hh->m[l],l+1,1,r);
116  p_Setm(hh->m[l],r);
117  }
118  id_Test(hh, r);
119  return hh;
120 }
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:486
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231

◆ id_MaxIdeal() [2/2]

ideal id_MaxIdeal ( int  deg,
const ring  r 
)

Definition at line 1246 of file simpleideals.cc.

1247 {
1248  if (deg < 1)
1249  {
1250  ideal I=idInit(1,1);
1251  I->m[0]=p_One(r);
1252  return I;
1253  }
1254  if (deg == 1
1255 #ifdef HAVE_SHIFTBBA
1256  && !r->isLPring
1257 #endif
1258  )
1259  {
1260  return id_MaxIdeal(r);
1261  }
1262 
1263  int vars, i;
1264 #ifdef HAVE_SHIFTBBA
1265  if (r->isLPring)
1266  {
1267  vars = r->isLPring - r->LPncGenCount;
1268  i = 1;
1269  // i = vars^deg
1270  for (int j = 0; j < deg; j++)
1271  {
1272  i *= vars;
1273  }
1274  }
1275  else
1276 #endif
1277  {
1278  vars = rVar(r);
1279  i = binom(vars+deg-1,deg);
1280  }
1281  if (i<=0) return idInit(1,1);
1282  ideal id=idInit(i,1);
1283  idpower = id->m;
1284  idpowerpoint = 0;
1285 #ifdef HAVE_SHIFTBBA
1286  if (r->isLPring)
1287  {
1288  lpmakemonoms(vars, deg, r);
1289  }
1290  else
1291 #endif
1292  {
1293  makemonoms(vars,1,deg,0,r);
1294  }
1295  idpower = NULL;
1296  idpowerpoint = 0;
1297  return id;
1298 }
STATIC_VAR int idpowerpoint
Definition: simpleideals.cc:31
STATIC_VAR poly * idpower
Definition: simpleideals.cc:29
static void makemonoms(int vars, int actvar, int deg, int monomdeg, const ring r)
ideal id_MaxIdeal(const ring r)
initialise the maximal ideal (at 0)
Definition: simpleideals.cc:98
static void lpmakemonoms(int vars, int deg, const ring r)

◆ id_MinDegW()

int id_MinDegW ( ideal  M,
intvec w,
const ring  r 
)

Definition at line 1919 of file simpleideals.cc.

1920 {
1921  int d=-1;
1922  for(int i=0;i<IDELEMS(M);i++)
1923  {
1924  if (M->m[i]!=NULL)
1925  {
1926  int d0=p_MinDeg(M->m[i],w,r);
1927  if(-1<d0&&((d0<d)||(d==-1)))
1928  d=d0;
1929  }
1930  }
1931  return d;
1932 }
int p_MinDeg(poly p, intvec *w, const ring R)
Definition: p_polys.cc:4444
#define M
Definition: sirandom.c:25

◆ id_Module2formatedMatrix()

matrix id_Module2formatedMatrix ( ideal  mod,
int  rows,
int  cols,
const ring  R 
)

Definition at line 1522 of file simpleideals.cc.

1523 {
1524  matrix result = mpNew(rows,cols);
1525  int i,cp,r=id_RankFreeModule(mod,R),c=IDELEMS(mod);
1526  poly p,h;
1527 
1528  if (r>rows) r = rows;
1529  if (c>cols) c = cols;
1530  for(i=0;i<c;i++)
1531  {
1532  p=pReverse(mod->m[i]);
1533  mod->m[i]=NULL;
1534  while (p!=NULL)
1535  {
1536  h=p;
1537  pIter(p);
1538  pNext(h)=NULL;
1539  cp = p_GetComp(h,R);
1540  if (cp<=r)
1541  {
1542  p_SetComp(h,0,R);
1543  p_SetmComp(h,R);
1544  MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1545  }
1546  else
1547  p_Delete(&h,R);
1548  }
1549  }
1550  id_Delete(&mod,R);
1551  return result;
1552 }
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition: matpol.cc:37
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static poly pReverse(poly p)
Definition: p_polys.h:333
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s

◆ id_Module2Matrix()

matrix id_Module2Matrix ( ideal  mod,
const ring  R 
)

Definition at line 1476 of file simpleideals.cc.

1477 {
1478  matrix result = mpNew(mod->rank,IDELEMS(mod));
1479  long i; long cp;
1480  poly p,h;
1481 
1482  for(i=0;i<IDELEMS(mod);i++)
1483  {
1484  p=pReverse(mod->m[i]);
1485  mod->m[i]=NULL;
1486  while (p!=NULL)
1487  {
1488  h=p;
1489  pIter(p);
1490  pNext(h)=NULL;
1491  cp = si_max(1L,p_GetComp(h, R)); // if used for ideals too
1492  //cp = p_GetComp(h,R);
1493  p_SetComp(h,0,R);
1494  p_SetmComp(h,R);
1495 #ifdef TEST
1496  if (cp>mod->rank)
1497  {
1498  Print("## inv. rank %ld -> %ld\n",mod->rank,cp);
1499  int k,l,o=mod->rank;
1500  mod->rank=cp;
1501  matrix d=mpNew(mod->rank,IDELEMS(mod));
1502  for (l=0; l<o; l++)
1503  {
1504  for (k=0; k<IDELEMS(mod); k++)
1505  {
1506  MATELEM0(d,l,k)=MATELEM0(result,l,k);
1507  MATELEM0(result,l,k)=NULL;
1508  }
1509  }
1510  id_Delete((ideal *)&result,R);
1511  result=d;
1512  }
1513 #endif
1514  MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1515  }
1516  }
1517  // obachman 10/99: added the following line, otherwise memory leack!
1518  id_Delete(&mod,R);
1519  return result;
1520 }

◆ id_Mult()

ideal id_Mult ( ideal  h1,
ideal  h2,
const ring  R 
)

h1 * h2 one h_i must be an ideal (with at least one column) the other h_i may be a module (with no columns at all)

Definition at line 876 of file simpleideals.cc.

877 {
878  id_Test(h1, R);
879  id_Test(h2, R);
880 
881  int j = IDELEMS(h1);
882  while ((j > 0) && (h1->m[j-1] == NULL)) j--;
883 
884  int i = IDELEMS(h2);
885  while ((i > 0) && (h2->m[i-1] == NULL)) i--;
886 
887  j *= i;
888  int r = si_max( h2->rank, h1->rank );
889  if (j==0)
890  {
891  if ((IDELEMS(h1)>0) && (IDELEMS(h2)>0)) j=1;
892  return idInit(j, r);
893  }
894  ideal hh = idInit(j, r);
895 
896  int k = 0;
897  for (i=0; i<IDELEMS(h1); i++)
898  {
899  if (h1->m[i] != NULL)
900  {
901  for (j=0; j<IDELEMS(h2); j++)
902  {
903  if (h2->m[j] != NULL)
904  {
905  hh->m[k] = pp_Mult_qq(h1->m[i],h2->m[j],R);
906  k++;
907  }
908  }
909  }
910  }
911 
912  id_Compactify(hh,R);
913  return hh;
914 }
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1149

◆ id_NextPotence()

static void id_NextPotence ( ideal  given,
ideal  result,
int  begin,
int  end,
int  deg,
int  restdeg,
poly  ap,
const ring  r 
)
static

Definition at line 1300 of file simpleideals.cc.

1302 {
1303  poly p;
1304  int i;
1305 
1306  p = p_Power(p_Copy(given->m[begin],r),restdeg,r);
1307  i = result->nrows;
1308  result->m[i] = p_Mult_q(p_Copy(ap,r),p,r);
1309 //PrintS(".");
1310  (result->nrows)++;
1311  if (result->nrows >= IDELEMS(result))
1312  {
1313  pEnlargeSet(&(result->m),IDELEMS(result),16);
1314  IDELEMS(result) += 16;
1315  }
1316  if (begin == end) return;
1317  for (i=restdeg-1;i>0;i--)
1318  {
1319  p = p_Power(p_Copy(given->m[begin],r),i,r);
1320  p = p_Mult_q(p_Copy(ap,r),p,r);
1321  id_NextPotence(given, result, begin+1, end, deg, restdeg-i, p,r);
1322  p_Delete(&p,r);
1323  }
1324  id_NextPotence(given, result, begin+1, end, deg, restdeg, ap,r);
1325 }
Definition: ap.h:40
poly p_Power(poly p, int i, const ring r)
Definition: p_polys.cc:2193
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1112
static void id_NextPotence(ideal given, ideal result, int begin, int end, int deg, int restdeg, poly ap, const ring r)

◆ id_Norm()

void id_Norm ( ideal  id,
const ring  r 
)

ideal id = (id[i]), result is leadcoeff(id[i]) = 1

Definition at line 239 of file simpleideals.cc.

240 {
241  id_Test(id, r);
242  for (int i=IDELEMS(id)-1; i>=0; i--)
243  {
244  if (id->m[i] != NULL)
245  {
246  p_Norm(id->m[i],r);
247  }
248  }
249 }
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3715

◆ id_Normalize()

void id_Normalize ( ideal  I,
const ring  r 
)

normialize all polys in id

Definition at line 1909 of file simpleideals.cc.

1910 {
1911  if (rField_has_simple_inverse(r)) return; /* Z/p, GF(p,n), R, long R/C */
1912  int i;
1913  for(i=I->nrows*I->ncols-1;i>=0;i--)
1914  {
1915  p_Normalize(I->m[i],r);
1916  }
1917 }
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3809
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:548

◆ id_PosConstant()

int id_PosConstant ( ideal  id,
const ring  r 
)

index of generator with leading term in ground ring (if any); otherwise -1

Definition at line 80 of file simpleideals.cc.

81 {
82  id_Test(id, r);
83  const int N = IDELEMS(id) - 1;
84  const poly * m = id->m + N;
85 
86  for (int k = N; k >= 0; --k, --m)
87  {
88  const poly p = *m;
89  if (p!=NULL)
90  if (p_LmIsConstantComp(p, r) == TRUE)
91  return k;
92  }
93 
94  return -1;
95 }
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:1004

◆ id_Power()

ideal id_Power ( ideal  given,
int  exp,
const ring  r 
)

Definition at line 1327 of file simpleideals.cc.

1328 {
1329  ideal result,temp;
1330  poly p1;
1331  int i;
1332 
1333  if (idIs0(given)) return idInit(1,1);
1334  temp = id_Copy(given,r);
1335  idSkipZeroes(temp);
1336  i = binom(IDELEMS(temp)+exp-1,exp);
1337  result = idInit(i,1);
1338  result->nrows = 0;
1339 //Print("ideal contains %d elements\n",i);
1340  p1=p_One(r);
1341  id_NextPotence(temp,result,0,IDELEMS(temp)-1,exp,exp,p1,r);
1342  p_Delete(&p1,r);
1343  id_Delete(&temp,r);
1344  result->nrows = 1;
1345  id_DelEquals(result,r);
1347  return result;
1348 }
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
ideal id_Copy(ideal h1, const ring r)
copy an ideal
void id_DelEquals(ideal id, const ring r)
ideal id = (id[i]) if id[i] = id[j] then id[j] is deleted for j > i

◆ id_QHomWeight()

intvec* id_QHomWeight ( ideal  id,
const ring  r 
)

Definition at line 1843 of file simpleideals.cc.

1844 {
1845  poly head, tail;
1846  int k;
1847  int in=IDELEMS(id)-1, ready=0, all=0,
1848  coldim=rVar(r), rowmax=2*coldim;
1849  if (in<0) return NULL;
1850  intvec *imat=new intvec(rowmax+1,coldim,0);
1851 
1852  do
1853  {
1854  head = id->m[in--];
1855  if (head!=NULL)
1856  {
1857  tail = pNext(head);
1858  while (tail!=NULL)
1859  {
1860  all++;
1861  for (k=1;k<=coldim;k++)
1862  IMATELEM(*imat,all,k) = p_GetExpDiff(head,tail,k,r);
1863  if (all==rowmax)
1864  {
1865  ivTriangIntern(imat, ready, all);
1866  if (ready==coldim)
1867  {
1868  delete imat;
1869  return NULL;
1870  }
1871  }
1872  pIter(tail);
1873  }
1874  }
1875  } while (in>=0);
1876  if (all>ready)
1877  {
1878  ivTriangIntern(imat, ready, all);
1879  if (ready==coldim)
1880  {
1881  delete imat;
1882  return NULL;
1883  }
1884  }
1885  intvec *result = ivSolveKern(imat, ready);
1886  delete imat;
1887  return result;
1888 }
CanonicalForm head(const CanonicalForm &f)
void ivTriangIntern(intvec *imat, int &ready, int &all)
Definition: intvec.cc:404
intvec * ivSolveKern(intvec *imat, int dimtr)
Definition: intvec.cc:442
#define IMATELEM(M, I, J)
Definition: intvec.h:85
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:633

◆ id_RankFreeModule()

long id_RankFreeModule ( ideal  s,
ring  lmRing,
ring  tailRing 
)

return the maximal component number found in any polynomial in s

Definition at line 931 of file simpleideals.cc.

932 {
933  long j = 0;
934 
935  if (rRing_has_Comp(tailRing) && rRing_has_Comp(lmRing))
936  {
937  poly *p=s->m;
938  for (unsigned int l=IDELEMS(s); l > 0; --l, ++p)
939  if (*p != NULL)
940  {
941  pp_Test(*p, lmRing, tailRing);
942  const long k = p_MaxComp(*p, lmRing, tailRing);
943  if (k>j) j = k;
944  }
945  }
946 
947  return j; // return -1;
948 }
const CanonicalForm int s
Definition: facAbsFact.cc:51
#define rRing_has_Comp(r)
Definition: monomials.h:266
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:161

◆ id_ReadOutPivot()

int id_ReadOutPivot ( ideal  arg,
int *  comp,
const ring  r 
)

Definition at line 1766 of file simpleideals.cc.

1767 {
1768  if (idIs0(arg)) return -1;
1769  int i=0,j, generator=-1;
1770  int rk_arg=arg->rank; //idRankFreeModule(arg);
1771  int * componentIsUsed =(int *)omAlloc((rk_arg+1)*sizeof(int));
1772  poly p;
1773 
1774  while ((generator<0) && (i<IDELEMS(arg)))
1775  {
1776  memset(componentIsUsed,0,(rk_arg+1)*sizeof(int));
1777  p = arg->m[i];
1778  while (p!=NULL)
1779  {
1780  j = __p_GetComp(p,r);
1781  if (componentIsUsed[j]==0)
1782  {
1783  if (p_LmIsConstantComp(p,r) &&
1784  (!rField_is_Ring(r) || n_IsUnit(pGetCoeff(p),r->cf)))
1785  {
1786  generator = i;
1787  componentIsUsed[j] = 1;
1788  }
1789  else
1790  {
1791  componentIsUsed[j] = -1;
1792  }
1793  }
1794  else if (componentIsUsed[j]>0)
1795  {
1796  (componentIsUsed[j])++;
1797  }
1798  pIter(p);
1799  }
1800  i++;
1801  }
1802  i = 0;
1803  *comp = -1;
1804  for (j=0;j<=rk_arg;j++)
1805  {
1806  if (componentIsUsed[j]>0)
1807  {
1808  if ((*comp==-1) || (componentIsUsed[j]<i))
1809  {
1810  *comp = j;
1811  i= componentIsUsed[j];
1812  }
1813  }
1814  }
1815  omFree(componentIsUsed);
1816  return generator;
1817 }
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
#define omFree(addr)
Definition: omAllocDecl.h:261

◆ id_ResizeModule()

ideal id_ResizeModule ( ideal  mod,
int  rows,
int  cols,
const ring  R 
)

Definition at line 1554 of file simpleideals.cc.

1555 {
1556  // columns?
1557  if (cols!=IDELEMS(mod))
1558  {
1559  for(int i=IDELEMS(mod)-1;i>=cols;i--) p_Delete(&mod->m[i],R);
1560  pEnlargeSet(&(mod->m),IDELEMS(mod),cols-IDELEMS(mod));
1561  IDELEMS(mod)=cols;
1562  }
1563  // rows?
1564  if (rows<mod->rank)
1565  {
1566  for(int i=IDELEMS(mod)-1;i>=0;i--)
1567  {
1568  if (mod->m[i]!=NULL)
1569  {
1570  while((mod->m[i]!=NULL) && (p_GetComp(mod->m[i],R)>rows))
1571  mod->m[i]=p_LmDeleteAndNext(mod->m[i],R);
1572  poly p=mod->m[i];
1573  while(pNext(p)!=NULL)
1574  {
1575  if (p_GetComp(pNext(p),R)>rows)
1577  else
1578  pIter(p);
1579  }
1580  }
1581  }
1582  }
1583  mod->rank=rows;
1584  return mod;
1585 }
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:753

◆ id_ShallowDelete()

void id_ShallowDelete ( ideal *  h,
ring  r 
)

Shallowdeletes an ideal/matrix.

Definition at line 157 of file simpleideals.cc.

158 {
159  id_Test(*h, r);
160 
161  if (*h == NULL)
162  return;
163 
164  int j,elems;
165  elems=j=(*h)->nrows*(*h)->ncols;
166  if (j>0)
167  {
168  assume( (*h)->m != NULL );
169  do
170  {
171  p_ShallowDelete(&((*h)->m[--j]), r);
172  }
173  while (j>0);
174  omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
175  }
177  *h=NULL;
178 }
void p_ShallowDelete(poly *p, const ring r)

◆ id_Shift()

void id_Shift ( ideal  M,
int  s,
const ring  r 
)

Definition at line 2121 of file simpleideals.cc.

2122 {
2123 // id_Test( M, r );
2124 
2125 // assume( s >= 0 ); // negative is also possible // TODO: verify input ideal in such a case!?
2126 
2127  for(int i=IDELEMS(M)-1; i>=0;i--)
2128  p_Shift(&(M->m[i]),s,r);
2129 
2130  M->rank += s;
2131 
2132 // id_Test( M, r );
2133 }
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4702

◆ id_SimpleAdd()

ideal id_SimpleAdd ( ideal  h1,
ideal  h2,
const ring  R 
)

concat the lists h1 and h2 without zeros

Definition at line 747 of file simpleideals.cc.

748 {
749  id_Test(h1, R);
750  id_Test(h2, R);
751 
752  if ( idIs0(h1) )
753  {
754  ideal res=id_Copy(h2,R);
755  if (res->rank<h1->rank) res->rank=h1->rank;
756  return res;
757  }
758  if ( idIs0(h2) )
759  {
760  ideal res=id_Copy(h1,R);
761  if (res->rank<h2->rank) res->rank=h2->rank;
762  return res;
763  }
764 
765  int j = IDELEMS(h1)-1;
766  while ((j >= 0) && (h1->m[j] == NULL)) j--;
767 
768  int i = IDELEMS(h2)-1;
769  while ((i >= 0) && (h2->m[i] == NULL)) i--;
770 
771  const int r = si_max(h1->rank, h2->rank);
772 
773  ideal result = idInit(i+j+2,r);
774 
775  int l;
776 
777  for (l=j; l>=0; l--)
778  result->m[l] = p_Copy(h1->m[l],R);
779 
780  j = i+j+1;
781  for (l=i; l>=0; l--, j--)
782  result->m[j] = p_Copy(h2->m[l],R);
783 
784  return result;
785 }

◆ id_Sort()

intvec* id_Sort ( const ideal  id,
const BOOLEAN  nolex,
const ring  r 
)

sorts the ideal w.r.t. the actual ringordering uses lex-ordering when nolex = FALSE

Definition at line 652 of file simpleideals.cc.

653 {
654  id_Test(id, r);
655 
656  intvec * result = new intvec(IDELEMS(id));
657  int i, j, actpos=0, newpos;
658  int diff, olddiff, lastcomp, newcomp;
659  BOOLEAN notFound;
660 
661  for (i=0;i<IDELEMS(id);i++)
662  {
663  if (id->m[i]!=NULL)
664  {
665  notFound = TRUE;
666  newpos = actpos / 2;
667  diff = (actpos+1) / 2;
668  diff = (diff+1) / 2;
669  lastcomp = p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r);
670  if (lastcomp<0)
671  {
672  newpos -= diff;
673  }
674  else if (lastcomp>0)
675  {
676  newpos += diff;
677  }
678  else
679  {
680  notFound = FALSE;
681  }
682  //while ((newpos>=0) && (newpos<actpos) && (notFound))
683  while (notFound && (newpos>=0) && (newpos<actpos))
684  {
685  newcomp = p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r);
686  olddiff = diff;
687  if (diff>1)
688  {
689  diff = (diff+1) / 2;
690  if ((newcomp==1)
691  && (actpos-newpos>1)
692  && (diff>1)
693  && (newpos+diff>=actpos))
694  {
695  diff = actpos-newpos-1;
696  }
697  else if ((newcomp==-1)
698  && (diff>1)
699  && (newpos<diff))
700  {
701  diff = newpos;
702  }
703  }
704  if (newcomp<0)
705  {
706  if ((olddiff==1) && (lastcomp>0))
707  notFound = FALSE;
708  else
709  newpos -= diff;
710  }
711  else if (newcomp>0)
712  {
713  if ((olddiff==1) && (lastcomp<0))
714  {
715  notFound = FALSE;
716  newpos++;
717  }
718  else
719  {
720  newpos += diff;
721  }
722  }
723  else
724  {
725  notFound = FALSE;
726  }
727  lastcomp = newcomp;
728  if (diff==0) notFound=FALSE; /*hs*/
729  }
730  if (newpos<0) newpos = 0;
731  if (newpos>actpos) newpos = actpos;
732  while ((newpos<actpos) && (p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r)==0))
733  newpos++;
734  for (j=actpos;j>newpos;j--)
735  {
736  (*result)[j] = (*result)[j-1];
737  }
738  (*result)[newpos] = i;
739  actpos++;
740  }
741  }
742  for (j=0;j<actpos;j++) (*result)[j]++;
743  return result;
744 }
static int p_Comp_RevLex(poly a, poly b, BOOLEAN nolex, const ring R)
for idSort: compare a and b revlex inclusive module comp.

◆ id_Subst()

ideal id_Subst ( ideal  id,
int  n,
poly  e,
const ring  r 
)

Definition at line 1591 of file simpleideals.cc.

1592 {
1593  int k=MATROWS((matrix)id)*MATCOLS((matrix)id);
1594  ideal res=(ideal)mpNew(MATROWS((matrix)id),MATCOLS((matrix)id));
1595 
1596  res->rank = id->rank;
1597  for(k--;k>=0;k--)
1598  {
1599  res->m[k]=p_Subst(id->m[k],n,e,r);
1600  id->m[k]=NULL;
1601  }
1602  id_Delete(&id,r);
1603  return res;
1604 }
poly * m
Definition: matpol.h:18
poly p_Subst(poly p, int n, poly e, const ring r)
Definition: p_polys.cc:3954

◆ id_TensorModuleMult()

ideal id_TensorModuleMult ( const int  m,
const ideal  M,
const ring  rRing 
)

Definition at line 1992 of file simpleideals.cc.

1993 {
1994 // #ifdef DEBU
1995 // WarnS("tensorModuleMult!!!!");
1996 
1997  assume(m > 0);
1998  assume(M != NULL);
1999 
2000  const int n = rRing->N;
2001 
2002  assume(M->rank <= m * n);
2003 
2004  const int k = IDELEMS(M);
2005 
2006  ideal idTemp = idInit(k,m); // = {f_1, ..., f_k }
2007 
2008  for( int i = 0; i < k; i++ ) // for every w \in M
2009  {
2010  poly pTempSum = NULL;
2011 
2012  poly w = M->m[i];
2013 
2014  while(w != NULL) // for each term of w...
2015  {
2016  poly h = p_Head(w, rRing);
2017 
2018  const int gen = __p_GetComp(h, rRing); // 1 ...
2019 
2020  assume(gen > 0);
2021  assume(gen <= n*m);
2022 
2023  // TODO: write a formula with %, / instead of while!
2024  /*
2025  int c = gen;
2026  int v = 1;
2027  while(c > m)
2028  {
2029  c -= m;
2030  v++;
2031  }
2032  */
2033 
2034  int cc = gen % m;
2035  if( cc == 0) cc = m;
2036  int vv = 1 + (gen - cc) / m;
2037 
2038 // assume( cc == c );
2039 // assume( vv == v );
2040 
2041  // 1<= c <= m
2042  assume( cc > 0 );
2043  assume( cc <= m );
2044 
2045  assume( vv > 0 );
2046  assume( vv <= n );
2047 
2048  assume( (cc + (vv-1)*m) == gen );
2049 
2050  p_IncrExp(h, vv, rRing); // h *= var(j) && // p_AddExp(h, vv, 1, rRing);
2051  p_SetComp(h, cc, rRing);
2052 
2053  p_Setm(h, rRing); // addjust degree after the previous steps!
2054 
2055  pTempSum = p_Add_q(pTempSum, h, rRing); // it is slow since h will be usually put to the back of pTempSum!!!
2056 
2057  pIter(w);
2058  }
2059 
2060  idTemp->m[i] = pTempSum;
2061  }
2062 
2063  // simplify idTemp???
2064 
2065  ideal idResult = id_Transp(idTemp, rRing);
2066 
2067  id_Delete(&idTemp, rRing);
2068 
2069  return(idResult);
2070 }
static long p_IncrExp(poly p, int v, ring r)
Definition: p_polys.h:589
ideal id_Transp(ideal a, const ring rRing)
transpose a module

◆ id_Transp()

ideal id_Transp ( ideal  a,
const ring  rRing 
)

transpose a module

Definition at line 1939 of file simpleideals.cc.

1940 {
1941  int r = a->rank, c = IDELEMS(a);
1942  ideal b = idInit(r,c);
1943 
1944  int i;
1945  for (i=c; i>0; i--)
1946  {
1947  poly p=a->m[i-1];
1948  while(p!=NULL)
1949  {
1950  poly h=p_Head(p, rRing);
1951  int co=__p_GetComp(h, rRing)-1;
1952  p_SetComp(h, i, rRing);
1953  p_Setm(h, rRing);
1954  h->next=b->m[co];
1955  b->m[co]=h;
1956  pIter(p);
1957  }
1958  }
1959  for (i=IDELEMS(b)-1; i>=0; i--)
1960  {
1961  poly p=b->m[i];
1962  if(p!=NULL)
1963  {
1964  b->m[i]=p_SortMerge(p,rRing,TRUE);
1965  }
1966  }
1967  return b;
1968 }
static poly p_SortMerge(poly p, const ring r, BOOLEAN revert=FALSE)
Definition: p_polys.h:1227

◆ id_Vec2Ideal()

ideal id_Vec2Ideal ( poly  vec,
const ring  R 
)

Definition at line 1410 of file simpleideals.cc.

1411 {
1412  ideal result=idInit(1,1);
1414  p_Vec2Polys(vec, &(result->m), &(IDELEMS(result)),R);
1415  return result;
1416 }
fq_nmod_poly_t * vec
Definition: facHensel.cc:108
#define omFreeBinAddr(addr)
Definition: omAllocDecl.h:258
void p_Vec2Polys(poly v, poly **p, int *len, const ring r)
Definition: p_polys.cc:3621

◆ idGetNextChoise()

void idGetNextChoise ( int  r,
int  end,
BOOLEAN endch,
int *  choise 
)

Definition at line 1048 of file simpleideals.cc.

1049 {
1050  int i = r-1,j;
1051  while ((i >= 0) && (choise[i] == end))
1052  {
1053  i--;
1054  end--;
1055  }
1056  if (i == -1)
1057  *endch = TRUE;
1058  else
1059  {
1060  choise[i]++;
1061  for (j=i+1; j<r; j++)
1062  {
1063  choise[j] = choise[i]+j-i;
1064  }
1065  *endch = FALSE;
1066  }
1067 }

◆ idGetNumberOfChoise()

int idGetNumberOfChoise ( int  t,
int  d,
int  begin,
int  end,
int *  choise 
)

Definition at line 1074 of file simpleideals.cc.

1075 {
1076  int * localchoise,i,result=0;
1077  BOOLEAN b=FALSE;
1078 
1079  if (d<=1) return 1;
1080  localchoise=(int*)omAlloc((d-1)*sizeof(int));
1081  idInitChoise(d-1,begin,end,&b,localchoise);
1082  while (!b)
1083  {
1084  result++;
1085  i = 0;
1086  while ((i<t) && (localchoise[i]==choise[i])) i++;
1087  if (i>=t)
1088  {
1089  i = t+1;
1090  while ((i<d) && (localchoise[i-1]==choise[i])) i++;
1091  if (i>=d)
1092  {
1093  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1094  return result;
1095  }
1096  }
1097  idGetNextChoise(d-1,end,&b,localchoise);
1098  }
1099  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1100  return 0;
1101 }
void idGetNextChoise(int r, int end, BOOLEAN *endch, int *choise)
void idInitChoise(int r, int beg, int end, BOOLEAN *endch, int *choise)

◆ idInit()

ideal idInit ( int  idsize,
int  rank 
)

initialise an ideal / module

creates an ideal / module

Definition at line 35 of file simpleideals.cc.

36 {
37  assume( idsize >= 0 && rank >= 0 );
38 
39  ideal hh = (ideal)omAllocBin(sip_sideal_bin);
40 
41  IDELEMS(hh) = idsize; // ncols
42  hh->nrows = 1; // ideal/module!
43 
44  hh->rank = rank; // ideal: 1, module: >= 0!
45 
46  if (idsize>0)
47  hh->m = (poly *)omAlloc0(idsize*sizeof(poly));
48  else
49  hh->m = NULL;
50 
51  return hh;
52 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205

◆ idInitChoise()

void idInitChoise ( int  r,
int  beg,
int  end,
BOOLEAN endch,
int *  choise 
)

Definition at line 1026 of file simpleideals.cc.

1027 {
1028  /*returns the first choise of r numbers between beg and end*/
1029  int i;
1030  for (i=0; i<r; i++)
1031  {
1032  choise[i] = 0;
1033  }
1034  if (r <= end-beg+1)
1035  for (i=0; i<r; i++)
1036  {
1037  choise[i] = beg+i;
1038  }
1039  if (r > end-beg+1)
1040  *endch = TRUE;
1041  else
1042  *endch = FALSE;
1043 }

◆ idInsertPoly()

BOOLEAN idInsertPoly ( ideal  h1,
poly  h2 
)

insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted

Definition at line 789 of file simpleideals.cc.

790 {
791  if (h2==NULL) return FALSE;
792  assume (h1 != NULL);
793 
794  int j = IDELEMS(h1) - 1;
795 
796  while ((j >= 0) && (h1->m[j] == NULL)) j--;
797  j++;
798  if (j==IDELEMS(h1))
799  {
800  pEnlargeSet(&(h1->m),IDELEMS(h1),16);
801  IDELEMS(h1)+=16;
802  }
803  h1->m[j]=h2;
804  return TRUE;
805 }

◆ idInsertPolyOnPos()

BOOLEAN idInsertPolyOnPos ( ideal  I,
poly  p,
int  pos 
)

insert p into I on position pos

Definition at line 808 of file simpleideals.cc.

809 {
810  if (p==NULL) return FALSE;
811  assume (I != NULL);
812 
813  int j = IDELEMS(I) - 1;
814 
815  while ((j >= 0) && (I->m[j] == NULL)) j--;
816  j++;
817  if (j==IDELEMS(I))
818  {
819  pEnlargeSet(&(I->m),IDELEMS(I),IDELEMS(I)+1);
820  IDELEMS(I)+=1;
821  }
822  for(j = IDELEMS(I)-1;j>pos;j--)
823  I->m[j] = I->m[j-1];
824  I->m[pos]=p;
825  return TRUE;
826 }

◆ idIs0()

BOOLEAN idIs0 ( ideal  h)

returns true if h is the zero ideal

Definition at line 917 of file simpleideals.cc.

918 {
919  assume (h != NULL); // will fail :(
920 // if (h == NULL) return TRUE;
921 
922  for( int i = IDELEMS(h)-1; i >= 0; i-- )
923  if(h->m[i] != NULL)
924  return FALSE;
925 
926  return TRUE;
927 
928 }

◆ idShow()

void idShow ( const ideal  id,
const ring  lmRing,
const ring  tailRing,
const int  debugPrint 
)

Definition at line 57 of file simpleideals.cc.

58 {
59  assume( debugPrint >= 0 );
60 
61  if( id == NULL )
62  PrintS("(NULL)");
63  else
64  {
65  Print("Module of rank %ld,real rank %ld and %d generators.\n",
66  id->rank,id_RankFreeModule(id, lmRing, tailRing),IDELEMS(id));
67 
68  int j = (id->ncols*id->nrows) - 1;
69  while ((j > 0) && (id->m[j]==NULL)) j--;
70  for (int i = 0; i <= j; i++)
71  {
72  Print("generator %d: ",i); p_wrp(id->m[i], lmRing, tailRing);PrintLn();
73  }
74  }
75 }
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:373
void PrintLn()
Definition: reporter.cc:310

◆ idSkipZeroes()

void idSkipZeroes ( ideal  ide)

gives an ideal/module the minimal possible size

Definition at line 181 of file simpleideals.cc.

182 {
183  assume (ide != NULL);
184 
185  int k;
186  int j = -1;
187  int idelems=IDELEMS(ide);
188  BOOLEAN change=FALSE;
189 
190  for (k=0; k<idelems; k++)
191  {
192  if (ide->m[k] != NULL)
193  {
194  j++;
195  if (change)
196  {
197  ide->m[j] = ide->m[k];
198  }
199  }
200  else
201  {
202  change=TRUE;
203  }
204  }
205  if (change)
206  {
207  if (j == -1)
208  j = 0;
209  else
210  {
211  for (k=j+1; k<idelems; k++)
212  ide->m[k] = NULL;
213  }
214  j++;
215  pEnlargeSet(&(ide->m),idelems,j-idelems);
216  IDELEMS(ide) = j;
217  }
218 }

◆ lpmakemonoms()

static void lpmakemonoms ( int  vars,
int  deg,
const ring  r 
)
static

Definition at line 1208 of file simpleideals.cc.

1209 {
1210  assume(deg <= r->N/r->isLPring);
1211  if (deg == 0)
1212  {
1213  idpower[0] = p_One(r);
1214  return;
1215  }
1216  else
1217  {
1218  lpmakemonoms(vars, deg - 1, r);
1219  }
1220 
1221  int size = idpowerpoint + 1;
1222  for (int j = 2; j <= vars; j++)
1223  {
1224  for (int i = 0; i < size; i++)
1225  {
1226  idpowerpoint = (j-1)*size + i;
1228  }
1229  }
1230  for (int j = 1; j <= vars; j++)
1231  {
1232  for (int i = 0; i < size; i++)
1233  {
1234  idpowerpoint = (j-1)*size + i;
1235  p_SetExp(idpower[idpowerpoint], ((deg - 1) * r->isLPring) + j, 1, r);
1238  }
1239  }
1240 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600

◆ makemonoms()

static void makemonoms ( int  vars,
int  actvar,
int  deg,
int  monomdeg,
const ring  r 
)
static

Definition at line 1160 of file simpleideals.cc.

1161 {
1162  poly p;
1163  int i=0;
1164 
1165  if ((idpowerpoint == 0) && (actvar ==1))
1166  {
1167  idpower[idpowerpoint] = p_One(r);
1168  monomdeg = 0;
1169  }
1170  while (i<=deg)
1171  {
1172  if (deg == monomdeg)
1173  {
1175  idpowerpoint++;
1176  return;
1177  }
1178  if (actvar == vars)
1179  {
1180  p_SetExp(idpower[idpowerpoint],actvar,deg-monomdeg,r);
1183  idpowerpoint++;
1184  return;
1185  }
1186  else
1187  {
1188  p = p_Copy(idpower[idpowerpoint],r);
1189  makemonoms(vars,actvar+1,deg,monomdeg,r);
1190  idpower[idpowerpoint] = p;
1191  }
1192  monomdeg++;
1193  p_SetExp(idpower[idpowerpoint],actvar,p_GetExp(idpower[idpowerpoint],actvar,r)+1,r);
1196  i++;
1197  }
1198 }
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:467

◆ p_Comp_RevLex()

static int p_Comp_RevLex ( poly  a,
poly  b,
BOOLEAN  nolex,
const ring  R 
)
static

for idSort: compare a and b revlex inclusive module comp.

Definition at line 615 of file simpleideals.cc.

616 {
617  if (b==NULL) return 1;
618  if (a==NULL) return -1;
619 
620  if (nolex)
621  {
622  int r=p_LtCmp(a,b,R);
623  return r;
624  #if 0
625  if (r!=0) return r;
626  number h=n_Sub(pGetCoeff(a),pGetCoeff(b),R->cf);
627  r = -1+n_IsZero(h,R->cf)+2*n_GreaterZero(h,R->cf); /* -1: <, 0:==, 1: > */
628  n_Delete(&h, R->cf);
629  return r;
630  #endif
631  }
632  int l=rVar(R);
633  while ((l>0) && (p_GetExp(a,l,R)==p_GetExp(b,l,R))) l--;
634  if (l==0)
635  {
636  if (p_GetComp(a,R)==p_GetComp(b,R))
637  {
638  number h=n_Sub(pGetCoeff(a),pGetCoeff(b),R->cf);
639  int r = -1+n_IsZero(h,R->cf)+2*n_GreaterZero(h,R->cf); /* -1: <, 0:==, 1: > */
640  n_Delete(&h,R->cf);
641  return r;
642  }
643  if (p_GetComp(a,R)>p_GetComp(b,R)) return 1;
644  }
645  else if (p_GetExp(a,l,R)>p_GetExp(b,l,R))
646  return 1;
647  return -1;
648 }
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition: coeffs.h:491
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:652
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
static int p_LtCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1619

Variable Documentation

◆ idpower

STATIC_VAR poly* idpower

Definition at line 29 of file simpleideals.cc.

◆ idpowerpoint

STATIC_VAR int idpowerpoint

Definition at line 31 of file simpleideals.cc.

◆ sip_sideal_bin

VAR omBin sip_sideal_bin = omGetSpecBin(sizeof(sip_sideal))

Definition at line 27 of file simpleideals.cc.