f5gb.h
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: f5gb interface
6 */
7 #ifndef F5_HEADER
8 #define F5_HEADER
9 
10 #ifdef HAVE_F5
11 #include <kernel/GBEngine/f5data.h>
13 
14 
15 /*
16 ======================================================
17 sort polynomials in ideal i by decreasing total degree
18 ======================================================
19 */
20 void qsortDegree(poly* left, poly* right);
21 
22 /*!
23  * ======================================================================
24  * builds the sum of the entries of the exponent vectors, i.e. the degree
25  * of the corresponding monomial
26  * ======================================================================
27 */
28 long sumVector(int* v, int k);
29 
30 /**
31 ==========================================================================
32 compare monomials, i.e. divisibility tests for criterion 1 and criterion 2
33 ==========================================================================
34 */
35 bool compareMonomials(int* m1, int** m2, int numberOfRuleOlds);
36 
37 
38 /*
39 ==================================================
40 computes incrementally gbs of subsets of the input
41 gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
42 ==================================================
43 */
44 LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus ,int termination);
45 
46 /*
47 ================================================================
48 computes a list of critical pairs for the next reduction process
49 the first element is always "useful" thus the critical pair
50 computed is either "useful" or "useless" depending on the second
51 element which generates the critical pair.
52 first element in gPrev is always the newest element which must
53 build critical pairs with all other elements in gPrev
54 ================================================================
55 */
56 void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList, int plus);
57 
58 
59 bool checkDGB(LList* gPrev);
60 
61 
62 /*
63  * Arris Check if we are finished after the current degree step:
64  * Checks all remaining critical pairs, i.e. those of higher degree,
65  * by the two Buchberger criteria.
66  * return value: 0, if all remaining critical pairs are deleted by
67  * Buchberger's criteria
68  * 1, otherwise
69  */
70 bool arrisCheck(CNode* first,LNode* firstGCurr, long arrisdeg);
71 
72 /*
73 ================================================================
74 computes a list of critical pairs for the next reduction process
75 the first element is always "useless" thus the critical pair
76 computed is "useless".
77 first element in gPrev is always the newest element which must
78 build critical pairs with all other elements in gPrev
79 ================================================================
80 */
81 void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList);
82 
83 /*
84 ========================================
85 Criterion 1, i.e. Faugere's F5 Criterion
86 ========================================
87 */
88 inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
89 
90 /*
91 =====================================
92 Criterion 2, i.e. Rewritten Criterion
93 =====================================
94 */
95 inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag);
96 
97 /*
98 ==========================================================================================================
99 Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter
100 ==========================================================================================================
101 */
102 inline bool criterion2(poly t, LPolyOld* l, RList* RuleOlds, RuleOld* testedRuleOld);
103 
104 /*
105  * check for useful pairs in the given subset of critical pairs
106  */
107 int computeUsefulMinDeg(CNode* first);
108 
109 /*
110 ==================================
111 Computation of S-Polynomials in F5
112 ==================================
113 */
114 inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList, PList* rejectedGBList);
115 
116 /*
117 ========================================================================
118 reduction including subalgorithm topReduction() using Faugere's criteria
119 ========================================================================
120 */
121 inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
122  ideal gbPrev, PList* rejectedGBList, int plus);
123 
124 /*
125 ========================================================================
126 reduction including subalgorithm topReduction() using Faugere's criteria
127 ========================================================================
128 */
129 inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination, PList* rejectedGBList, int plus);
130 
131 /*!
132  * ================================================================================
133  * searches for reducers of temp similar to the symbolic preprocessing of F4 and
134  * divides them into a "good" and "bad" part:
135  *
136  * the "good" ones are the reducers which do not corrupt the label of temp, with
137  * these the normal form of temp is computed
138  *
139  * the "bad" ones are the reducers which corrupt the label of temp, they are tested
140  * later on for possible new RuleOlds and S-polynomials to be added to the algorithm
141  * ================================================================================
142  */
143 void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus);
144 
145 /*
146 =====================================================================================
147 top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
148 the same index whereas the labels are taken into account
149 =====================================================================================
150 */
151 inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus);
152 
153 /*
154 =======================================================================================
155 merging 2 polynomials p & q without requiring that all monomials of p & q are different
156 if there are equal monomials in p & q only one of these monomials (always that of p!)
157 is taken into account
158 =======================================================================================
159 
160 poly p_MergeEq_q(poly p, poly q, const ring r);
161 */
162 /*
163 =====================================================================
164 subalgorithm to find a possible reductor for the labeled polynomial l
165 =====================================================================
166 */
167 inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag);
168 
169 /*
170 ======================================
171 main function of our F5 implementation
172 ======================================
173 */
174 ideal F5main(ideal i, ring r, int opt, int plus, int termination);
175 
176 #endif
177 #endif
bool checkDGB(LList *gPrev)
Definition: f5gb.cc:303
void findReducers(LNode *l, LList *sPolyList, ideal gbPrev, LList *gPrev, LList *reducers, CListOld *critPairs, RList *rules, LTagList *lTag, RTagList *rTag, int termination, PList *rejectedGBList, int plus)
searches for reducers of temp similar to the symbolic preprocessing of F4 and divides them into a "g...
Definition: f5gb.cc:1206
bool arrisCheck(CNode *first, LNode *firstGCurr, long arrisdeg)
Definition: f5gb.cc:386
int computeUsefulMinDeg(CNode *first)
Definition: f5gb.cc:832
void topReduction(LNode *l, LList *sPolyList, LList *gPrev, CListOld *critPairs, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1708
Definition: f5lists.h:313
structure of RuleOlds(i.e.
Definition: f5data.h:232
void newReduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, LList *reducers, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, int termination, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1139
int k
Definition: cfEzgcd.cc:93
LList * F5inc(int i, poly f_i, LList *gPrev, LList *reducers, ideal gbPrev, poly ONE, LTagList *lTag, RList *rules, RTagList *rTag, int plus, int termination)
Definition: f5gb.cc:134
class PList of lists of PNodes
Definition: f5lists.h:50
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList, int plus)
Definition: f5gb.cc:445
const ring r
Definition: syzextra.cc:208
Definition: f5lists.h:65
Definition: f5lists.h:232
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag)
bool criterion2(int idx, poly t, LNode *l, RList *RuleOlds, RTagList *rTag)
Definition: f5gb.cc:679
class of labeled polynomials
Definition: f5data.h:28
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:618
ideal F5main(ideal i, ring r, int opt, int plus, int termination)
Definition: f5gb.cc:1893
int i
Definition: cfEzgcd.cc:123
long sumVector(int *v, int k)
builds the sum of the entries of the exponent vectors, i.e.
Definition: f5gb.cc:96
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
void computeSPols(CNode *first, RTagList *rTag, RList *RuleOlds, LList *sPolyList, PList *rejectedGBList)
Definition: f5gb.cc:848
Definition: f5lists.h:127
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:55
polyrec * poly
Definition: hilb.h:10
int l
Definition: cfEzgcd.cc:94
bool compareMonomials(int *m1, int **m2, int numberOfRuleOlds)
compare monomials, i.e.
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList)
Definition: f5gb.cc:557