# source:git/kernel/f5gb.cc@a41f3aa

spielwiese
Last change on this file since a41f3aa was a41f3aa, checked in by Christian Eder, 15 years ago
criterion1() and criterion2() done, changed rules(added pointer on LPoly generating this rule) git-svn-id: file:///usr/local/Singular/svn/trunk@11348 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to 100644
File size: 8.0 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.cc,v 1.21 2009-02-03 20:55:43 ederc Exp \$ */
5/*
6* ABSTRACT: f5gb interface
7*/
8#include "mod2.h"
9#ifdef HAVE_F5
10#include "kutil.h"
11#include "structs.h"
12#include "omalloc.h"
13#include "polys.h"
14#include "p_polys.h"
15#include "ideals.h"
16#include "febase.h"
17#include "kstd1.h"
18#include "khstd.h"
19#include "kbuckets.h"
20#include "weight.h"
21#include "intvec.h"
22#include "pInline1.h"
23#include "f5gb.h"
24#include "f5data.h"
25#include "f5lists.h"
26
27
28/*
29====================================================================
30sorting ideals by decreasing total degree "left" and "right" are the
31pointer of the first and last polynomial in the considered ideal
32====================================================================
33*/
34void qsortDegree(poly* left, poly* right) {
35    poly* ptr1 = left;
36    poly* ptr2 = right;
37    poly p1,p2;
38    p2 = *(left + (right - left >> 1));
39    do {
40            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
41                    ptr1++;
42            }
43            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
44                    ptr2--;
45            }
46            if(ptr1 > ptr2) {
47                    break;
48            }
49            p1    = *ptr1;
50            *ptr1 = *ptr2;
51            *ptr2 = p1;
52    } while(++ptr1 <= --ptr2);
53
54    if(left < ptr2) {
55            qsortDegree(left,ptr2);
56    }
57    if(ptr1 < right) {
58            qsortDegree(ptr1,right);
59    }
60}
61
62
63/*
64==================================================
65computes incrementally gbs of subsets of the input
66gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
67==================================================
68*/
69LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE) {
70    // tag the first element of index i-1 for criterion 1
71    LTagList* lTag  =   new LTagList(gPrev->getFirst());
72    // first element in rTag is NULL, this must be done due to possible later improvements
73    RTagList* rTag  =   new RTagList();
74    gPrev->insert(ONE,i,f_i);
75    CList* critPairs    =   new CList();
76    critPairs           =   criticalPair(gPrev, critPairs, lTag, rTag);
77
78    return gPrev;
79}
80
81
82/*
83================================================================
84computes a list of critical pairs for the next reduction process
85first element in gPrev is always the newest element which must
86build critical pairs with all other elements in gPrev
87================================================================
88*/
89CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag) {
90    // initialization for usage in pLcm()
91    number nOne         =   nInit(1);
92    LNode* first        =   gPrev->getFirst();
93    LNode* l            =   gPrev->getFirst()->getNext();
94    poly* u1            =   new poly(pInit());
95    poly* u2            =   new poly(pInit());
96    poly* lcm           =   new poly(pInit());
97    // computation of critical pairs
98    while( NULL != l) {
99        //pWrite( *(gPrev->getFirst()->getPoly()) );
100        //pWrite( *(l->getPoly()) );
101        pLcm(first->getPoly(), l->getPoly(), *lcm);
102        pSetCoeff(*lcm,nOne);
103        // computing factors u1 & u2 for new labels
105        pSetCoeff(*u1,nOne);
107        pSetCoeff(*u2,nOne);
108        pWrite(*u2);
109        // testing both new labels by the F5 Criterion
110        if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) &&
111           !criterion2(u1, first, rTag) && !criterion2(u2, l, rTag)) {
112            Print("Criteria passed\n");
113            // if they pass the test, add them to CList critPairs, having the LPoly with greater
114            // label as first element in the CPair
115            if(first->getIndex() == l->getIndex() &&
116            pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
117                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2,
118                                l->getLPoly(), *u1, first->getLPoly());
119                    critPairs->insert(cp);
120            }
121            else {
122                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1,
123                                first->getLPoly(), *u2, l->getLPoly());
124                    critPairs->insert(cp);
125            }
126        }
127        else {
128            Print("Criteria not passed\n");
129        }
130
131        // for debugging
132        if(NULL != critPairs) {
133            critPairs->print();
134        }
135        l   =   l->getNext();
136    }
137    Print("ENDE CRITPAIRS\n");
138    return critPairs;
139}
140
141/*
142========================================
143Criterion 1, i.e. Faugere's F5 Criterion
144========================================
145*/
146bool criterion1(poly* t, LNode* l, LTagList* lTag) {
147    // starts at the first element in gPrev with index = (index of l)-1, these tags are saved in lTag
148    LNode* testNode =   lTag->get(l->getIndex());
149    // save the monom t1*label_term(l) as it is tested various times in the following
150    poly u1 = ppMult_qq(*t,l->getTerm());
151    while(NULL != testNode) {
153            return true;
154        }
155        testNode    =   testNode->getNext();
156    }
157    return false;
158}
159
160/*
161=====================================
162Criterion 2, i.e. Rewritten Criterion
163=====================================
164*/
165bool criterion2(poly* t, LNode* l, RTagList* rTag) {
166    // start at the previously added element to gPrev, as all other elements will have the same index for sure
167    RNode* testNode =   rTag->get(l->getIndex());
168    // save the monom t1*label_term(l) as it is tested various times in the following
169    poly u1 = ppMult_qq(*t,l->getTerm());
170    // first element added to rTag was NULL, check for this
171    Print("Hier1\n");
172    while(NULL != testNode && testNode->getRule()->getOrigin() != l->getLPoly()) {
173        Print("Hier2\n");
174        if(pLmDivisibleByNoComp(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
175            return true;
176        }
177        testNode    =   testNode->getNext();
178    }
179    return false;
180}
181
182
183/*
184==========================================================================
185MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
186==========================================================================
187*/
188ideal F5main(ideal id, ring r) {
189    int i,j;
190    // 1 polynomial for defining initial labels & further tests
191    poly ONE = pOne();
192    // list of rules
193    RList* rules    =   new RList();
194    i = 1;
195    LList* gPrev    =   new LList( &ONE, &i, &id->m[0]);
196    poly* lcm = new poly;
197    // initialization for usage in pLcm()
198    *lcm = pOne();
199    pWrite(*lcm);
200    // definition of one-polynomial as global constant ONE
201    //poly one = pInit();
202    //pSetCoeff(one, nInit(1));
203    //static poly ONE = one;
204
205    for(j=0; j<IDELEMS(id); j++) {
206        if(NULL != id->m[j]) {
207            if(pComparePolys(id->m[j],ONE)) {
208                Print("One Polynomial in Input => Computations stopped\n");
209                ideal idNew = idInit(1,1);
210                idNew->m[0] = ONE;
211                return(idNew);
212            }
213        }
214    }
215    pLcm( id->m[0], id->m[1], *lcm);
216    Print("LCM NEU\n");
218    //pWrite(*lcm);
219    Print("\n\n");
220    id = kInterRed(id,0);
221    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
222    idShow(id);
224    pWrite(p);
226    pWrite(q);
227    for(i=2; i<=IDELEMS(id); i++) {
228        gPrev   =   F5inc(&i, &id->m[i-1], gPrev, &ONE);
229        Print("JA\n");
230    }
231    // only for debugging
232    //LNode* current;
233    //LList* g_curr = new LList(lp);
234    //}
235    //for(i=2; i<IDELEMS(id); i++) {
236        //g_curr = F5inc(&i,&id->m[i],g_prev);
237        //if(g_curr->polyTest(&ONE)) {
238        //    Print("One Polynomial in Input => Computations stopped\n");
239         //   ideal id_new = idInit(1,1);
240        //    id_new->m[0] = ONE;
241        //    return(id_new);
242        //}
243    //}
244    return(id);
245
246
247}
248
249#endif
Note: See TracBrowser for help on using the repository browser.