My Project  debian-1:4.1.2-p1+ds-2
Namespaces | Functions
gitfan.cc File Reference
#include "kernel/mod2.h"
#include "Singular/dyn_modules/gfanlib/callgfanlib_conversion.h"
#include "Singular/dyn_modules/gfanlib/bbcone.h"
#include "Singular/dyn_modules/gfanlib/bbfan.h"
#include "Singular/mod_lib.h"
#include "gitfan.h"

Go to the source code of this file.

Namespaces

 gitfan
 

Functions

void gitfan::mergeFacets (facets &F, const facets &newFacets)
 
static gfan::ZCone subcone (const lists &cones, const gfan::ZVector &point)
 
static gitfan::facets interiorFacets (const gfan::ZCone &zc, const gfan::ZCone &bound)
 
BOOLEAN refineCones (leftv res, leftv args)
 
static int binomial (int n, int k)
 
intvecintToAface (unsigned int v0, int n, int k)
 
BOOLEAN listOfAfacesToCheck (leftv res, leftv args)
 
BOOLEAN nextAfaceToCheck (leftv res, leftv args)
 
BOOLEAN checkSigns (leftv res, leftv args)
 
BOOLEAN binaryToBigint (leftv res, leftv args)
 
BOOLEAN composeIntvecs (leftv res, leftv args)
 
BOOLEAN findPlaceToInsert (leftv res, leftv args)
 
void subset (std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
 
int SI_MOD_INIT() gitfan (SModulFunctions *p)
 

Function Documentation

◆ binaryToBigint()

BOOLEAN binaryToBigint ( leftv  res,
leftv  args 
)

Definition at line 412 of file gitfan.cc.

412  : unexpected parameter");
413  return TRUE;
414 }
415 
416 
417 BOOLEAN binaryToBigint(leftv res, leftv args)
418 {
419  leftv u = args;
420  if ((u != NULL) && (u->Typ() == INTVEC_CMD) && (u->next == NULL))
421  {
422  intvec* iv = (intvec*) u->Data();
423  const int l = (iv->rows())*(iv->cols());
424  number base = n_Init(2,coeffs_BIGINT);
425  number endResult;
426  n_Power(base,(*iv)[0]-1,&endResult,coeffs_BIGINT);
427  for (int i=1; i<l; i++)
428  {
429  number endResultCache;
430  number currentBit;
431  n_Power(base,(*iv)[i]-1,&currentBit,coeffs_BIGINT);
432  endResultCache = n_Add(endResult,currentBit,coeffs_BIGINT);
433  n_Delete(&endResult,coeffs_BIGINT);
434  n_Delete(&currentBit,coeffs_BIGINT);
435  endResult = endResultCache;
436  endResultCache = NULL;
437  }
438  n_Delete(&base,coeffs_BIGINT);
439  res->rtyp = BIGINT_CMD;
440  res->data = (void*) endResult;

◆ binomial()

static int binomial ( int  n,
int  k 
)
static

Definition at line 257 of file gitfan.cc.

257  : unexpected parameters");
258  return TRUE;
259 }
260 
261 
262 static int binomial(int n, int k)
263 {
264  if (n<k)
265  return(0);
266  gfan::Integer num = 1;
267  gfan::Integer den = 1;
268  for (int i=1; i<=k; i++)
269  den = den*i;

◆ checkSigns()

BOOLEAN checkSigns ( leftv  res,
leftv  args 
)

Definition at line 363 of file gitfan.cc.

363  : unexpected parameter");
364  return TRUE;
365 }
366 
367 
368 BOOLEAN checkSigns(leftv res, leftv args)
369 {
370  leftv u = args;
371  if ((u != NULL) && (u->Typ()==BIGINTMAT_CMD || u->Typ()==INTMAT_CMD))
372  {
373  leftv v = u->next;
374  if ((v != NULL) && (v->Typ() == INTVEC_CMD) && (v->next == NULL))
375  {
376  bigintmat* interiorPoint = NULL;
377  if (u->Typ() == INTMAT_CMD)
378  {
379  intvec* p0 = (intvec*) u->Data();
380  interiorPoint = iv2bim(p0,coeffs_BIGINT);
381  }
382  else
383  interiorPoint = (bigintmat*) u->Data();
384  intvec* hash = (intvec*) v->Data();
385  res->rtyp = INT_CMD;
386  for (int i=0; i<hash->length(); i++)
387  {
388  if ( (*hash)[i]<0 && n_GreaterZero((*interiorPoint)[i],interiorPoint->basecoeffs()) )
389  {
390  res->data = (void*) (long) 0;
391  return FALSE;
392  }
393  if ( (*hash)[i]>0 && !n_IsZero((*interiorPoint)[i],interiorPoint->basecoeffs()) )
394  {
395  number neg = n_Copy((*interiorPoint)[i],interiorPoint->basecoeffs());
396  neg = n_InpNeg(neg,interiorPoint->basecoeffs());
397  if (n_GreaterZero(neg,interiorPoint->basecoeffs()))
398  {
399  n_Delete(&neg,interiorPoint->basecoeffs());
400  res->data = (void*) (long) 0;
401  return FALSE;
402  }
403  n_Delete(&neg,interiorPoint->basecoeffs());
404  }
405  }
406  res->data = (void*) (long) 1;
407  if (v->Typ() == INTMAT_CMD)
408  delete interiorPoint;
409  return FALSE;

◆ composeIntvecs()

BOOLEAN composeIntvecs ( leftv  res,
leftv  args 
)

Definition at line 443 of file gitfan.cc.

443  : unexpected parameter");
444  return TRUE;
445 }
446 
447 
448 BOOLEAN composeIntvecs(leftv res, leftv args)
449 {
450  leftv u = args;
451  if ((u!=NULL) && (u->Typ()==INTVEC_CMD))
452  {
453  leftv v = u->next;
454  if ((v!=NULL) && (v->Typ()==INTVEC_CMD) && (v->next==NULL))
455  {
456  intvec* iv1 = (intvec*) u->Data();
457  intvec* iv2 = (intvec*) v->Data();
458  int k = iv2->length();
459  intvec* composedIntvec = new intvec(k);
460  for (int i=0; i<k; i++)
461  (*composedIntvec)[i] = (*iv1)[(*iv2)[i]-1];
462  res->rtyp = INTVEC_CMD;
463  res->data = (void*) composedIntvec;
464  return FALSE;

◆ findPlaceToInsert()

BOOLEAN findPlaceToInsert ( leftv  res,
leftv  args 
)

Definition at line 467 of file gitfan.cc.

467  : unexpected parameter");
468  return TRUE;
469 }
470 
471 
472 BOOLEAN findPlaceToInsert(leftv res, leftv args)
473 {
474  leftv u = args;
475  if ((u!=NULL) && (u->Typ()==LIST_CMD))
476  {
477  leftv v = u->next;
478  if ((v!=NULL) && (v->Typ()==BIGINT_CMD) && (v->next==NULL))
479  {
480  lists listOfNumbers = (lists) u->Data();
481  number numberToInsert = (number) v->Data();
482  int lowerBound = 0;
483  int upperBound = lSize(listOfNumbers);
484  if (upperBound<0)
485  {
486  res->rtyp = INT_CMD;
487  res->data = (void*) (long) (lowerBound+1);
488  return FALSE;
489  }
490 
491  number lowerNumber = (number) listOfNumbers->m[lowerBound].Data();
492  if (n_Equal(lowerNumber,numberToInsert,coeffs_BIGINT))
493  {
494  res->rtyp = INT_CMD;
495  res->data = (void*) (long) (-1);
496  return FALSE;
497  }
498  if (n_Greater(lowerNumber,numberToInsert,coeffs_BIGINT))
499  {
500  res->rtyp = INT_CMD;
501  res->data = (void*) (long) (lowerBound+1);
502  return FALSE;
503  }
504 
505  number upperNumber = (number) listOfNumbers->m[upperBound].Data();
506  if (n_Equal(numberToInsert,upperNumber,coeffs_BIGINT))
507  {
508  res->rtyp = INT_CMD;
509  res->data = (void*) (long) (-1);
510  return FALSE;
511  }
512  if (n_Greater(numberToInsert,upperNumber,coeffs_BIGINT))
513  {
514  res->rtyp = INT_CMD;
515  res->data = (void*) (long) (upperBound+2);
516  return FALSE;
517  }
518 
519  while (lowerBound+1<upperBound)
520  {
521  int middle = lowerBound + (upperBound-lowerBound) / 2;
522  number lowerNumber = (number) listOfNumbers->m[lowerBound].Data();
523  number upperNumber = (number) listOfNumbers->m[upperBound].Data();
524  number middleNumber = (number) listOfNumbers->m[middle].Data();
525  if ((n_Equal(lowerNumber,numberToInsert,coeffs_BIGINT)) ||
526  (n_Equal(middleNumber,numberToInsert,coeffs_BIGINT)) ||
527  (n_Equal(upperNumber,numberToInsert,coeffs_BIGINT)))
528  {
529  res->rtyp = INT_CMD;
530  res->data = (void*) (long) -1;
531  return FALSE;
532  }
533  if (n_Greater(numberToInsert,middleNumber,coeffs_BIGINT))
534  lowerBound = middle;
535  if (n_Greater(middleNumber,numberToInsert,coeffs_BIGINT))
536  upperBound = middle;
537  }
538 
539  res->rtyp = INT_CMD;
540  res->data = (void*) (long) (upperBound+1);
541  return FALSE;

◆ gitfan()

int SI_MOD_INIT() gitfan ( SModulFunctions p)

Definition at line 560 of file gitfan.cc.

566 {
567  gfan::initializeCddlibIfRequired();
568  p->iiAddCproc("gitfan.lib","refineCones",FALSE,refineCones);
569  p->iiAddCproc("gitfan.lib","listOfAfacesToCheck",FALSE,listOfAfacesToCheck);
570  p->iiAddCproc("gitfan.lib","nextAfaceToCheck",FALSE,nextAfaceToCheck);
571  p->iiAddCproc("gitfan.lib","checkSigns",FALSE,checkSigns);

◆ interiorFacets()

static gitfan::facets interiorFacets ( const gfan::ZCone &  zc,
const gfan::ZCone &  bound 
)
static

Definition at line 104 of file gitfan.cc.

105 {
106  gfan::ZMatrix inequalities = zc.getFacets();
107  gfan::ZMatrix equations = zc.getImpliedEquations();
108  int r = inequalities.getHeight();
109  int c = inequalities.getWidth();
110  gitfan::facets F;
111  if (r*c == 0)
112  /***
113  * this is the trivial case where either we are in a zerodimensional ambient space,
114  * or the cone has no facets.
115  **/
116  return F;
117 
118  // int index = 0;
119  /* next we iterate over each of the r facets, build the respective cone and add it to the list */
120  /* this is the i=0 case */
121  gfan::ZMatrix newInequalities = inequalities.submatrix(1,0,r,c);
122  gfan::ZMatrix newEquations = equations;
123  newEquations.appendRow(inequalities[0]);
124  gfan::ZCone eta = gfan::ZCone(newInequalities,newEquations);
125  eta.canonicalize();
126  gfan::ZVector v = eta.getRelativeInteriorPoint();
127  gfan::ZVector w = inequalities[0];
128 
129  if (bound.containsRelatively(v))
130  F.insert(gitfan::facet(eta,v,w));
131 
132  /* these are the cases i=1,...,r-2 */
133  for (int i=1; i<r-1; i++)
134  {
135  newInequalities = inequalities.submatrix(0,0,i,c);
136  newInequalities.append(inequalities.submatrix(i+1,0,r,c));
137  newEquations = equations;
138  newEquations.appendRow(inequalities[i]);
139  eta = gfan::ZCone(newInequalities,newEquations);
140  eta.canonicalize();
141  v = eta.getRelativeInteriorPoint();
142  w = inequalities[i];
143  if (bound.containsRelatively(v))
144  F.insert(gitfan::facet(eta,v,w));
145  }
146 
147  /* this is the i=r-1 case */
148  newInequalities = inequalities.submatrix(0,0,r-1,c);
149  newEquations = equations;
150  newEquations.appendRow(inequalities[r-1]);
151  eta = gfan::ZCone(newInequalities,newEquations);
152  eta.canonicalize();
153 
154  v = eta.getRelativeInteriorPoint();
155  w = inequalities[r-1];
156  if (bound.containsRelatively(v))
157  F.insert(gitfan::facet(eta,v,w));
158 
159  return F;

◆ intToAface()

intvec* intToAface ( unsigned int  v0,
int  n,
int  k 
)

Definition at line 272 of file gitfan.cc.

278 {
279  intvec* v = new intvec(k);
280  int j = 0;
281  for (int i=0; i<n; i++)
282  {

◆ listOfAfacesToCheck()

BOOLEAN listOfAfacesToCheck ( leftv  res,
leftv  args 
)

Definition at line 285 of file gitfan.cc.

291 {
292  leftv u = args;
293  if ((u != NULL) && (u->Typ() == INT_CMD))
294  {
295  leftv v = u->next;
296  if ((v != NULL) && (v->Typ() == INT_CMD))
297  {
298  int n = (int)(long) u->Data();
299  int k = (int)(long) v->Data();
300  unsigned int v = 0;
301  for (int i=0; i<k; i++)
302  v |= 1<<i; // sets the first k bits of v as 1
303 
305  int count = (int) binomial(n,k); L->Init(count);
306  unsigned int t;
307  while (!(v & (1<<n)))
308  {
309  L->m[--count].rtyp = INTVEC_CMD;
310  L->m[count].data = (void*) intToAface(v,n,k);
311 
312  // t gets v's least significant 0 bits set to 1
313  t = v | (v - 1);
314  // Next set to 1 the most significant bit to change,
315  // set to 0 the least significant ones, and add the necessary 1 bits.
316  v = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
317  }
318  res->rtyp = LIST_CMD;
319  res->data = (void*) L;
320  return FALSE;

◆ nextAfaceToCheck()

BOOLEAN nextAfaceToCheck ( leftv  res,
leftv  args 
)

Definition at line 323 of file gitfan.cc.

323  : unexpected parameter");
324  return TRUE;
325 }
326 
327 
328 BOOLEAN nextAfaceToCheck(leftv res, leftv args)
329 {
330  leftv u = args;
331  if ((u != NULL) && (u->Typ() == INTVEC_CMD))
332  {
333  leftv v = u->next;
334  if ((v != NULL) && (v->Typ() == INT_CMD))
335  {
336  leftv w = v->next;
337  if ((w != NULL) && (w->Typ() == INT_CMD))
338  {
339  intvec* aface = (intvec*) u->Data();
340  int ambientDimension = (int)(long) v->Data();
341  int dimension = (int)(long) w->Data();
342 
343  unsigned int af = 0;
344  for (int i=0; i<aface->length(); i++)
345  af |= 1<<((*aface)[i]-1);
346 
347  unsigned int t = af | (af - 1);
348  af = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(af) + 1));
349 
350  if (af & (1<<ambientDimension))
351  {
352  res->rtyp = INTVEC_CMD;
353  res->data = (void*) new intvec(1);
354  return FALSE;
355  }
356 
357  res->rtyp = INTVEC_CMD;
358  res->data = (void*) intToAface(af,ambientDimension,dimension);
359  return FALSE;
360  }

◆ refineCones()

BOOLEAN refineCones ( leftv  res,
leftv  args 
)

Definition at line 161 of file gitfan.cc.

163 {
164  leftv u=args;
165  if ((u != NULL) && (u->Typ() == LIST_CMD))
166  {
167  leftv v=u->next;
168  if ((v != NULL) && (v->Typ() == BIGINTMAT_CMD))
169  {
170  lists cones = (lists) u->Data();
171  bigintmat* bim = (bigintmat*) v->Data();
172  gfan::ZMatrix* zm = bigintmatToZMatrix(bim->transpose());
173  gfan::ZCone support = gfan::ZCone::givenByRays(*zm, gfan::ZMatrix(0, zm->getWidth()));
174  delete zm;
175 
176  /***
177  * Randomly compute a first full-dimensional cone and insert it into the fan.
178  * Compute a list of facets and relative interior points.
179  * The relative interior points are unique, assuming the cone is stored in canonical form,
180  * which is the case in our algorithm, as we supply no redundant inequalities.
181  * Hence we can decide whether a facet need to be traversed by crosschecking
182  * its relative interior point with this list.
183  **/
184  gfan::ZCone lambda; gfan::ZVector point;
185  do
186  {
187  point = randomPoint(&support);
188  lambda = subcone(cones, point);
189  }
190  while (lambda.dimension() < lambda.ambientDimension());
191  int iterationNumber = 1;
192  std::cout << "cones found: " << iterationNumber++ << std::endl;
193 
194  lambda.canonicalize();
195  gfan::ZFan* Sigma = new gfan::ZFan(lambda.ambientDimension());
196  Sigma->insert(lambda);
198  if (F.empty())
199  {
200  res->rtyp = fanID;
201  res->data = (void*) Sigma;
202  return FALSE;
203  }
204  int mu = 1024;
205 
207  gfan::ZCone eta;
208  gfan::ZVector interiorPoint;
209  gfan::ZVector facetNormal;
210  gitfan::facets newFacets;
211  while (!F.empty())
212  {
213  /***
214  * Extract a facet to traverse and its relative interior point.
215  **/
216  f = *(F.begin());
217  eta = f.getEta();
218  interiorPoint = f.getInteriorPoint();
219  facetNormal = f.getFacetNormal();
220 
221  /***
222  * construct a point, which lies on the other side of the facet.
223  * make sure it lies in the known support of our fan
224  * and that the cone around the point is maximal, containing eta.
225  **/
226  point = mu * interiorPoint - facetNormal;
227  while (!support.containsRelatively(point))
228  {
229  mu = mu * 16;
230  point = mu * interiorPoint - facetNormal;
231  }
232 
233  lambda = subcone(cones,point);
234  while ((lambda.dimension() < lambda.ambientDimension()) && !(lambda.contains(interiorPoint)))
235  {
236  mu = mu * 16;
237  point = mu * interiorPoint - facetNormal;
238  lambda = subcone(cones,point);
239  }
240  std::cout << "cones found: " << iterationNumber++ << std::endl;
241 
242  /***
243  * insert lambda into Sigma, and create a list of facets of lambda.
244  * merge the two lists of facets
245  **/
246  lambda.canonicalize();
247  Sigma->insert(lambda);
248  newFacets = interiorFacets(lambda, support);
249  mergeFacets(F,newFacets);
250  newFacets.clear();
251  }
252  res->rtyp = fanID;
253  res->data = (void*) Sigma;
254  return FALSE;

◆ subcone()

static gfan::ZCone subcone ( const lists cones,
const gfan::ZVector &  point 
)
static

Definition at line 91 of file gitfan.cc.

92 {
93  gfan::ZCone sigma = gfan::ZCone(gfan::ZMatrix(1,point.size()), gfan::ZMatrix(1,point.size()));
94  gfan::ZCone* zc;
95  for (int i=0; i<=cones->nr; i++)
96  {
97  zc = (gfan::ZCone*) cones->m[i].Data();
98  if (zc->contains(point))
99  sigma = gfan::intersection(sigma,*zc);
100  }
101  return(sigma);
102 }

◆ subset()

void subset ( std::vector< int > &  arr,
int  size,
int  left,
int  index,
std::vector< int > &  l,
std::vector< std::vector< int > > &  L 
)

Definition at line 544 of file gitfan.cc.

544  : unexpected parameter");
545  return TRUE;
546 }
547 
548 
549 void subset(std::vector<int> &arr, int size, int left, int index, std::vector<int> &l, std::vector<std::vector<int> > &L)
550 {
551  if(left==0)
552  {
553  L.push_back(l);
554  return;
555  }
556 
557  for(int i=index; i<size;i++)
558  {
checkSigns
BOOLEAN checkSigns(leftv res, leftv args)
Definition: gitfan.cc:363
FALSE
#define FALSE
Definition: auxiliary.h:96
sleftv::Data
void * Data()
Definition: subexpr.cc:1175
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
listOfAfacesToCheck
BOOLEAN listOfAfacesToCheck(leftv res, leftv args)
Definition: gitfan.cc:285
k
int k
Definition: cfEzgcd.cc:92
bigintmat
Definition: bigintmat.h:49
LIST_CMD
Definition: tok.h:117
gitfan::mergeFacets
void mergeFacets(facets &F, const facets &newFacets)
Definition: gitfan.cc:85
interiorFacets
static gitfan::facets interiorFacets(const gfan::ZCone &zc, const gfan::ZCone &bound)
Definition: gitfan.cc:104
intToAface
intvec * intToAface(unsigned int v0, int n, int k)
Definition: gitfan.cc:272
binomial
static int binomial(int n, int k)
Definition: gitfan.cc:257
randomPoint
gfan::ZVector randomPoint(const gfan::ZCone *zc, const int b)
Definition: bbcone.cc:1069
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
BIGINTMAT_CMD
Definition: grammar.cc:278
sleftv
Class used for (list of) interpreter objects.
Definition: subexpr.h:81
slists::nr
int nr
Definition: lists.h:43
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
gitfan::facet
Definition: gitfan.h:17
mu
void mu(int **points, int sizePoints)
Definition: cfNewtonPolygon.cc:467
i
int i
Definition: cfEzgcd.cc:125
res
CanonicalForm res
Definition: facAbsFact.cc:64
INT_CMD
Definition: tok.h:95
support
BOOLEAN support(leftv res, leftv args)
Definition: cohomo.cc:4972
intvec
Definition: intvec.h:18
sleftv::data
void * data
Definition: subexpr.h:87
slists::m
sleftv * m
Definition: lists.h:45
inequalities
BOOLEAN inequalities(leftv res, leftv args)
Definition: bbcone.cc:560
gitfan::facets
std::set< facet, facet_compare > facets
Definition: gitfan.h:50
slists
Definition: lists.h:22
INTVEC_CMD
Definition: tok.h:100
bigintmatToZMatrix
gfan::ZMatrix * bigintmatToZMatrix(const bigintmat &bim)
Definition: callgfanlib_conversion.cc:57
lambda
void lambda(int **points, int sizePoints)
Definition: cfNewtonPolygon.cc:449
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
slists_bin
VAR omBin slists_bin
Definition: lists.cc:22
nextAfaceToCheck
BOOLEAN nextAfaceToCheck(leftv res, leftv args)
Definition: gitfan.cc:323
sleftv::Typ
int Typ()
Definition: subexpr.cc:1032
sleftv::rtyp
int rtyp
Definition: subexpr.h:90
NULL
#define NULL
Definition: omList.c:11
lists
slists * lists
Definition: mpr_numeric.h:145
refineCones
BOOLEAN refineCones(leftv res, leftv args)
Definition: gitfan.cc:161
equations
BOOLEAN equations(leftv res, leftv args)
Definition: bbcone.cc:577
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
slists::Init
INLINE_THIS void Init(int l=0)
p
int p
Definition: cfModGcd.cc:4019
count
int status int void size_t count
Definition: si_signals.h:58
subcone
static gfan::ZCone subcone(const lists &cones, const gfan::ZVector &point)
Definition: gitfan.cc:91
bigintmat::transpose
bigintmat * transpose()
Definition: bigintmat.cc:37
sleftv::next
leftv next
Definition: subexpr.h:85
fanID
VAR int fanID
Definition: bbfan.cc:19