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