source: git/kernel/f5gb.h @ 0ad81f

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