source: git/kernel/f5gb.h @ d51339

jengelh-datetimespielwiese
Last change on this file since d51339 was d51339, checked in by Christian Eder, 14 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.