source: git/kernel/f5gb.h @ d59666c

spielwiese
Last change on this file since d59666c was 416ea2, checked in by Christian Eder, 15 years ago
new try on reduction procedures, no longer list of completed elements, adding a "last" node to LLists for more flexibility using the lists git-svn-id: file:///usr/local/Singular/svn/trunk@11401 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 3.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5gb.h,v 1.26 2009-02-16 14:23:42 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*/
46CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
47
48/*
49========================================
50Criterion 1, i.e. Faugere's F5 Criterion
51========================================
52*/
53bool criterion1(poly* t, LNode* l, LTagList* lTag);
54
55/*
56=====================================
57Criterion 2, i.e. Rewritten Criterion
58=====================================
59*/
60bool criterion2(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*/
67bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested);
68
69/*
70==================================
71Computation of S-Polynomials in F5
72==================================
73*/
74void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
75
76/*
77========================================================================
78reduction including subalgorithm topReduction() using Faugere's criteria
79========================================================================
80*/
81void reduction(LList* sPolyList, LList* completed, 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*/
90void topReduction(LNode* l, LList* completed, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag); 
91
92/*
93=====================================================================
94subalgorithm to find a possible reductor for the labeled polynomial l
95=====================================================================
96*/
97LNode* findReductor(LNode* l,LList* completed,LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag,
98                    LNode* gPrevRedCheck);
99
100/*
101======================================
102main function of our F5 implementation
103======================================
104*/
105ideal F5main(ideal i, ring r);
106
107#endif
108#endif
Note: See TracBrowser for help on using the repository browser.