Functions
tropicalStrategy.cc File Reference
#include <tropicalStrategy.h>
#include <adjustWeights.h>
#include <ppinitialReduction.h>
#include <tropical.h>
#include <std_wrapper.h>
#include <tropicalCurves.h>
#include <kernel/ideals.h>
#include <kernel/combinatorics/stairc.h>
#include <kernel/GBEngine/kstd1.h>
#include <misc/prime.h>

Go to the source code of this file.

Functions

int dim (ideal I, ring r)
 
static void swapElements (ideal I, ideal J)
 
static bool noExtraReduction (ideal I, ring r, number)
 
static ring constructStartingRing (ring r)
 Given a polynomial ring r over the rational numbers and a weighted ordering, returns a polynomial ring s over the integers with one extra variable, which is weighted -1. More...
 
static ideal constructStartingIdeal (ideal originalIdeal, ring originalRing, number uniformizingParameter, ring startingRing)
 
static void deleteOrdering (ring r)
 
BOOLEAN computeWitnessDebug (leftv res, leftv args)
 
BOOLEAN computeFlipDebug (leftv res, leftv args)
 

Function Documentation

§ computeFlipDebug()

BOOLEAN computeFlipDebug ( leftv  res,
leftv  args 
)

Definition at line 970 of file tropicalStrategy.cc.

971 {
972  leftv u = args;
973  if ((u!=NULL) && (u->Typ()==IDEAL_CMD))
974  {
975  leftv v = u->next;
976  if ((v!=NULL) && (v->Typ()==NUMBER_CMD))
977  {
978  leftv w = v->next;
979  if ((w!=NULL) && (w->Typ()==BIGINTMAT_CMD))
980  {
981  leftv x = w->next;
982  if ((x!=NULL) && (x->Typ()==BIGINTMAT_CMD))
983  {
984  omUpdateInfo();
985  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
986 
987  ideal I = (ideal) u->CopyD();
988  number p = (number) v->CopyD();
989  bigintmat* interiorPoint0 = (bigintmat*) w->CopyD();
990  bigintmat* facetNormal0 = (bigintmat*) x->CopyD();
992 
993  gfan::ZVector* interiorPoint = bigintmatToZVector(interiorPoint0);
994  gfan::ZVector* facetNormal = bigintmatToZVector(facetNormal0);
995  std::pair<ideal,ring> Js = debug.computeFlip(I,currRing,*interiorPoint,*facetNormal);
996  ideal J = Js.first;
997  ring s = Js.second;
998 
999  id_Delete(&J,s);
1000  rDelete(s);
1001 
1002  id_Delete(&I,currRing);
1003  n_Delete(&p,currRing->cf);
1004  delete interiorPoint0;
1005  delete facetNormal0;
1006  delete interiorPoint;
1007  delete facetNormal;
1008 
1009  res->rtyp = NONE;
1010  res->data = NULL;
1011  return FALSE;
1012  }
1013  }
1014  }
1015  }
1016  WerrorS("computeFlipDebug: unexpected parameters");
1017  return TRUE;
1018 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
Matrices of numbers.
Definition: bigintmat.h:51
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:101
void WerrorS(const char *s)
Definition: feFopen.cc:24
static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing)
int Typ()
Definition: subexpr.cc:979
std::pair< ideal, ring > computeFlip(const ideal Ir, const ring r, const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const
given an interior point of a groebner cone computes the groebner cone adjacent to it ...
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
leftv next
Definition: subexpr.h:88
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
void omUpdateInfo()
Definition: omStats.c:24
const CanonicalForm & w
Definition: facAbsFact.cc:55
int rtyp
Definition: subexpr.h:93
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
#define NONE
Definition: tok.h:216
void * CopyD(int t)
Definition: subexpr.cc:679
gfan::ZVector * bigintmatToZVector(const bigintmat &bim)

§ computeWitnessDebug()

BOOLEAN computeWitnessDebug ( leftv  res,
leftv  args 
)

Definition at line 933 of file tropicalStrategy.cc.

934 {
935  leftv u = args;
936  if ((u!=NULL) && (u->Typ()==IDEAL_CMD))
937  {
938  leftv v = u->next;
939  if ((v!=NULL) && (v->Typ()==IDEAL_CMD))
940  {
941  leftv w = v->next;
942  if ((w!=NULL) && (w->Typ()==IDEAL_CMD))
943  {
944  leftv x = w->next;
945  if ((x!=NULL) && (x->Typ()==NUMBER_CMD))
946  {
947  omUpdateInfo();
948  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
949 
950  ideal inJ = (ideal) u->CopyD();
951  ideal inI = (ideal) v->CopyD();
952  ideal I = (ideal) w->CopyD();
953  number p = (number) x->CopyD();
955  ideal J = debug.computeWitness(inJ,inI,I,currRing);
956  id_Delete(&inJ,currRing);
957  id_Delete(&inI,currRing);
958  id_Delete(&I,currRing);
959  n_Delete(&p,currRing->cf);
960  res->rtyp = IDEAL_CMD;
961  res->data = (char*) J;
962  return FALSE;
963  }
964  }
965  }
966  }
967  return TRUE;
968 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:84
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:97
return P p
Definition: myNF.cc:203
ideal computeWitness(const ideal inJ, const ideal inI, const ideal I, const ring r) const
suppose w a weight in maximal groebner cone of > suppose I (initially) reduced standard basis w...
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:101
static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing)
int Typ()
Definition: subexpr.cc:979
void * data
Definition: subexpr.h:90
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
omInfo_t om_Info
Definition: omStats.c:13
leftv next
Definition: subexpr.h:88
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
const CanonicalForm & w
Definition: facAbsFact.cc:55
int rtyp
Definition: subexpr.h:93
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void * CopyD(int t)
Definition: subexpr.cc:679

§ constructStartingIdeal()

static ideal constructStartingIdeal ( ideal  originalIdeal,
ring  originalRing,
number  uniformizingParameter,
ring  startingRing 
)
static

Definition at line 220 of file tropicalStrategy.cc.

221 {
222  // construct p-t
223  poly g = p_One(startingRing);
224  p_SetCoeff(g,uniformizingParameter,startingRing);
225  pNext(g) = p_One(startingRing);
226  p_SetExp(pNext(g),1,1,startingRing);
227  p_SetCoeff(pNext(g),n_Init(-1,startingRing->cf),startingRing);
228  p_Setm(pNext(g),startingRing);
229  ideal pt = idInit(1);
230  pt->m[0] = g;
231 
232  // map originalIdeal from originalRing into startingRing
233  int k = IDELEMS(originalIdeal);
234  ideal J = idInit(k+1);
235  nMapFunc nMap = n_SetMap(originalRing->cf,startingRing->cf);
236  int n = rVar(originalRing);
237  int* shiftByOne = (int*) omAlloc((n+1)*sizeof(int));
238  for (int i=1; i<=n; i++)
239  shiftByOne[i]=i+1;
240  for (int i=0; i<k; i++)
241  {
242  if(originalIdeal->m[i]!=NULL)
243  {
244  J->m[i] = p_PermPoly(originalIdeal->m[i],shiftByOne,originalRing,startingRing,nMap,NULL,0);
245  }
246  }
247  omFreeSize(shiftByOne,(n+1)*sizeof(int));
248 
249  ring origin = currRing;
250  rChangeCurrRing(startingRing);
251  ideal startingIdeal = kNF(pt,startingRing->qideal,J); // mathematically redundant,
252  rChangeCurrRing(origin); // but helps with upcoming std computation
253  // ideal startingIdeal = J; J = NULL;
254  assume(startingIdeal->m[k]==NULL);
255  startingIdeal->m[k] = pt->m[0];
256  startingIdeal = gfanlib_kStd_wrapper(startingIdeal,startingRing);
257 
258  id_Delete(&J,startingRing);
259  pt->m[0] = NULL;
260  id_Delete(&pt,startingRing);
261  return startingIdeal;
262 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
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:542
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:580
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
#define omAlloc(size)
Definition: omAllocDecl.h:210
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition: p_polys.cc:3939
poly p_One(const ring r)
Definition: p_polys.cc:1313
ideal gfanlib_kStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:5
#define assume(x)
Definition: mod2.h:403
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:725
void rChangeCurrRing(ring r)
Definition: polys.cc:12
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
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
#define pNext(p)
Definition: monomials.h:43
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
polyrec * poly
Definition: hilb.h:10

§ constructStartingRing()

static ring constructStartingRing ( ring  r)
static

Given a polynomial ring r over the rational numbers and a weighted ordering, returns a polynomial ring s over the integers with one extra variable, which is weighted -1.

Definition at line 159 of file tropicalStrategy.cc.

160 {
161  assume(rField_is_Q(r));
162 
163  ring s = rCopy0(r,FALSE,FALSE);
164  nKillChar(s->cf);
165  s->cf = nInitChar(n_Z,NULL);
166 
167  int n = rVar(s)+1;
168  s->N = n;
169  char** oldNames = s->names;
170  s->names = (char**) omAlloc((n+1)*sizeof(char**));
171  s->names[0] = omStrDup("t");
172  for (int i=1; i<n; i++)
173  s->names[i] = oldNames[i-1];
174  omFree(oldNames);
175 
176  s->order = (int*) omAlloc0(3*sizeof(int));
177  s->block0 = (int*) omAlloc0(3*sizeof(int));
178  s->block1 = (int*) omAlloc0(3*sizeof(int));
179  s->wvhdl = (int**) omAlloc0(3*sizeof(int**));
180  s->order[0] = ringorder_ws;
181  s->block0[0] = 1;
182  s->block1[0] = n;
183  s->wvhdl[0] = (int*) omAlloc(n*sizeof(int));
184  s->wvhdl[0][0] = 1;
185  if (r->order[0] == ringorder_lp)
186  {
187  s->wvhdl[0][1] = 1;
188  }
189  else if (r->order[0] == ringorder_ls)
190  {
191  s->wvhdl[0][1] = -1;
192  }
193  else if (r->order[0] == ringorder_dp)
194  {
195  for (int i=1; i<n; i++)
196  s->wvhdl[0][i] = -1;
197  }
198  else if (r->order[0] == ringorder_ds)
199  {
200  for (int i=1; i<n; i++)
201  s->wvhdl[0][i] = 1;
202  }
203  else if (r->order[0] == ringorder_ws)
204  {
205  for (int i=1; i<n; i++)
206  s->wvhdl[0][i] = r->wvhdl[0][i-1];
207  }
208  else
209  {
210  for (int i=1; i<n; i++)
211  s->wvhdl[0][i] = -r->wvhdl[0][i-1];
212  }
213  s->order[1] = ringorder_C;
214 
215  rComplete(s);
216  rTest(s);
217  return s;
218 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define FALSE
Definition: auxiliary.h:97
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:580
#define omAlloc(size)
Definition: omAllocDecl.h:210
const ring r
Definition: syzextra.cc:208
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3435
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:403
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1321
#define rTest(r)
Definition: ring.h:775
only used if HAVE_RINGS is defined
Definition: coeffs.h:43
int i
Definition: cfEzgcd.cc:123
static BOOLEAN rField_is_Q(const ring r)
Definition: ring.h:501
#define NULL
Definition: omList.c:10
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:490
#define omAlloc0(size)
Definition: omAllocDecl.h:211
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:329
#define omStrDup(s)
Definition: omAllocDecl.h:263

§ deleteOrdering()

static void deleteOrdering ( ring  r)
static

Definition at line 686 of file tropicalStrategy.cc.

687 {
688  if (r->order != NULL)
689  {
690  int i=rBlocks(r);
691  assume(r->block0 != NULL && r->block1 != NULL && r->wvhdl != NULL);
692  /* delete order */
693  omFreeSize((ADDRESS)r->order,i*sizeof(int));
694  omFreeSize((ADDRESS)r->block0,i*sizeof(int));
695  omFreeSize((ADDRESS)r->block1,i*sizeof(int));
696  /* delete weights */
697  for (int j=0; j<i; j++)
698  if (r->wvhdl[j]!=NULL)
699  omFree(r->wvhdl[j]);
700  omFreeSize((ADDRESS)r->wvhdl,i*sizeof(int *));
701  }
702  else
703  assume(r->block0 == NULL && r->block1 == NULL && r->wvhdl == NULL);
704  return;
705 }
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
void * ADDRESS
Definition: auxiliary.h:118
static int rBlocks(ring r)
Definition: ring.h:556
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10

§ dim()

int dim ( ideal  I,
ring  r 
)

Definition at line 19 of file tropicalStrategy.cc.

20 {
21  ring origin = currRing;
22  if (origin != r)
24  int d;
26  {
27  int i = idPosConstant(I);
28  if ((i != -1)
29  #ifdef HAVE_RINGS
30  && (n_IsUnit(p_GetCoeff(I->m[i],currRing->cf),currRing->cf))
31  #endif
32  )
33  return -1;
34  ideal vv = id_Head(I,currRing);
35  if (i != -1) pDelete(&vv->m[i]);
36  d = scDimInt(vv, currRing->qideal);
37  if (rField_is_Ring_Z(currRing) && (i==-1)) d++;
38  idDelete(&vv);
39  return d;
40  }
41  else
42  d = scDimInt(I,currRing->qideal);
43  if (origin != r)
44  rChangeCurrRing(origin);
45  return d;
46 }
#define idPosConstant(I)
index of generator with leading term in ground ring (if any); otherwise -1
Definition: ideals.h:39
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:519
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
const ring r
Definition: syzextra.cc:208
int scDimInt(ideal S, ideal Q)
Definition: hdegree.cc:72
int i
Definition: cfEzgcd.cc:123
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:474
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
#define pDelete(p_ptr)
Definition: polys.h:169
#define p_GetCoeff(p, r)
Definition: monomials.h:57

§ noExtraReduction()

static bool noExtraReduction ( ideal  I,
ring  r,
number   
)
static

Definition at line 60 of file tropicalStrategy.cc.

61 {
62  int n = rVar(r);
63  gfan::ZVector allOnes(n);
64  for (int i=0; i<n; i++)
65  allOnes[i] = 1;
66  ring rShortcut = rCopy0(r);
67 
68  int* order = rShortcut->order;
69  int* block0 = rShortcut->block0;
70  int* block1 = rShortcut->block1;
71  int** wvhdl = rShortcut->wvhdl;
72 
73  int h = rBlocks(r);
74  rShortcut->order = (int*) omAlloc0((h+1)*sizeof(int));
75  rShortcut->block0 = (int*) omAlloc0((h+1)*sizeof(int));
76  rShortcut->block1 = (int*) omAlloc0((h+1)*sizeof(int));
77  rShortcut->wvhdl = (int**) omAlloc0((h+1)*sizeof(int*));
78  rShortcut->order[0] = ringorder_a;
79  rShortcut->block0[0] = 1;
80  rShortcut->block1[0] = n;
81  bool overflow;
82  rShortcut->wvhdl[0] = ZVectorToIntStar(allOnes,overflow);
83  for (int i=1; i<=h; i++)
84  {
85  rShortcut->order[i] = order[i-1];
86  rShortcut->block0[i] = block0[i-1];
87  rShortcut->block1[i] = block1[i-1];
88  rShortcut->wvhdl[i] = wvhdl[i-1];
89  }
90 
91  rComplete(rShortcut);
92  rTest(rShortcut);
93 
94  omFree(order);
95  omFree(block0);
96  omFree(block1);
97  omFree(wvhdl);
98 
99  int k = IDELEMS(I);
100  ideal IShortcut = idInit(k);
101  nMapFunc intoShortcut = n_SetMap(r->cf,rShortcut->cf);
102  for (int i=0; i<k; i++)
103  {
104  if(I->m[i]!=NULL)
105  {
106  IShortcut->m[i] = p_PermPoly(I->m[i],NULL,r,rShortcut,intoShortcut,NULL,0);
107  }
108  }
109 
110  ideal JShortcut = gfanlib_kStd_wrapper(IShortcut,rShortcut);
111 
112  ideal J = idInit(k);
113  nMapFunc outofShortcut = n_SetMap(rShortcut->cf,r->cf);
114  for (int i=0; i<k; i++)
115  J->m[i] = p_PermPoly(JShortcut->m[i],NULL,rShortcut,r,outofShortcut,NULL,0);
116 
117  swapElements(I,J);
118  id_Delete(&IShortcut,rShortcut);
119  id_Delete(&JShortcut,rShortcut);
120  rDelete(rShortcut);
121  id_Delete(&J,r);
122  return false;
123 }
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:580
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
int * ZVectorToIntStar(const gfan::ZVector &v, bool &overflow)
int k
Definition: cfEzgcd.cc:93
static void swapElements(ideal I, ideal J)
static int rBlocks(ring r)
Definition: ring.h:556
const ring r
Definition: syzextra.cc:208
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition: p_polys.cc:3939
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3435
ideal gfanlib_kStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:5
#define omFree(addr)
Definition: omAllocDecl.h:261
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1321
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
#define rTest(r)
Definition: ring.h:775
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:725
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define NULL
Definition: omList.c:10
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
static Poly * h
Definition: janet.cc:978
#define omAlloc0(size)
Definition: omAllocDecl.h:211

§ swapElements()

static void swapElements ( ideal  I,
ideal  J 
)
static

Definition at line 48 of file tropicalStrategy.cc.

49 {
50  assume(IDELEMS(I)==IDELEMS(J));
51 
52  for (int i=IDELEMS(I)-1; i>=0; i--)
53  {
54  poly cache = I->m[i];
55  I->m[i] = J->m[i];
56  J->m[i] = cache;
57  }
58 }
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
polyrec * poly
Definition: hilb.h:10