source: git/kernel/f5gb.h @ 26da1d

spielwiese
Last change on this file since 26da1d was 341696, checked in by Hans Schönemann <hannes@…>, 14 years ago
Adding Id property to all files git-svn-id: file:///usr/local/Singular/svn/trunk@12231 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 6.4 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5/*
6* ABSTRACT: f5gb interface
7*/
8#ifndef F5_HEADER
9#define F5_HEADER
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 numberOfRuleOlds);
37
38
39/*
40==================================================
41computes incrementally gbs of subsets of the input
42gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} 
43==================================================
44*/
45LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag,int termination);
46
47/*
48================================================================
49computes a list of critical pairs for the next reduction process
50the first element is always "useful" thus the critical pair
51computed is either "useful" or "useless" depending on the second
52element which generates the critical pair.
53first element in gPrev is always the newest element which must
54build critical pairs with all other elements in gPrev
55================================================================
56*/
57void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
58
59/*
60================================================================
61computes a list of critical pairs for the next reduction process
62the first element is always "useless" thus the critical pair
63computed is "useless".
64first element in gPrev is always the newest element which must
65build critical pairs with all other elements in gPrev
66================================================================
67*/
68void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
69
70/*
71========================================
72Criterion 1, i.e. Faugere's F5 Criterion
73========================================
74*/
75inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
76
77/*
78=====================================
79Criterion 2, i.e. Rewritten Criterion
80=====================================
81*/
82inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag);
83
84/*
85==========================================================================================================
86Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter
87==========================================================================================================
88*/
89inline bool criterion2(poly t, LPolyOld* l, RList* RuleOlds, RuleOld* testedRuleOld);
90
91/*
92==================================
93Computation of S-Polynomials in F5
94==================================
95*/
96inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList);
97
98/*
99========================================================================
100reduction including subalgorithm topReduction() using Faugere's criteria
101========================================================================
102*/
103inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
104                 ideal gbPrev);
105
106/*
107========================================================================
108reduction including subalgorithm topReduction() using Faugere's criteria
109========================================================================
110*/
111inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination);
112
113/*!
114 * ================================================================================
115 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
116 * divides them into a "good" and "bad" part:
117 *
118 * the "good" ones are the reducers which do not corrupt the label of temp, with
119 * these the normal form of temp is computed
120 *
121 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
122 * later on for possible new RuleOlds and S-polynomials to be added to the algorithm
123 * ================================================================================
124 */
125void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination); 
126
127/*
128=====================================================================================
129top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
130the same index whereas the labels are taken into account
131=====================================================================================
132*/
133inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev); 
134
135/*
136=======================================================================================
137merging 2 polynomials p & q without requiring that all monomials of p & q are different
138if there are equal monomials in p & q only one of these monomials (always that of p!)
139is taken into account
140=======================================================================================
141
142poly p_MergeEq_q(poly p, poly q, const ring r);
143*/   
144/*
145=====================================================================
146subalgorithm to find a possible reductor for the labeled polynomial l
147=====================================================================
148*/
149inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag);
150
151/*
152======================================
153main function of our F5 implementation
154======================================
155*/
156ideal F5main(ideal i, ring r, int opt, int termination);
157
158#endif
159#endif
Note: See TracBrowser for help on using the repository browser.