source: git/kernel/f5gb.h @ 29d76d4

spielwiese
Last change on this file since 29d76d4 was 6ce030f, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
removal of the $Id$ svn tag from everywhere NOTE: the git SHA1 may be used instead (only on special places) NOTE: the libraries Singular/LIB/*.lib still contain the marker due to our current use of svn
  • Property mode set to 100644
File size: 7.2 KB
Line 
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/f5data.h>
12#include <kernel/f5lists.h>
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
Note: See TracBrowser for help on using the repository browser.