My Project
Loading...
Searching...
No Matches
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';
1177 if (GF)
1178 {
1179 d= getGFDegree();
1180 bufGFName=gf_name;
1181 }
1182
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:4078
g
Definition: cfModGcd.cc:4090
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:31
#define GaloisFieldDomain
Definition: cf_defs.h:18
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;
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:4082
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: variable.h:33
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:4103
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;
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
#define swap(_i, _j)
static bool isConvex(int *point1, int *point2, int *point3)
static void sort(int **points, int sizePoints)
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@param point a 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);
1253 return true;
1254 }
1255 }
1256 }
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);
1277 return true;
1278 }
1279 }
1280 }
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
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);
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);
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);
1382 return true;
1383 }
1384 }
1385 }
1386 }
1387 }
1388
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}