# source:git/kernel/f5gb.h@f6c7c9b

jengelh-datetimespielwiese
Last change on this file since f6c7c9b was f6c7c9b, checked in by Christian Eder, 14 years ago
deleted criterion2-tests if the element does not have the current index git-svn-id: file:///usr/local/Singular/svn/trunk@11570 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 3.8 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.h,v 1.33 2009-03-18 13:39:13 ederc Exp \$ */
5/*
6* ABSTRACT: f5gb interface
7*/
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==============================================
25generating the list lp of ideal generators and
26test if 1 is in lp(return 1) or not(return 0)
27==============================================
28*/
29void generate_input_list(LPoly* lp, ideal id, poly one);
30
31/*
32==================================================
33computes incrementally gbs of subsets of the input
34gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
35==================================================
36*/
37inline LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag);
38
39/*
40================================================================
41computes a list of critical pairs for the next reduction process
42first element in gPrev is always the newest element which must
43build critical pairs with all other elements in gPrev
44================================================================
45*/
46void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
47
48/*
49========================================
50Criterion 1, i.e. Faugere's F5 Criterion
51========================================
52*/
53inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
54
55/*
56=====================================
57Criterion 2, i.e. Rewritten Criterion
58=====================================
59*/
60inline bool criterion2(int idx, poly t, LNode* l, RList* rules, RTagList* rTag);
61
62/*
63==========================================================================================================
64Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
65==========================================================================================================
66*/
67inline bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule);
68
69/*
70==================================
71Computation of S-Polynomials in F5
72==================================
73*/
74inline void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
75
76/*
77========================================================================
78reduction including subalgorithm topReduction() using Faugere's criteria
79========================================================================
80*/
81inline void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
82                 ideal gbPrev);
83
84/*
85=====================================================================================
86top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
87the same index whereas the labels are taken into account
88=====================================================================================
89*/
90inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev);
91
92/*
93=====================================================================
94subalgorithm to find a possible reductor for the labeled polynomial l
95=====================================================================
96*/
97inline LNode* findReductor(LNode* l, LNode* gPrevRedCheck, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
98
99/*
100======================================
101main function of our F5 implementation
102======================================
103*/
104ideal F5main(ideal i, ring r);
105
106#endif
107#endif
Note: See TracBrowser for help on using the repository browser.