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

spielwiese
Last change on this file since cce6ed3 was cce6ed3, checked in by Christian Eder, 15 years ago
lists done, started implementing f5incremental and critpair subalgorithms git-svn-id: file:///usr/local/Singular/svn/trunk@11330 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 6.4 KB
Line
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* \$Id: f5gb.cc,v 1.17 2009-01-25 17:13:05 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 "lpolynomial.h"
25#include "lists.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    gPrev->insert(ONE,i,f_i);
71    CList* critPairs    =   criticalPair(gPrev);
72
73    return gPrev;
74}
75
76
77/*
78================================================================
79computes a list of critical pairs for the next reduction process
80first element in gPrev is always the newest element which must
81build critical pairs with all other elements in gPrev
82================================================================
83*/
84CList* criticalPair(LList* gPrev) {
85    poly lcm   = pInit();
86    number n    = nInit(2);
87    nWrite(n);
88    pWrite(lcm);
89    // initialization for usage in pLcm()
90    LNode* first        =   gPrev->getFirst();
91    LNode* l            =   gPrev->getFirst()->getNext();
92    poly t1, t2         =   pInit();
94    poly u1             =   pOne();
95    poly u2             =   pOne();
96    CList*  critpairs   =   NULL;
97    // computation of critical pairs
98    while( NULL != l) {
99        //pWrite( *(gPrev->getFirst()->getPoly()) );
100        //pWrite( *(l->getPoly()) );
101        pLcm(*first->getPoly(), *l->getPoly(), t1);
102        pWrite(t1);
103        pWrite(u1);
104        pWrite(u2);
105        pSetCoeff0(lcm,n);
106        poly p = lcm;
107        pWrite(p);
108        Print("%ld\n",pDeg(t1));
109        // computing factors u1 & u2 for new labels
110        u1  = pDivide(lcm, t1);
111        pWrite(u1);
112        pWrite(t1);
113        Print("%ld\n",pDeg(t1));
114        //pSetCoeff(u1,pGetCoeff(pOne()));
115        pWrite(u1);
117        pWrite(t2);
118        // testing stuff
119        u1 = ppMult_qq(t1,t2);
120        pWrite(u1);
121        pWrite(t2);
122        Print("%ld\n",pDeg(u1));
123        Print("%ld\n",pDeg(t2));
124        u2  = pDivide(lcm, t2);
125        pSetCoeff(u2, pGetCoeff(pOne()));
126        pWrite(u2);
127        Print("%ld\n",pDeg(u2));
128        // testing both new labels by the F5 Criterion
129        if(!criterion1(first, gPrev) &&
130           !criterion1(l, gPrev)) {
131            if(*first->getIndex() == *l->getIndex()) {
132                if(pMult(u1, *first->getTerm()) < pMult(u2, *l->getTerm())) {
133                    //if(!critPairs) {
134                        CPair* cp   =   new CPair(pDeg(lcm), u1, first->getLPoly(), u2,
135                                        l->getLPoly());
136                    //}
137                }
138            }
139        }
140
141        Print("\n");
142        l   =   l->getNext();
143    }
144    return NULL;
145}
146
147/*
148========================================
149Criterion 1, i.e. Faugere's F5 Criterion
150========================================
151*/
152bool criterion1(LNode* l, LList* gPrev) {
153    LNode* testNode =   l->getNext();
154    while(NULL != testNode) {
155        while(*testNode->getIndex() == *l->getIndex()) {
156            testNode = testNode->getNext();
157        }
158    }
159
160
161    return true;
162}
163
164/*
165==========================================================================
166MAIN:computes a gb of the ideal i in the ring r with our f5 implementation
167==========================================================================
168*/
169ideal F5main(ideal id, ring r) {
170    int i,j;
171    // 1 polynomial for defining initial labels & further tests
172    static poly ONE = pOne();
173    i = 1;
174    LList* gPrev = new LList( &ONE, &i, &id->m[0]);
175    poly* lcm = new poly;
176    // initialization for usage in pLcm()
177    *lcm = pOne();
178    pWrite(*lcm);
179    // definition of one-polynomial as global constant ONE
180    //poly one = pInit();
181    //pSetCoeff(one, nInit(1));
182    //static poly ONE = one;
183
184    for(j=0; j<IDELEMS(id); j++) {
185        if(NULL != id->m[j]) {
186            if(pComparePolys(id->m[j],ONE)) {
187                Print("One Polynomial in Input => Computations stopped\n");
188                ideal idNew = idInit(1,1);
189                idNew->m[0] = ONE;
190                return(idNew);
191            }
192        }
193    }
194    pLcm( id->m[0], id->m[1], *lcm);
195    Print("LCM NEU\n");
197    //pWrite(*lcm);
198    Print("\n\n");
199    id = kInterRed(id,0);
200    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
201    idShow(id);
203    pWrite(p);
205    pWrite(q);
206    for(i=2; i<=IDELEMS(id); i++) {
207        gPrev   =   F5inc( &i, &id->m[i-1], gPrev, &ONE );
208    }
209    // only for debugging
210    //LNode* current;
211    //LList* g_curr = new LList(lp);
212    //}
213    //for(i=2; i<IDELEMS(id); i++) {
214        //g_curr = F5inc(&i,&id->m[i],g_prev);
215        //if(g_curr->polyTest(&ONE)) {
216        //    Print("One Polynomial in Input => Computations stopped\n");
217         //   ideal id_new = idInit(1,1);
218        //    id_new->m[0] = ONE;
219        //    return(id_new);
220        //}
221    //}
222    return(id);
223
224
225}
226
227#endif
Note: See TracBrowser for help on using the repository browser.