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 "chainstructures.hpp" 10 #include "BPASRegularChain.hpp" 16 extern int intersectDepth;
17 extern int regularGCDDepth;
18 extern int intersectFreeDepth;
19 extern int intersectAlgebraicDepth;
20 extern int regularizeDepth;
21 extern int regularizeSingleDepth;
22 extern int extendDepth;
23 extern int cleanChainDepth;
26 extern float primitivePartTime;
27 extern float squareFreePartTime;
28 extern float subresultantChainTime;
29 extern float zerodimensionalregularchainTime;
30 extern float pseudoDivideTime;
31 extern float normalFormTime;
32 extern float removeRedundantChainsTime;
33 extern float factorTime;
35 extern float intersectTime;
36 extern float regularGCDTime;
37 extern float intersectFreeTime;
38 extern float intersectAlgebraicTime;
39 extern float regularizeTime;
40 extern float extendTime;
41 extern float cleanChainTime;
42 extern float constructChainTime;
43 extern float constructChainsTime;
44 extern float GCDFreeFactorizationTime;
45 extern float ZDIntersectTime;
46 extern float ZDRegularizeTime;
47 extern float isRegularTime;
48 extern float isInSaturatedIdealTime;
49 extern float cleanSetTime;
51 extern float tsCopyTime;
52 extern float rcCopyTime;
53 extern float zdrcCopyTime;
55 #define RC_TRIANGULARIZE_TASKTREEDATA 1 60 template <
class Field,
class RecursivePoly>
63 template <
class Value>
68 template <
class Field,
class RecursivePoly>
73 template<
class Field,
class RecursivePoly>
76 template<
class Field,
class RecursivePoly>
83 enum RegularChainOption {
84 ASSUME_REGULAR = 0x001,
85 ASSUME_REDUCED = 0x002,
86 ASSUME_PRIMITIVE = 0x004,
87 ASSUME_SQUAREFREE = 0x008,
88 ASSUME_ZERODIMENSIONAL = 0x010,
89 ASSUME_MAKESCHAIN = 0x020,
90 MAINTAIN_SQUAREFREE = 0x040,
91 MAINTAIN_NORMALIZED = 0x080,
92 MAINTAIN_PRIME = 0x100,
93 CONSTRUCT_FACTORIZE = 0x200,
100 template <
class Field,
class RecursivePoly>
117 #if defined(RC_TRIANGULARIZE_TASKTREEDATA) && RC_TRIANGULARIZE_TASKTREEDATA 118 mutable int RegChain_UniqueID;
121 int regularChainOptions = CONSTRUCT_FACTORIZE;
126 int saturatedIdealPrimeLevel;
134 void updateRegularChainStates();
142 void updateRegularChainStates(
const RecursivePoly& p);
156 RecursivePoly makeCanonical(
const RecursivePoly& p_in)
const;
165 RecursivePoly reduceMinimal(
const RecursivePoly& p)
const;
172 RecursivePoly reduceMinimalPrimitivePart(
const RecursivePoly& p)
const;
179 RecursivePoly reduceMinimalPrimitiveSquareFreePart(
const RecursivePoly& p_in)
const;
186 RecursivePoly removeZero(
const RecursivePoly& p)
const;
253 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 254 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;
256 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;
265 void constructChain(
const RecursivePoly& p,
int options=ASSUME_REGULAR);
284 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 287 std::vector<RegularChain<Field,RecursivePoly>> constructChainsFromPoly(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound,
int options=ASSUME_REGULAR)
const;
307 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 310 std::vector<RegularChain<Field,RecursivePoly>> intersectFree(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
322 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 325 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;
338 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 349 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 350 void regularizeSingle(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
352 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> regularizeSingle(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound)
const;
362 std::vector<RecursivePoly> GCDFreeFactorization(
const RecursivePoly& p,
int type = 2)
const;
370 std::vector<RegularChain<Field,RecursivePoly>> extend(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
378 std::vector<RegularChain<Field,RecursivePoly>> extend(
const std::vector<RecursivePoly>& T,
const Symbol& v,
bool lazardDecompose,
int heightBound)
const;
397 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 398 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;
400 std::vector<RegularChain<Field,RecursivePoly>> _squareFreePartInner(
const RecursivePoly& p,
const Symbol& v,
const SubResultantChain<RecursivePoly,RecursivePoly>& src,
bool lazardDecompose,
int heightBound,
int options)
const;
410 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 413 std::vector<RegularChain<Field,RecursivePoly>> _squareFreePart(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound,
int options)
const;
425 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 426 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;
428 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;
439 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 442 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _squareFreePartPolynomial(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose,
int heightBound,
int options)
const;
487 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 488 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;
490 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;
500 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 501 void _regularize(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound, AsyncGenerator<PolyChainPair<RecursivePoly,
RegularChain<Field,RecursivePoly>>>& results)
const;
503 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> _regularize(
const RecursivePoly& p,
bool lazardDecompose,
int heightBound)
const;
513 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 516 std::vector<RegularChain<Field,RecursivePoly>> _intersect(
const RecursivePoly& p,
bool lazardDecompose,
int inputHeightBound)
const;
526 #if defined(RC_WITH_GENERATORS) && RC_WITH_GENERATORS 529 std::vector<RegularChain<Field,RecursivePoly>> _triangularize(
const std::vector<RecursivePoly>& polys, std::vector<
RegularChain<Field,RecursivePoly>>& chains,
bool lazardDecompose,
int heightBound)
const;
532 std::vector<RegularChain<Field,RecursivePoly>> _triangularizeByTasks(std::vector<RecursivePoly>& polys,
bool lazardDecompose,
int heightBound)
const;
534 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);
538 std::vector<RegularChain<Field,RecursivePoly>> intersectTrivial(
const RecursivePoly& p)
const;
540 bool isIntersectionTrivial(
const RecursivePoly& p, RecursivePoly& pReduced)
const;
542 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>> regularizeTrivial(
const RecursivePoly& p,
const RecursivePoly& pReduced)
const;
544 bool isRegularizationTrivial(
const RecursivePoly& p, RecursivePoly& pReduced)
const;
546 RecursivePoly moduloPolysWithConstantInitial(
const RecursivePoly& p_in)
const;
548 std::vector<RecursivePoly> factorPolynomial(
const RecursivePoly& p)
const;
657 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);
808 return squareFreeLevel >= algVars.size();
811 bool isSaturatedIdealPrime()
const {
812 return saturatedIdealPrimeLevel >= algVars.size();
822 bool isInSaturatedIdealMinimal_inner(
const RecursivePoly& p)
const;
852 bool isRegular(
const RecursivePoly& p)
const;
940 std::vector<RegularChain<Field,RecursivePoly>>
triangularize(
const std::vector<RecursivePoly>& F,
bool lazardDecompose =
false,
int type = 0);
949 std::vector<RegularChain<Field,RecursivePoly>>
intersect(
const RecursivePoly& p,
bool lazardDecompose =
false,
int heightBound = 0)
const;
959 std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly>>>
regularize(
const RecursivePoly& p,
bool lazardDecompose =
false,
int heightBound = 0)
const;
971 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;
980 std::vector<RegularChain<Field,RecursivePoly>>
squareFreePart(
const RecursivePoly& p,
const Symbol& v,
bool lazardDecompose =
false,
int heightBound = 0,
int options=ASSUME_REGULAR)
const;
995 void randomRegularChain(
int nVars,
int nAlgVars,
int nTrcVars,
int nTerms,
unsigned long int coefBound,
int pSparsity,
bool includeNeg);
1009 void randomRegularChain(
int nVars,
int nAlgVars,
int nTrcVars, std::vector<int> maxDegs,
unsigned long int coefBound,
double pSparsity,
bool includeNeg);
1016 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:64
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:807
A class for handling regular chains in dimension zero.
Definition: regularchain.hpp:61
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:903
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:894
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:69
int numberOfVariables() const
Get the number of (potentially algebraic) variables in the current object.
Definition: regularchain.hpp:783
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: BPASRegularChain.hpp:11
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...