My Project
Loading...
Searching...
No Matches
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
13
14
15/*
16======================================================
17sort polynomials in ideal i by decreasing total degree
18======================================================
19*/
20void 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*/
28long sumVector(int* v, int k);
29
30/**
31==========================================================================
32compare monomials, i.e. divisibility tests for criterion 1 and criterion 2
33==========================================================================
34*/
35bool compareMonomials(int* m1, int** m2, int numberOfRuleOlds);
36
37
38/*
39==================================================
40computes incrementally gbs of subsets of the input
41gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
42==================================================
43*/
44LList* 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================================================================
48computes a list of critical pairs for the next reduction process
49the first element is always "useful" thus the critical pair
50computed is either "useful" or "useless" depending on the second
51element which generates the critical pair.
52first element in gPrev is always the newest element which must
53build critical pairs with all other elements in gPrev
54================================================================
55*/
56void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList, int plus);
57
58
59bool 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 */
70bool arrisCheck(CNode* first,LNode* firstGCurr, long arrisdeg);
71
72/*
73================================================================
74computes a list of critical pairs for the next reduction process
75the first element is always "useless" thus the critical pair
76computed is "useless".
77first element in gPrev is always the newest element which must
78build critical pairs with all other elements in gPrev
79================================================================
80*/
81void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList);
82
83/*
84========================================
85Criterion 1, i.e. Faugere's F5 Criterion
86========================================
87*/
88inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
89
90/*
91=====================================
92Criterion 2, i.e. Rewritten Criterion
93=====================================
94*/
95inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag);
96
97/*
98==========================================================================================================
99Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter
100==========================================================================================================
101*/
102inline 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 */
107int computeUsefulMinDeg(CNode* first);
108
109/*
110==================================
111Computation of S-Polynomials in F5
112==================================
113*/
114inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList, PList* rejectedGBList);
115
116/*
117========================================================================
118reduction including subalgorithm topReduction() using Faugere's criteria
119========================================================================
120*/
121inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
122 ideal gbPrev, PList* rejectedGBList, int plus);
123
124/*
125========================================================================
126reduction including subalgorithm topReduction() using Faugere's criteria
127========================================================================
128*/
129inline 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 */
143void 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=====================================================================================
147top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
148the same index whereas the labels are taken into account
149=====================================================================================
150*/
151inline 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=======================================================================================
155merging 2 polynomials p & q without requiring that all monomials of p & q are different
156if there are equal monomials in p & q only one of these monomials (always that of p!)
157is taken into account
158=======================================================================================
159
160poly p_MergeEq_q(poly p, poly q, const ring r);
161*/
162/*
163=====================================================================
164subalgorithm to find a possible reductor for the labeled polynomial l
165=====================================================================
166*/
167inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag);
168
169/*
170======================================
171main function of our F5 implementation
172======================================
173*/
174ideal F5main(ideal i, ring r, int opt, int plus, int termination);
175
176#endif
177#endif
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Definition: f5lists.h:232
Definition: f5lists.h:127
Definition: f5lists.h:65
class PList of lists of PNodes
Definition: f5lists.h:50
Definition: f5lists.h:313
void criticalPair2(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList)
Definition: f5gb.cc:553
ideal F5main(ideal i, ring r, int opt, int plus, int termination)
Definition: f5gb.cc:1889
void criticalPair(LList *gPrev, CListOld *critPairs, LTagList *lTag, RTagList *rTag, RList *RuleOlds, PList *rejectedGBList, int plus)
Definition: f5gb.cc:441
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1089
long sumVector(int *v, int k)
Definition: f5gb.cc:92
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:1704
bool checkDGB(LList *gPrev)
Definition: f5gb.cc:299
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:1135
void qsortDegree(poly *left, poly *right)
Definition: f5gb.cc:51
void computeSPols(CNode *first, RTagList *rTag, RList *RuleOlds, LList *sPolyList, PList *rejectedGBList)
Definition: f5gb.cc:844
bool criterion1(LList *gPrev, poly t, LNode *l, LTagList *lTag)
Definition: f5gb.cc:614
bool criterion2(int idx, poly t, LNode *l, RList *RuleOlds, RTagList *rTag)
Definition: f5gb.cc:675
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:130
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)
Definition: f5gb.cc:1202
int computeUsefulMinDeg(CNode *first)
Definition: f5gb.cc:828
bool compareMonomials(int *m1, int **m2, int numberOfRuleOlds)
LNode * findReductor(LNode *l, LList *sPolyList, LNode *gPrevRedCheck, LList *gPrev, RList *RuleOlds, LTagList *lTag, RTagList *rTag)
bool arrisCheck(CNode *first, LNode *firstGCurr, long arrisdeg)
Definition: f5gb.cc:382
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39