source: git/kernel/f5gb.h @ 341696

spielwiese
Last change on this file since 341696 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
RevLine 
[936551]1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
[341696]4/* $Id$ */
[936551]5/*
[d0f98e]6* ABSTRACT: f5gb interface
[936551]7*/
8#ifndef F5_HEADER
9#define F5_HEADER
10
11#ifdef HAVE_F5
[5d0556]12#include "f5data.h"
[a3771a]13#include "f5lists.h"
[d0f98e]14
15
[199ae7]16/*
17======================================================
18sort polynomials in ideal i by decreasing total degree
19======================================================
20*/
[61944d0]21void qsortDegree(poly* left, poly* right);
[199ae7]22
[2ae96e]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
[bb02ea]31/**
32==========================================================================
33compare monomials, i.e. divisibility tests for criterion 1 and criterion 2
34==========================================================================
35*/
[a05c71]36bool compareMonomials(int* m1, int** m2, int numberOfRuleOlds);
[bb02ea]37
[8627ad]38
[199ae7]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==================================================
[948192]44*/
[a05c71]45LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag,int termination);
[8627ad]46
[cce6ed3]47/*
48================================================================
49computes a list of critical pairs for the next reduction process
[418bd6]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.
[cce6ed3]53first element in gPrev is always the newest element which must
54build critical pairs with all other elements in gPrev
55================================================================
56*/
[a05c71]57void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds);
[418bd6]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);
[d51339]69
[cce6ed3]70/*
71========================================
72Criterion 1, i.e. Faugere's F5 Criterion
73========================================
74*/
[9cb4078]75inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
[66e7b5]76
77/*
78=====================================
79Criterion 2, i.e. Rewritten Criterion
80=====================================
81*/
[a05c71]82inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag);
[66e7b5]83
[8978fd]84/*
85==========================================================================================================
[a05c71]86Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter
[8978fd]87==========================================================================================================
88*/
[a05c71]89inline bool criterion2(poly t, LPolyOld* l, RList* RuleOlds, RuleOld* testedRuleOld);
[9bb97e]90
91/*
92==================================
93Computation of S-Polynomials in F5
94==================================
95*/
[a05c71]96inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList);
[9bb97e]97
98/*
99========================================================================
100reduction including subalgorithm topReduction() using Faugere's criteria
101========================================================================
102*/
[a05c71]103inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag,
[fcb8022]104                 ideal gbPrev);
[9bb97e]105
[6b0aa2]106/*
107========================================================================
108reduction including subalgorithm topReduction() using Faugere's criteria
109========================================================================
110*/
[a05c71]111inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination);
[6b0aa2]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
[a05c71]122 * later on for possible new RuleOlds and S-polynomials to be added to the algorithm
[6b0aa2]123 * ================================================================================
124 */
[a05c71]125void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination); 
[6b0aa2]126
[9bb97e]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*/
[a05c71]133inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev); 
[9bb97e]134
[c3efd3b]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*/   
[9bb97e]144/*
145=====================================================================
146subalgorithm to find a possible reductor for the labeled polynomial l
147=====================================================================
148*/
[a05c71]149inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag);
[9bb97e]150
[199ae7]151/*
152======================================
[87beab7]153main function of our F5 implementation
[199ae7]154======================================
155*/
[d4cec61]156ideal F5main(ideal i, ring r, int opt, int termination);
[199ae7]157
[936551]158#endif
159#endif
Note: See TracBrowser for help on using the repository browser.