My Project
Loading...
Searching...
No Matches
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
23int 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
31int ** 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
39int ** 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
47bool 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
58int* 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
68bool
69irreducibilityTest (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
77bool
78absIrredTest (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
87bool
88modularIrredTest (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
97bool
98modularIrredTestWithShift (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
104void 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
116compress (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
129decompress (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
bool modularIrredTest(const CanonicalForm &F)
modular absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Abs...
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...
void convexDense(int **points, int sizePoints, mpz_t *&M, mpz_t *&A)
Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization by Berthomieu,...
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *M, const mpz_t *A)
decompress a bivariate poly
int polygon(int **points, int sizePoints)
compute a polygon
CanonicalForm compress(const CanonicalForm &F, mpz_t *&inverseM, mpz_t *&A, bool computeMA=true)
compress a bivariate poly
factory's main class
Definition: canonicalform.h:86
STATIC_VAR coordinates * points
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25