source: git/kernel/f5gb.h @ 39e423

spielwiese
Last change on this file since 39e423 was 6b0aa2, checked in by Christian Eder, 15 years ago
new alternative reduction - still in progress! git-svn-id: file:///usr/local/Singular/svn/trunk@11732 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 5.5 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5gb.h,v 1.37 2009-04-20 13:54:50 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==============================================
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,
105                 ideal gbPrev);
106
107/*!
108 * ================================================================================
109 * searches for reducers of temp similar to the symbolic preprocessing of F4  and
110 * divides them into a "good" and "bad" part:
111 *
112 * the "good" ones are the reducers which do not corrupt the label of temp, with
113 * these the normal form of temp is computed
114 *
115 * the "bad" ones are the reducers which corrupt the label of temp, they are tested
116 * later on for possible new rules and S-polynomials to be added to the algorithm
117 * ================================================================================
118 */
119void findReducers(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag); 
120
121/*
122=====================================================================================
123top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
124the same index whereas the labels are taken into account
125=====================================================================================
126*/
127inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev); 
128
129/*
130=====================================================================
131subalgorithm to find a possible reductor for the labeled polynomial l
132=====================================================================
133*/
134inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
135
136/*
137======================================
138main function of our F5 implementation
139======================================
140*/
141ideal F5main(ideal i, ring r);
142
143#endif
144#endif
Note: See TracBrowser for help on using the repository browser.