My Project  UNKNOWN_GIT_VERSION
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)
 
BOOLEAN subsets (leftv res, leftv args)
 
int SI_MOD_INIT() gitfan (SModulFunctions *p)
 

Function Documentation

◆ binaryToBigint()

BOOLEAN binaryToBigint ( leftv  res,
leftv  args 
)

Definition at line 417 of file gitfan.cc.

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  }
439  res->rtyp = BIGINT_CMD;
440  res->data = (void*) endResult;
441  return FALSE;
442  }
443  WerrorS("binaryToBigint: unexpected parameter");
444  return TRUE;
445 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
#define FALSE
Definition: auxiliary.h:94
Definition: tok.h:38
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:538
int rows() const
Definition: intvec.h:94
char N base
Definition: ValueTraits.h:144
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
coeffs coeffs_BIGINT
Definition: ipid.cc:52
int Typ()
Definition: subexpr.cc:1039
Definition: intvec.h:17
CanonicalForm res
Definition: facAbsFact.cc:64
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:656
int i
Definition: cfEzgcd.cc:125
leftv next
Definition: subexpr.h:86
static FORCE_INLINE void n_Power(number a, int b, number *res, const coeffs r)
fill res with the power a^b
Definition: coeffs.h:632
#define NULL
Definition: omList.c:10
int cols() const
Definition: intvec.h:93
void * Data()
Definition: subexpr.cc:1182
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
int l
Definition: cfEzgcd.cc:93

◆ binomial()

static int binomial ( int  n,
int  k 
)
static

Definition at line 262 of file gitfan.cc.

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;
270  for (int j=n-k+1; j<=n; j++)
271  num = num*j;
272  gfan::Integer bin = num/den;
273  return(bin.toInt());
274 }
int j
Definition: facHensel.cc:105
CanonicalForm num(const CanonicalForm &f)
int k
Definition: cfEzgcd.cc:92
int i
Definition: cfEzgcd.cc:125
CanonicalForm den(const CanonicalForm &f)

◆ checkSigns()

BOOLEAN checkSigns ( leftv  res,
leftv  args 
)

Definition at line 368 of file gitfan.cc.

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;
410  }
411  }
412  WerrorS("checkSigns: unexpected parameter");
413  return TRUE;
414 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
Definition: tok.h:96
#define FALSE
Definition: auxiliary.h:94
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * iv2bim(intvec *b, const coeffs C)
Definition: bigintmat.cc:349
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
coeffs coeffs_BIGINT
Definition: ipid.cc:52
int Typ()
Definition: subexpr.cc:1039
Definition: intvec.h:17
CanonicalForm res
Definition: facAbsFact.cc:64
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:557
int i
Definition: cfEzgcd.cc:125
Variable next() const
Definition: factory.h:137
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
leftv next
Definition: subexpr.h:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
int length() const
Definition: intvec.h:92
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
coeffs basecoeffs() const
Definition: bigintmat.h:147
void * Data()
Definition: subexpr.cc:1182
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
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:494

◆ composeIntvecs()

BOOLEAN composeIntvecs ( leftv  res,
leftv  args 
)

Definition at line 448 of file gitfan.cc.

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;
465  }
466  }
467  WerrorS("composeIntvecs: unexpected parameter");
468  return TRUE;
469 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
#define FALSE
Definition: auxiliary.h:94
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:92
int Typ()
Definition: subexpr.cc:1039
Definition: intvec.h:17
CanonicalForm res
Definition: facAbsFact.cc:64
int i
Definition: cfEzgcd.cc:125
Variable next() const
Definition: factory.h:137
leftv next
Definition: subexpr.h:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
int length() const
Definition: intvec.h:92
void * Data()
Definition: subexpr.cc:1182

◆ findPlaceToInsert()

BOOLEAN findPlaceToInsert ( leftv  res,
leftv  args 
)

Definition at line 472 of file gitfan.cc.

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;
542  }
543  }
544  WerrorS("findPlaceToInsert: unexpected parameter");
545  return TRUE;
546 }
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:511
sleftv * m
Definition: lists.h:45
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
Definition: tok.h:96
Definition: lists.h:22
#define FALSE
Definition: auxiliary.h:94
Definition: tok.h:38
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
coeffs coeffs_BIGINT
Definition: ipid.cc:52
int Typ()
Definition: subexpr.cc:1039
CanonicalForm res
Definition: facAbsFact.cc:64
Variable next() const
Definition: factory.h:137
int lSize(lists L)
Definition: lists.cc:25
leftv next
Definition: subexpr.h:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
slists * lists
Definition: mpr_numeric.h:146
void * Data()
Definition: subexpr.cc:1182
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
Definition: coeffs.h:460
Definition: tok.h:118

◆ gitfan()

int SI_MOD_INIT() gitfan ( SModulFunctions p)

Definition at line 608 of file gitfan.cc.

609 {
610  gfan::initializeCddlibIfRequired();
611  p->iiAddCproc("gitfan.lib","refineCones",FALSE,refineCones);
612  p->iiAddCproc("gitfan.lib","listOfAfacesToCheck",FALSE,listOfAfacesToCheck);
613  p->iiAddCproc("gitfan.lib","nextAfaceToCheck",FALSE,nextAfaceToCheck);
614  p->iiAddCproc("gitfan.lib","checkSigns",FALSE,checkSigns);
615  p->iiAddCproc("gitfan.lib","binaryToBigint",FALSE,binaryToBigint);
616  p->iiAddCproc("gitfan.lib","composeIntvecs",FALSE,composeIntvecs);
617  p->iiAddCproc("gitfan.lib","findPlaceToInsert",FALSE,findPlaceToInsert);
618  p->iiAddCproc("gitfan.lib","subsets",FALSE,subsets);
619  return (MAX_TOK);
620 }
#define FALSE
Definition: auxiliary.h:94
Definition: tok.h:216
BOOLEAN composeIntvecs(leftv res, leftv args)
Definition: gitfan.cc:448
BOOLEAN listOfAfacesToCheck(leftv res, leftv args)
Definition: gitfan.cc:290
BOOLEAN binaryToBigint(leftv res, leftv args)
Definition: gitfan.cc:417
BOOLEAN findPlaceToInsert(leftv res, leftv args)
Definition: gitfan.cc:472
BOOLEAN nextAfaceToCheck(leftv res, leftv args)
Definition: gitfan.cc:328
BOOLEAN checkSigns(leftv res, leftv args)
Definition: gitfan.cc:368
BOOLEAN subsets(leftv res, leftv args)
Definition: gitfan.cc:565
int p
Definition: cfModGcd.cc:4019
BOOLEAN refineCones(leftv res, leftv args)
Definition: gitfan.cc:162

◆ 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;
160 }
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
BOOLEAN inequalities(leftv res, leftv args)
Definition: bbcone.cc:560
std::set< facet, facet_compare > facets
Definition: gitfan.h:50
int i
Definition: cfEzgcd.cc:125
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
BOOLEAN equations(leftv res, leftv args)
Definition: bbcone.cc:577
const CanonicalForm & w
Definition: facAbsFact.cc:55

◆ intToAface()

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

Definition at line 277 of file gitfan.cc.

278 {
279  intvec* v = new intvec(k);
280  int j = 0;
281  for (int i=0; i<n; i++)
282  {
283  if (v0 & (1<<i))
284  (*v)[j++] = i+1;
285  }
286  return v;
287 }
int j
Definition: facHensel.cc:105
int k
Definition: cfEzgcd.cc:92
Definition: intvec.h:17
int i
Definition: cfEzgcd.cc:125
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37

◆ listOfAfacesToCheck()

BOOLEAN listOfAfacesToCheck ( leftv  res,
leftv  args 
)

Definition at line 290 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;
321  }
322  }
323  WerrorS("listOfAfacesToCheck: unexpected parameter");
324  return TRUE;
325 }
int status int void size_t count
Definition: si_signals.h:59
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static int binomial(int n, int k)
Definition: gitfan.cc:262
sleftv * m
Definition: lists.h:45
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
Definition: tok.h:96
Definition: lists.h:22
#define FALSE
Definition: auxiliary.h:94
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:92
int Typ()
Definition: subexpr.cc:1039
void * data
Definition: subexpr.h:88
CanonicalForm res
Definition: facAbsFact.cc:64
int i
Definition: cfEzgcd.cc:125
leftv next
Definition: subexpr.h:86
INLINE_THIS void Init(int l=0)
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
slists * lists
Definition: mpr_numeric.h:146
int rtyp
Definition: subexpr.h:91
void * Data()
Definition: subexpr.cc:1182
Definition: tok.h:118
omBin slists_bin
Definition: lists.cc:23
intvec * intToAface(unsigned int v0, int n, int k)
Definition: gitfan.cc:277

◆ nextAfaceToCheck()

BOOLEAN nextAfaceToCheck ( leftv  res,
leftv  args 
)

Definition at line 328 of file gitfan.cc.

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  }
361  }
362  }
363  WerrorS("nextAfaceToCheck: unexpected parameter");
364  return TRUE;
365 }
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
Definition: tok.h:96
#define FALSE
Definition: auxiliary.h:94
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
int Typ()
Definition: subexpr.cc:1039
Definition: intvec.h:17
CanonicalForm res
Definition: facAbsFact.cc:64
int i
Definition: cfEzgcd.cc:125
Variable next() const
Definition: factory.h:137
leftv next
Definition: subexpr.h:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
BOOLEAN dimension(leftv res, leftv args)
Definition: bbcone.cc:757
#define NULL
Definition: omList.c:10
int length() const
Definition: intvec.h:92
const CanonicalForm & w
Definition: facAbsFact.cc:55
BOOLEAN ambientDimension(leftv res, leftv args)
Definition: bbcone.cc:723
void * Data()
Definition: subexpr.cc:1182
intvec * intToAface(unsigned int v0, int n, int k)
Definition: gitfan.cc:277

◆ refineCones()

BOOLEAN refineCones ( leftv  res,
leftv  args 
)

Definition at line 162 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);
197  gitfan::facets F = interiorFacets(lambda, support);
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;
255  }
256  }
257  WerrorS("refineCones: unexpected parameters");
258  return TRUE;
259 }
bigintmat * transpose()
Definition: bigintmat.cc:37
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
void mu(int **points, int sizePoints)
Definition: lists.h:22
#define FALSE
Definition: auxiliary.h:94
Matrices of numbers.
Definition: bigintmat.h:51
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
int fanID
Definition: bbfan.cc:19
int Typ()
Definition: subexpr.cc:1039
gfan::ZVector randomPoint(const gfan::ZCone *zc)
Definition: bbcone.cc:1055
void mergeFacets(facets &F, const facets &newFacets)
Definition: gitfan.cc:77
CanonicalForm res
Definition: facAbsFact.cc:64
gfan::ZMatrix * bigintmatToZMatrix(const bigintmat &bim)
std::set< facet, facet_compare > facets
Definition: gitfan.h:50
FILE * f
Definition: checklibs.c:9
leftv next
Definition: subexpr.h:86
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
slists * lists
Definition: mpr_numeric.h:146
static gfan::ZCone subcone(const lists &cones, const gfan::ZVector &point)
Definition: gitfan.cc:91
void lambda(int **points, int sizePoints)
void * Data()
Definition: subexpr.cc:1182
Definition: tok.h:118
static gitfan::facets interiorFacets(const gfan::ZCone &zc, const gfan::ZCone &bound)
Definition: gitfan.cc:104

◆ 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 }
sleftv * m
Definition: lists.h:45
int i
Definition: cfEzgcd.cc:125
int nr
Definition: lists.h:43
void * Data()
Definition: subexpr.cc:1182

◆ 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 549 of file gitfan.cc.

550 {
551  if(left==0)
552  {
553  L.push_back(l);
554  return;
555  }
556 
557  for(int i=index; i<size;i++)
558  {
559  l.push_back(arr[i]);
560  subset(arr,size,left-1,i+1,l,L);
561  l.pop_back();
562  }
563 }
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
Definition: gitfan.cc:549
int i
Definition: cfEzgcd.cc:125
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int l
Definition: cfEzgcd.cc:93

◆ subsets()

BOOLEAN subsets ( leftv  res,
leftv  args 
)

Definition at line 565 of file gitfan.cc.

566 {
567  leftv u = args;
568  if ((u!=NULL) && (u->Typ()==INT_CMD))
569  {
570  leftv v = u->next;
571  if ((v!=NULL) && (v->Typ()==INT_CMD) && (v->next==NULL))
572  {
573  int n = (int)(long) u->Data();
574  int k = (int)(long) v->Data();
575  std::vector<int> array(n);
576  for (int i=0; i<n; i++)
577  array[i]=i+1;
578  std::vector<int> ltemp;
579  std::vector<std::vector<int> > lt;
580  subset(array,n,k,0,ltemp,lt);
581 
583  Lt->Init(lt.size());
584  for (int i=0; i<lt.size(); i++)
585  {
586  std::vector<int> lti = lt[i];
587  lists Lti = (lists) omAllocBin(slists_bin);
588  Lti->Init(k);
589  for(int j=0; j<lti.size(); j++)
590  {
591  Lti->m[j].rtyp = INT_CMD;
592  Lti->m[j].data = (void*)(long)lti[j];
593  }
594  Lt->m[i].rtyp = LIST_CMD;
595  Lt->m[i].data = (void*) Lti;
596  }
597 
598  res->rtyp = LIST_CMD;
599  res->data = (void*) Lt;
600  return FALSE;
601  }
602  }
603  WerrorS("subsets: unexpected parameter");
604  return TRUE;
605 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
Definition: gitfan.cc:549
sleftv * m
Definition: lists.h:45
int j
Definition: facHensel.cc:105
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
Definition: tok.h:96
Definition: lists.h:22
#define FALSE
Definition: auxiliary.h:94
#define TRUE
Definition: auxiliary.h:98
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:92
int Typ()
Definition: subexpr.cc:1039
void * data
Definition: subexpr.h:88
CanonicalForm res
Definition: facAbsFact.cc:64
int i
Definition: cfEzgcd.cc:125
Variable next() const
Definition: factory.h:137
leftv next
Definition: subexpr.h:86
INLINE_THIS void Init(int l=0)
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
slists * lists
Definition: mpr_numeric.h:146
int rtyp
Definition: subexpr.h:91
void * Data()
Definition: subexpr.cc:1182
Definition: tok.h:118
omBin slists_bin
Definition: lists.cc:23