1 #ifndef _REGULARCHAIN_H_ 2 #define _REGULARCHAIN_H_ 4 #include "regularchain_macros.hpp" 6 #include "../TriangularSet/triangularset.hpp" 7 #include "../SubResultantChain/subresultantchain.hpp" 8 #include "../polynomial.h" 9 #include "chainstructures.hpp" 12 extern int intersectDepth;
13 extern int regularGCDDepth;
14 extern int intersectFreeDepth;
15 extern int intersectAlgebraicDepth;
16 extern int regularizeDepth;
17 extern int regularizeSingleDepth;
18 extern int extendDepth;
19 extern int cleanChainDepth;
22 extern float primitivePartTime;
23 extern float squareFreePartTime;
24 extern float subresultantChainTime;
25 extern float zerodimensionalregularchainTime;
26 extern float pseudoDivideTime;
27 extern float normalFormTime;
28 extern float removeRedundantChainsTime;
29 extern float factorTime;
31 extern float intersectTime;
32 extern float regularGCDTime;
33 extern float intersectFreeTime;
34 extern float intersectAlgebraicTime;
35 extern float regularizeTime;
36 extern float extendTime;
37 extern float cleanChainTime;
38 extern float constructChainTime;
39 extern float constructChainsTime;
40 extern float GCDFreeFactorizationTime;
41 extern float ZDIntersectTime;
42 extern float ZDRegularizeTime;
43 extern float isRegularTime;
44 extern float isInSaturatedIdealTime;
45 extern float cleanSetTime;
47 extern float tsCopyTime;
48 extern float rcCopyTime;
49 extern float zdrcCopyTime;
54 template <
class Field,
class RecursivePoly>
57 template <
class Value>
62 template <
class Field,
class RecursivePoly>
67 template<
class Field,
class RecursivePoly>
70 template<
class Field,
class RecursivePoly>
77 enum RegularChainOption {
78 ASSUME_REGULAR = 0x001,
79 ASSUME_REDUCED = 0x002,
80 ASSUME_PRIMITIVE = 0x004,
81 ASSUME_SQUAREFREE = 0x008,
82 ASSUME_ZERODIMENSIONAL = 0x010,
83 ASSUME_MAKESCHAIN = 0x020,
84 MAINTAIN_SQUAREFREE = 0x040,
85 MAINTAIN_NORMALIZED = 0x080,
86 MAINTAIN_PRIME = 0x100,
87 CONSTRUCT_FACTORIZE = 0x200,
94 template <
class Field,
class RecursivePoly>
111 int regularChainOptions = CONSTRUCT_FACTORIZE;
116 int saturatedIdealPrimeLevel;
124 void updateRegularChainStates();
132 void updateRegularChainStates(
const RecursivePoly& p);
146 RecursivePoly makeCanonical(
const RecursivePoly& p_in)
const;
155 RecursivePoly reduceMinimal(
const RecursivePoly& p)
const;
162 RecursivePoly reduceMinimalPrimitivePart(
const RecursivePoly& p)
const;
169 RecursivePoly reduceMinimalPrimitiveSquareFreePart(
const RecursivePoly& p_in)
const;
176 RecursivePoly removeZero(
const RecursivePoly& p)
const;
243 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 244 void regularizeListStream(
const RecursivePoly& p,
const std::vector<RecursivePoly>& knownRegular,
const std::vector<RecursivePoly>& unknownIfRegular,
bool lazardDecompose,
int heightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
246 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> regularizeListStream(
const RecursivePoly& p,
const std::vector<RecursivePoly>& knownRegular,
const std::vector<RecursivePoly>& unknownIfRegular,
bool lazardDecompose,
int heightBound)
const;
255 void constructChain(
const RecursivePoly& p,
int options=ASSUME_REGULAR);
274 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 277 std::vector<RegularChain<Field,RecursivePoly>> constructChainsFromPoly(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound,
int options=ASSUME_REGULAR)
const;
297 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 300 std::vector<RegularChain<Field,RecursivePoly>> intersectFree(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
312 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 315 std::vector<RegularChain<Field,RecursivePoly>> intersectAlgebraic(
const RecursivePoly& p,
const RegularChain<Field,RecursivePoly>& T,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound)
const;
328 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 339 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 340 void regularizeSingle(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
342 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> regularizeSingle(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound)
const;
352 std::vector<RecursivePoly> GCDFreeFactorization(
const RecursivePoly& p,
int type = 2)
const;
360 std::vector<RegularChain<Field,RecursivePoly>> extend(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
368 std::vector<RegularChain<Field,RecursivePoly>> extend(
const std::vector<RecursivePoly>& T,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
387 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 388 void _squareFreePartInner(
const RecursivePoly& p,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound,
int options, AsyncGenerator<
RegularChain<Field,RecursivePoly>>& results)
const;
390 std::vector<RegularChain<Field,RecursivePoly>> _squareFreePartInner(
const RecursivePoly& p,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound,
int options)
const;
400 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 403 std::vector<RegularChain<Field,RecursivePoly>> _squareFreePart(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound,
int options)
const;
415 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 416 void _squareFreePartPolynomialInner(
const RecursivePoly& p,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound,
int options, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
418 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _squareFreePartPolynomialInner(
const RecursivePoly& p,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound,
int options)
const;
429 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 432 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _squareFreePartPolynomial(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound,
int options)
const;
477 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 478 void _regularGCD(
const RecursivePoly& p,
const RecursivePoly& q,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& S,
bool lazardDecompose,
int inputHeightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
480 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _regularGCD(
const RecursivePoly& p,
const RecursivePoly& q,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose =
false,
int heightBound = 0)
const;
490 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 491 void _regularize(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
493 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _regularize(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound)
const;
503 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 506 std::vector<RegularChain<Field,RecursivePoly>> _intersect(
const RecursivePoly& p,
bool lazardDecompose,
int inputHeightBound)
const;
516 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 519 std::vector<RegularChain<Field,RecursivePoly>> _triangularize(
const std::vector<RecursivePoly>& polys, std::vector<
RegularChain<Field,RecursivePoly>>& chains,
bool lazardDecompose,
int heightBound)
const;
522 std::vector<RegularChain<Field,RecursivePoly>> _triangularizeByTasks(std::vector<RecursivePoly>& polys,
bool lazardDecompose,
int heightBound)
const;
524 friend void triangularizeTask<Field,RecursivePoly>(
const RegularChain<Field, RecursivePoly>& rc, std::vector<RecursivePoly>& polys,
bool lazardDecompose,
int heightBound, TaskScheduler* tasks, std::shared_ptr<SynchronizedWriteVector<RegularChain<Field,RecursivePoly>>> results);
528 std::vector<RegularChain<Field,RecursivePoly>> intersectTrivial(
const RecursivePoly& p)
const;
530 bool isIntersectionTrivial(
const RecursivePoly& p, RecursivePoly& pReduced)
const;
532 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> regularizeTrivial(
const RecursivePoly& p,
const RecursivePoly& pReduced)
const;
534 bool isRegularizationTrivial(
const RecursivePoly& p, RecursivePoly& pReduced)
const;
536 RecursivePoly moduloPolysWithConstantInitial(
const RecursivePoly& p_in)
const;
538 std::vector<RecursivePoly> factorPolynomial(
const RecursivePoly& p)
const;
647 RegularChain<Field,RecursivePoly> (
const std::vector<Symbol>&& vs,
const std::vector<Symbol>&& avs,
const std::vector<Symbol>&& tvs,
const std::vector<RecursivePoly>&& ts, TriangularSetMode tsm,
const mpz_class& c);
798 return squareFreeLevel >= algVars.size();
801 bool isSaturatedIdealPrime()
const {
802 return saturatedIdealPrimeLevel >= algVars.size();
812 bool isInSaturatedIdealMinimal_inner(
const RecursivePoly& p)
const;
842 bool isRegular(
const RecursivePoly& p)
const;
930 std::vector<RegularChain<Field,RecursivePoly>>
triangularize(
const std::vector<RecursivePoly>& F,
bool lazardDecompose =
false,
int type = 0);
939 std::vector<RegularChain<Field,RecursivePoly>>
intersect(
const RecursivePoly& p,
bool lazardDecompose =
false,
int heightBound = 0)
const;
949 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>>
regularize(
const RecursivePoly& p,
bool lazardDecompose =
false,
int heightBound = 0)
const;
961 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>>
regularGCD(
const RecursivePoly& p,
const RecursivePoly& q,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose =
false,
int heightBound = 0)
const;
970 std::vector<RegularChain<Field,RecursivePoly>>
squareFreePart(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose =
false,
int heightBound = 0,
int options=ASSUME_REGULAR)
const;
985 void randomRegularChain(
int nVars,
int nAlgVars,
int nTrcVars,
int nTerms,
unsigned long int coefBound,
int pSparsity,
bool includeNeg);
999 void randomRegularChain(
int nVars,
int nAlgVars,
int nTrcVars, std::vector<int> maxDegs,
unsigned long int coefBound,
double pSparsity,
bool includeNeg);
1006 bool cleanSet(std::vector<RecursivePoly>& polys)
const;
void randomRegularChain(int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
Generate a random regular chain based on the number of terms of the polynomials in the chain...
A triangular set templated by a multivariate polynomial over a field.
Definition: triangularset.hpp:44
std::vector< Symbol > variables() const
Get the variable names in decreasing order.
Definition: triangularset.hpp:311
Definition: regularchain.hpp:58
void lowerSlice(const Symbol &s)
Destructively converts the current object into lower(s) by changing the set of (potentially algebraic...
int numberOfVariables() const
Get the number of variables.
Definition: triangularset.hpp:275
bool isSquareFree() const
Find out if the regular chain is known to be squarefree.
Definition: regularchain.hpp:797
A class for handling regular chains in dimension zero.
Definition: regularchain.hpp:55
static void removeRedundantChains(const std::vector< RegularChain< Field, RecursivePoly >> &lrc, std::vector< RegularChain< Field, RecursivePoly >> &results)
Remove redundancy from the input list of regular chains.
RecursivePoly select(const Symbol &s) const
Select a polynomial given the leading variable; if no such polynomial, 0 is returned.
RecursivePoly select(const Symbol &s) const
Select the polynomial in the current object with main variable s, if it exists.
Definition: regularchain.hpp:893
bool isInSaturatedIdeal(const RecursivePoly &p) const
Find out if the input polynomial is in the saturated ideal of the current regular chain...
static bool compareHeuristicNoSplit(const RegularChain< Field, RecursivePoly > &rc1, const RegularChain< Field, RecursivePoly > &rc2)
Determine whether or not the quasicomponent of the first regular chain is contained in the quasicompo...
bool isInSaturatedIdealMinimal(const RecursivePoly &p) const
Efficiently find out if the input polynomial is in the saturated ideal of the current regular chain...
void setOptions(int opts)
Set the encoded options of the regular chain.
bool cleanSet(std::vector< RecursivePoly > &polys) const
Reduce the polynomials of the input vector modulo the saturated ideal of the current object and detec...
std::vector< PolyChainPair< RecursivePoly, RegularChain< Field, RecursivePoly > > > regularGCD(const RecursivePoly &p, const RecursivePoly &q, const Symbol &v, const SubResultantChain< RecursivePoly, RecursivePoly > &src, bool lazardDecompose=false, int heightBound=0) const
Compute the gcd of two input polynomials p and q modulo the saturated ideal of the current object...
static bool compareCertifiedNoSplit(const RegularChain< Field, RecursivePoly > &rc1, const RegularChain< Field, RecursivePoly > &rc2)
Determine whether or not the quasicomponent of the first regular chain is contained in the quasicompo...
RegularChain< Field, RecursivePoly > & operator+=(const RecursivePoly &p)
Add assignment operator +=: Adds a polynomial to a regular chain, assuming that the main variable of ...
std::vector< Symbol > variables() const
Get the (potentially algebriac) variable names in decreasing order.
Definition: regularchain.hpp:884
bool isIteratedResultantZeroModular(const RecursivePoly &p) const
Using a modular method determine if the iterated resultant of p and this regular chain is zero or not...
static std::vector< RegularChain< Field, RecursivePoly > > constructChains(const TriangularSet< Field, RecursivePoly > &T)
Construct a set of regular chains from an input triangular set by triangularizing the elements of the...
bool operator!=(const RegularChain< Field, RecursivePoly > &a) const
Negated identity operator !=.
int options() const
Get the encoded options of the regular chain, a bitwise or of RegularChainOption values.
std::vector< RegularChain< Field, RecursivePoly > > squareFreePart(const RecursivePoly &p, const Symbol &v, bool lazardDecompose=false, int heightBound=0, int options=ASSUME_REGULAR) const
A routine that decomposes the regular chain formed from the current object and an input polynomial in...
RegularChain< Field, RecursivePoly > operator+(const RecursivePoly &p) const
Add operator +: Adds a polynomial to a regular chain and returns a new regular chain, assuming that the main variable of p is above any in the current object and that init(p) is regular modulo the saturated ideal of the current object.
std::vector< RegularChain< Field, RecursivePoly > > triangularize(const std::vector< RecursivePoly > &F, bool lazardDecompose=false, int type=0)
Compute a triangular decomposition of the list of input polynomials.
bool operator==(const RegularChain< Field, RecursivePoly > &a) const
Identity operator ==.
std::vector< RegularChain< Field, RecursivePoly > > intersect(const RecursivePoly &p, bool lazardDecompose=false, int heightBound=0) const
Compute the common solutions of the input polynomial and the current regular chain.
A class for handling regular chains of arbitrary dimension.
Definition: regularchain.hpp:63
int numberOfVariables() const
Get the number of (potentially algebraic) variables in the current object.
Definition: regularchain.hpp:773
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
RegularChain< Field, RecursivePoly > & operator=(const ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
Assignment operator = for a zero-dimensional regular chain.
std::vector< PolyChainPair< RecursivePoly, RegularChain< Field, RecursivePoly > > > regularize(const RecursivePoly &p, bool lazardDecompose=false, int heightBound=0) const
Compute a decomposition of the current object such that on each component the input polynomial is eit...
An abstract class defining the interface of a regular chain.
Definition: polynomial.h:220
bool isInRadicalSaturatedIdeal(const RecursivePoly &p) const
Find out if the input polynomial is in the radical saturated ideal of the current regular chain...
bool isRegular(const RecursivePoly &p) const
Find out if the input polynomial is regular modulo the saturated ideal of the current regular chain...