source: git/kernel/f5gb.h @ d51339

spielwiese
Last change on this file since d51339 was d51339, checked in by Christian Eder, 15 years ago
new written reduction process, still problems getting the right rules in criterion2() ->lastRuleTested shouldnt be part of the CPair as it is a characteristic of an LPoly git-svn-id: file:///usr/local/Singular/svn/trunk@11406 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 4.2 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5gb.h,v 1.27 2009-02-18 20:43:05 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 qsort_degree(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*/
37LList* 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================================================================
50computes a list of critical pairs for the next reduction process
51first element in gPrev is always the newest element which must
52build critical pairs with all other elements in gPrev
53NOTE: this is a special version for the call inside reduction()
54      which adds to the already existing critical pairs new ones
55================================================================
56*/
57void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
58
59/*
60========================================
61Criterion 1, i.e. Faugere's F5 Criterion
62========================================
63*/
64bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
65
66/*
67=====================================
68Criterion 2, i.e. Rewritten Criterion
69=====================================
70*/
71bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag);
72
73/*
74==========================================================================================================
75Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
76==========================================================================================================
77*/
78bool criterion2(poly t, LPoly* l, RList* rules, Rule* lastRuleTested);
79
80/*
81==================================
82Computation of S-Polynomials in F5
83==================================
84*/
85void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
86
87/*
88========================================================================
89reduction including subalgorithm topReduction() using Faugere's criteria
90========================================================================
91*/
92void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
93                 ideal gbPrev);
94
95/*
96=====================================================================================
97top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
98the same index whereas the labels are taken into account
99=====================================================================================
100*/
101void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag); 
102
103/*
104=====================================================================
105subalgorithm to find a possible reductor for the labeled polynomial l
106=====================================================================
107*/
108LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
109
110/*
111======================================
112main function of our F5 implementation
113======================================
114*/
115ideal F5main(ideal i, ring r);
116
117#endif
118#endif
Note: See TracBrowser for help on using the repository browser.