source: git/kernel/f5gb.h @ f2b6f0b

spielwiese
Last change on this file since f2b6f0b was 599326, checked in by Kai Krüger <krueger@…>, 14 years ago
Anne, Kai, Frank: - changes to #include "..." statements to allow cleaner build structure - affected directories: omalloc, kernel, Singular - not yet done: IntergerProgramming git-svn-id: file:///usr/local/Singular/svn/trunk@13032 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.2 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 <kernel/f5data.h>
13#include <kernel/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 plus ,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, PList* rejectedGBList, int plus);
58
59
60bool checkDGB(LList* gPrev);
61
62
63/*
64 * Arris Check if we are finished after the current degree step:
65 * Checks all remaining critical pairs, i.e. those of higher degree,
66 * by the two Buchberger criteria.
67 * return value: 0, if all remaining critical pairs are deleted by
68 *                  Buchberger's criteria
69 *               1, otherwise
70 */
71bool arrisCheck(CNode* first,LNode* firstGCurr, long arrisdeg); 
72
73/*
74================================================================
75computes a list of critical pairs for the next reduction process
76the first element is always "useless" thus the critical pair
77computed is "useless".
78first element in gPrev is always the newest element which must
79build critical pairs with all other elements in gPrev
80================================================================
81*/
82void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList);
83
84/*
85========================================
86Criterion 1, i.e. Faugere's F5 Criterion
87========================================
88*/
89inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
90
91/*
92=====================================
93Criterion 2, i.e. Rewritten Criterion
94=====================================
95*/
96inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag);
97
98/*
99==========================================================================================================
100Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter
101==========================================================================================================
102*/
103inline bool criterion2(poly t, LPolyOld* l, RList* RuleOlds, RuleOld* testedRuleOld);
104
105/*
106 * check for useful pairs in the given subset of critical pairs
107 */
108int computeUsefulMinDeg(CNode* first);
109
110/*
111==================================
112Computation of S-Polynomials in F5
113==================================
114*/
115inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList, PList* rejectedGBList);
116
117/*
118========================================================================
119reduction including subalgorithm topReduction() using Faugere's criteria
120========================================================================
121*/
122inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
123                 ideal gbPrev, PList* rejectedGBList, int plus);
124
125/*
126========================================================================
127reduction including subalgorithm topReduction() using Faugere's criteria
128========================================================================
129*/
130inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination, PList* rejectedGBList, int plus);
131
132/*!
133 * ================================================================================
134 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
135 * divides them into a "good" and "bad" part:
136 *
137 * the "good" ones are the reducers which do not corrupt the label of temp, with
138 * these the normal form of temp is computed
139 *
140 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
141 * later on for possible new RuleOlds and S-polynomials to be added to the algorithm
142 * ================================================================================
143 */
144void 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); 
145
146/*
147=====================================================================================
148top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
149the same index whereas the labels are taken into account
150=====================================================================================
151*/
152inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus); 
153
154/*
155=======================================================================================
156merging 2 polynomials p & q without requiring that all monomials of p & q are different
157if there are equal monomials in p & q only one of these monomials (always that of p!)
158is taken into account
159=======================================================================================
160
161poly p_MergeEq_q(poly p, poly q, const ring r);
162*/   
163/*
164=====================================================================
165subalgorithm to find a possible reductor for the labeled polynomial l
166=====================================================================
167*/
168inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag);
169
170/*
171======================================
172main function of our F5 implementation
173======================================
174*/
175ideal F5main(ideal i, ring r, int opt, int plus, int termination);
176
177#endif
178#endif
Note: See TracBrowser for help on using the repository browser.