cfNewtonPolygon.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file cfNewtonPolygon.h
5  *
6  * This file provides functions to compute the Newton polygon of a bivariate
7  * polynomial
8  *
9  * @author Martin Lee
10  *
11  **/
12 /*****************************************************************************/
13 
14 #ifndef CF_NEWTON_POLYGON_H
15 #define CF_NEWTON_POLYGON_H
16 
17 // #include "config.h"
18 
19 /// compute a polygon
20 ///
21 /// @return an integer n such that the first n entries of @a points are the
22 /// vertices of the convex hull of @a points
23 int polygon (int** points, ///< [in,out] an array of points in the plane
24  int sizePoints///< [in] number of elements in @a points
25  );
26 
27 /// compute the Newton polygon of a bivariate polynomial
28 ///
29 /// @return an array of points in the plane which are the vertices of the Newton
30 /// polygon of F
31 int ** newtonPolygon (const CanonicalForm& F,///< [in] a bivariate polynomial
32  int& sizeOfNewtonPoly ///< [in, out] size of the result
33  );
34 
35 /// compute the convex hull of the support of two bivariate polynomials
36 ///
37 /// @return an array of points in the plane which are the vertices of the convex
38 /// hull of the support of F and G
39 int ** newtonPolygon (const CanonicalForm& F,///< [in] a bivariate polynomial
40  const CanonicalForm& G,///< [in] a bivariate polynomial
41  int& sizeOfNewtonPoly ///< [in, out] size of the result
42  );
43 
44 /// check if @a point is inside a polygon described by points
45 ///
46 /// @return true if @a point is inside a polygon described by points
47 bool isInPolygon (int ** points, ///< [in] an array of points in the
48  ///< plane describing a polygon
49  int sizePoints,///< [in] size of @a points
50  int* point ///< [in] a point in the plane
51  );
52 
53 /// get the y-direction slopes of all edges with positive slope in y-direction
54 /// of a convex polygon with at least one point of the polygon lying on the
55 /// x-axis and one lying on the y-axis
56 ///
57 /// @return an array containing the slopes as described above
58 int* getRightSide (int** polygon, ///<[in] vertices of a polygon
59  int sizeOfPolygon, ///<[in] number of vertices
60  int& sizeOfOutput ///<[in,out] size of the output
61  );
62 
63 /// computes the Newton polygon of F and checks if it satisfies the
64 /// irreducibility criterion from S.Gao "Absolute irreducibility of polynomials
65 /// via polytopes", Example 1
66 ///
67 /// @return true if it satisfies the above criterion, false otherwise
68 bool
69 irreducibilityTest (const CanonicalForm& F ///<[in] a bivariate polynomial
70  );
71 
72 /// absolute irreducibility test as described in "Modular Las Vegas Algorithms
73 /// for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo
74 ///
75 /// @return true if F satisfies condition (C) from the above paper and thus
76 /// is absolutely irreducible, false otherwise
77 bool
78 absIrredTest (const CanonicalForm& F ///< [in] a bivariate polynomial
79  ///< irreducible over ground field
80  );
81 
82 /// modular absolute irreducibility test as described in "Modular Las Vegas
83 /// Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze,
84 /// A. Galligo
85 ///
86 /// @return true if F is absolutely irreducible, false otherwise
87 bool
88 modularIrredTest (const CanonicalForm& F ///< [in] a bivariate polynomial
89  ///< irreducible over Z
90  );
91 
92 /// modular absolute irreducibility test with shift as described in "Modular Las
93 /// Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone,
94 /// G. Cheze, A. Galligo
95 ///
96 /// @return true if F is absolutely irreducible, false otherwise
97 bool
98 modularIrredTestWithShift (const CanonicalForm& F ///< [in] a bivariate polynomial
99  ///< irreducible over Z
100  );
101 
102 /// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization
103 /// by Berthomieu, Lecerf
104 void convexDense (int** points, ///< [in, out] a set of points in Z^2, returns
105  ///< M (points)+A
106  int sizePoints,///< [in] size of points
107  mpz_t*& M, ///< [in,out] returns an invertible 2x2 matrix
108  mpz_t*& A ///< [in,out] returns translation
109  );
110 
111 /// compress a bivariate poly
112 ///
113 /// @return @a compress returns a compressed bivariate poly
114 /// @sa convexDense, decompress
116 compress (const CanonicalForm& F, ///< [in] compressed, i.e. F.level()==2,
117  ///< bivariate poly
118  mpz_t*& inverseM, ///< [in,out] returns the inverse of M,
119  ///< if computeMA==true, M otherwise
120  mpz_t*& A, ///< [in,out] returns translation
121  bool computeMA= true ///< [in] whether to compute M and A
122  );
123 
124 /// decompress a bivariate poly
125 ///
126 /// @return @a decompress returns a decompressed bivariate poly
127 /// @sa convexDense, decompress
129 decompress (const CanonicalForm& F,///< [in] compressed, i.e. F.level()<= 2,
130  ///< uni- or bivariate poly
131  const mpz_t* M, ///< [in] matrix M obtained from compress
132  const mpz_t* A ///< [in] vector A obtained from compress
133  );
134 
135 #endif
136 
STATIC_VAR coordinates * points
CanonicalForm compress(const CanonicalForm &F, mpz_t *&inverseM, mpz_t *&A, bool computeMA=true)
compress a bivariate poly
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 a...
factory&#39;s main class
Definition: canonicalform.h:77
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool modularIrredTest(const CanonicalForm &F)
modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Abs...
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S...
#define M
Definition: sirandom.c:25
#define A
Definition: sirandom.c:24
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *M, const mpz_t *A)
decompress a bivariate poly
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
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.
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
STATIC_VAR TreeM * G
Definition: janet.cc:31
int polygon(int **points, int sizePoints)
compute a polygon