[f7aaec3] | 1 | /////////////////////////////////////////////////////////////////////////////// |
---|
[7f3ad4] | 2 | version="$Id: compregb.lib,v 1.3 2009-01-14 16:07:03 Singular Exp $"; |
---|
[f7aaec3] | 3 | category="General purpose"; |
---|
| 4 | info=" |
---|
[270ff6] | 5 | LIBRARY: compregb.lib experimental implementation for comprehensive Groebner systems |
---|
[f7aaec3] | 6 | AUTHOR: Akira Suzuki (http://kurt.scitec.kobe-u.ac.jp/~sakira/CGBusingGB/) |
---|
[270ff6] | 7 | (<sakira@kobe-u.ac.jp>) |
---|
| 8 | OVERVIEW: |
---|
| 9 | see \"A Simple Algorithm to compute Comprehensive Groebner Bases using Groebner |
---|
| 10 | Bases\" by Akira Suzuki and Yosuke Sato for details. |
---|
[f7aaec3] | 11 | |
---|
| 12 | PROCEDURES: |
---|
[270ff6] | 13 | cgs(polys,vars,pars,R1,R2); comprehensive Groebner systems |
---|
| 14 | base2str(G); pretty print of the result G |
---|
| 15 | |
---|
| 16 | KEYWORDS: comprehensive Groebner system |
---|
[f7aaec3] | 17 | "; |
---|
[270ff6] | 18 | /////////////////////////////////////////////////////////////////////////////// |
---|
[f7aaec3] | 19 | // global variables are the followings: |
---|
| 20 | // Parameters, Variables, VMinDPoly, |
---|
| 21 | // RingAll, RingVar; |
---|
| 22 | |
---|
[270ff6] | 23 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 24 | static proc setup_special_dpolys() |
---|
[f7aaec3] | 25 | { |
---|
| 26 | poly VMinDPoly = Variables[size(Variables)]; |
---|
| 27 | export(VMinDPoly); |
---|
| 28 | } |
---|
| 29 | |
---|
[270ff6] | 30 | static proc newcasebasis(poly Case, ideal Basis) |
---|
[f7aaec3] | 31 | { |
---|
| 32 | list CB = Case, Basis; |
---|
| 33 | return(CB); |
---|
| 34 | } |
---|
| 35 | |
---|
[270ff6] | 36 | static proc contains(poly Vari, list Varis) |
---|
[f7aaec3] | 37 | { |
---|
| 38 | int l = size(Varis); |
---|
| 39 | for (int i = 1; i <= l; i ++) |
---|
| 40 | { |
---|
| 41 | if (Vari == Varis[i]) |
---|
| 42 | { |
---|
| 43 | return(1); |
---|
| 44 | } |
---|
| 45 | } |
---|
| 46 | |
---|
| 47 | return(0); |
---|
| 48 | } |
---|
| 49 | |
---|
[270ff6] | 50 | static proc polys_heads(list PolyL) |
---|
[f7aaec3] | 51 | { |
---|
| 52 | int i, j; |
---|
| 53 | int length = size(PolyL); |
---|
| 54 | if (!length) |
---|
| 55 | { |
---|
| 56 | return(PolyL); |
---|
| 57 | } |
---|
| 58 | |
---|
| 59 | setring(RingVar); |
---|
| 60 | list PolyL = imap(RingAll, PolyL); |
---|
| 61 | list HCoefs = list(); |
---|
| 62 | length = size(PolyL); |
---|
| 63 | for (i = 1; i <= length; i ++) |
---|
| 64 | { |
---|
| 65 | HCoefs = insert(HCoefs, leadcoef(PolyL[i])); |
---|
| 66 | } |
---|
| 67 | setring(RingAll); |
---|
| 68 | list HCoefs = imap(RingVar, HCoefs); |
---|
| 69 | |
---|
| 70 | list CoefL; |
---|
| 71 | ideal CoefLsub; |
---|
| 72 | poly Coef; |
---|
| 73 | for (i = 1; i <= length; i ++) |
---|
| 74 | { |
---|
| 75 | Coef = HCoefs[i]; |
---|
| 76 | if (typeof(Coef) == "poly") |
---|
| 77 | { |
---|
| 78 | CoefLsub = factorize(Coef, 1); |
---|
| 79 | for (j = 1; j <= size(CoefLsub); j ++) |
---|
| 80 | { |
---|
[7f3ad4] | 81 | if (CoefLsub[j] > 1) |
---|
[f7aaec3] | 82 | { |
---|
[7f3ad4] | 83 | CoefL = insert(CoefL, CoefLsub[j]); |
---|
| 84 | } |
---|
[f7aaec3] | 85 | } |
---|
| 86 | } |
---|
| 87 | } |
---|
| 88 | |
---|
| 89 | for (i = 1; i <= size(CoefL); i ++) |
---|
| 90 | { |
---|
| 91 | Coef = CoefL[i]; |
---|
| 92 | for (j = i + 1; j <= size(CoefL); j ++) |
---|
| 93 | { |
---|
| 94 | if (Coef == CoefL[j]) |
---|
| 95 | { |
---|
[7f3ad4] | 96 | CoefL = delete(CoefL, j); |
---|
| 97 | j --; |
---|
[f7aaec3] | 98 | } |
---|
| 99 | } |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | return(CoefL); |
---|
| 103 | } |
---|
| 104 | |
---|
[270ff6] | 105 | static proc polys_restrict_v(ideal Polys) |
---|
[f7aaec3] | 106 | { |
---|
| 107 | return(polys_separate_v_p(Polys)[0]); |
---|
| 108 | } |
---|
| 109 | |
---|
[270ff6] | 110 | static proc polys_restrict_p(ideal Polys) |
---|
[f7aaec3] | 111 | { |
---|
| 112 | return(polys_separate_v_p(Polys)[1]); |
---|
| 113 | } |
---|
| 114 | |
---|
[270ff6] | 115 | static proc polys_separate_v_p(ideal Polys) |
---|
[f7aaec3] | 116 | { |
---|
| 117 | list R_v, R_p; |
---|
| 118 | poly P; |
---|
| 119 | int length = size(Polys); |
---|
[a1c745] | 120 | |
---|
[f7aaec3] | 121 | for (int i = 1; i <= length; i ++) |
---|
| 122 | { |
---|
| 123 | P = Polys[i]; |
---|
| 124 | if (P < VMinDPoly) |
---|
| 125 | { |
---|
| 126 | R_p = insert(R_p, P); |
---|
| 127 | } |
---|
| 128 | else |
---|
| 129 | { |
---|
| 130 | R_v = insert(R_v, P); |
---|
| 131 | } |
---|
| 132 | } |
---|
| 133 | |
---|
| 134 | return(R_v, R_p); |
---|
| 135 | } |
---|
| 136 | |
---|
[270ff6] | 137 | static proc cgs_main(ideal Polys) |
---|
[f7aaec3] | 138 | { |
---|
| 139 | ideal F; |
---|
| 140 | list FP, FV, HFact, Bases; |
---|
| 141 | poly H; |
---|
| 142 | int i; |
---|
| 143 | |
---|
| 144 | // F = groebner(Polys); |
---|
| 145 | F = slimgb(Polys); |
---|
| 146 | |
---|
| 147 | if (F[1] == 1) |
---|
| 148 | { |
---|
| 149 | return(list()); |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | FV, FP = polys_separate_v_p(F); |
---|
| 153 | |
---|
| 154 | HFact = polys_heads(FV); |
---|
| 155 | int HFL = size(HFact); |
---|
| 156 | |
---|
| 157 | H = 1; |
---|
| 158 | for (i = 1; i <= HFL; i ++) |
---|
| 159 | { |
---|
| 160 | H = H * HFact[i]; |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | Bases = insert(Bases, list(H, F)); |
---|
| 164 | |
---|
| 165 | for (i = 1; i <= HFL; i ++) |
---|
| 166 | { |
---|
| 167 | // print("paras:" + string(FP)); |
---|
| 168 | // print("ideal:" + string(HFact[i])); |
---|
| 169 | Bases = cgs_main(F + ideal(HFact[i])) + Bases; |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | return(Bases); |
---|
| 173 | } |
---|
| 174 | |
---|
| 175 | proc cgs(ideal Polys, list Vars, list Paras, RingVar, RingAll) |
---|
[270ff6] | 176 | "USAGE: cgs(Polys,Vars,Paras,RingVar,RingAll); Polys an ideal, Vars, the list |
---|
| 177 | of variables, Paras the list of parameters, RingVar the ring with |
---|
| 178 | Paras as parameters, RingAll the ring with Paras as variables |
---|
| 179 | (RingAll should be the current ring) |
---|
| 180 | RETURN: a list L of lists L[i] of a polynomial and an ideal: |
---|
| 181 | L[i][1] the polynomial giving the condition on the parameters |
---|
[a1c745] | 182 | L[i][2] the Groebner basis for this case |
---|
[270ff6] | 183 | EXAMPLE: example cgs; shows an example |
---|
| 184 | " |
---|
[f7aaec3] | 185 | { |
---|
| 186 | option(redSB); |
---|
| 187 | list Parameters = Paras; |
---|
| 188 | list Variables = Vars; |
---|
| 189 | poly VMinDPoly = Vars[size(Vars)]; |
---|
| 190 | export(Parameters, Variables, VMinDPoly); |
---|
| 191 | |
---|
| 192 | export(RingVar, RingAll); |
---|
| 193 | setring(RingAll); |
---|
| 194 | |
---|
| 195 | list G = cgs_main(Polys); |
---|
| 196 | |
---|
| 197 | keepring(RingAll); |
---|
| 198 | return(G); |
---|
| 199 | } |
---|
[270ff6] | 200 | example |
---|
[a1c745] | 201 | { "EXAMPLE:";echo=2; |
---|
| 202 | ring RingVar=(0,a,b),(x,y,t),lp; |
---|
[270ff6] | 203 | ring RingAll=0,(x,y,t,a,b),(lp(3),dp); |
---|
[a1c745] | 204 | ideal polys=x^3-a,y^4-b,x+y-t; |
---|
| 205 | list vars=x,y,t; |
---|
[270ff6] | 206 | list paras=a,b; |
---|
| 207 | list G = cgs(polys,vars,paras,RingVar,RingAll); |
---|
| 208 | G; |
---|
| 209 | } |
---|
[f7aaec3] | 210 | proc basis2str(list B) |
---|
| 211 | { |
---|
| 212 | string Str; |
---|
| 213 | ideal Factors; |
---|
| 214 | int i; |
---|
| 215 | |
---|
| 216 | Str = "("; |
---|
| 217 | Factors = factorize(B[1], 1); |
---|
| 218 | for (i = 1; i <= size(Factors); i ++) |
---|
| 219 | { |
---|
| 220 | Str = Str + "(" + string(Factors[i]) + ")"; |
---|
| 221 | } |
---|
| 222 | Str = Str + "!=0,"; |
---|
| 223 | |
---|
| 224 | list FV, FP; |
---|
| 225 | FV, FP = polys_separate_v_p(B[2]); |
---|
| 226 | for (i = 1; i <= size(FP); i ++) |
---|
| 227 | { |
---|
| 228 | Str = Str + string(FP[i]) + "=0,"; |
---|
| 229 | } |
---|
| 230 | |
---|
| 231 | if (size(Str) > 1) |
---|
| 232 | { |
---|
| 233 | Str = Str[1, size(Str) - 1] + ")["; |
---|
| 234 | } |
---|
| 235 | else |
---|
| 236 | { |
---|
| 237 | Str = "()["; |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | if (size(FV)) |
---|
| 241 | { |
---|
| 242 | for (i = 1; i <= size(FV); i ++) |
---|
| 243 | { |
---|
| 244 | Str = Str + string(FV[i]) + ","; |
---|
| 245 | } |
---|
| 246 | |
---|
| 247 | Str = Str[1, size(Str) - 1] + "]"; |
---|
| 248 | } |
---|
| 249 | else |
---|
| 250 | { |
---|
| 251 | Str += "]"; |
---|
| 252 | } |
---|
| 253 | |
---|
| 254 | return(Str); |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | proc bases2str(list Bases) |
---|
| 258 | { |
---|
| 259 | string Str; |
---|
| 260 | int i; |
---|
| 261 | |
---|
| 262 | Str = ""; |
---|
| 263 | for (i = 1; i <= size(Bases); i ++) |
---|
| 264 | { |
---|
| 265 | Str = Str + basis2str(Bases[i]) + newline; |
---|
| 266 | } |
---|
[a1c745] | 267 | |
---|
[f7aaec3] | 268 | return(Str); |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | /* |
---|
| 272 | ring RingVar=(0,a,b),(x,y,t),lp; ring RingAll=0,(x,y,t,a,b),(lp(3),dp); |
---|
| 273 | ideal polys=x^3-a,y^4-b,x+y-t; list vars=x,y,t; list paras=a,b; |
---|
| 274 | list G = cgs(polys,vars,paras,RingVar,RingAll); |
---|
| 275 | bases2str(G); |
---|
| 276 | */ |
---|