# source:git/kernel/f5gb.h@e3b5ed

jengelh-datetimespielwiese
Last change on this file since e3b5ed was e3b5ed, checked in by Christian Eder, 14 years ago
• Property mode set to `100644`
File size: 5.5 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.h,v 1.38 2009-05-04 13:30:53 ederc Exp \$ */
5/*
6* ABSTRACT: f5gb interface
7*/
10
11#ifdef HAVE_F5
12#include "f5data.h"
13#include "f5lists.h"
14
15
16/*
17======================================================
18sort polynomials in ideal i by decreasing total degree
19======================================================
20*/
21void qsortDegree(poly* left, poly* right);
22
23/*!
24 * ======================================================================
25 * builds the sum of the entries of the exponent vectors, i.e. the degree
26 * of the corresponding monomial
27 * ======================================================================
28*/
29long sumVector(int* v, int k);
30
31/**
32==========================================================================
33compare monomials, i.e. divisibility tests for criterion 1 and criterion 2
34==========================================================================
35*/
36bool compareMonomials(int* m1, int** m2, int numberOfRules);
37
38/*
39==============================================
40generating the list lp of ideal generators and
41test if 1 is in lp(return 1) or not(return 0)
42==============================================
43*/
44void generate_input_list(LPoly* lp, ideal id, poly one);
45
46/*
47==================================================
48computes incrementally gbs of subsets of the input
49gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
50==================================================
51*/
52inline LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag);
53
54/*
55================================================================
56computes a list of critical pairs for the next reduction process
57first element in gPrev is always the newest element which must
58build critical pairs with all other elements in gPrev
59================================================================
60*/
61void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
62
63/*
64========================================
65Criterion 1, i.e. Faugere's F5 Criterion
66========================================
67*/
68inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
69
70/*
71=====================================
72Criterion 2, i.e. Rewritten Criterion
73=====================================
74*/
75inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag);
76
77/*
78==========================================================================================================
79Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
80==========================================================================================================
81*/
82inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule);
83
84/*
85==================================
86Computation of S-Polynomials in F5
87==================================
88*/
89inline void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
90
91/*
92========================================================================
93reduction including subalgorithm topReduction() using Faugere's criteria
94========================================================================
95*/
96inline void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
97                 ideal gbPrev);
98
99/*
100========================================================================
101reduction including subalgorithm topReduction() using Faugere's criteria
102========================================================================
103*/
104inline void newReduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev);
105
106/*!
107 * ================================================================================
108 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
109 * divides them into a "good" and "bad" part:
110 *
111 * the "good" ones are the reducers which do not corrupt the label of temp, with
112 * these the normal form of temp is computed
113 *
114 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
115 * later on for possible new rules and S-polynomials to be added to the algorithm
116 * ================================================================================
117 */
118void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag);
119
120/*
121=====================================================================================
122top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
123the same index whereas the labels are taken into account
124=====================================================================================
125*/
126inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev);
127
128/*
129=====================================================================
130subalgorithm to find a possible reductor for the labeled polynomial l
131=====================================================================
132*/
133inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
134
135/*
136======================================
137main function of our F5 implementation
138======================================
139*/
140ideal F5main(ideal i, ring r);
141
142#endif
143#endif
Note: See TracBrowser for help on using the repository browser.