1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* $Id: f5gb.cc,v 1.14 2008-12-26 13:49:29 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 | ======================= |
---|
30 | static/global variables |
---|
31 | ======================= |
---|
32 | */ |
---|
33 | static poly ONE = one_poly(); |
---|
34 | |
---|
35 | |
---|
36 | /* |
---|
37 | ================================================ |
---|
38 | computation of ONE polynomial as global variable |
---|
39 | ================================================ |
---|
40 | */ |
---|
41 | poly one_poly() { |
---|
42 | poly one = pInit(); |
---|
43 | pSetCoeff(one,nInit(1)); |
---|
44 | return one; |
---|
45 | } |
---|
46 | |
---|
47 | /* |
---|
48 | ==================================================================== |
---|
49 | sorting ideals by decreasing total degree "left" and "right" are the |
---|
50 | pointer of the first and last polynomial in the considered ideal |
---|
51 | ==================================================================== |
---|
52 | */ |
---|
53 | void qsortDegree(poly* left, poly* right) { |
---|
54 | poly* ptr1 = left; |
---|
55 | poly* ptr2 = right; |
---|
56 | poly p1,p2; |
---|
57 | p2 = *(left + (right - left >> 1)); |
---|
58 | do { |
---|
59 | while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) { |
---|
60 | ptr1++; |
---|
61 | } |
---|
62 | while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) { |
---|
63 | ptr2--; |
---|
64 | } |
---|
65 | if(ptr1 > ptr2) { |
---|
66 | break; |
---|
67 | } |
---|
68 | p1 = *ptr1; |
---|
69 | *ptr1 = *ptr2; |
---|
70 | *ptr2 = p1; |
---|
71 | } while(++ptr1 <= --ptr2); |
---|
72 | |
---|
73 | if(left < ptr2) { |
---|
74 | qsortDegree(left,ptr2); |
---|
75 | } |
---|
76 | if(ptr1 < right) { |
---|
77 | qsortDegree(ptr1,right); |
---|
78 | } |
---|
79 | } |
---|
80 | |
---|
81 | |
---|
82 | /* |
---|
83 | ================================================== |
---|
84 | computes incrementally gbs of subsets of the input |
---|
85 | gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} |
---|
86 | ================================================== |
---|
87 | */ |
---|
88 | |
---|
89 | LList* F5inc(long i, poly* f_i, LList* g_prev) { |
---|
90 | LList* g_curr = g_prev; |
---|
91 | LNode* prev_last = g_prev->getLast(); //tags the end of g_prev->only 1 list for g_prev & g_curr |
---|
92 | g_curr->append(&ONE,&i,f_i); |
---|
93 | |
---|
94 | return g_curr; |
---|
95 | |
---|
96 | |
---|
97 | |
---|
98 | |
---|
99 | } |
---|
100 | |
---|
101 | /* |
---|
102 | ========================================================================== |
---|
103 | MAIN:computes a gb of the ideal i in the ring r with our f5 implementation |
---|
104 | ========================================================================== |
---|
105 | */ |
---|
106 | ideal F5main(ideal id, ring r) { |
---|
107 | long i,j; |
---|
108 | LPoly* lp = new LPoly; |
---|
109 | // definition of one-polynomial as global constant ONE |
---|
110 | //poly one = pInit(); |
---|
111 | //pSetCoeff(one, nInit(1)); |
---|
112 | //static poly ONE = one; |
---|
113 | |
---|
114 | for(j=0; j<IDELEMS(id); j++) { |
---|
115 | if(NULL != id->m[j]) { |
---|
116 | if(pComparePolys(id->m[j],ONE)) { |
---|
117 | Print("One Polynomial in Input => Computations stopped\n"); |
---|
118 | ideal id_new = idInit(1,1); |
---|
119 | id_new->m[0] = ONE; |
---|
120 | return(id_new); |
---|
121 | } |
---|
122 | } |
---|
123 | } |
---|
124 | |
---|
125 | id = kInterRed(id,0); |
---|
126 | qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]); |
---|
127 | idShow(id); |
---|
128 | i = 1; |
---|
129 | //lp->setIndex(&i); |
---|
130 | //lp->setTerm(&ONE); |
---|
131 | //lp->setPoly(&id->m[0]); |
---|
132 | //lp->set(ONE,1,ONE); |
---|
133 | /* if(generate_input_list(lp,iTmp,ONE)) { |
---|
134 | Print("One Polynomial in Input => Computations stopped"); |
---|
135 | iTmp = idInit(1,0); |
---|
136 | iTmp->m[0] = ONE; |
---|
137 | return(iTmp); |
---|
138 | } |
---|
139 | */ |
---|
140 | // only for debugging |
---|
141 | long k = 1; |
---|
142 | LList* g_prev = new LList(lp); |
---|
143 | //LList* g_curr = new LList; |
---|
144 | //LNode* current = new LNode; |
---|
145 | g_prev->append(&ONE,&k,&id->m[2]); |
---|
146 | i = g_prev->getLength(); |
---|
147 | Print("%ld\n\n",i); |
---|
148 | LPoly* current = g_prev->getFirst()->getLPoly(); |
---|
149 | if(pComparePolys(current->getPoly(), id->m[0])) { |
---|
150 | Print("Yes!\n"); |
---|
151 | } |
---|
152 | //current = g_prev->getFirst(); |
---|
153 | //current++; |
---|
154 | //Print("Term: %ld\n\n",current->get()->getTerm); |
---|
155 | /*for(i=2; i<IDELEMS(id); i++) { |
---|
156 | g_curr = F5inc(i,g_prev); |
---|
157 | if(g_curr->poly_test(ONE)) { |
---|
158 | Print("One Polynomial in Input => Computations stopped\n"); |
---|
159 | ideal id_new = idInit(1,1); |
---|
160 | id_new->m[0] = ONE; |
---|
161 | return(id_new); |
---|
162 | } |
---|
163 | } |
---|
164 | */ |
---|
165 | return(id); |
---|
166 | |
---|
167 | |
---|
168 | } |
---|
169 | |
---|
170 | |
---|
171 | #endif |
---|