My Project
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

◆ 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 1163 of file cfNewtonPolygon.cc.

1164 {
1165  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1166  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1167 
1168  int sizeOfNewtonPolygon;
1169  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1170  bool isRat= isOn (SW_RATIONAL);
1171  if (isRat)
1172  Off (SW_RATIONAL);
1173  int p=getCharacteristic();
1174  int d=1;
1175  char bufGFName='Z';
1176  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
1177  if (GF)
1178  {
1179  d= getGFDegree();
1180  bufGFName=gf_name;
1181  }
1182 
1183  setCharacteristic(0);
1184 
1185  CanonicalForm g= gcd (newtonPolyg[0][0], newtonPolyg[0][1]); //maybe it's better to use plain intgcd
1186 
1187  int i= 1;
1188  while (!g.isOne() && i < sizeOfNewtonPolygon)
1189  {
1190  g= gcd (g, newtonPolyg[i][0]);
1191  g= gcd (g, newtonPolyg[i][1]);
1192  i++;
1193  }
1194 
1195  bool result= g.isOne();
1196 
1197  if (GF)
1198  setCharacteristic (p, d, bufGFName);
1199  else
1201 
1202  if (isRat)
1203  On (SW_RATIONAL);
1204 
1205  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1206  delete [] newtonPolyg[i];
1207 
1208  delete [] newtonPolyg;
1209 
1210  return result;
1211 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int getGFDegree()
Definition: cf_char.cc:75
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
#define GaloisFieldDomain
Definition: cf_defs.h:24
static int gettype()
Definition: cf_factory.h:28
factory's main class
Definition: canonicalform.h:86
return result
Definition: facAbsBiFact.cc:75
VAR char gf_name
Definition: gfops.cc:52
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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]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 exps_maxcount=0;
730  int count= 0;
731  for (CFIterator i= F; i.hasTerms(); i++)
732  {
733  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
734  {
735  mpz_set (expX, A[0]);
736  mpz_set (expY, A[1]);
737  mpz_addmul_ui (expX, M[1], i.exp());
738  mpz_addmul_ui (expY, M[3], i.exp());
739 
740  if (k == 0)
741  {
742  mpz_set (minExpX, expX);
743  mpz_set (minExpY, expY);
744  k= 1;
745  }
746  else
747  {
748  if (mpz_cmp (minExpY, expY) > 0)
749  mpz_set (minExpY, expY);
750  if (mpz_cmp (minExpX, expX) > 0)
751  mpz_set (minExpX, expX);
752  }
753  mpz_init_set (exps[count], expX);
754  count++;
755  mpz_init_set (exps[count], expY);
756  exps_maxcount=count;
757  count++;
758  continue;
759  }
760  CFIterator j= i.coeff();
761  if (k == 0)
762  {
763  mpz_set (expX, A[0]);
764  mpz_addmul_ui (expX, M[1], i.exp());
765  mpz_addmul_ui (expX, M[0], j.exp());
766 
767  mpz_set (expY, A[1]);
768  mpz_addmul_ui (expY, M[3], i.exp());
769  mpz_addmul_ui (expY, M[2], j.exp());
770 
771  mpz_set (minExpX, expX);
772  mpz_set (minExpY, expY);
773  mpz_init_set (exps[count], expX);
774  count++;
775  mpz_init_set (exps[count], expY);
776  exps_maxcount=count;
777  count++;
778  j++;
779  k= 1;
780  }
781 
782  for (; j.hasTerms(); j++)
783  {
784  mpz_set (expX, A[0]);
785  mpz_addmul_ui (expX, M[1], i.exp());
786  mpz_addmul_ui (expX, M[0], j.exp());
787 
788  mpz_set (expY, A[1]);
789  mpz_addmul_ui (expY, M[3], i.exp());
790  mpz_addmul_ui (expY, M[2], j.exp());
791 
792  mpz_init_set (exps[count], expX);
793  count++;
794  mpz_init_set (exps[count], expY);
795  exps_maxcount=count;
796  count++;
797  if (mpz_cmp (minExpY, expY) > 0)
798  mpz_set (minExpY, expY);
799  if (mpz_cmp (minExpX, expX) > 0)
800  mpz_set (minExpX, expX);
801  }
802  }
803 
804  count= 0;
805  int mExpX= mpz_get_si (minExpX);
806  int mExpY= mpz_get_si (minExpY);
807  for (CFIterator i= F; i.hasTerms(); i++)
808  {
809  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
810  {
811  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
812  power (y, mpz_get_si (exps[count+1])-mExpY);
813  count += 2;
814  continue;
815  }
816  CFIterator j= i.coeff();
817  for (; j.hasTerms(); j++)
818  {
819  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
820  power (y, mpz_get_si (exps[count+1])-mExpY);
821  count += 2;
822  }
823  }
824 
825  CanonicalForm tmp= LC (result);
826  if (tmp.inPolyDomain() && degree (tmp) <= 0)
827  {
828  int d= degree (result);
829  Variable x= result.mvar();
830  result -= tmp*power (x, d);
831  result += Lc (tmp)*power (x, d);
832  }
833 
834  if (computeMA)
835  {
836  for (int i= 0; i < n; i++)
837  delete [] newtonPolyg [i];
838  delete [] newtonPolyg;
839  mpz_mat_inv (M);
840  }
841 
842  for(int tt=exps_maxcount;tt>=0;tt--) mpz_clear(exps[tt]);
843  delete [] exps;
844  mpz_clear (expX);
845  mpz_clear (expY);
846  mpz_clear (minExpX);
847  mpz_clear (minExpY);
848 
849  return result;
850 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4084
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,...
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
bool inPolyDomain() const
factory's class for variables
Definition: factory.h:134
Variable alpha
Definition: facAbsBiFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
int j
Definition: facHensel.cc:110
#define NULL
Definition: omList.c:12
int status int void size_t count
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25

◆ 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 }
CanonicalForm b
Definition: cfModGcd.cc:4105
void lambda(int **points, int sizePoints)
void lambdaInverse(int **points, int sizePoints)
void getMaxMin(int **points, int sizePoints, int &minDiff, int &minSum, int &maxDiff, int &maxSum, int &maxX, int &maxY)
void tau(int **points, int sizePoints, int k)
void mu(int **points, int sizePoints)
void mpz_mat_mul(const mpz_t *N, mpz_t *&M)
FILE * f
Definition: checklibs.c:9
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
STATIC_VAR coordinates * points
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ 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]inverseMmatrix M obtained from compress
[in]Avector A obtained from compress

Definition at line 853 of file cfNewtonPolygon.cc.

854 {
856  Variable x= Variable (1);
857  Variable y= Variable (2);
858 
859  mpz_t expX, expY, minExpX, minExpY;
860  mpz_init (expX);
861  mpz_init (expY);
862  mpz_init (minExpX);
863  mpz_init (minExpY);
864 
865  mpz_t * exps= new mpz_t [2*size(F)];
866  int max_exps=0;
867  int count= 0;
868  if (F.isUnivariate() && F.level() == 1)
869  {
870  CFIterator i= F;
871 
872  mpz_set_si (expX, i.exp());
873  mpz_sub (expX, expX, A[0]);
874  mpz_mul (expX, expX, inverseM[0]);
875  mpz_submul (expX, inverseM[1], A[1]);
876 
877  mpz_set_si (expY, i.exp());
878  mpz_sub (expY, expY, A[0]);
879  mpz_mul (expY, expY, inverseM[2]);
880  mpz_submul (expY, inverseM[3], A[1]);
881 
882  mpz_set (minExpX, expX);
883  mpz_set (minExpY, expY);
884 
885  mpz_init_set (exps[count], expX);
886  count++;
887  mpz_init_set (exps[count], expY);
888  count++;
889  max_exps=count;
890 
891  i++;
892  for (; i.hasTerms(); i++)
893  {
894  mpz_set_si (expX, i.exp());
895  mpz_sub (expX, expX, A[0]);
896  mpz_mul (expX, expX, inverseM[0]);
897  mpz_submul (expX, inverseM[1], A[1]);
898 
899  mpz_set_si (expY, i.exp());
900  mpz_sub (expY, expY, A[0]);
901  mpz_mul (expY, expY, inverseM[2]);
902  mpz_submul (expY, inverseM[3], A[1]);
903 
904  mpz_init_set (exps[count], expX);
905  count++;
906  mpz_init_set (exps[count], expY);
907  max_exps=count;
908  count++;
909 
910  if (mpz_cmp (minExpY, expY) > 0)
911  mpz_set (minExpY, expY);
912  if (mpz_cmp (minExpX, expX) > 0)
913  mpz_set (minExpX, expX);
914  }
915 
916  int mExpX= mpz_get_si (minExpX);
917  int mExpY= mpz_get_si (minExpY);
918  count= 0;
919  for (i= F; i.hasTerms(); i++)
920  {
921  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
922  power (y, mpz_get_si (exps[count+1])-mExpY);
923  max_exps=count+1;
924  count += 2;
925  }
926 
927  mpz_clear (expX);
928  mpz_clear (expY);
929  mpz_clear (minExpX);
930  mpz_clear (minExpY);
931 
932  for(int tt=max_exps;tt>=0;tt--) mpz_clear(exps[tt]);
933  delete [] exps;
934  return result/ Lc (result); //normalize
935  }
936 
937  mpz_t tmp;
938  mpz_init (tmp);
939  int k= 0;
940  Variable alpha;
941  for (CFIterator i= F; i.hasTerms(); i++)
942  {
943  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
944  {
945  mpz_set_si (expX, i.exp());
946  mpz_sub (expX, expX, A[1]);
947  mpz_mul (expX, expX, inverseM[1]);
948  mpz_submul (expX, A[0], inverseM[0]);
949 
950  mpz_set_si (expY, i.exp());
951  mpz_sub (expY, expY, A[1]);
952  mpz_mul (expY, expY, inverseM[3]);
953  mpz_submul (expY, A[0], inverseM[2]);
954 
955  if (k == 0)
956  {
957  mpz_set (minExpX, expX);
958  mpz_set (minExpY, expY);
959  k= 1;
960  }
961  else
962  {
963  if (mpz_cmp (minExpY, expY) > 0)
964  mpz_set (minExpY, expY);
965  if (mpz_cmp (minExpX, expX) > 0)
966  mpz_set (minExpX, expX);
967  }
968  mpz_init_set (exps[count], expX);
969  count++;
970  mpz_init_set (exps[count], expY);
971  max_exps=count;
972  count++;
973  continue;
974  }
975  CFIterator j= i.coeff();
976  if (k == 0)
977  {
978  mpz_set_si (expX, j.exp());
979  mpz_sub (expX, expX, A[0]);
980  mpz_mul (expX, expX, inverseM[0]);
981  mpz_set_si (tmp, i.exp());
982  mpz_sub (tmp, tmp, A[1]);
983  mpz_addmul (expX, tmp, inverseM[1]);
984 
985  mpz_set_si (expY, j.exp());
986  mpz_sub (expY, expY, A[0]);
987  mpz_mul (expY, expY, inverseM[2]);
988  mpz_set_si (tmp, i.exp());
989  mpz_sub (tmp, tmp, A[1]);
990  mpz_addmul (expY, tmp, inverseM[3]);
991 
992  mpz_set (minExpX, expX);
993  mpz_set (minExpY, expY);
994 
995  mpz_init_set (exps[count], expX);
996  count++;
997  mpz_init_set (exps[count], expY);
998  max_exps=count;
999  count++;
1000 
1001  j++;
1002  k= 1;
1003  }
1004 
1005  for (; j.hasTerms(); j++)
1006  {
1007  mpz_set_si (expX, j.exp());
1008  mpz_sub (expX, expX, A[0]);
1009  mpz_mul (expX, expX, inverseM[0]);
1010  mpz_set_si (tmp, i.exp());
1011  mpz_sub (tmp, tmp, A[1]);
1012  mpz_addmul (expX, tmp, inverseM[1]);
1013 
1014  mpz_set_si (expY, j.exp());
1015  mpz_sub (expY, expY, A[0]);
1016  mpz_mul (expY, expY, inverseM[2]);
1017  mpz_set_si (tmp, i.exp());
1018  mpz_sub (tmp, tmp, A[1]);
1019  mpz_addmul (expY, tmp, inverseM[3]);
1020 
1021  mpz_init_set (exps[count], expX);
1022  count++;
1023  mpz_init_set (exps[count], expY);
1024  max_exps=count;
1025  count++;
1026 
1027  if (mpz_cmp (minExpY, expY) > 0)
1028  mpz_set (minExpY, expY);
1029  if (mpz_cmp (minExpX, expX) > 0)
1030  mpz_set (minExpX, expX);
1031  }
1032  }
1033 
1034  int mExpX= mpz_get_si (minExpX);
1035  int mExpY= mpz_get_si (minExpY);
1036  count= 0;
1037  for (CFIterator i= F; i.hasTerms(); i++)
1038  {
1039  if (i.coeff().inCoeffDomain() && hasFirstAlgVar (i.coeff(), alpha))
1040  {
1041  result += i.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1042  power (y, mpz_get_si (exps[count+1])-mExpY);
1043  max_exps=count+1;
1044  count += 2;
1045  continue;
1046  }
1047  for (CFIterator j= i.coeff(); j.hasTerms(); j++)
1048  {
1049  result += j.coeff()*power (x, mpz_get_si (exps[count])-mExpX)*
1050  power (y, mpz_get_si (exps[count+1])-mExpY);
1051  max_exps=count+1;
1052  count += 2;
1053  }
1054  }
1055 
1056  mpz_clear (expX);
1057  mpz_clear (expY);
1058  mpz_clear (minExpX);
1059  mpz_clear (minExpY);
1060  mpz_clear (tmp);
1061 
1062  for(int tt=max_exps;tt>=0;tt--) mpz_clear(exps[tt]);
1063  delete [] exps;
1064 
1065  return result/Lc (result); //normalize
1066 }
int level() const
level() returns the level of CO.
bool isUnivariate() const

◆ getDegrees()

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

◆ getMaxMin()

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 }
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45

◆ getPoints()

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 int * getDegrees(const CanonicalForm &F, int &sizeOfOutput)
int status int void * buf
Definition: si_signals.h:59

◆ 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 1071 of file cfNewtonPolygon.cc.

1072 {
1073  int maxY= polygon [0][0];
1074  int indexY= 0;
1075  for (int i= 1; i < sizeOfPolygon; i++)
1076  {
1077  if (maxY < polygon [i][0])
1078  {
1079  maxY= polygon [i][0];
1080  indexY= i;
1081  }
1082  else if (maxY == polygon [i][0])
1083  {
1084  if (polygon [indexY][1] < polygon[i][1])
1085  indexY= i;
1086  }
1087  if (maxY > polygon [i][0])
1088  break;
1089  }
1090 
1091  int count= -1;
1092  for (int i= indexY; i < sizeOfPolygon; i++)
1093  {
1094  if (polygon[i][0] == 0)
1095  {
1096  count= i - indexY;
1097  break;
1098  }
1099  }
1100 
1101  int * result;
1102  int index= 0;
1103  if (count < 0)
1104  {
1105  result= new int [sizeOfPolygon - indexY];
1106  sizeOfOutput= sizeOfPolygon - indexY;
1107  count= sizeOfPolygon - indexY - 1;
1108  result [0]= polygon[sizeOfPolygon - 1][0] - polygon [0] [0];
1109  index= 1;
1110  }
1111  else
1112  {
1113  sizeOfOutput= count;
1114  result= new int [count];
1115  }
1116 
1117  for (int i= indexY + count; i > indexY; i--, index++)
1118  result [index]= polygon [i - 1] [0] - polygon [i] [0];
1119 
1120  return result;
1121 }
int polygon(int **points, int sizePoints)
compute a polygon
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592

◆ grahamScan()

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 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
static bool isConvex(int *point1, int *point2, int *point3)
static void sort(int **points, int sizePoints)
static void swap(int **points, int i, int j)
static void translate(int **points, int *point, int sizePoints)
static int smallestPointIndex(int **points, int sizePoints)

◆ 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 1123 of file cfNewtonPolygon.cc.

1124 {
1125  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1126  ASSERT (getCharacteristic() == 0, "expected polynomial over integers or rationals");
1127 
1128  int sizeOfNewtonPolygon;
1129  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
1130  if (sizeOfNewtonPolygon == 3)
1131  {
1132  bool check1=
1133  (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
1134  if (check1)
1135  {
1136  bool check2=
1137  (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
1138  if (check2)
1139  {
1140  bool isRat= isOn (SW_RATIONAL);
1141  if (isRat)
1142  Off (SW_RATIONAL);
1143  CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
1144  tmp= gcd (tmp, newtonPolyg[1][0]);
1145  tmp= gcd (tmp, newtonPolyg[1][1]);
1146  tmp= gcd (tmp, newtonPolyg[2][0]);
1147  tmp= gcd (tmp, newtonPolyg[2][1]);
1148  if (isRat)
1149  On (SW_RATIONAL);
1150  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1151  delete [] newtonPolyg [i];
1152  delete [] newtonPolyg;
1153  return (tmp==1);
1154  }
1155  }
1156  }
1157  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1158  delete [] newtonPolyg [i];
1159  delete [] newtonPolyg;
1160  return false;
1161 }

◆ isConvex() [1/2]

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 }

◆ isConvex() [2/2]

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 }

◆ 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 }

◆ isLess()

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 }

◆ lambda()

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 }

◆ lambdaInverse()

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 }

◆ merge()

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 }

◆ 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 1213 of file cfNewtonPolygon.cc.

1214 {
1215  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1216  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1217 
1218  bool isRat= isOn (SW_RATIONAL);
1219  if (isRat)
1220  Off (SW_RATIONAL);
1221 
1222  if (isRat)
1223  {
1224  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1225  }
1226 
1227  CanonicalForm Fp, N= maxNorm (F);
1228  int tdeg= totaldegree (F);
1229 
1230  int i= 0;
1231  //TODO: maybe it's better to choose the characteristic as large as possible
1232  // as factorization over large finite field will be faster
1233  //TODO: handle those cases where our factory primes are not enough
1234  //TODO: factorize coefficients corresponding to the vertices of the Newton
1235  // polygon and only try the obtained factors
1237  {
1238  while (i < cf_getNumSmallPrimes() && N > cf_getSmallPrime(i))
1239  {
1241  Fp= F.mapinto();
1242  i++;
1243  if (totaldegree (Fp) == tdeg)
1244  {
1245  if (absIrredTest (Fp))
1246  {
1247  CFFList factors= factorize (Fp);
1248  if (factors.length() == 2 && factors.getLast().exp() == 1)
1249  {
1250  if (isRat)
1251  On (SW_RATIONAL);
1252  setCharacteristic (0);
1253  return true;
1254  }
1255  }
1256  }
1257  setCharacteristic (0);
1258  }
1259  }
1260  else
1261  {
1262  while (i < cf_getNumPrimes() && N > cf_getPrime (i))
1263  {
1265  Fp= F.mapinto();
1266  i++;
1267  if (totaldegree (Fp) == tdeg)
1268  {
1269  if (absIrredTest (Fp))
1270  {
1271  CFFList factors= factorize (Fp);
1272  if (factors.length() == 2 && factors.getLast().exp() == 1)
1273  {
1274  if (isRat)
1275  On (SW_RATIONAL);
1276  setCharacteristic (0);
1277  return true;
1278  }
1279  }
1280  }
1281  setCharacteristic (0);
1282  }
1283  }
1284 
1285  if (isRat)
1286  On (SW_RATIONAL);
1287 
1288  return false;
1289 }
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
int cf_getPrime(int i)
Definition: cf_primes.cc:14
int cf_getNumPrimes()
Definition: cf_primes.cc:23
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
CanonicalForm mapinto() const
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
int tdeg(poly p)
Definition: walkSupport.cc:35

◆ 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 1292 of file cfNewtonPolygon.cc.

1293 {
1294  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
1295  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
1296 
1297  bool isRat= isOn (SW_RATIONAL);
1298  if (isRat)
1299  Off (SW_RATIONAL);
1300 
1301  if (isRat)
1302  {
1303  ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
1304  }
1305 
1306  Variable x= Variable (1);
1307  Variable y= Variable (2);
1308  CanonicalForm Fp;
1309  int tdeg= totaldegree (F);
1310 
1311  REvaluation E;
1312 
1313  setCharacteristic (2);
1314  Fp= F.mapinto();
1315 
1316  E= REvaluation (1,2, FFRandom());
1317 
1318  E.nextpoint();
1319 
1320  Fp= Fp (x+E[1], x);
1321  Fp= Fp (y+E[2], y);
1322 
1323  if (tdeg == totaldegree (Fp))
1324  {
1325  if (absIrredTest (Fp))
1326  {
1327  CFFList factors= factorize (Fp);
1328  if (factors.length() == 2 && factors.getLast().exp() == 1)
1329  {
1330  if (isRat)
1331  On (SW_RATIONAL);
1332  setCharacteristic (0);
1333  return true;
1334  }
1335  }
1336  }
1337 
1338  E.nextpoint();
1339 
1340  Fp= Fp (x+E[1], x);
1341  Fp= Fp (y+E[2], y);
1342 
1343  if (tdeg == totaldegree (Fp))
1344  {
1345  if (absIrredTest (Fp))
1346  {
1347  CFFList factors= factorize (Fp);
1348  if (factors.length() == 2 && factors.getLast().exp() == 1)
1349  {
1350  if (isRat)
1351  On (SW_RATIONAL);
1352  setCharacteristic (0);
1353  return true;
1354  }
1355  }
1356  }
1357 
1358  int i= 0;
1359  while (cf_getSmallPrime (i) < 102)
1360  {
1362  i++;
1363  E= REvaluation (1, 2, FFRandom());
1364 
1365  for (int j= 0; j < 3; j++)
1366  {
1367  Fp= F.mapinto();
1368  E.nextpoint();
1369  Fp= Fp (x+E[1], x);
1370  Fp= Fp (y+E[2], y);
1371 
1372  if (tdeg == totaldegree (Fp))
1373  {
1374  if (absIrredTest (Fp))
1375  {
1376  CFFList factors= factorize (Fp);
1377  if (factors.length() == 2 && factors.getLast().exp() == 1)
1378  {
1379  if (isRat)
1380  On (SW_RATIONAL);
1381  setCharacteristic (0);
1382  return true;
1383  }
1384  }
1385  }
1386  }
1387  }
1388 
1389  setCharacteristic (0);
1390  if (isRat)
1391  On (SW_RATIONAL);
1392 
1393  return false;
1394 }
generate random elements in F_p
Definition: cf_random.h:44
class to generate random evaluation points
Definition: cf_reval.h:26
void nextpoint()
Definition: cf_reval.cc:46
REvaluation E(1, terms.length(), IntRandom(25))

◆ mpz_mat_inv()

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 }

◆ mpz_mat_mul()

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 }

◆ mu()

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 }

◆ newtonPolygon() [1/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_VAR TreeM * G
Definition: janet.cc:31

◆ newtonPolygon() [2/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 }

◆ 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 }
int grahamScan(int **points, int sizePoints)

◆ quickSort()

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 quickSort(int lo, int hi, int **points)
static bool isLess(int *point1, int *point2)

◆ smallestPointIndex()

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

◆ sort()

static void sort ( int **  points,
int  sizePoints 
)
static

Definition at line 100 of file cfNewtonPolygon.cc.

101 {
102  quickSort (1, sizePoints - 1, points);
103 }

◆ swap()

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 }

◆ tau()

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 }

◆ translate()

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 }