# source:git/factory/cfNewtonPolygon.h@d0015c

jengelh-datetimespielwiese
Last change on this file since d0015c was 9752db, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: use irreducibility criterion also in characteristic 0
• Property mode set to `100644`
File size: 4.4 KB
Line
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
20// #include "config.h"
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
30int 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
38int ** newtonPolygon (const CanonicalForm& F,///< [in] a bivariate polynomial
39                      int& sizeOfNewtonPoly  ///< [in, out] size of the result
40                     );
41
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
46int ** 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
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
54bool 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
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
65int* 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
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
75bool
76irreducibilityTest (const CanonicalForm& F ///<[in] a bivariate polynomial
77                   );
78
79#ifdef HAVE_NTL
80/// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization
81/// by Berthomieu, Lecerf
82void 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
93CanonicalForm
94compress (const CanonicalForm& F, ///< [in] compressed, i.e. F.level()==2,
95                                  ///< bivariate poly
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
100         );
101
102/// decompress a bivariate poly
103///
104/// @return @a decompress returns a decompressed bivariate poly
105/// @sa convexDense, decompress
106CanonicalForm
107decompress (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
Note: See TracBrowser for help on using the repository browser.