source: git/factory/cfNewtonPolygon.h @ e4e36c

spielwiese
Last change on this file since e4e36c was b79b58, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: added naive implementations of abs. irred. tests from Bertone, Cheze, Galligo
  • Property mode set to 100644
File size: 5.6 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 **/
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
27int 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
35int ** 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
43int ** 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
51bool 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
62int* 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
72bool
73irreducibilityTest (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
81bool
82absIrredTest (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
91bool
92modularIrredTest (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
101bool
102modularIrredTestWithShift (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
110void 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
121CanonicalForm
122compress (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
134CanonicalForm
135decompress (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
Note: See TracBrowser for help on using the repository browser.