source: git/kernel/f5gb.h @ c9193a

spielwiese
Last change on this file since c9193a was c9193a, checked in by Christian Eder, 15 years ago
fixed bug: zero reduction after top reduction git-svn-id: file:///usr/local/Singular/svn/trunk@11501 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 4.3 KB
RevLine 
[936551]1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
[c9193a]4/* $Id: f5gb.h,v 1.30 2009-02-28 21:14:06 ederc Exp $ */
[936551]5/*
[d0f98e]6* ABSTRACT: f5gb interface
[936551]7*/
8#ifndef F5_HEADER
9#define F5_HEADER
10
11#ifdef HAVE_F5
[5d0556]12#include "f5data.h"
[a3771a]13#include "f5lists.h"
[d0f98e]14
15
[199ae7]16/*
17======================================================
18sort polynomials in ideal i by decreasing total degree
19======================================================
20*/
[61944d0]21void qsortDegree(poly* left, poly* right);
[199ae7]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);
[8627ad]30
[199ae7]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==================================================
[948192]36*/
[87beab7]37LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag);
[8627ad]38
[cce6ed3]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*/
[d51339]46void criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
47
[c9193a]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
53this is a special version for reduction() in which the first
54generator of the critical pair is not tested by criterion2()
55as there are no rules added until then to test for
56================================================================
57*/
58void criticalPairRed(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
59
[cce6ed3]60/*
61========================================
62Criterion 1, i.e. Faugere's F5 Criterion
63========================================
64*/
[d51339]65bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag);
[66e7b5]66
67/*
68=====================================
69Criterion 2, i.e. Rewritten Criterion
70=====================================
71*/
[d51339]72bool criterion2(poly t, LNode* l, RList* rules, RTagList* rTag);
[66e7b5]73
[8978fd]74/*
75==========================================================================================================
76Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
77==========================================================================================================
78*/
[eab144e]79bool criterion2(poly t, LPoly* l, RList* rules, Rule* testedRule);
[9bb97e]80
81/*
82==================================
83Computation of S-Polynomials in F5
84==================================
85*/
[fcb8022]86void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList);
[9bb97e]87
88/*
89========================================================================
90reduction including subalgorithm topReduction() using Faugere's criteria
91========================================================================
92*/
[d51339]93void reduction(LList* sPolyList, CList* critPairs, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag,
[fcb8022]94                 ideal gbPrev);
[9bb97e]95
96/*
97=====================================================================================
98top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
99the same index whereas the labels are taken into account
100=====================================================================================
101*/
[61944d0]102void topReduction(LNode* l, LList* sPolyList, LList* gPrev, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev); 
[9bb97e]103
104/*
105=====================================================================
106subalgorithm to find a possible reductor for the labeled polynomial l
107=====================================================================
108*/
[d51339]109LNode* findReductor(LNode* l, LList* gPrev, RList* rules, LTagList* lTag,RTagList* rTag);
[9bb97e]110
[199ae7]111/*
112======================================
[87beab7]113main function of our F5 implementation
[199ae7]114======================================
115*/
[171950]116ideal F5main(ideal i, ring r);
[199ae7]117
[936551]118#endif
119#endif
Note: See TracBrowser for help on using the repository browser.