source: git/kernel/f5gb.h @ f414c0

spielwiese
Last change on this file since f414c0 was d4cec61, checked in by Christian Eder, 14 years ago
implemented test for termination ideas git-svn-id: file:///usr/local/Singular/svn/trunk@12088 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 5.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5gb.h,v 1.43 2009-08-30 15:26:00 ederc Exp $ */
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 numberOfRules);
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, 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
50first element in gPrev is always the newest element which must
51build critical pairs with all other elements in gPrev
52================================================================
53*/
54void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
55
56/*
57========================================
58Criterion 1, i.e. Faugere's F5 Criterion
59========================================
60*/
61inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
62
63/*
64=====================================
65Criterion 2, i.e. Rewritten Criterion
66=====================================
67*/
68inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag);
69
70/*
71==========================================================================================================
72Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
73==========================================================================================================
74*/
75inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule);
76
77/*
78==================================
79Computation of S-Polynomials in F5
80==================================
81*/
82inline void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
83
84/*
85========================================================================
86reduction including subalgorithm topReduction() using Faugere's criteria
87========================================================================
88*/
89inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
90                 ideal gbPrev);
91
92/*
93========================================================================
94reduction including subalgorithm topReduction() using Faugere's criteria
95========================================================================
96*/
97inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination);
98
99/*!
100 * ================================================================================
101 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
102 * divides them into a "good" and "bad" part:
103 *
104 * the "good" ones are the reducers which do not corrupt the label of temp, with
105 * these the normal form of temp is computed
106 *
107 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
108 * later on for possible new rules and S-polynomials to be added to the algorithm
109 * ================================================================================
110 */
111void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination); 
112
113/*
114=====================================================================================
115top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
116the same index whereas the labels are taken into account
117=====================================================================================
118*/
119inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev); 
120
121/*
122=======================================================================================
123merging 2 polynomials p & q without requiring that all monomials of p & q are different
124if there are equal monomials in p & q only one of these monomials (always that of p!)
125is taken into account
126=======================================================================================
127
128poly p_MergeEq_q(poly p, poly q, const ring r);
129*/   
130/*
131=====================================================================
132subalgorithm to find a possible reductor for the labeled polynomial l
133=====================================================================
134*/
135inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
136
137/*
138======================================
139main function of our F5 implementation
140======================================
141*/
142ideal F5main(ideal i, ring r, int opt, int termination);
143
144#endif
145#endif
Note: See TracBrowser for help on using the repository browser.