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

BOOLEAN computeFlipDebug ( leftv  res,
leftv  args 
)

Definition at line 958 of file tropicalStrategy.cc.

959 {
960  leftv u = args;
961  if ((u!=NULL) && (u->Typ()==IDEAL_CMD))
962  {
963  leftv v = u->next;
964  if ((v!=NULL) && (v->Typ()==NUMBER_CMD))
965  {
966  leftv w = v->next;
967  if ((w!=NULL) && (w->Typ()==BIGINTMAT_CMD))
968  {
969  leftv x = w->next;
970  if ((x!=NULL) && (x->Typ()==BIGINTMAT_CMD))
971  {
972  omUpdateInfo();
973  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
974 
975  ideal I = (ideal) u->CopyD();
976  number p = (number) v->CopyD();
977  bigintmat* interiorPoint0 = (bigintmat*) w->CopyD();
978  bigintmat* facetNormal0 = (bigintmat*) x->CopyD();
980 
981  gfan::ZVector* interiorPoint = bigintmatToZVector(interiorPoint0);
982  gfan::ZVector* facetNormal = bigintmatToZVector(facetNormal0);
983  std::pair<ideal,ring> Js = debug.computeFlip(I,currRing,*interiorPoint,*facetNormal);
984  ideal J = Js.first;
985  ring s = Js.second;
986 
987  id_Delete(&J,s);
988  rDelete(s);
989 
990  id_Delete(&I,currRing);
991  n_Delete(&p,currRing->cf);
992  delete interiorPoint0;
993  delete facetNormal0;
994  delete interiorPoint;
995  delete facetNormal;
996 
997  res->rtyp = NONE;
998  res->data = NULL;
999  return FALSE;
1000  }
1001  }
1002  }
1003  }
1004  WerrorS("computeFlipDebug: unexpected parameters");
1005  return TRUE;
1006 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
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:144
void WerrorS(const char *s)
Definition: feFopen.cc:24
static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing)
int Typ()
Definition: subexpr.cc:976
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
omInfo_t om_Info
Definition: omStats.c:13
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 ...
leftv next
Definition: subexpr.h:87
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:92
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
#define NONE
Definition: tok.h:220
void * CopyD(int t)
Definition: subexpr.cc:676
gfan::ZVector * bigintmatToZVector(const bigintmat &bim)
BOOLEAN computeWitnessDebug ( leftv  res,
leftv  args 
)

Definition at line 921 of file tropicalStrategy.cc.

922 {
923  leftv u = args;
924  if ((u!=NULL) && (u->Typ()==IDEAL_CMD))
925  {
926  leftv v = u->next;
927  if ((v!=NULL) && (v->Typ()==IDEAL_CMD))
928  {
929  leftv w = v->next;
930  if ((w!=NULL) && (w->Typ()==IDEAL_CMD))
931  {
932  leftv x = w->next;
933  if ((x!=NULL) && (x->Typ()==NUMBER_CMD))
934  {
935  omUpdateInfo();
936  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
937 
938  ideal inJ = (ideal) u->CopyD();
939  ideal inI = (ideal) v->CopyD();
940  ideal I = (ideal) w->CopyD();
941  number p = (number) x->CopyD();
943  ideal J = debug.computeWitness(inJ,inI,I,currRing);
944  id_Delete(&inJ,currRing);
945  id_Delete(&inI,currRing);
946  id_Delete(&I,currRing);
947  n_Delete(&p,currRing->cf);
948  res->rtyp = IDEAL_CMD;
949  res->data = (char*) J;
950  return FALSE;
951  }
952  }
953  }
954  }
955  return TRUE;
956 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
#define Print
Definition: emacs.cc:83
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...
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:144
static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing)
int Typ()
Definition: subexpr.cc:976
void * data
Definition: subexpr.h:89
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
omInfo_t om_Info
Definition: omStats.c:13
leftv next
Definition: subexpr.h:87
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:92
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
void * CopyD(int t)
Definition: subexpr.cc:676
static ideal constructStartingIdeal ( ideal  originalIdeal,
ring  originalRing,
number  uniformizingParameter,
ring  startingRing 
)
static

Definition at line 215 of file tropicalStrategy.cc.

216 {
217  // construct p-t
218  poly g = p_One(startingRing);
219  p_SetCoeff(g,uniformizingParameter,startingRing);
220  pNext(g) = p_One(startingRing);
221  p_SetExp(pNext(g),1,1,startingRing);
222  p_SetCoeff(pNext(g),n_Init(-1,startingRing->cf),startingRing);
223  p_Setm(pNext(g),startingRing);
224  ideal pt = idInit(1);
225  pt->m[0] = g;
226 
227  // map originalIdeal from originalRing into startingRing
228  int k = idSize(originalIdeal);
229  ideal J = idInit(k+1);
230  nMapFunc nMap = n_SetMap(originalRing->cf,startingRing->cf);
231  int n = rVar(originalRing);
232  int* shiftByOne = (int*) omAlloc((n+1)*sizeof(int));
233  for (int i=1; i<=n; i++)
234  shiftByOne[i]=i+1;
235  for (int i=0; i<k; i++)
236  J->m[i] = p_PermPoly(originalIdeal->m[i],shiftByOne,originalRing,startingRing,nMap,NULL,0);
237  omFreeSize(shiftByOne,(n+1)*sizeof(int));
238 
239  ring origin = currRing;
240  rChangeCurrRing(startingRing);
241  ideal startingIdeal = kNF(pt,startingRing->qideal,J); // mathematically redundant,
242  rChangeCurrRing(origin); // but helps with upcoming std computation
243  // ideal startingIdeal = J; J = NULL;
244  assume(startingIdeal->m[k]==NULL);
245  startingIdeal->m[k] = pt->m[0];
246  startingIdeal = gfanlib_kStd_wrapper(startingIdeal,startingRing);
247 
248  id_Delete(&J,startingRing);
249  pt->m[0] = NULL;
250  id_Delete(&pt,startingRing);
251  return startingIdeal;
252 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2819
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:537
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:12
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:3937
poly p_One(const ring r)
Definition: p_polys.cc:1318
ideal gfanlib_kStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:5
#define assume(x)
Definition: mod2.h:405
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:72
int i
Definition: cfEzgcd.cc:123
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:722
void rChangeCurrRing(ring r)
Definition: polys.cc:14
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
static int idSize(const ideal id)
Count the effective size of an ideal (without the trailing allocated zero-elements) ...
Definition: ideals.h:43
polyrec * poly
Definition: hilb.h:10
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 154 of file tropicalStrategy.cc.

155 {
156  assume(rField_is_Q(r));
157 
158  ring s = rCopy0(r,FALSE,FALSE);
159  nKillChar(s->cf);
160  s->cf = nInitChar(n_Z,NULL);
161 
162  int n = rVar(s)+1;
163  s->N = n;
164  char** oldNames = s->names;
165  s->names = (char**) omAlloc((n+1)*sizeof(char**));
166  s->names[0] = omStrDup("t");
167  for (int i=1; i<n; i++)
168  s->names[i] = oldNames[i-1];
169  omFree(oldNames);
170 
171  s->order = (int*) omAlloc0(3*sizeof(int));
172  s->block0 = (int*) omAlloc0(3*sizeof(int));
173  s->block1 = (int*) omAlloc0(3*sizeof(int));
174  s->wvhdl = (int**) omAlloc0(3*sizeof(int**));
175  s->order[0] = ringorder_ws;
176  s->block0[0] = 1;
177  s->block1[0] = n;
178  s->wvhdl[0] = (int*) omAlloc(n*sizeof(int));
179  s->wvhdl[0][0] = 1;
180  if (r->order[0] == ringorder_lp)
181  {
182  s->wvhdl[0][1] = 1;
183  }
184  else if (r->order[0] == ringorder_ls)
185  {
186  s->wvhdl[0][1] = -1;
187  }
188  else if (r->order[0] == ringorder_dp)
189  {
190  for (int i=1; i<n; i++)
191  s->wvhdl[0][i] = -1;
192  }
193  else if (r->order[0] == ringorder_ds)
194  {
195  for (int i=1; i<n; i++)
196  s->wvhdl[0][i] = 1;
197  }
198  else if (r->order[0] == ringorder_ws)
199  {
200  for (int i=1; i<n; i++)
201  s->wvhdl[0][i] = r->wvhdl[0][i-1];
202  }
203  else
204  {
205  for (int i=1; i<n; i++)
206  s->wvhdl[0][i] = -r->wvhdl[0][i-1];
207  }
208  s->order[1] = ringorder_C;
209 
210  rComplete(s);
211  rTest(s);
212  return s;
213 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define FALSE
Definition: auxiliary.h:140
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:537
#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:3436
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:405
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1318
#define rTest(r)
Definition: ring.h:778
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:42
int i
Definition: cfEzgcd.cc:123
static BOOLEAN rField_is_Q(const ring r)
Definition: ring.h:458
#define NULL
Definition: omList.c:10
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:488
#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:327
#define omStrDup(s)
Definition: omAllocDecl.h:263
static void deleteOrdering ( ring  r)
static

Definition at line 674 of file tropicalStrategy.cc.

675 {
676  if (r->order != NULL)
677  {
678  int i=rBlocks(r);
679  assume(r->block0 != NULL && r->block1 != NULL && r->wvhdl != NULL);
680  /* delete order */
681  omFreeSize((ADDRESS)r->order,i*sizeof(int));
682  omFreeSize((ADDRESS)r->block0,i*sizeof(int));
683  omFreeSize((ADDRESS)r->block1,i*sizeof(int));
684  /* delete weights */
685  for (int j=0; j<i; j++)
686  if (r->wvhdl[j]!=NULL)
687  omFree(r->wvhdl[j]);
688  omFreeSize((ADDRESS)r->wvhdl,i*sizeof(int *));
689  }
690  else
691  assume(r->block0 == NULL && r->block1 == NULL && r->wvhdl == NULL);
692  return;
693 }
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
void * ADDRESS
Definition: auxiliary.h:161
static int rBlocks(ring r)
Definition: ring.h:513
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:405
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
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:516
#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:12
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:14
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:434
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:431
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
#define pDelete(p_ptr)
Definition: polys.h:157
#define p_GetCoeff(p, r)
Definition: monomials.h:57
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 = idSize(I);
100  ideal IShortcut = idInit(k);
101  nMapFunc intoShortcut = n_SetMap(r->cf,rShortcut->cf);
102  for (int i=0; i<k; i++)
103  IShortcut->m[i] = p_PermPoly(I->m[i],NULL,r,rShortcut,intoShortcut,NULL,0);
104 
105  ideal JShortcut = gfanlib_kStd_wrapper(IShortcut,rShortcut);
106 
107  ideal J = idInit(k);
108  nMapFunc outofShortcut = n_SetMap(rShortcut->cf,r->cf);
109  for (int i=0; i<k; i++)
110  J->m[i] = p_PermPoly(JShortcut->m[i],NULL,rShortcut,r,outofShortcut,NULL,0);
111 
112  swapElements(I,J);
113  id_Delete(&IShortcut,rShortcut);
114  id_Delete(&JShortcut,rShortcut);
115  rDelete(rShortcut);
116  id_Delete(&J,r);
117  return false;
118 }
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:537
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:513
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:3937
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:3436
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:1318
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:72
#define rTest(r)
Definition: ring.h:778
int i
Definition: cfEzgcd.cc:123
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:722
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 int idSize(const ideal id)
Count the effective size of an ideal (without the trailing allocated zero-elements) ...
Definition: ideals.h:43
static Poly * h
Definition: janet.cc:978
#define omAlloc0(size)
Definition: omAllocDecl.h:211
static void swapElements ( ideal  I,
ideal  J 
)
static

Definition at line 48 of file tropicalStrategy.cc.

49 {
50  assume(idSize(I)==idSize(J));
51 
52  for (int i=idSize(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:405
int i
Definition: cfEzgcd.cc:123
static int idSize(const ideal id)
Count the effective size of an ideal (without the trailing allocated zero-elements) ...
Definition: ideals.h:43
polyrec * poly
Definition: hilb.h:10