Functions
cfNewtonPolygon.cc File Reference

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

#include "config.h"
#include "cf_assert.h"
#include <stdlib.h>
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_algorithm.h"
#include "cf_primes.h"
#include "cf_reval.h"
#include "cf_factory.h"
#include "gfops.h"
#include "cfNewtonPolygon.h"
#include "templates/ftmpl_functions.h"

Go to the source code of this file.

Functions

static void translate (int **points, int *point, int sizePoints)
 
static int smallestPointIndex (int **points, int sizePoints)
 
static void swap (int **points, int i, int j)
 
static bool isLess (int *point1, int *point2)
 
static void quickSort (int lo, int hi, int **points)
 
static void sort (int **points, int sizePoints)
 
static bool isConvex (int *point1, int *point2, int *point3)
 
static bool isConvex (int **points, int i)
 
int grahamScan (int **points, int sizePoints)
 
int polygon (int **points, int sizePoints)
 compute a polygon More...
 
static int * getDegrees (const CanonicalForm &F, int &sizeOfOutput)
 
int ** getPoints (const CanonicalForm &F, int &n)
 
int ** merge (int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
 
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...
 
void lambda (int **points, int sizePoints)
 
void lambdaInverse (int **points, int sizePoints)
 
void tau (int **points, int sizePoints, int k)
 
void mu (int **points, int sizePoints)
 
void getMaxMin (int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
 
void mpz_mat_mul (const mpz_t *N, mpz_t *&M)
 
void mpz_mat_inv (mpz_t *&M)
 
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 *&M, mpz_t *&A, bool computeMA)
 compress a bivariate poly More...
 
CanonicalForm decompress (const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
 decompress a bivariate poly 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...
 

Detailed Description

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

Author
Martin Lee

Definition in file cfNewtonPolygon.cc.

Function Documentation

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 }
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
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
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:27
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
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]Mreturns 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
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
factory&#39;s class for variables
Definition: variable.h:32
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)
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
#define M
Definition: sirandom.c:24
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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
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
bool inPolyDomain() const
#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 exp() const
get the current exponent
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
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)
f
Definition: cfModGcd.cc:4022
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)
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
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]inverseMmatrix 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
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: variable.h:32
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 level() const
level() returns the level of CO.
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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
bool isUnivariate() const
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 exp() const
get the current exponent
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76
static int* getDegrees ( const CanonicalForm F,
int &  sizeOfOutput 
)
static

Definition at line 179 of file cfNewtonPolygon.cc.

180 {
181  if (F.inCoeffDomain())
182  {
183  int* result= new int [1];
184  result [0]= 0;
185  sizeOfOutput= 1;
186  return result;
187  }
188  sizeOfOutput= size (F);
189  int* result= new int [sizeOfOutput];
190  int j= 0;
191  for (CFIterator i= F; i.hasTerms(); i++, j++)
192  result [j]= i.exp();
193  return result;
194 }
bool inCoeffDomain() const
int j
Definition: myNF.cc:70
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
void getMaxMin ( int **  points,
int  sizePoints,
int &  minDiff,
int &  minSum,
int &  maxDiff,
int &  maxSum,
int &  maxX,
int &  maxY 
)

Definition at line 478 of file cfNewtonPolygon.cc.

481 {
482  minDiff= points [0] [1] - points [0] [0];
483  minSum= points [0] [1] + points [0] [0];
484  maxDiff= points [0] [1] - points [0] [0];
485  maxSum= points [0] [1] + points [0] [0];
486  maxX= points [0] [1];
487  maxY= points [0] [0];
488  int diff, sum;
489  for (int i= 1; i < sizePoints; i++)
490  {
491  diff= points [i] [1] - points [i] [0];
492  sum= points [i] [1] + points [i] [0];
493  minDiff= tmin (minDiff, diff);
494  minSum= tmin (minSum, sum);
495  maxDiff= tmax (maxDiff, diff);
496  maxSum= tmax (maxSum, sum);
497  maxX= tmax (maxX, points [i] [1]);
498  maxY= tmax (maxY, points [i] [0]);
499  }
500 }
static gmp_float * diff
Definition: mpr_complex.cc:47
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
static coordinates * points
int i
Definition: cfEzgcd.cc:123
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
int** getPoints ( const CanonicalForm F,
int &  n 
)

Definition at line 197 of file cfNewtonPolygon.cc.

198 {
199  n= size (F);
200  int ** points= new int* [n];
201  for (int i= 0; i < n; i++)
202  points [i]= new int [2];
203 
204  int j= 0;
205  int * buf;
206  int bufSize;
207  if (F.isUnivariate() && F.level() == 1)
208  {
209  for (CFIterator i= F; i.hasTerms(); i++, j++)
210  {
211  points [j] [0]= i.exp();
212  points [j] [1]= 0;
213  }
214  return points;
215  }
216  for (CFIterator i= F; i.hasTerms(); i++)
217  {
218  buf= getDegrees (i.coeff(), bufSize);
219  for (int k= 0; k < bufSize; k++, j++)
220  {
221  points [j] [0]= i.exp();
222  points [j] [1]= buf [k];
223  }
224  delete [] buf;
225  }
226  return points;
227 }
static coordinates * points
int k
Definition: cfEzgcd.cc:93
int level() const
level() returns the level of CO.
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 i
Definition: cfEzgcd.cc:123
bool isUnivariate() const
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
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:597
return result
Definition: facAbsBiFact.cc:76
int grahamScan ( int **  points,
int  sizePoints 
)

Definition at line 128 of file cfNewtonPolygon.cc.

129 {
130  swap (points, 0, smallestPointIndex (points, sizePoints));
131  int * minusPoint= new int [2];
132  minusPoint [0]= points[0] [0];
133  minusPoint [1]= points[0] [1];
134  translate (points, minusPoint, sizePoints);
135  sort (points, sizePoints);
136  minusPoint[0]= - minusPoint[0];
137  minusPoint[1]= - minusPoint[1];
138  translate (points, minusPoint, sizePoints); //reverse translation
139  delete [] minusPoint;
140  int i= 3, k= 3;
141  while (k < sizePoints)
142  {
143  swap (points, i, k);
144  while (!isConvex (points, i - 1))
145  {
146  swap (points, i - 1, i);
147  i--;
148  }
149  k++;
150  i++;
151  }
152  if (i + 1 <= sizePoints || i == sizePoints)
153  {
154  long relArea=
155  (points [i-2][0] - points [i-1][0])*(points [0][1] - points [i-1][1])-
156  (points [i-2][1] - points [i-1][1])*(points [0][0] - points [i-1][0]);
157  if (relArea == 0)
158  {
159  if (abs (points [i-2][0] - points [0][0]) +
160  abs (points [i-2][1] - points [0][1]) >=
161  abs (points [i-1][0] - points [i-2][0]) +
162  abs (points [i-1][1] - points [i-2][1]) +
163  abs (points [i-1][0] - points [0][0]) +
164  abs (points [i-1][1] - points [0][1]))
165  i--;
166  }
167  }
168  return i;
169 }
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
int k
Definition: cfEzgcd.cc:93
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
static void sort(int **points, int sizePoints)
int i
Definition: cfEzgcd.cc:123
static int smallestPointIndex(int **points, int sizePoints)
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
static bool isConvex ( int *  point1,
int *  point2,
int *  point3 
)
static

Definition at line 107 of file cfNewtonPolygon.cc.

108 {
109  long relArea= (point1[0] - point2[0])*(point3[1] - point2[1]) -
110  (point1[1] - point2[1])*(point3[0] - point2[0]);
111  if (relArea < 0)
112  return true;
113  if (relArea == 0)
114  {
115  return !(abs (point1[0] - point3[0]) + abs (point1[1] - point3[1]) >=
116  (abs (point2[0] - point1[0]) + abs (point2[1] - point1[1]) +
117  abs (point2[0] - point3[0]) + abs (point2[1] - point3[1])));
118  }
119  return false;
120 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
static bool isConvex ( int **  points,
int  i 
)
static

Definition at line 123 of file cfNewtonPolygon.cc.

124 {
125  return isConvex (points[i - 1], points [i], points [i + 1]);
126 }
static bool isConvex(int *point1, int *point2, int *point3)
static coordinates * points
int i
Definition: cfEzgcd.cc:123
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
static bool isLess ( int *  point1,
int *  point2 
)
static

Definition at line 64 of file cfNewtonPolygon.cc.

65 {
66  long area= point1[0]*point2[1]- point1[1]*point2[0];
67  if (area > 0) return true;
68  if (area == 0)
69  {
70  return (abs (point1[0]) + abs (point1[1]) >
71  abs (point2[0]) + abs (point2[1]));
72  }
73  return false;
74 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
void lambda ( int **  points,
int  sizePoints 
)

Definition at line 449 of file cfNewtonPolygon.cc.

450 {
451  for (int i= 0; i < sizePoints; i++)
452  points [i] [1]= points [i] [1] - points [i] [0];
453 }
static coordinates * points
int i
Definition: cfEzgcd.cc:123
void lambdaInverse ( int **  points,
int  sizePoints 
)

Definition at line 455 of file cfNewtonPolygon.cc.

456 {
457  for (int i= 0; i < sizePoints; i++)
458  points [i] [1]= points [i] [1] + points [i] [0];
459 }
static coordinates * points
int i
Definition: cfEzgcd.cc:123
int** merge ( int **  points1,
int  sizePoints1,
int **  points2,
int  sizePoints2,
int &  sizeResult 
)

Definition at line 230 of file cfNewtonPolygon.cc.

232 {
233  int i, j;
234  sizeResult= sizePoints1+sizePoints2;
235  for (i= 0; i < sizePoints1; i++)
236  {
237  for (j= 0; j < sizePoints2; j++)
238  {
239  if (points1[i][0] != points2[j][0])
240  continue;
241  else
242  {
243  if (points1[i][1] != points2[j][1])
244  continue;
245  else
246  {
247  points2[j][0]= -1;
248  points2[j][1]= -1;
249  sizeResult--;
250  }
251  }
252  }
253  }
254  if (sizeResult == 0)
255  return points1;
256 
257  int ** result= new int *[sizeResult];
258  for (i= 0; i < sizeResult; i++)
259  result [i]= new int [2];
260 
261  int k= 0;
262  for (i= 0; i < sizePoints1; i++, k++)
263  {
264  result[k][0]= points1[i][0];
265  result[k][1]= points1[i][1];
266  }
267  for (i= 0; i < sizePoints2; i++)
268  {
269  if (points2[i][0] < 0)
270  continue;
271  else
272  {
273  result[k][0]= points2[i][0];
274  result[k][1]= points2[i][1];
275  k++;
276  }
277  }
278  return result;
279 }
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76
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
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
CanonicalForm mapinto() const
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
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
T getLast() const
Definition: ftmpl_list.cc:309
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
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: variable.h:32
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
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
CanonicalForm mapinto() const
generate random elements in F_p
Definition: cf_random.h:43
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
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
REvaluation E(1, terms.length(), IntRandom(25))
T getLast() const
Definition: ftmpl_list.cc:309
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
void mpz_mat_inv ( mpz_t *&  M)

Definition at line 535 of file cfNewtonPolygon.cc.

536 {
537  mpz_t det;
538  mpz_init_set (det, M[0]);
539  mpz_mul (det, det, M[3]);
540  mpz_submul (det, M[1], M[2]);
541 
542  mpz_t tmp;
543  mpz_init_set (tmp, M[0]);
544  mpz_divexact (tmp, tmp, det);
545  mpz_set (M[0], M[3]);
546  mpz_divexact (M[0], M[0], det);
547  mpz_set (M[3], tmp);
548 
549  mpz_neg (M[1], M[1]);
550  mpz_divexact (M[1], M[1], det);
551  mpz_neg (M[2], M[2]);
552  mpz_divexact (M[2], M[2], det);
553 
554  mpz_clear (det);
555  mpz_clear (tmp);
556 }
#define M
Definition: sirandom.c:24
void mpz_mat_mul ( const mpz_t *  N,
mpz_t *&  M 
)

Definition at line 502 of file cfNewtonPolygon.cc.

503 {
504  mpz_t * tmp= new mpz_t[4];
505 
506  mpz_init_set (tmp[0], N[0]);
507  mpz_mul (tmp[0], tmp[0], M[0]);
508  mpz_addmul (tmp[0], N[1], M[2]);
509 
510  mpz_init_set (tmp[1], N[0]);
511  mpz_mul (tmp[1], tmp[1], M[1]);
512  mpz_addmul (tmp[1], N[1], M[3]);
513 
514  mpz_init_set (tmp[2], N[2]);
515  mpz_mul (tmp[2], tmp[2], M[0]);
516  mpz_addmul (tmp[2], N[3], M[2]);
517 
518  mpz_init_set (tmp[3], N[2]);
519  mpz_mul (tmp[3], tmp[3], M[1]);
520  mpz_addmul (tmp[3], N[3], M[3]);
521 
522  mpz_set (M[0], tmp[0]);
523  mpz_set (M[1], tmp[1]);
524  mpz_set (M[2], tmp[2]);
525  mpz_set (M[3], tmp[3]);
526 
527  mpz_clear (tmp[0]);
528  mpz_clear (tmp[1]);
529  mpz_clear (tmp[2]);
530  mpz_clear (tmp[3]);
531 
532  delete [] tmp;
533 }
#define M
Definition: sirandom.c:24
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
void mu ( int **  points,
int  sizePoints 
)

Definition at line 467 of file cfNewtonPolygon.cc.

468 {
469  int tmp;
470  for (int i= 0; i < sizePoints; i++)
471  {
472  tmp= points [i] [0];
473  points [i] [0]= points [i] [1];
474  points [i] [1]= tmp;
475  }
476 }
static coordinates * points
int i
Definition: cfEzgcd.cc:123
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
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
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)
static void quickSort ( int  lo,
int  hi,
int **  points 
)
static

Definition at line 77 of file cfNewtonPolygon.cc.

78 {
79  int i= lo, j= hi;
80  int* point= new int [2];
81  point [0]= points [(lo+hi)/2] [0];
82  point [1]= points [(lo+hi)/2] [1];
83  while (i <= j)
84  {
85  while (isLess (points [i], point) && i < hi) i++;
86  while (isLess (point, points[j]) && j > lo) j--;
87  if (i <= j)
88  {
89  swap (points, i, j);
90  i++;
91  j--;
92  }
93  }
94  delete [] point;
95  if (lo < j) quickSort (lo, j, points);
96  if (i < hi) quickSort (i, hi, points);
97 }
static void swap(int **points, int i, int j)
static bool isLess(int *point1, int *point2)
static coordinates * points
static void quickSort(int lo, int hi, int **points)
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
static int smallestPointIndex ( int **  points,
int  sizePoints 
)
static

Definition at line 43 of file cfNewtonPolygon.cc.

44 {
45  int min= 0;
46  for (int i= 1; i < sizePoints; i++)
47  {
48  if (points[i][0] < points[min][0] ||
49  (points[i] [0] == points[min] [0] && points[i] [1] < points[min] [1]))
50  min= i;
51  }
52  return min;
53 }
static int min(int a, int b)
Definition: fast_mult.cc:268
static coordinates * points
int i
Definition: cfEzgcd.cc:123
static void sort ( int **  points,
int  sizePoints 
)
static

Definition at line 100 of file cfNewtonPolygon.cc.

101 {
102  quickSort (1, sizePoints - 1, points);
103 }
static coordinates * points
static void quickSort(int lo, int hi, int **points)
static void swap ( int **  points,
int  i,
int  j 
)
static

Definition at line 56 of file cfNewtonPolygon.cc.

57 {
58  int* tmp= points[i];
59  points[i]= points[j];
60  points[j]= tmp;
61 }
static coordinates * points
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
void tau ( int **  points,
int  sizePoints,
int  k 
)

Definition at line 461 of file cfNewtonPolygon.cc.

462 {
463  for (int i= 0; i < sizePoints; i++)
464  points [i] [1]= points [i] [1] + k;
465 }
static coordinates * points
int k
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:123
static void translate ( int **  points,
int *  point,
int  sizePoints 
)
static

Definition at line 33 of file cfNewtonPolygon.cc.

34 {
35  for (int i= 0; i < sizePoints; i++)
36  {
37  points[i] [0] -= point [0];
38  points[i] [1] -= point [1];
39  }
40 }
static coordinates * points
int i
Definition: cfEzgcd.cc:123