Functions
cfNewtonPolygon.h File Reference

This file provides functions to compute the Newton polygon of a bivariate polynomial. More...

Go to the source code of this file.

Functions

int polygon (int **points, int sizePoints)
 compute a polygon More...
 
int ** newtonPolygon (const CanonicalForm &F, int &sizeOfNewtonPoly)
 compute the Newton polygon of a bivariate polynomial More...
 
int ** newtonPolygon (const CanonicalForm &F, const CanonicalForm &G, int &sizeOfNewtonPoly)
 compute the convex hull of the support of two bivariate polynomials More...
 
bool isInPolygon (int **points, int sizePoints, int *point)
 check if point is inside a polygon described by points More...
 
int * getRightSide (int **polygon, int sizeOfPolygon, int &sizeOfOutput)
 get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with at least one point of the polygon lying on the x-axis and one lying on the y-axis More...
 
bool irreducibilityTest (const CanonicalForm &F)
 computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S.Gao "Absolute irreducibility of polynomials via polytopes", Example 1 More...
 
bool absIrredTest (const CanonicalForm &F)
 absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo More...
 
bool modularIrredTest (const CanonicalForm &F)
 modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo More...
 
bool modularIrredTestWithShift (const CanonicalForm &F)
 modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo More...
 
void convexDense (int **points, int sizePoints, mpz_t *&M, mpz_t *&A)
 Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu, Lecerf. More...
 
CanonicalForm compress (const CanonicalForm &F, mpz_t *&inverseM, mpz_t *&A, bool computeMA=true)
 compress a bivariate poly More...
 
CanonicalForm decompress (const CanonicalForm &F, const mpz_t *M, const mpz_t *A)
 decompress a bivariate poly More...
 

Detailed Description

This file provides functions to compute the Newton polygon of a bivariate polynomial.

Author
Martin Lee

Definition in file cfNewtonPolygon.h.

Function Documentation

◆ absIrredTest()

bool absIrredTest ( const CanonicalForm F)

absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo

Returns
true if F satisfies condition (C) from the above paper and thus is absolutely irreducible, false otherwise
Parameters
[in]Fa bivariate polynomial irreducible over ground field

Definition at line 1142 of file cfNewtonPolygon.cc.

1143 {
1144  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1145  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1146 
1147  int sizeOfNewtonPolygon;
1148  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1149  bool isRat= isOn (SW_RATIONAL);
1150  if (isRat)
1151  Off (SW_RATIONAL);
1152  int p=getCharacteristic();
1153  int d=1;
1154  char bufGFName='Z';
1155  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
1156  if (GF)
1157  {
1158  d= getGFDegree();
1159  bufGFName=gf_name;
1160  }
1161 
1162  setCharacteristic(0);
1163 
1164  CanonicalForm g= gcd (newtonPolyg[0][0], newtonPolyg[0][1]); //maybe it's better to use plain intgcd
1165 
1166  int i= 1;
1167  while (!g.isOne() && i < sizeOfNewtonPolygon)
1168  {
1169  g= gcd (g, newtonPolyg[i][0]);
1170  g= gcd (g, newtonPolyg[i][1]);
1171  i++;
1172  }
1173 
1174  bool result= g.isOne();
1175 
1176  if (GF)
1177  setCharacteristic (p, d, bufGFName);
1178  else
1179  setCharacteristic(p);
1180 
1181  if (isRat)
1182  On (SW_RATIONAL);
1183 
1184  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1185  delete [] newtonPolyg[i];
1186 
1187  delete [] newtonPolyg;
1188 
1189  return result;
1190 }
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
void Off(int sw)
switches
return P p
Definition: myNF.cc:203
factory&#39;s main class
Definition: canonicalform.h:75
char gf_name
Definition: gfops.cc:52
g
Definition: cfModGcd.cc:4031
void setCharacteristic(int c)
Definition: cf_char.cc:23
int getCharacteristic()
Definition: cf_char.cc:51
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
static int gettype()
Definition: cf_factory.h:28
int gcd(int a, int b)
Definition: walkSupport.cc:839
int getGFDegree()
Definition: cf_char.cc:56
#define GaloisFieldDomain
Definition: cf_defs.h:22
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76

◆ compress()

CanonicalForm compress ( const CanonicalForm F,
mpz_t *&  inverseM,
mpz_t *&  A,
bool  computeMA = true 
)

compress a bivariate poly

Returns
compress returns a compressed bivariate poly
See also
convexDense, decompress
Parameters
[in]Fcompressed, i.e. F.level()==2, bivariate poly
[in,out]inverseMreturns the inverse of M, if computeMA==true, M otherwise
[in,out]Areturns translation
[in]computeMAwhether to compute M and A

Definition at line 706 of file cfNewtonPolygon.cc.

707 {
708  int n;
709  int ** newtonPolyg= NULL;
710  if (computeMA)
711  {
712  newtonPolyg= newtonPolygon (F, n);
713  convexDense (newtonPolyg, n, M, A);
714  }
715 
717  Variable x= Variable (1);
718  Variable y= Variable (2);
719 
720  mpz_t expX, expY, minExpX, minExpY;
721  mpz_init (expX);
722  mpz_init (expY);
723  mpz_init (minExpX);
724  mpz_init (minExpY);
725 
726  int k= 0;
727  Variable alpha;
728  mpz_t * exps= new mpz_t [2*size (F)];
729  int count= 0;
730  for (CFIterator i= F; i.hasTerms(); i++)
731  {
732  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
733  {
734  mpz_set (expX, A[0]);
735  mpz_set (expY, A[1]);
736  mpz_addmul_ui (expX, M[1], i.exp());
737  mpz_addmul_ui (expY, M[3], i.exp());
738 
739  if (k == 0)
740  {
741  mpz_set (minExpX, expX);
742  mpz_set (minExpY, expY);
743  k= 1;
744  }
745  else
746  {
747  if (mpz_cmp (minExpY, expY) > 0)
748  mpz_set (minExpY, expY);
749  if (mpz_cmp (minExpX, expX) > 0)
750  mpz_set (minExpX, expX);
751  }
752  mpz_init_set (exps[count], expX);
753  count++;
754  mpz_init_set (exps[count], expY);
755  count++;
756  continue;
757  }
758  CFIterator j= i.coeff();
759  if (k == 0)
760  {
761  mpz_set (expX, A[0]);
762  mpz_addmul_ui (expX, M[1], i.exp());
763  mpz_addmul_ui (expX, M[0], j.exp());
764 
765  mpz_set (expY, A[1]);
766  mpz_addmul_ui (expY, M[3], i.exp());
767  mpz_addmul_ui (expY, M[2], j.exp());
768 
769  mpz_set (minExpX, expX);
770  mpz_set (minExpY, expY);
771  mpz_init_set (exps[count], expX);
772  count++;
773  mpz_init_set (exps[count], expY);
774  count++;
775  j++;
776  k= 1;
777  }
778 
779  for (; j.hasTerms(); j++)
780  {
781  mpz_set (expX, A[0]);
782  mpz_addmul_ui (expX, M[1], i.exp());
783  mpz_addmul_ui (expX, M[0], j.exp());
784 
785  mpz_set (expY, A[1]);
786  mpz_addmul_ui (expY, M[3], i.exp());
787  mpz_addmul_ui (expY, M[2], j.exp());
788 
789  mpz_init_set (exps[count], expX);
790  count++;
791  mpz_init_set (exps[count], expY);
792  count++;
793  if (mpz_cmp (minExpY, expY) > 0)
794  mpz_set (minExpY, expY);
795  if (mpz_cmp (minExpX, expX) > 0)
796  mpz_set (minExpX, expX);
797  }
798  }
799 
800  count= 0;
801  int mExpX= mpz_get_si (minExpX);
802  int mExpY= mpz_get_si (minExpY);
803  for (CFIterator i= F; i.hasTerms(); i++)
804  {
805  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
806  {
807  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
808  power (y, mpz_get_si (exps[count+1])-mExpY);
809  count += 2;
810  continue;
811  }
812  CFIterator j= i.coeff();
813  for (; j.hasTerms(); j++)
814  {
815  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
816  power (y, mpz_get_si (exps[count+1])-mExpY);
817  count += 2;
818  }
819  }
820 
821  CanonicalForm tmp= LC (result);
822  if (tmp.inPolyDomain() && degree (tmp) <= 0)
823  {
824  int d= degree (result);
825  Variable x= result.mvar();
826  result -= tmp*power (x, d);
827  result += Lc (tmp)*power (x, d);
828  }
829 
830  if (computeMA)
831  {
832  for (int i= 0; i < n; i++)
833  delete [] newtonPolyg [i];
834  delete [] newtonPolyg;
835  mpz_mat_inv (M);
836  }
837 
838  delete [] exps;
839  mpz_clear (expX);
840  mpz_clear (expY);
841  mpz_clear (minExpX);
842  mpz_clear (minExpY);
843 
844  return result;
845 }
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
void mpz_mat_inv(mpz_t *&M)
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
#define M
Definition: sirandom.c:24
bool inPolyDomain() const
int j
Definition: myNF.cc:70
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
#define NULL
Definition: omList.c:10
void convexDense(int **points, int sizePoints, mpz_t *&M, mpz_t *&A)
Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu, Lecerf.
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ convexDense()

void convexDense ( int **  points,
int  sizePoints,
mpz_t *&  M,
mpz_t *&  A 
)

Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu, Lecerf.

Parameters
[in,out]pointsa set of points in Z^2, returns M (points)+A
[in]sizePointssize of points
[in,out]Mreturns an invertible 2x2 matrix
[in,out]Areturns translation

Definition at line 558 of file cfNewtonPolygon.cc.

559 {
560  if (sizePoints < 3)
561  {
562  if (sizePoints == 2)
563  {
564  mpz_t u,v,g,maxX,maxY;
565  mpz_init (u);
566  mpz_init (v);
567  mpz_init (g);
568  mpz_init_set_si (maxX,
569  (points[1][1] < points[0][1])?points[0][1]:points[1][1]);
570  mpz_init_set_si (maxY,
571  (points[1][0] < points[0][0])?points[0][0]:points[1][0]);
572  mpz_gcdext (g, u, v, maxX, maxY);
573  if (points [0] [1] != points [0] [0] && points [1] [0] != points [1] [1])
574  {
575  mpz_set (A[0], u);
576  mpz_mul (A[0], A[0], maxX);
577  mpz_set (M[2], maxY);
578  mpz_divexact (M[2], M[2], g);
579  mpz_set (A[1], M[2]);
580  mpz_neg (A[1], A[1]);
581  mpz_mul (A[1], A[1], maxX);
582  mpz_neg (u, u);
583  mpz_set (M[0], u);
584  mpz_set (M[1], v);
585  mpz_set (M[3], maxX);
586  mpz_divexact (M[3], M[3], g);
587  }
588  else
589  {
590  mpz_set (M[0], u);
591  mpz_set (M[1], v);
592  mpz_set (M[2], maxY);
593  mpz_divexact (M[2], M[2], g);
594  mpz_neg (M[2], M[2]);
595  mpz_set (M[3], maxX);
596  mpz_divexact (M[3], M[3], g);
597  }
598  mpz_clear (u);
599  mpz_clear (v);
600  mpz_clear (g);
601  mpz_clear (maxX);
602  mpz_clear (maxY);
603  }
604  else if (sizePoints == 1)
605  {
606  mpz_set_si (M[0], 1);
607  mpz_set_si (M[3], 1);
608  }
609  return;
610  }
611  mpz_set_si (M[0], 1);
612  mpz_set_si (M[3], 1);
613 
614  mpz_t * Mu= new mpz_t[4];
615  mpz_init_set_si (Mu[1], 1);
616  mpz_init_set_si (Mu[2], 1);
617  mpz_init (Mu[0]);
618  mpz_init (Mu[3]);
619 
620  mpz_t * Lambda= new mpz_t[4];
621  mpz_init_set_si (Lambda[0], 1);
622  mpz_init_set_si (Lambda[1], -1);
623  mpz_init_set_si (Lambda[3], 1);
624  mpz_init (Lambda[2]);
625 
626  mpz_t * InverseLambda= new mpz_t[4];
627  mpz_init_set_si (InverseLambda[0], 1);
628  mpz_init_set_si (InverseLambda[1], 1);
629  mpz_init_set_si (InverseLambda[3], 1);
630  mpz_init (InverseLambda[2]);
631 
632  mpz_t tmp;
633  mpz_init (tmp);
634  int minDiff, minSum, maxDiff, maxSum, maxX, maxY, b, d, f, h;
635  getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
636  do
637  {
638  if (maxX < maxY)
639  {
640  mu (points, sizePoints);
641 
642  mpz_mat_mul (Mu, M);
643 
644  mpz_set (tmp, A[0]);
645  mpz_set (A[0], A[1]);
646  mpz_set (A[1], tmp);
647  }
648  getMaxMin(points, sizePoints, minDiff, minSum, maxDiff, maxSum, maxX, maxY);
649  b= maxX - maxDiff;
650  d= maxX + maxY - maxSum;
651  f= maxY + minDiff;
652  h= minSum;
653  if (b + f > maxY)
654  {
655  lambda (points, sizePoints);
656  tau (points, sizePoints, maxY - f);
657 
658  mpz_mat_mul (Lambda, M);
659 
660  if (maxY-f > 0)
661  mpz_add_ui (A[0], A[0], maxY-f);
662  else
663  mpz_add_ui (A[0], A[0], f-maxY);
664  maxX= maxX + maxY - b - f;
665  }
666  else if (d + h > maxY)
667  {
668  lambdaInverse (points, sizePoints);
669  tau (points, sizePoints, -h);
670 
671  mpz_mat_mul (InverseLambda, M);
672 
673  if (h < 0)
674  mpz_add_ui (A[0], A[0], -h);
675  else
676  mpz_sub_ui (A[0], A[0], h);
677  maxX= maxX + maxY - d - h;
678  }
679  else
680  {
681  mpz_clear (tmp);
682  mpz_clear (Mu[0]);
683  mpz_clear (Mu[1]);
684  mpz_clear (Mu[2]);
685  mpz_clear (Mu[3]);
686  delete [] Mu;
687 
688  mpz_clear (Lambda[0]);
689  mpz_clear (Lambda[1]);
690  mpz_clear (Lambda[2]);
691  mpz_clear (Lambda[3]);
692  delete [] Lambda;
693 
694  mpz_clear (InverseLambda[0]);
695  mpz_clear (InverseLambda[1]);
696  mpz_clear (InverseLambda[2]);
697  mpz_clear (InverseLambda[3]);
698  delete [] InverseLambda;
699 
700  return;
701  }
702  } while (1);
703 }
void getMaxMin(int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
void mu(int **points, int sizePoints)
static coordinates * points
g
Definition: cfModGcd.cc:4031
#define M
Definition: sirandom.c:24
void lambdaInverse(int **points, int sizePoints)
#define A
Definition: sirandom.c:23
void tau(int **points, int sizePoints, int k)
FILE * f
Definition: checklibs.c:9
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
void lambda(int **points, int sizePoints)
void mpz_mat_mul(const mpz_t *N, mpz_t *&M)
static Poly * h
Definition: janet.cc:978
const poly b
Definition: syzextra.cc:213

◆ decompress()

CanonicalForm decompress ( const CanonicalForm F,
const mpz_t *  M,
const mpz_t *  A 
)

decompress a bivariate poly

Returns
decompress returns a decompressed bivariate poly
See also
convexDense, decompress
Parameters
[in]Fcompressed, i.e. F.level()<= 2, uni- or bivariate poly
[in]Mmatrix M obtained from compress
[in]Avector A obtained from compress

Definition at line 848 of file cfNewtonPolygon.cc.

849 {
851  Variable x= Variable (1);
852  Variable y= Variable (2);
853 
854  mpz_t expX, expY, minExpX, minExpY;
855  mpz_init (expX);
856  mpz_init (expY);
857  mpz_init (minExpX);
858  mpz_init (minExpY);
859 
860  mpz_t * exps= new mpz_t [2*size(F)];
861  int count= 0;
862  if (F.isUnivariate() && F.level() == 1)
863  {
864  CFIterator i= F;
865 
866  mpz_set_si (expX, i.exp());
867  mpz_sub (expX, expX, A[0]);
868  mpz_mul (expX, expX, inverseM[0]);
869  mpz_submul (expX, inverseM[1], A[1]);
870 
871  mpz_set_si (expY, i.exp());
872  mpz_sub (expY, expY, A[0]);
873  mpz_mul (expY, expY, inverseM[2]);
874  mpz_submul (expY, inverseM[3], A[1]);
875 
876  mpz_set (minExpX, expX);
877  mpz_set (minExpY, expY);
878 
879  mpz_init_set (exps[count], expX);
880  mpz_init_set (exps[count+1], expY);
881  count += 2;
882 
883  i++;
884  for (; i.hasTerms(); i++)
885  {
886  mpz_set_si (expX, i.exp());
887  mpz_sub (expX, expX, A[0]);
888  mpz_mul (expX, expX, inverseM[0]);
889  mpz_submul (expX, inverseM[1], A[1]);
890 
891  mpz_set_si (expY, i.exp());
892  mpz_sub (expY, expY, A[0]);
893  mpz_mul (expY, expY, inverseM[2]);
894  mpz_submul (expY, inverseM[3], A[1]);
895 
896  mpz_init_set (exps[count], expX);
897  mpz_init_set (exps[count+1], expY);
898  count += 2;
899 
900  if (mpz_cmp (minExpY, expY) > 0)
901  mpz_set (minExpY, expY);
902  if (mpz_cmp (minExpX, expX) > 0)
903  mpz_set (minExpX, expX);
904  }
905 
906  int mExpX= mpz_get_si (minExpX);
907  int mExpY= mpz_get_si (minExpY);
908  count= 0;
909  for (i= F; i.hasTerms(); i++)
910  {
911  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
912  power (y, mpz_get_si (exps[count+1])-mExpY);
913  count += 2;
914  }
915 
916  mpz_clear (expX);
917  mpz_clear (expY);
918  mpz_clear (minExpX);
919  mpz_clear (minExpY);
920 
921  delete [] exps;
922  return result/ Lc (result); //normalize
923  }
924 
925  mpz_t tmp;
926  mpz_init (tmp);
927  int k= 0;
928  Variable alpha;
929  for (CFIterator i= F; i.hasTerms(); i++)
930  {
931  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
932  {
933  mpz_set_si (expX, i.exp());
934  mpz_sub (expX, expX, A[1]);
935  mpz_mul (expX, expX, inverseM[1]);
936  mpz_submul (expX, A[0], inverseM[0]);
937 
938  mpz_set_si (expY, i.exp());
939  mpz_sub (expY, expY, A[1]);
940  mpz_mul (expY, expY, inverseM[3]);
941  mpz_submul (expY, A[0], inverseM[2]);
942 
943  if (k == 0)
944  {
945  mpz_set (minExpX, expX);
946  mpz_set (minExpY, expY);
947  k= 1;
948  }
949  else
950  {
951  if (mpz_cmp (minExpY, expY) > 0)
952  mpz_set (minExpY, expY);
953  if (mpz_cmp (minExpX, expX) > 0)
954  mpz_set (minExpX, expX);
955  }
956  mpz_init_set (exps[count], expX);
957  mpz_init_set (exps[count+1], expY);
958  count += 2;
959  continue;
960  }
961  CFIterator j= i.coeff();
962  if (k == 0)
963  {
964  mpz_set_si (expX, j.exp());
965  mpz_sub (expX, expX, A[0]);
966  mpz_mul (expX, expX, inverseM[0]);
967  mpz_set_si (tmp, i.exp());
968  mpz_sub (tmp, tmp, A[1]);
969  mpz_addmul (expX, tmp, inverseM[1]);
970 
971  mpz_set_si (expY, j.exp());
972  mpz_sub (expY, expY, A[0]);
973  mpz_mul (expY, expY, inverseM[2]);
974  mpz_set_si (tmp, i.exp());
975  mpz_sub (tmp, tmp, A[1]);
976  mpz_addmul (expY, tmp, inverseM[3]);
977 
978  mpz_set (minExpX, expX);
979  mpz_set (minExpY, expY);
980 
981  mpz_init_set (exps[count], expX);
982  mpz_init_set (exps[count+1], expY);
983  count += 2;
984 
985  j++;
986  k= 1;
987  }
988 
989  for (; j.hasTerms(); j++)
990  {
991  mpz_set_si (expX, j.exp());
992  mpz_sub (expX, expX, A[0]);
993  mpz_mul (expX, expX, inverseM[0]);
994  mpz_set_si (tmp, i.exp());
995  mpz_sub (tmp, tmp, A[1]);
996  mpz_addmul (expX, tmp, inverseM[1]);
997 
998  mpz_set_si (expY, j.exp());
999  mpz_sub (expY, expY, A[0]);
1000  mpz_mul (expY, expY, inverseM[2]);
1001  mpz_set_si (tmp, i.exp());
1002  mpz_sub (tmp, tmp, A[1]);
1003  mpz_addmul (expY, tmp, inverseM[3]);
1004 
1005  mpz_init_set (exps[count], expX);
1006  mpz_init_set (exps[count+1], expY);
1007  count += 2;
1008 
1009  if (mpz_cmp (minExpY, expY) > 0)
1010  mpz_set (minExpY, expY);
1011  if (mpz_cmp (minExpX, expX) > 0)
1012  mpz_set (minExpX, expX);
1013  }
1014  }
1015 
1016  int mExpX= mpz_get_si (minExpX);
1017  int mExpY= mpz_get_si (minExpY);
1018  count= 0;
1019  for (CFIterator i= F; i.hasTerms(); i++)
1020  {
1021  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
1022  {
1023  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1024  power (y, mpz_get_si (exps[count+1])-mExpY);
1025  count += 2;
1026  continue;
1027  }
1028  for (CFIterator j= i.coeff(); j.hasTerms(); j++)
1029  {
1030  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1031  power (y, mpz_get_si (exps[count+1])-mExpY);
1032  count += 2;
1033  }
1034  }
1035 
1036  mpz_clear (expX);
1037  mpz_clear (expY);
1038  mpz_clear (minExpX);
1039  mpz_clear (minExpY);
1040  mpz_clear (tmp);
1041 
1042  delete [] exps;
1043 
1044  return result/Lc (result); //normalize
1045 }
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
int j
Definition: myNF.cc:70
bool isUnivariate() const
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ getRightSide()

int* getRightSide ( int **  polygon,
int  sizeOfPolygon,
int &  sizeOfOutput 
)

get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with at least one point of the polygon lying on the x-axis and one lying on the y-axis

Returns
an array containing the slopes as described above
Parameters
[in]polygonvertices of a polygon
[in]sizeOfPolygonnumber of vertices
[in,out]sizeOfOutputsize of the output

Definition at line 1050 of file cfNewtonPolygon.cc.

1051 {
1052  int maxY= polygon [0][0];
1053  int indexY= 0;
1054  for (int i= 1; i < sizeOfPolygon; i++)
1055  {
1056  if (maxY < polygon [i][0])
1057  {
1058  maxY= polygon [i][0];
1059  indexY= i;
1060  }
1061  else if (maxY == polygon [i][0])
1062  {
1063  if (polygon [indexY][1] < polygon[i][1])
1064  indexY= i;
1065  }
1066  if (maxY > polygon [i][0])
1067  break;
1068  }
1069 
1070  int count= -1;
1071  for (int i= indexY; i < sizeOfPolygon; i++)
1072  {
1073  if (polygon[i][0] == 0)
1074  {
1075  count= i - indexY;
1076  break;
1077  }
1078  }
1079 
1080  int * result;
1081  int index= 0;
1082  if (count < 0)
1083  {
1084  result= new int [sizeOfPolygon - indexY];
1085  sizeOfOutput= sizeOfPolygon - indexY;
1086  count= sizeOfPolygon - indexY - 1;
1087  result [0]= polygon[sizeOfPolygon - 1][0] - polygon [0] [0];
1088  index= 1;
1089  }
1090  else
1091  {
1092  sizeOfOutput= count;
1093  result= new int [count];
1094  }
1095 
1096  for (int i= indexY + count; i > indexY; i--, index++)
1097  result [index]= polygon [i - 1] [0] - polygon [i] [0];
1098 
1099  return result;
1100 }
int status int void size_t count
Definition: si_signals.h:59
int polygon(int **points, int sizePoints)
compute a polygon
int i
Definition: cfEzgcd.cc:123
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
return result
Definition: facAbsBiFact.cc:76

◆ irreducibilityTest()

bool irreducibilityTest ( const CanonicalForm F)

computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S.Gao "Absolute irreducibility of polynomials via polytopes", Example 1

Returns
true if it satisfies the above criterion, false otherwise
Parameters
[in]Fa bivariate polynomial

Definition at line 1102 of file cfNewtonPolygon.cc.

1103 {
1104  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1105  ASSERT (getCharacteristic() == 0, "expected polynomial over integers or rationals");
1106 
1107  int sizeOfNewtonPolygon;
1108  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1109  if (sizeOfNewtonPolygon == 3)
1110  {
1111  bool check1=
1112  (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
1113  if (check1)
1114  {
1115  bool check2=
1116  (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
1117  if (check2)
1118  {
1119  bool isRat= isOn (SW_RATIONAL);
1120  if (isRat)
1121  Off (SW_RATIONAL);
1122  CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
1123  tmp= gcd (tmp, newtonPolyg[1][0]);
1124  tmp= gcd (tmp, newtonPolyg[1][1]);
1125  tmp= gcd (tmp, newtonPolyg[2][0]);
1126  tmp= gcd (tmp, newtonPolyg[2][1]);
1127  if (isRat)
1128  On (SW_RATIONAL);
1129  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1130  delete [] newtonPolyg [i];
1131  delete [] newtonPolyg;
1132  return (tmp==1);
1133  }
1134  }
1135  }
1136  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1137  delete [] newtonPolyg [i];
1138  delete [] newtonPolyg;
1139  return false;
1140 }
void Off(int sw)
switches
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ isInPolygon()

bool isInPolygon ( int **  points,
int  sizePoints,
int *  point 
)

check if point is inside a polygon described by points

Returns
true if point is inside a polygon described by points
Parameters
[in]pointsan array of points in the plane describing a polygon
[in]sizePointssize of points
[in]pointa point in the plane

Definition at line 383 of file cfNewtonPolygon.cc.

384 {
385  int ** buf= new int* [sizePoints + 1];
386  for (int i= 0; i < sizePoints; i++)
387  {
388  buf [i]= new int [2];
389  buf [i] [0]= points [i] [0];
390  buf [i] [1]= points [i] [1];
391  }
392  buf [sizePoints]= new int [2];
393  buf [sizePoints] [0]= point [0];
394  buf [sizePoints] [1]= point [1];
395  int sizeBuf= sizePoints + 1;
396 
397  swap (buf, 0, smallestPointIndex (buf, sizeBuf));
398  int * minusPoint= new int [2];
399  minusPoint [0]= buf[0] [0];
400  minusPoint [1]= buf[0] [1];
401  translate (buf, minusPoint, sizeBuf);
402  sort (buf, sizeBuf);
403  minusPoint[0]= - minusPoint[0];
404  minusPoint[1]= - minusPoint[1];
405  translate (buf, minusPoint, sizeBuf); //reverse translation
406  delete [] minusPoint;
407 
408  if (buf [0] [0] == point [0] && buf [0] [1] == point [1])
409  {
410  for (int i= 0; i < sizeBuf; i++)
411  delete [] buf[i];
412  delete [] buf;
413  return false;
414  }
415 
416  for (int i= 1; i < sizeBuf-1; i++)
417  {
418  if (buf [i] [0] == point [0] && buf [i] [1] == point [1])
419  {
420  bool result= !isConvex (buf, i);
421  for (int i= 0; i < sizeBuf; i++)
422  delete [] buf [i];
423  delete [] buf;
424  return result;
425  }
426  }
427 
428  if (buf [sizeBuf - 1] [0] == point [0] && buf [sizeBuf-1] [1] == point [1])
429  {
430  buf [1] [0]= point [0];
431  buf [1] [1]= point [1];
432  buf [2] [0]= buf [0] [0];
433  buf [2] [1]= buf [0] [1];
434  buf [0] [0]= buf [sizeBuf-2] [0];
435  buf [0] [1]= buf [sizeBuf-2] [1];
436  bool result= !isConvex (buf, 1);
437  for (int i= 0; i < sizeBuf; i++)
438  delete [] buf [i];
439  delete [] buf;
440  return result;
441  }
442  for (int i= 0; i < sizeBuf; i++)
443  delete [] buf [i];
444  delete [] buf;
445 
446  return false;
447 }
static bool isConvex(int *point1, int *point2, int *point3)
static void translate(int **points, int *point, int sizePoints)
static void swap(int **points, int i, int j)
static coordinates * points
static void sort(int **points, int sizePoints)
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
static int smallestPointIndex(int **points, int sizePoints)
return result
Definition: facAbsBiFact.cc:76

◆ modularIrredTest()

bool modularIrredTest ( const CanonicalForm F)

modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo

Returns
true if F is absolutely irreducible, false otherwise
Parameters
[in]Fa bivariate polynomial irreducible over Z

Definition at line 1192 of file cfNewtonPolygon.cc.

1193 {
1194  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1195  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1196 
1197  bool isRat= isOn (SW_RATIONAL);
1198  if (isRat)
1199  Off (SW_RATIONAL);
1200 
1201  if (isRat)
1202  {
1203  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1204  }
1205 
1206  CanonicalForm Fp, N= maxNorm (F);
1207  int tdeg= totaldegree (F);
1208 
1209  int i= 0;
1210  //TODO: maybe it's better to choose the characteristic as large as possible
1211  // as factorization over large finite field will be faster
1212  //TODO: handle those cases where our factory primes are not enough
1213  //TODO: factorize coefficients corresponding to the vertices of the Newton
1214  // polygon and only try the obtained factors
1215  if (N < cf_getSmallPrime (cf_getNumSmallPrimes()-1))
1216  {
1217  while (i < cf_getNumSmallPrimes() && N > cf_getSmallPrime(i))
1218  {
1220  Fp= F.mapinto();
1221  i++;
1222  if (totaldegree (Fp) == tdeg)
1223  {
1224  if (absIrredTest (Fp))
1225  {
1226  CFFList factors= factorize (Fp);
1227  if (factors.length() == 2 && factors.getLast().exp() == 1)
1228  {
1229  if (isRat)
1230  On (SW_RATIONAL);
1231  setCharacteristic (0);
1232  return true;
1233  }
1234  }
1235  }
1236  setCharacteristic (0);
1237  }
1238  }
1239  else
1240  {
1241  while (i < cf_getNumPrimes() && N > cf_getPrime (i))
1242  {
1244  Fp= F.mapinto();
1245  i++;
1246  if (totaldegree (Fp) == tdeg)
1247  {
1248  if (absIrredTest (Fp))
1249  {
1250  CFFList factors= factorize (Fp);
1251  if (factors.length() == 2 && factors.getLast().exp() == 1)
1252  {
1253  if (isRat)
1254  On (SW_RATIONAL);
1255  setCharacteristic (0);
1256  return true;
1257  }
1258  }
1259  }
1260  setCharacteristic (0);
1261  }
1262  }
1263 
1264  if (isRat)
1265  On (SW_RATIONAL);
1266 
1267  return false;
1268 }
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
int cf_getPrime(int i)
Definition: cf_primes.cc:14
void Off(int sw)
switches
factory&#39;s main class
Definition: canonicalform.h:75
void setCharacteristic(int c)
Definition: cf_char.cc:23
int tdeg(poly p)
Definition: walkSupport.cc:38
CanonicalForm mapinto() const
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool isOn(int sw)
switches
void On(int sw)
switches
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int length() const
Definition: ftmpl_list.cc:273
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int cf_getNumPrimes()
Definition: cf_primes.cc:23

◆ modularIrredTestWithShift()

bool modularIrredTestWithShift ( const CanonicalForm F)

modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo

Returns
true if F is absolutely irreducible, false otherwise
Parameters
[in]Fa bivariate polynomial irreducible over Z

Definition at line 1271 of file cfNewtonPolygon.cc.

1272 {
1273  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1274  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1275 
1276  bool isRat= isOn (SW_RATIONAL);
1277  if (isRat)
1278  Off (SW_RATIONAL);
1279 
1280  if (isRat)
1281  {
1282  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1283  }
1284 
1285  Variable x= Variable (1);
1286  Variable y= Variable (2);
1287  CanonicalForm Fp;
1288  int tdeg= totaldegree (F);
1289 
1290  REvaluation E;
1291 
1292  setCharacteristic (2);
1293  Fp= F.mapinto();
1294 
1295  E= REvaluation (1,2, FFRandom());
1296 
1297  E.nextpoint();
1298 
1299  Fp= Fp (x+E[1], x);
1300  Fp= Fp (y+E[2], y);
1301 
1302  if (tdeg == totaldegree (Fp))
1303  {
1304  if (absIrredTest (Fp))
1305  {
1306  CFFList factors= factorize (Fp);
1307  if (factors.length() == 2 && factors.getLast().exp() == 1)
1308  {
1309  if (isRat)
1310  On (SW_RATIONAL);
1311  setCharacteristic (0);
1312  return true;
1313  }
1314  }
1315  }
1316 
1317  E.nextpoint();
1318 
1319  Fp= Fp (x+E[1], x);
1320  Fp= Fp (y+E[2], y);
1321 
1322  if (tdeg == totaldegree (Fp))
1323  {
1324  if (absIrredTest (Fp))
1325  {
1326  CFFList factors= factorize (Fp);
1327  if (factors.length() == 2 && factors.getLast().exp() == 1)
1328  {
1329  if (isRat)
1330  On (SW_RATIONAL);
1331  setCharacteristic (0);
1332  return true;
1333  }
1334  }
1335  }
1336 
1337  int i= 0;
1338  while (cf_getSmallPrime (i) < 102)
1339  {
1341  i++;
1342  E= REvaluation (1, 2, FFRandom());
1343 
1344  for (int j= 0; j < 3; j++)
1345  {
1346  Fp= F.mapinto();
1347  E.nextpoint();
1348  Fp= Fp (x+E[1], x);
1349  Fp= Fp (y+E[2], y);
1350 
1351  if (tdeg == totaldegree (Fp))
1352  {
1353  if (absIrredTest (Fp))
1354  {
1355  CFFList factors= factorize (Fp);
1356  if (factors.length() == 2 && factors.getLast().exp() == 1)
1357  {
1358  if (isRat)
1359  On (SW_RATIONAL);
1360  setCharacteristic (0);
1361  return true;
1362  }
1363  }
1364  }
1365  }
1366  }
1367 
1368  setCharacteristic (0);
1369  if (isRat)
1370  On (SW_RATIONAL);
1371 
1372  return false;
1373 }
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
void Off(int sw)
switches
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
class to generate random evaluation points
Definition: cf_reval.h:25
void setCharacteristic(int c)
Definition: cf_char.cc:23
int tdeg(poly p)
Definition: walkSupport.cc:38
CanonicalForm mapinto() const
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
int j
Definition: myNF.cc:70
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool isOn(int sw)
switches
void On(int sw)
switches
generate random elements in F_p
Definition: cf_random.h:43
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int length() const
Definition: ftmpl_list.cc:273
REvaluation E(1, terms.length(), IntRandom(25))
void nextpoint()
Definition: cf_reval.cc:46
Variable x
Definition: cfModGcd.cc:4023
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ newtonPolygon() [1/2]

int** newtonPolygon ( const CanonicalForm F,
int &  sizeOfNewtonPoly 
)

compute the Newton polygon of a bivariate polynomial

Returns
an array of points in the plane which are the vertices of the Newton polygon of F
Parameters
[in]Fa bivariate polynomial
[in,out]sizeOfNewtonPolysize of the result

Definition at line 282 of file cfNewtonPolygon.cc.

283 {
284  int sizeF= size (F);
285  int ** points= new int* [sizeF];
286  for (int i= 0; i < sizeF; i++)
287  points [i]= new int [2];
288  int j= 0;
289  int * buf;
290  int bufSize;
291  for (CFIterator i= F; i.hasTerms(); i++)
292  {
293  buf= getDegrees (i.coeff(), bufSize);
294  for (int k= 0; k < bufSize; k++, j++)
295  {
296  points [j] [0]= i.exp();
297  points [j] [1]= buf [k];
298  }
299  delete [] buf;
300  }
301 
302  int n= polygon (points, sizeF);
303 
304  int ** result= new int* [n];
305  for (int i= 0; i < n; i++)
306  {
307  result [i]= new int [2];
308  result [i] [0]= points [i] [0];
309  result [i] [1]= points [i] [1];
310  }
311 
312  sizeOfNewtonPoly= n;
313  for (int i= 0; i < sizeF; i++)
314  delete [] points[i];
315  delete [] points;
316 
317  return result;
318 }
static coordinates * points
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
static int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
int polygon(int **points, int sizePoints)
compute a polygon
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
return result
Definition: facAbsBiFact.cc:76

◆ newtonPolygon() [2/2]

int** newtonPolygon ( const CanonicalForm F,
const CanonicalForm G,
int &  sizeOfNewtonPoly 
)

compute the convex hull of the support of two bivariate polynomials

Returns
an array of points in the plane which are the vertices of the convex hull of the support of F and G
Parameters
[in]Fa bivariate polynomial
[in]Ga bivariate polynomial
[in,out]sizeOfNewtonPolysize of the result

Definition at line 321 of file cfNewtonPolygon.cc.

323 {
324  int sizeF= size (F);
325  int ** pointsF= new int* [sizeF];
326  for (int i= 0; i < sizeF; i++)
327  pointsF [i]= new int [2];
328  int j= 0;
329  int * buf;
330  int bufSize;
331  for (CFIterator i= F; i.hasTerms(); i++)
332  {
333  buf= getDegrees (i.coeff(), bufSize);
334  for (int k= 0; k < bufSize; k++, j++)
335  {
336  pointsF [j] [0]= i.exp();
337  pointsF [j] [1]= buf [k];
338  }
339  delete [] buf;
340  }
341 
342  int sizeG= size (G);
343  int ** pointsG= new int* [sizeG];
344  for (int i= 0; i < sizeG; i++)
345  pointsG [i]= new int [2];
346  j= 0;
347  for (CFIterator i= G; i.hasTerms(); i++)
348  {
349  buf= getDegrees (i.coeff(), bufSize);
350  for (int k= 0; k < bufSize; k++, j++)
351  {
352  pointsG [j] [0]= i.exp();
353  pointsG [j] [1]= buf [k];
354  }
355  delete [] buf;
356  }
357 
358  int sizePoints;
359  int ** points= merge (pointsF, sizeF, pointsG, sizeG, sizePoints);
360 
361  int n= polygon (points, sizePoints);
362 
363  int ** result= new int* [n];
364  for (int i= 0; i < n; i++)
365  {
366  result [i]= new int [2];
367  result [i] [0]= points [i] [0];
368  result [i] [1]= points [i] [1];
369  }
370 
371  sizeOfNewtonPoly= n;
372  for (int i= 0; i < sizeF; i++)
373  delete [] pointsF[i];
374  delete [] pointsF;
375  for (int i= 0; i < sizeG; i++)
376  delete [] pointsG[i];
377  delete [] pointsG;
378 
379  return result;
380 }
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
static coordinates * points
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
static int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
int polygon(int **points, int sizePoints)
compute a polygon
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
return result
Definition: facAbsBiFact.cc:76

◆ polygon()

int polygon ( int **  points,
int  sizePoints 
)

compute a polygon

Returns
an integer n such that the first n entries of points are the vertices of the convex hull of points
Parameters
[in,out]pointsan array of points in the plane
[in]sizePointsnumber of elements in points

Definition at line 172 of file cfNewtonPolygon.cc.

173 {
174  if (sizePoints < 3) return sizePoints;
175  return grahamScan (points, sizePoints);
176 }
static coordinates * points
int grahamScan(int **points, int sizePoints)