1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* $Id: f5gb.cc,v 1.9 2008-08-07 13:18:36 Singular Exp $ */ |
---|
5 | /* |
---|
6 | * ABSTRACT: f5gb interface |
---|
7 | */ |
---|
8 | #include "mod2.h" |
---|
9 | |
---|
10 | #ifdef HAVE_F5 |
---|
11 | #include "kutil.h" |
---|
12 | #include "structs.h" |
---|
13 | #include "omalloc.h" |
---|
14 | #include "polys.h" |
---|
15 | #include "p_polys.h" |
---|
16 | #include "ideals.h" |
---|
17 | #include "febase.h" |
---|
18 | #include "kstd1.h" |
---|
19 | #include "khstd.h" |
---|
20 | #include "kbuckets.h" |
---|
21 | #include "weight.h" |
---|
22 | #include "intvec.h" |
---|
23 | #include "pInline1.h" |
---|
24 | #include "f5gb.h" |
---|
25 | #include "lpolynom.h" |
---|
26 | |
---|
27 | |
---|
28 | /*2 |
---|
29 | * sorting ideals by decreasing total degree |
---|
30 | * "left" and "right" are the pointer of the first |
---|
31 | * and last polynomial in the considered ideal |
---|
32 | */ |
---|
33 | void qsort_degree(poly* left, poly* right) |
---|
34 | { |
---|
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 | qsort_degree(left,ptr2); |
---|
56 | } |
---|
57 | if(ptr1 < right){ |
---|
58 | qsort_degree(ptr1,right); |
---|
59 | } |
---|
60 | } |
---|
61 | |
---|
62 | |
---|
63 | /*2 |
---|
64 | * computes incrementally gbs of subsets of the input |
---|
65 | * gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} |
---|
66 | */ |
---|
67 | lpoly *f5_inc(lpoly* lp, lpoly* g_prev) |
---|
68 | { |
---|
69 | |
---|
70 | |
---|
71 | return lp; |
---|
72 | } |
---|
73 | |
---|
74 | |
---|
75 | /*2 |
---|
76 | * computes a gb of the ideal i in the ring r with our f5 |
---|
77 | * implementation |
---|
78 | */ |
---|
79 | ideal F5main(ideal i, ring r) |
---|
80 | { |
---|
81 | ideal iTmp, g_basis; |
---|
82 | long j, k; |
---|
83 | poly one = pInit(); |
---|
84 | pSetCoeff(one, nInit(1)); |
---|
85 | pWrite(one); |
---|
86 | lpoly *lp, *gb; |
---|
87 | intvec* sort; |
---|
88 | iTmp = idInit(IDELEMS(i),i->rank); |
---|
89 | |
---|
90 | for(j=0; j<IDELEMS(i); j++) |
---|
91 | { |
---|
92 | if(NULL != i->m[j]) |
---|
93 | { |
---|
94 | iTmp->m[j] = i->m[j]; |
---|
95 | } |
---|
96 | } |
---|
97 | |
---|
98 | iTmp = kInterRed(i,0); |
---|
99 | qsort_degree(&iTmp->m[0],&iTmp->m[IDELEMS(iTmp)-1]); |
---|
100 | idShow(iTmp); |
---|
101 | |
---|
102 | lp = new lpoly[IDELEMS(iTmp)]; |
---|
103 | |
---|
104 | for(j=0; j <IDELEMS(iTmp); j++){ |
---|
105 | lp[j].setPoly(iTmp->m[j]); |
---|
106 | |
---|
107 | if(pComparePolys(lp[j].getPoly(), one)){ |
---|
108 | Print("1 in GB"); |
---|
109 | return(NULL); |
---|
110 | } |
---|
111 | |
---|
112 | lp[j].setIndex(j+1); |
---|
113 | lp[j].setTerm(one); |
---|
114 | Print("Labeled Polynomial %d: ",j+1); |
---|
115 | Print("Signature Term: "); |
---|
116 | pWrite(lp[j].getTerm()); |
---|
117 | Print("Signature Index: %d\n", lp[j].getIndex()); |
---|
118 | pWrite(lp[j].getPoly()); |
---|
119 | Print("\n\n"); |
---|
120 | |
---|
121 | } |
---|
122 | |
---|
123 | // PROBLEM: muss signatur mitliefern, daher datentyp |
---|
124 | // ideal nicht zu gebrauchen? |
---|
125 | gb = new lpoly; |
---|
126 | gb = &lp[IDELEMS(iTmp)-1]; |
---|
127 | pWrite((*gb).getPoly()); |
---|
128 | |
---|
129 | for(j=IDELEMS(iTmp)-2; j>0; j--){ |
---|
130 | //PROBLEM: muss dynamisch Speicher allozieren |
---|
131 | gb = f5_inc(&lp[j], gb); |
---|
132 | for(k=0; k< IDELEMS(iTmp); k++){ |
---|
133 | if(gb[k].getPoly()){ |
---|
134 | } |
---|
135 | } |
---|
136 | |
---|
137 | |
---|
138 | |
---|
139 | |
---|
140 | } |
---|
141 | |
---|
142 | |
---|
143 | |
---|
144 | |
---|
145 | return iTmp; |
---|
146 | } |
---|
147 | |
---|
148 | |
---|
149 | #endif |
---|