[a2dd9b2] | 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 | * @internal |
---|
| 12 | * @version \$Id$ |
---|
| 13 | * |
---|
| 14 | **/ |
---|
| 15 | /*****************************************************************************/ |
---|
| 16 | |
---|
| 17 | #ifndef CF_NEWTON_POLYGON_H |
---|
| 18 | #define CF_NEWTON_POLYGON_H |
---|
| 19 | |
---|
[e4fe2b] | 20 | // #include "config.h" |
---|
[a2dd9b2] | 21 | |
---|
| 22 | #ifdef HAVE_NTL |
---|
| 23 | #include "NTLconvert.h" |
---|
| 24 | #endif |
---|
| 25 | |
---|
| 26 | /// compute a polygon |
---|
| 27 | /// |
---|
| 28 | /// @return an integer n such that the first n entries of @a points are the |
---|
| 29 | /// vertices of the convex hull of @a points |
---|
| 30 | int polygon (int** points, ///< [in,out] an array of points in the plane |
---|
| 31 | int sizePoints///< [in] number of elements in @a points |
---|
| 32 | ); |
---|
| 33 | |
---|
| 34 | /// compute the Newton polygon of a bivariate polynomial |
---|
| 35 | /// |
---|
| 36 | /// @return an array of points in the plane which are the vertices of the Newton |
---|
| 37 | /// polygon of F |
---|
| 38 | int ** newtonPolygon (const CanonicalForm& F,///< [in] a bivariate polynomial |
---|
| 39 | int& sizeOfNewtonPoly ///< [in, out] size of the result |
---|
| 40 | ); |
---|
| 41 | |
---|
[16a0df] | 42 | /// compute the convex hull of the support of two bivariate polynomials |
---|
| 43 | /// |
---|
| 44 | /// @return an array of points in the plane which are the vertices of the convex |
---|
| 45 | /// hull of the support of F and G |
---|
| 46 | int ** newtonPolygon (const CanonicalForm& F,///< [in] a bivariate polynomial |
---|
| 47 | const CanonicalForm& G,///< [in] a bivariate polynomial |
---|
| 48 | int& sizeOfNewtonPoly ///< [in, out] size of the result |
---|
| 49 | ); |
---|
| 50 | |
---|
[a2dd9b2] | 51 | /// check if @a point is inside a polygon described by points |
---|
| 52 | /// |
---|
| 53 | /// @return true if @a point is inside a polygon described by points |
---|
| 54 | bool isInPolygon (int ** points, ///< [in] an array of points in the |
---|
| 55 | ///< plane describing a polygon |
---|
| 56 | int sizePoints,///< [in] size of @a points |
---|
| 57 | int* point ///< [in] a point in the plane |
---|
| 58 | ); |
---|
| 59 | |
---|
[6fd83c4] | 60 | /// get the y-direction slopes of all edges with positive slope in y-direction |
---|
| 61 | /// of a convex polygon with at least one point of the polygon lying on the |
---|
| 62 | /// x-axis and one lying on the y-axis |
---|
| 63 | /// |
---|
| 64 | /// @return an array containing the slopes as described above |
---|
| 65 | int* getRightSide (int** polygon, ///<[in] vertices of a polygon |
---|
| 66 | int sizeOfPolygon, ///<[in] number of vertices |
---|
| 67 | int& sizeOfOutput ///<[in,out] size of the output |
---|
| 68 | ); |
---|
| 69 | |
---|
[9752db] | 70 | /// computes the Newton polygon of F and checks if it satisfies the |
---|
| 71 | /// irreducibility criterion from S.Gao "Absolute irreducibility of polynomials |
---|
| 72 | /// via polytopes", Example 1 |
---|
| 73 | /// |
---|
| 74 | /// @return true if it satisfies the above criterion, false otherwise |
---|
| 75 | bool |
---|
| 76 | irreducibilityTest (const CanonicalForm& F ///<[in] a bivariate polynomial |
---|
| 77 | ); |
---|
| 78 | |
---|
[a2dd9b2] | 79 | #ifdef HAVE_NTL |
---|
| 80 | /// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization |
---|
| 81 | /// by Berthomieu, Lecerf |
---|
| 82 | void convexDense (int** points, ///< [in, out] a set of points in Z^2, returns |
---|
| 83 | ///< M (points)+A |
---|
| 84 | int sizePoints,///< [in] size of points |
---|
| 85 | mat_ZZ& M, ///< [in,out] returns an invertible matrix |
---|
| 86 | vec_ZZ& A ///< [in,out] returns translation |
---|
| 87 | ); |
---|
| 88 | |
---|
| 89 | /// compress a bivariate poly |
---|
| 90 | /// |
---|
| 91 | /// @return @a compress returns a compressed bivariate poly |
---|
| 92 | /// @sa convexDense, decompress |
---|
| 93 | CanonicalForm |
---|
| 94 | compress (const CanonicalForm& F, ///< [in] compressed, i.e. F.level()==2, |
---|
| 95 | ///< bivariate poly |
---|
[e243418] | 96 | mat_ZZ& inverseM, ///< [in,out] returns the inverse of M, |
---|
| 97 | ///< if computeMA==true, M otherwise |
---|
| 98 | vec_ZZ& A, ///< [in,out] returns translation |
---|
| 99 | bool computeMA= true ///< [in] whether to compute M and A |
---|
[a2dd9b2] | 100 | ); |
---|
| 101 | |
---|
| 102 | /// decompress a bivariate poly |
---|
| 103 | /// |
---|
| 104 | /// @return @a decompress returns a decompressed bivariate poly |
---|
| 105 | /// @sa convexDense, decompress |
---|
| 106 | CanonicalForm |
---|
| 107 | decompress (const CanonicalForm& F,///< [in] compressed, i.e. F.level()<= 2, |
---|
| 108 | ///< uni- or bivariate poly |
---|
| 109 | const mat_ZZ& M, ///< [in] matrix M obtained from compress |
---|
| 110 | const vec_ZZ& A ///< [in] vector A obtained from compress |
---|
| 111 | ); |
---|
| 112 | #endif |
---|
| 113 | |
---|
| 114 | #endif |
---|
| 115 | |
---|