[5482cda] | 1 | //////////////////////////////////////////////////////////////// |
---|
[6391eb] | 2 | version="version fpaprops.lib 4.1.2.0 Feb_2019 "; // $Id$ |
---|
[5482cda] | 3 | category="Noncommutative"; |
---|
| 4 | info=" |
---|
[7a968b] | 5 | LIBRARY: fpaprops.lib Algorithmic ring-theoretic properties of finitely presented algebras (Letterplace) |
---|
[5482cda] | 6 | AUTHORS: Karim Abou Zeid, karim.abou.zeid at rwth-aachen.de |
---|
| 7 | |
---|
[5edf31] | 8 | Support: Project II.6 in the transregional collaborative research centre |
---|
[b4ab792] | 9 | SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG |
---|
[5edf31] | 10 | |
---|
[5482cda] | 11 | OVERVIEW: |
---|
[ccef1e] | 12 | In this library, algorithms for computing various ring-theoretic properties of |
---|
| 13 | finitely presented algebras are implemented. |
---|
| 14 | Applicability: Letterplace rings. |
---|
[5482cda] | 15 | |
---|
| 16 | REFERENCES: |
---|
| 17 | Huishi Li: Groebner bases in ring theory. World Scientific, 2010. |
---|
| 18 | |
---|
[4aa50a] | 19 | KEYWORDS: finitely presented algebra; ring theory; Letterplace Groebner basis; |
---|
[6276a9] | 20 | growth of algebra; Gelfand-Kirillov dimension; global homological dimension; semi-prime ideal; Ufnarovski graph |
---|
[7a968b] | 21 | |
---|
[5edf31] | 22 | SEE ALSO: fpadim_lib, freegb_lib |
---|
[5482cda] | 23 | |
---|
| 24 | PROCEDURES: |
---|
[3d9a64] | 25 | lpNoetherian(<GB>); check whether A/<LM(GB)> is (left/right) Noetherian |
---|
[7a968b] | 26 | lpIsSemiPrime(<GB>); check whether A/<LM(GB)> is semi-prime |
---|
[cb8c57] | 27 | lpIsPrime(<GB>); check whether A/<LM(GB)> is prime |
---|
[6107b2] | 28 | lpGkDim(<GB>); compute the Gelfand Kirillov dimension of A/<GB> |
---|
| 29 | lpGlDimBound(<GB>); compute an upper bound for the global dimension of A/<GB> |
---|
[7a968b] | 30 | lpSubstitute(); substitute a variable with polynomials (ring homomorphism) |
---|
[ccef1e] | 31 | lpUfGraph(<GB>); constructs the Ufnarovskij graph for <LM(GB)> |
---|
[16610f] | 32 | lpCalcSubstDegBound(); utility for lpSubstitute |
---|
[5482cda] | 33 | "; |
---|
| 34 | |
---|
| 35 | LIB "fpadim.lib"; |
---|
[ccef1e] | 36 | |
---|
[7a968b] | 37 | /* very fast and cheap test of consistency and functionality |
---|
| 38 | DO NOT make it static ! |
---|
| 39 | after adding the new proc, add it here */ |
---|
[ccef1e] | 40 | proc tstfpaprops() |
---|
| 41 | { |
---|
| 42 | example lpNoetherian; |
---|
| 43 | example lpIsSemiPrime; |
---|
| 44 | example lpIsPrime; |
---|
| 45 | example lpGkDim; |
---|
| 46 | example lpGlDimBound; |
---|
| 47 | example lpSubstitute; |
---|
| 48 | example lpUfGraph; |
---|
[4aa50a] | 49 | example lpCalcSubstDegBound; |
---|
[ccef1e] | 50 | }; |
---|
| 51 | |
---|
| 52 | |
---|
[5482cda] | 53 | //////////////////////////////////////////////////////////////////// |
---|
| 54 | proc lpNoetherian(ideal G) |
---|
| 55 | "USAGE: lpNoetherian(G); G an ideal in a Letterplace ring |
---|
| 56 | RETURN: int |
---|
[dfa15b] | 57 | 0 not Noetherian |
---|
| 58 | 1 left Noetherian |
---|
| 59 | 2 right Noetherian |
---|
| 60 | 3 Noetherian |
---|
| 61 | 4 weak Noetherian |
---|
[c1af7f] | 62 | PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian |
---|
[5482cda] | 63 | ASSUME: - basering is a Letterplace ring |
---|
[dfa15b] | 64 | - G is a Groebner basis |
---|
[3d9a64] | 65 | THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>. |
---|
[3ad764] | 66 | If it gives an affirmative answer for one of the properties, then it |
---|
| 67 | holds for both A/<LM(G)> and A/<G>. However, a negative answer applies |
---|
[3d9a64] | 68 | only to A/<LM(G)> and not necessarily to A/<G>. |
---|
[fba1c39] | 69 | NOTE: Weak Noetherian means that two-sided ideals in A/<LM(G)> satisfy |
---|
[3d9a64] | 70 | the acc (ascending chain condition). |
---|
[5482cda] | 71 | " |
---|
| 72 | { |
---|
| 73 | G = lead(G); |
---|
| 74 | G = simplify(G, 2+4+8); |
---|
| 75 | |
---|
| 76 | // check special case 1 |
---|
| 77 | int l = 0; |
---|
| 78 | for (int i = 1; i <= size(G); i++) { |
---|
| 79 | // find the max degree in G |
---|
| 80 | int d = deg(G[i]); |
---|
| 81 | if (d > l) { |
---|
| 82 | l = d; |
---|
| 83 | } |
---|
| 84 | |
---|
| 85 | // also if G is the whole ring |
---|
| 86 | if (leadmonom(G[i]) == 1) { |
---|
| 87 | ERROR("noetherianity not defined for 0-ring") |
---|
| 88 | } |
---|
[4d9f75e] | 89 | kill d; |
---|
| 90 | } kill i; |
---|
[5482cda] | 91 | // if longest word has length 1 we handle it as a special case |
---|
| 92 | if (l == 1) { |
---|
[921f32] | 93 | int n = lpVarBlockSize(basering); // variable count |
---|
[5482cda] | 94 | int k = size(G); |
---|
| 95 | if (k == n) { // only the field left |
---|
| 96 | return(3); // every field is noetherian |
---|
| 97 | } |
---|
| 98 | if (k == n-1) { // V = {1} with loop |
---|
| 99 | return(3); |
---|
| 100 | } |
---|
| 101 | if (k <= n-2) { // V = {1} with more than one loop |
---|
| 102 | return(0); |
---|
| 103 | } |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | intmat UG = lpUfGraph(G); |
---|
| 107 | |
---|
| 108 | // check special case 2 |
---|
| 109 | intmat zero[nrows(UG)][ncols(UG)]; |
---|
| 110 | if (UG == zero) { |
---|
| 111 | return (3); |
---|
| 112 | } |
---|
| 113 | |
---|
| 114 | if (!imHasLoops(UG) && imIsUpRightTriangle(topologicalSort(UG))) { |
---|
| 115 | // UG is a DAG |
---|
| 116 | return (3); |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | // DFS from every vertex, if cycle is found, check every vertex for incomming/outcom |
---|
| 120 | intvec visited; |
---|
| 121 | visited[ncols(UG)] = 0; |
---|
[c0631ae] | 122 | int inFlag, outFlag, inOutFlag; |
---|
[5482cda] | 123 | for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) { |
---|
[c0631ae] | 124 | int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0); |
---|
[5482cda] | 125 | if (inOutFlags == 1) { |
---|
| 126 | inFlag = 1; |
---|
| 127 | } |
---|
| 128 | if (inOutFlags == 2) { |
---|
[c0631ae] | 129 | outFlag = 1; |
---|
[5482cda] | 130 | } |
---|
| 131 | if (inOutFlags == 3) { |
---|
| 132 | inFlag = 1; |
---|
[c0631ae] | 133 | outFlag = 1; |
---|
| 134 | } |
---|
| 135 | if (inOutFlags == 4) { |
---|
| 136 | inOutFlag = 1; |
---|
| 137 | } |
---|
| 138 | if (inOutFlags == 5) { |
---|
| 139 | inFlag = 1; |
---|
| 140 | inOutFlag = 1; |
---|
| 141 | } |
---|
| 142 | if (inOutFlags == 6) { |
---|
| 143 | outFlag = 1; |
---|
| 144 | inOutFlag = 1; |
---|
| 145 | } |
---|
| 146 | if (inOutFlags == 7) { |
---|
| 147 | inFlag = 1; |
---|
| 148 | outFlag = 1; |
---|
| 149 | inOutFlag = 1; |
---|
[5482cda] | 150 | } |
---|
[4d9f75e] | 151 | kill inOutFlags; |
---|
| 152 | } kill v; |
---|
[c0631ae] | 153 | int noetherian = 3 - 1*inFlag - 2*outFlag; |
---|
| 154 | if (noetherian == 0) { |
---|
| 155 | return (4 - 4*inOutFlag); // weak noetherian |
---|
| 156 | } |
---|
| 157 | return (noetherian); |
---|
[5482cda] | 158 | } |
---|
[7e51648] | 159 | example |
---|
| 160 | { |
---|
[b4ab792] | 161 | "EXAMPLE:"; echo = 2; |
---|
| 162 | ring r = 0,(x,y),dp; |
---|
[fceb4e] | 163 | def R = freeAlgebra(r, 5); |
---|
[b4ab792] | 164 | setring R; |
---|
[6a4f0d] | 165 | ideal G = x*x, y*x; // K<x,y>/<xx,yx> is right noetherian |
---|
[b4ab792] | 166 | lpNoetherian(G); |
---|
| 167 | } |
---|
[5482cda] | 168 | |
---|
[c0631ae] | 169 | static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) { |
---|
[5482cda] | 170 | // Mark the current vertex as visited |
---|
| 171 | visited[v] = 1; |
---|
| 172 | |
---|
| 173 | // Store the current vertex in path |
---|
| 174 | if (path[1] == 0) { |
---|
| 175 | path[1] = v; |
---|
| 176 | } else { |
---|
| 177 | path[size(path) + 1] = v; |
---|
| 178 | } |
---|
| 179 | |
---|
[c0631ae] | 180 | int inFlag, outFlag, inOutFlag; |
---|
[5482cda] | 181 | |
---|
| 182 | for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) { |
---|
| 183 | if (G[v,w] == 1) { |
---|
[c0631ae] | 184 | if (visited[w] == 1) { // new cycle |
---|
| 185 | int tmpInFlag; |
---|
| 186 | int tmpOutFlag; |
---|
| 187 | if (v == w) { // cycle is a loop |
---|
[5482cda] | 188 | for (int u = 1; u <= ncols(G); u++) { |
---|
| 189 | if (G[v,u] && u != v) { |
---|
[c0631ae] | 190 | outFlag = 1; |
---|
| 191 | tmpOutFlag = 1; |
---|
[5482cda] | 192 | } |
---|
| 193 | if (G[u,v] && u != v) { |
---|
| 194 | inFlag = 1; |
---|
[c0631ae] | 195 | tmpInFlag = 1; |
---|
[5482cda] | 196 | } |
---|
[4d9f75e] | 197 | } kill u; |
---|
[5482cda] | 198 | } else { |
---|
| 199 | for (int i = size(path); i >= 1; i--) { // for each vertex in the path |
---|
| 200 | // check for neighbors not directly next or prev in cycle |
---|
| 201 | for (int u = 1; u <= ncols(G); u++) { |
---|
| 202 | if (G[path[i],u] == 1) { // there is an edge to u |
---|
| 203 | if (path[i] != v) { |
---|
| 204 | if (u != path[i+1]) { // and u is not the next element in the cycle |
---|
[c0631ae] | 205 | outFlag = 1; |
---|
| 206 | tmpOutFlag = 1; |
---|
[5482cda] | 207 | } |
---|
| 208 | } else { |
---|
| 209 | if (u != w) { |
---|
[c0631ae] | 210 | outFlag = 1; |
---|
| 211 | tmpOutFlag = 1; |
---|
[5482cda] | 212 | } |
---|
| 213 | } |
---|
| 214 | } |
---|
| 215 | if (G[u,path[i]] == 1) { // there is an edge from u |
---|
| 216 | if (path[i] != w) { |
---|
| 217 | if (u != path[i-1]) { // and u is not the previous element in the cylce |
---|
| 218 | inFlag = 1; |
---|
[c0631ae] | 219 | tmpInFlag = 1; |
---|
[5482cda] | 220 | } |
---|
| 221 | } else { |
---|
| 222 | if (u != v) { |
---|
| 223 | inFlag = 1; |
---|
[c0631ae] | 224 | tmpInFlag = 1; |
---|
[5482cda] | 225 | } |
---|
| 226 | } |
---|
| 227 | } |
---|
[4d9f75e] | 228 | } kill u; |
---|
[5482cda] | 229 | if (path[i] == w) { |
---|
| 230 | break; |
---|
| 231 | } |
---|
[4d9f75e] | 232 | } kill i; |
---|
[5482cda] | 233 | } |
---|
[c0631ae] | 234 | if (tmpInFlag > 0 && tmpOutFlag > 0) { |
---|
| 235 | // there are both in and outcomming edges in this cycle |
---|
| 236 | inOutFlag = 1; |
---|
| 237 | } |
---|
| 238 | kill tmpInFlag; |
---|
| 239 | kill tmpOutFlag; |
---|
[5482cda] | 240 | } else { |
---|
[c0631ae] | 241 | int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path); |
---|
[5482cda] | 242 | if (inOutFlags == 1) { |
---|
| 243 | inFlag = 1; |
---|
| 244 | } |
---|
| 245 | if (inOutFlags == 2) { |
---|
[c0631ae] | 246 | outFlag = 1; |
---|
[5482cda] | 247 | } |
---|
| 248 | if (inOutFlags == 3) { |
---|
| 249 | inFlag = 1; |
---|
[c0631ae] | 250 | outFlag = 1; |
---|
| 251 | } |
---|
| 252 | if (inOutFlags == 4) { |
---|
| 253 | inOutFlag = 1; |
---|
| 254 | } |
---|
| 255 | if (inOutFlags == 5) { |
---|
| 256 | inFlag = 1; |
---|
| 257 | inOutFlag = 1; |
---|
| 258 | } |
---|
| 259 | if (inOutFlags == 6) { |
---|
| 260 | outFlag = 1; |
---|
| 261 | inOutFlag = 1; |
---|
| 262 | } |
---|
| 263 | if (inOutFlags == 7) { |
---|
| 264 | inFlag = 1; |
---|
| 265 | outFlag = 1; |
---|
| 266 | inOutFlag = 1; |
---|
[5482cda] | 267 | } |
---|
[4d9f75e] | 268 | kill inOutFlags; |
---|
[5482cda] | 269 | } |
---|
| 270 | } |
---|
[4d9f75e] | 271 | } kill w; |
---|
[5482cda] | 272 | |
---|
[c0631ae] | 273 | return (1*inFlag + 2*outFlag + 4*inOutFlag); |
---|
[5482cda] | 274 | } |
---|
| 275 | |
---|
| 276 | proc lpIsSemiPrime(ideal G) |
---|
| 277 | "USAGE: lpIsSemiPrime(G); G an ideal in a Letterplace ring |
---|
| 278 | RETURN: boolean |
---|
[d528f62] | 279 | PURPOSE: Check whether A/<LM(G)> is semi-prime ring, |
---|
| 280 | alternatively whether <LM(G)> is a semi-prime ideal in A. |
---|
[5482cda] | 281 | ASSUME: - basering is a Letterplace ring |
---|
[5edf31] | 282 | - G is a Groebner basis |
---|
[d528f62] | 283 | THEORY: A (two-sided) ideal I in the ring A is semi-prime, if for any a in A one has |
---|
| 284 | aAa subseteq I implies a in I. |
---|
| 285 | NOTE: lpIsSemiPrime works with the monomial algebra A/<LM(G)>. |
---|
[3ad764] | 286 | A positive answer holds for both A/<LM(G)> and A/<G>, while |
---|
| 287 | a negative answer applies only to A/<LM(G)> and not necessarily to |
---|
[3d9a64] | 288 | A/<G>. |
---|
[5482cda] | 289 | " |
---|
| 290 | { |
---|
[d528f62] | 291 | // old theory part: that is when p * (A/<LM(G)>) * p != 0 for all p in (A/<LM(G)> - {0}). |
---|
[5482cda] | 292 | G = lead(G); |
---|
| 293 | G = simplify(G, 2+4+8); |
---|
| 294 | |
---|
| 295 | // check special case 1 |
---|
| 296 | int l = 0; |
---|
| 297 | for (int i = 1; i <= size(G); i++) { |
---|
| 298 | // find the max degree in G |
---|
| 299 | int d = deg(G[i]); |
---|
| 300 | if (d > l) { |
---|
| 301 | l = d; |
---|
| 302 | } |
---|
| 303 | |
---|
| 304 | // also if G is the whole ring |
---|
| 305 | if (leadmonom(G[i]) == 1) { |
---|
| 306 | ERROR("primeness not defined for 0-ring") |
---|
| 307 | } |
---|
[4d9f75e] | 308 | kill d; |
---|
| 309 | } kill i; |
---|
[5482cda] | 310 | // if longest word has length 1 we handle it as a special case |
---|
| 311 | if (l == 1) { |
---|
| 312 | return(1); |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | list VUG = lpUfGraph(G, 1); |
---|
| 316 | intmat UG = VUG[1]; // the Ufnarovskij graph |
---|
| 317 | ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1) |
---|
| 318 | |
---|
| 319 | list LG = lpId2ivLi(G); |
---|
| 320 | list SW = ivStandardWordsUpToLength(LG, maxDeg(G)); |
---|
| 321 | list LV = lpId2ivLi(V); |
---|
| 322 | |
---|
| 323 | // delete the 0 in SW |
---|
| 324 | int indexofzero = ivIndexOf(SW, 0); |
---|
| 325 | if (indexofzero > 0) { // should be always true when |SW| > 0 |
---|
| 326 | SW = delete(SW, indexofzero); |
---|
| 327 | } |
---|
| 328 | |
---|
| 329 | // check if each monomial in SW is cyclic |
---|
| 330 | for (int i = 1; i <= size(SW); i++) { |
---|
| 331 | if (!isCyclicInUfGraph(UG, LV, SW[i])) { |
---|
| 332 | return (0); |
---|
| 333 | } |
---|
[4d9f75e] | 334 | } kill i; |
---|
[5482cda] | 335 | |
---|
| 336 | return (1); |
---|
| 337 | } |
---|
[7e51648] | 338 | example |
---|
| 339 | { |
---|
[b4ab792] | 340 | "EXAMPLE:"; echo = 2; |
---|
| 341 | ring r = 0,(x1,x2),dp; |
---|
[fceb4e] | 342 | def R = freeAlgebra(r, 5); |
---|
[b4ab792] | 343 | setring R; |
---|
[6a4f0d] | 344 | ideal G = x1*x2, x2*x1; // K<x1,x2>/<x1*x2,x2*x1> is semi prime |
---|
[b4ab792] | 345 | lpIsSemiPrime(G); |
---|
| 346 | } |
---|
[5482cda] | 347 | |
---|
| 348 | // checks whether a monomial is a cyclic monomial |
---|
| 349 | static proc isCyclicInUfGraph(intmat UG, list LV, intvec u) |
---|
| 350 | { |
---|
| 351 | if (ncols(UG) == 0) {return (0);} // UG is empty |
---|
| 352 | if (u == 0) {return (0);} // 0 is never cyclic |
---|
| 353 | |
---|
| 354 | int l = size(LV[1]) + 1; |
---|
| 355 | |
---|
| 356 | int s = size(u); |
---|
| 357 | if (s <= l - 1) { |
---|
| 358 | for (int i = 1; i <= size(LV); i++) { |
---|
| 359 | // for all vertices where u is a suffix |
---|
| 360 | if(isSF(u, LV[i])) { |
---|
| 361 | if (existsRoute(UG, i, i)) { |
---|
| 362 | return (1); |
---|
| 363 | } |
---|
| 364 | } |
---|
[4d9f75e] | 365 | } kill i; |
---|
[5482cda] | 366 | } else { // size(u) > l - 1 |
---|
| 367 | int m = s - l + 1; |
---|
| 368 | |
---|
| 369 | // there must be a route from v0 to vm |
---|
| 370 | intvec v0 = u[1..(l-1)]; // first in route of u |
---|
| 371 | intvec vm = u[m+1..m+(l-1)]; // last in route of u |
---|
| 372 | |
---|
| 373 | int iv0 = ivIndexOf(LV, v0); |
---|
| 374 | int ivm = ivIndexOf(LV, vm); |
---|
| 375 | if (iv0 <= 0 || ivm <= 0) { |
---|
| 376 | ERROR("u is not a standard word"); |
---|
| 377 | } |
---|
| 378 | |
---|
| 379 | return (existsRoute(UG, ivm, iv0)); |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | return (0); |
---|
| 383 | } |
---|
| 384 | |
---|
| 385 | proc lpIsPrime(ideal G) |
---|
| 386 | "USAGE: lpIsPrime(G); G an ideal in a Letterplace ring |
---|
| 387 | RETURN: boolean |
---|
[d528f62] | 388 | PURPOSE: Check whether A/<LM(G)> is prime ring, |
---|
| 389 | alternatively whether <LM(G)> is a prime ideal in A. |
---|
[5482cda] | 390 | ASSUME: - basering is a Letterplace ring |
---|
[5edf31] | 391 | - G is a Groebner basis |
---|
[d528f62] | 392 | THEORY: A (two-sided) ideal I in the ring A is prime, if for any a,b in A one has |
---|
| 393 | aAb subseteq I implies a in I or b in I. |
---|
| 394 | NOTE: lpIsPrime works with the monomial algebra A/<LM(G)>. |
---|
[3d9a64] | 395 | A positive answer holds for both A/<LM(G)> and A/<G>, while |
---|
| 396 | a negative answer applies only to A/<LM(G)> and not necessarily to A/<G>. |
---|
[5482cda] | 397 | " |
---|
| 398 | { |
---|
[d528f62] | 399 | // old theory part: that is when p1 * (A/<LM(G)>) * p2 != 0 for all p1, p2 in (A/<LM(G)> - {0}). |
---|
[5482cda] | 400 | G = lead(G); |
---|
| 401 | G = simplify(G, 2+4+8); |
---|
| 402 | |
---|
| 403 | // check special case 1 |
---|
| 404 | int l = 0; |
---|
| 405 | for (int i = 1; i <= size(G); i++) { |
---|
| 406 | // find the max degree in G |
---|
| 407 | int d = deg(G[i]); |
---|
| 408 | if (d > l) { |
---|
| 409 | l = d; |
---|
| 410 | } |
---|
| 411 | |
---|
| 412 | // also if G is the whole ring |
---|
| 413 | if (leadmonom(G[i]) == 1) { |
---|
| 414 | ERROR("primeness not defined for 0-ring") |
---|
| 415 | } |
---|
[4d9f75e] | 416 | kill d; |
---|
| 417 | } kill i; |
---|
[5482cda] | 418 | // if longest word has length 1 we handle it as a special case |
---|
| 419 | if (l == 1) { |
---|
| 420 | return(1); |
---|
| 421 | } |
---|
| 422 | |
---|
| 423 | list VUG = lpUfGraph(G, 1); |
---|
| 424 | intmat UG = VUG[1]; // the Ufnarovskij graph |
---|
| 425 | ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1) |
---|
| 426 | |
---|
| 427 | list LG = lpId2ivLi(G); |
---|
| 428 | list LV = lpId2ivLi(V); |
---|
| 429 | |
---|
| 430 | int n = ncols(UG); |
---|
| 431 | |
---|
| 432 | // 1) for each vi vj there exists a route from vi to vj (means UG is connected) |
---|
| 433 | for (int i = 1; i <= n; i++) { |
---|
| 434 | for (int j = 1; j <= n; j++) { |
---|
| 435 | if (!existsRoute(UG, i, j)) { |
---|
| 436 | return (0); |
---|
| 437 | } |
---|
[4d9f75e] | 438 | } kill j; |
---|
| 439 | } kill i; |
---|
[5482cda] | 440 | |
---|
| 441 | // 2) any standard word with length < l-1 is a suffix of a vertex |
---|
| 442 | list SW = ivStandardWordsUpToLength(LG, maxDeg(G) - 2); // < maxDeg - 1 |
---|
| 443 | if (size(SW) > 0 && size(LV) == 0) {return (0);} |
---|
| 444 | for (int i = 1; i <= size(SW); i++) { |
---|
| 445 | // check if SW[i] is a suffix of some LV |
---|
| 446 | for (int j = 1; j <= size(LV); j++) { |
---|
| 447 | if (!isSF(SW[i], LV[j])) { |
---|
| 448 | if (j == size(LV)) { |
---|
| 449 | return (0); |
---|
| 450 | } |
---|
| 451 | } else { |
---|
| 452 | break; |
---|
| 453 | } |
---|
| 454 | } |
---|
[4d9f75e] | 455 | } kill i; |
---|
[5482cda] | 456 | |
---|
| 457 | return (1); |
---|
| 458 | } |
---|
[7e51648] | 459 | example |
---|
| 460 | { |
---|
[5482cda] | 461 | "EXAMPLE:"; echo = 2; |
---|
| 462 | ring r = 0,(x,y),dp; |
---|
[fceb4e] | 463 | def R = freeAlgebra(r, 5); |
---|
[5482cda] | 464 | setring R; |
---|
[6a4f0d] | 465 | ideal G = x*x, y*y; // K<x,y>/<xx,yy> is prime |
---|
[5482cda] | 466 | lpIsPrime(G); |
---|
| 467 | } |
---|
| 468 | |
---|
| 469 | static proc existsRoute(intmat G, int v, int u, list #) |
---|
| 470 | "USAGE: existsRoute(G,v,u); G a graph, v and u vertices |
---|
| 471 | NOTE: don't pass anything to # (internal use for recursion) |
---|
[5edf31] | 472 | routes always have at least one edge |
---|
[5482cda] | 473 | " |
---|
| 474 | { |
---|
| 475 | int n = ncols(G); |
---|
| 476 | |
---|
| 477 | // init visited |
---|
| 478 | intvec visited; |
---|
| 479 | if (size(#) > 0) { |
---|
| 480 | if (v == u) {return (1);} // don't check on first call so |route| >= 1 holds |
---|
| 481 | visited = #[1]; |
---|
| 482 | } else { // first call |
---|
| 483 | visited[n] = 0; |
---|
| 484 | } |
---|
| 485 | |
---|
| 486 | // mark current vertex as visited |
---|
| 487 | visited[v] = 1; |
---|
| 488 | |
---|
| 489 | // recursive DFS |
---|
| 490 | for (int i = 1; i <= n; i++) { |
---|
| 491 | if (G[v,i] && (!visited[i] || i == u)) { // i == u to allow routes from u to u |
---|
| 492 | if (existsRoute(G, i, u, visited)) { |
---|
| 493 | return (1); |
---|
| 494 | } |
---|
| 495 | } |
---|
[4d9f75e] | 496 | } kill i; |
---|
[5482cda] | 497 | |
---|
| 498 | return (0); |
---|
| 499 | } |
---|
| 500 | |
---|
| 501 | static proc UfGraphURTNZDGrowth(intmat UG) { |
---|
| 502 | // URTNZD = upper right triangle non zero diagonal |
---|
| 503 | for (int i = 1; i <= ncols(UG); i++) { |
---|
| 504 | UG[i,i] = 0; // remove all loops |
---|
[4d9f75e] | 505 | } kill i; |
---|
[5482cda] | 506 | intmat UGk = UG; |
---|
| 507 | intmat zero[nrows(UGk)][ncols(UGk)]; |
---|
| 508 | int k = 1; |
---|
| 509 | while (UGk != zero) { |
---|
| 510 | UGk = UGk * UG; |
---|
| 511 | k++; |
---|
| 512 | } |
---|
| 513 | return (k); |
---|
| 514 | } |
---|
| 515 | |
---|
| 516 | static proc imIsUpRightTriangle(intmat M) { |
---|
| 517 | for (int i = 1; i <= nrows(M); i++) { |
---|
| 518 | for (int j = 1; j < i; j++) { |
---|
| 519 | if(M[i,j] != 0) { return (0); } |
---|
[4d9f75e] | 520 | } kill j; |
---|
| 521 | } kill i; |
---|
[5482cda] | 522 | return (1); |
---|
| 523 | } |
---|
| 524 | |
---|
| 525 | static proc eliminateZerosUpTriangle(intmat G) { |
---|
| 526 | // G is expected to be an upper triangle matrix |
---|
| 527 | for (int i = ncols(G); i >= 1; i--) { // loop order is important because we delete entries |
---|
| 528 | if (G[i,i] == 0) { // i doesn't have a cycle |
---|
| 529 | for (int j = 1; j < i; j++) { |
---|
| 530 | if (G[j,i] == 1) { // j has an edge to i |
---|
| 531 | for (int k = i + 1; k <= nrows(G); k++) { |
---|
| 532 | if (G[i,k] == 1) { |
---|
| 533 | G[j,k] = G[i,k]; // give j all edges from i |
---|
| 534 | } |
---|
[4d9f75e] | 535 | } kill k; |
---|
[5482cda] | 536 | } |
---|
[4d9f75e] | 537 | } kill j; |
---|
[5482cda] | 538 | G = imDelRowCol(G,i,i); // remove vertex i |
---|
| 539 | } |
---|
[4d9f75e] | 540 | } kill i; |
---|
[5482cda] | 541 | return (G); |
---|
| 542 | } |
---|
| 543 | |
---|
| 544 | static proc imDelRowCol(intmat M, int row, int col) { |
---|
| 545 | // row and col are expected to be > 0 |
---|
| 546 | int nr = nrows(M); |
---|
| 547 | int nc = ncols(M); |
---|
| 548 | intmat Mdel[nr - 1][nc - 1]; |
---|
| 549 | for (int i = 1; i <= nr; i++) { |
---|
| 550 | for (int j = 1; j <= nc; j++) { |
---|
| 551 | if(i != row && j != col) { |
---|
| 552 | int newi = i; |
---|
| 553 | int newj = j; |
---|
| 554 | if (i > row) { newi = i - 1; } |
---|
| 555 | if (j > col) { newj = j - 1; } |
---|
| 556 | Mdel[newi,newj] = M[i,j]; |
---|
[4d9f75e] | 557 | kill newi; kill newj; |
---|
[5482cda] | 558 | } |
---|
[4d9f75e] | 559 | } kill j; |
---|
| 560 | } kill i; |
---|
[5482cda] | 561 | return (Mdel); |
---|
| 562 | } |
---|
| 563 | |
---|
| 564 | static proc topologicalSort(intmat G) { |
---|
| 565 | // NOTE: ignores loops |
---|
| 566 | // NOTE: this takes O(|V^3|), can be optimized |
---|
| 567 | int n = ncols(G); |
---|
| 568 | for (int i = 1; i <= n; i++) { // only use the submat at i |
---|
| 569 | // find a vertex v in the submat at i with no incoming edges |
---|
| 570 | int v; |
---|
| 571 | for (int j = i; j <= n; j++) { |
---|
| 572 | int incoming = 0; |
---|
| 573 | for (int k = i; k <= n; k++) { |
---|
| 574 | if (k != j && G[k,j] == 1) { |
---|
| 575 | incoming = 1; |
---|
| 576 | } |
---|
[4d9f75e] | 577 | } kill k; |
---|
[5482cda] | 578 | if (incoming == 0) { |
---|
| 579 | v = j; |
---|
[cb81243] | 580 | kill incoming; |
---|
[5482cda] | 581 | break; |
---|
| 582 | } else { |
---|
| 583 | if (j == n) { |
---|
| 584 | // G contains at least one cycle, abort |
---|
| 585 | return (G); |
---|
| 586 | } |
---|
| 587 | } |
---|
[4d9f75e] | 588 | kill incoming; |
---|
| 589 | } kill j; |
---|
[5482cda] | 590 | |
---|
| 591 | // swap v and i |
---|
| 592 | if (v != i) { |
---|
| 593 | G = imPermcol(G, v, i); |
---|
| 594 | G = imPermrow(G, v, i); |
---|
| 595 | } |
---|
[4d9f75e] | 596 | kill v; |
---|
| 597 | } kill i; |
---|
[5482cda] | 598 | return (G); |
---|
| 599 | } |
---|
| 600 | |
---|
| 601 | static proc imPermcol (intmat A, int c1, int c2) |
---|
| 602 | { |
---|
| 603 | intmat B = A; |
---|
| 604 | int k = nrows(B); |
---|
| 605 | B[1..k,c1] = A[1..k,c2]; |
---|
| 606 | B[1..k,c2] = A[1..k,c1]; |
---|
| 607 | return (B); |
---|
| 608 | } |
---|
| 609 | |
---|
| 610 | static proc imPermrow (intmat A, int r1, int r2) |
---|
| 611 | { |
---|
| 612 | intmat B = A; |
---|
| 613 | int k = ncols(B); |
---|
| 614 | B[r1,1..k] = A[r2,1..k]; |
---|
| 615 | B[r2,1..k] = A[r1,1..k]; |
---|
| 616 | return (B); |
---|
| 617 | } |
---|
| 618 | |
---|
| 619 | static proc UfGraphGrowth(intmat UG) |
---|
| 620 | { |
---|
| 621 | int n = ncols(UG); // number of vertices |
---|
| 622 | // iterate through all vertices |
---|
| 623 | |
---|
[c8fd40] | 624 | intvec visited = 0:n; |
---|
| 625 | intvec cyclic = 0:n; |
---|
| 626 | intvec countedCycles = -2:n; |
---|
[5482cda] | 627 | |
---|
| 628 | int maxCycleCount = 0; |
---|
| 629 | for (int v = 1; v <= n; v++) { |
---|
[c8fd40] | 630 | countedCycles = countCycles(UG, v, visited, cyclic, 0, countedCycles); |
---|
[ecdeb5] | 631 | dbprint("counted " + string(countedCycles[v]) + " cycles from vertex " + string(v) + "/" + string(n) + " (cache: " + string(countedCycles) + ")"); |
---|
[c8fd40] | 632 | if (countedCycles[v] == -1) { |
---|
[5482cda] | 633 | return(-1); |
---|
| 634 | } |
---|
[c8fd40] | 635 | if (countedCycles[v] > maxCycleCount) { |
---|
| 636 | maxCycleCount = countedCycles[v]; |
---|
[5482cda] | 637 | } |
---|
[4d9f75e] | 638 | } kill v; |
---|
[c8fd40] | 639 | return (maxCycleCount); |
---|
[5482cda] | 640 | } |
---|
| 641 | |
---|
[c8fd40] | 642 | static proc countCycles(intmat G, int v, intvec visited, intvec cyclic, intvec path, intvec countedCycles) |
---|
[5482cda] | 643 | "USAGE: countCycles(G, v, visited, cyclic, path); G a Graph, v the vertex to |
---|
| 644 | start. The parameter visited, cyclic and path should be 0. |
---|
| 645 | RETURN: int |
---|
[dfa15b] | 646 | Maximal number of distinct cycles |
---|
[5482cda] | 647 | PURPOSE: Calculate the maximal number of distinct cycles in a single path starting at v |
---|
| 648 | ASSUME: Basering is a Letterplace ring |
---|
| 649 | " |
---|
| 650 | { |
---|
[c8fd40] | 651 | if (countedCycles[v] > -2) { |
---|
| 652 | return (countedCycles); |
---|
| 653 | } |
---|
[5482cda] | 654 | // Mark the current vertex as visited |
---|
| 655 | visited[v] = 1; |
---|
| 656 | |
---|
| 657 | // Store the current vertex in path |
---|
| 658 | if (path[1] == 0) { |
---|
| 659 | path[1] = v; |
---|
| 660 | } else { |
---|
| 661 | path[size(path) + 1] = v; |
---|
| 662 | } |
---|
| 663 | |
---|
| 664 | int cycles = 0; |
---|
| 665 | for (int w = 1; w <= ncols(G); w++) { |
---|
| 666 | if (G[v,w] == 1) { |
---|
[b5ac68] | 667 | if (visited[w] == 1) { // found new cycle |
---|
| 668 | // 1. for all vertices in path until w, check if they are cyclic |
---|
[5482cda] | 669 | for (int j = size(path); j >= 1; j--) { |
---|
| 670 | if(cyclic[path[j]] == 1) { |
---|
[b5ac68] | 671 | // 1.1 if yes, return -1 |
---|
[c8fd40] | 672 | countedCycles[v] = -1; |
---|
| 673 | return (countedCycles); |
---|
[5482cda] | 674 | } |
---|
| 675 | if (path[j] == w) { |
---|
| 676 | break; |
---|
| 677 | } |
---|
[4d9f75e] | 678 | } kill j; |
---|
[5482cda] | 679 | |
---|
[b5ac68] | 680 | // 2. otherwise cycles++ |
---|
[5482cda] | 681 | for (int j = size(path); j >= 1; j--) { |
---|
[b5ac68] | 682 | // 2.2 remove the edges from that cycle and mark the vertices as cyclic |
---|
| 683 | if (j == size(path)) { // special case in the first iteration |
---|
[5482cda] | 684 | cyclic[v] = 1; |
---|
| 685 | G[v, w] = 0; |
---|
| 686 | } else { |
---|
| 687 | cyclic[path[j]] = 1; |
---|
| 688 | G[path[j], path[j+1]] = 0; |
---|
| 689 | } |
---|
| 690 | if (path[j] == w) { |
---|
| 691 | break; |
---|
| 692 | } |
---|
[4d9f75e] | 693 | } kill j; |
---|
[5482cda] | 694 | |
---|
[b5ac68] | 695 | // 3. countCycles() on all these vertices |
---|
[5482cda] | 696 | int maxCycleCount = 0; |
---|
| 697 | for (int j = size(path); j >= 1; j--) { |
---|
[c8fd40] | 698 | countedCycles = countCycles(G, path[j], visited, cyclic, path, countedCycles); |
---|
| 699 | if(countedCycles[path[j]] == -1) { |
---|
| 700 | countedCycles[v] = -1; |
---|
| 701 | return (countedCycles); |
---|
[5482cda] | 702 | } |
---|
[c8fd40] | 703 | if (countedCycles[path[j]] > maxCycleCount) { |
---|
| 704 | maxCycleCount = countedCycles[path[j]]; |
---|
[5482cda] | 705 | } |
---|
| 706 | if (path[j] == w) { |
---|
| 707 | break; |
---|
| 708 | } |
---|
[4d9f75e] | 709 | } kill j; |
---|
[5482cda] | 710 | if (maxCycleCount >= cycles) { |
---|
| 711 | cycles = maxCycleCount + 1; |
---|
| 712 | } |
---|
[4d9f75e] | 713 | kill maxCycleCount; |
---|
[5482cda] | 714 | } else { |
---|
[c8fd40] | 715 | countedCycles = countCycles(G, w, visited, cyclic, path, countedCycles); |
---|
| 716 | if (countedCycles[w] == -1) { |
---|
| 717 | countedCycles[v] = -1; |
---|
| 718 | return (countedCycles); |
---|
[5482cda] | 719 | } |
---|
[c8fd40] | 720 | if (countedCycles[w] > cycles) { |
---|
| 721 | cycles = countedCycles[w]; |
---|
[5482cda] | 722 | } |
---|
| 723 | } |
---|
| 724 | } |
---|
[4d9f75e] | 725 | } kill w; |
---|
[c8fd40] | 726 | countedCycles[v] = cycles; |
---|
| 727 | return (countedCycles); |
---|
[5482cda] | 728 | } |
---|
| 729 | |
---|
[7b12a3] | 730 | proc lpUfGraph(ideal G, list #) |
---|
| 731 | "USAGE: lpUfGraph(G); G a set of monomials in a letterplace ring. |
---|
| 732 | RETURN: intmat or list |
---|
| 733 | NOTE: lpUfGraph(G); returns intmat. lpUfGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal. |
---|
| 734 | The intmat is the Ufnarovskij Graph and the ideal contains the vertices. |
---|
[5482cda] | 735 | PURPOSE: Constructs the Ufnarovskij graph induced by G |
---|
[5edf31] | 736 | the adjacency matrix of the Ufnarovskij graph induced by G |
---|
[5482cda] | 737 | ASSUME: - basering is a Letterplace ring |
---|
[5edf31] | 738 | - G are the leading monomials of a Groebner basis |
---|
[5482cda] | 739 | " |
---|
| 740 | { |
---|
[c8fd40] | 741 | dbprint("computing maxDeg"); |
---|
[5482cda] | 742 | int l = maxDeg(G); |
---|
[c8fd40] | 743 | if (l - 1 == 0) { |
---|
| 744 | // TODO: how should the graph look like when l - 1 = 0 ? |
---|
| 745 | ERROR("Ufnarovskij graph not implemented for l = 1"); |
---|
| 746 | } |
---|
[921f32] | 747 | int lV = lpVarBlockSize(basering); |
---|
[c8fd40] | 748 | // TODO: what if l <= 0? |
---|
| 749 | dbprint("computing standard words"); |
---|
| 750 | ideal SW = lpStandardWords(G, l - 1); // vertices |
---|
| 751 | int n = ncols(SW); |
---|
| 752 | dbprint("n = " + string(n)); |
---|
[5482cda] | 753 | intmat UG[n][n]; // Ufnarovskij graph |
---|
| 754 | for (int i = 1; i <= n; i++) { |
---|
| 755 | for (int j = 1; j <= n; j++) { |
---|
[c8fd40] | 756 | dbprint("Ufnarovskii graph: " + string((i-1)*n + j) + "/" + string(n*n) + " entries"); |
---|
[5482cda] | 757 | // [Studzinski page 76] |
---|
[c8fd40] | 758 | poly v = SW[i]; |
---|
| 759 | poly w = SW[j]; |
---|
[5482cda] | 760 | intvec v_overlap; |
---|
| 761 | intvec w_overlap; |
---|
| 762 | if (l - 1 > 1) { |
---|
[c8fd40] | 763 | v_overlap = leadexp(v); |
---|
| 764 | w_overlap = leadexp(w); |
---|
| 765 | v_overlap = v_overlap[(lV+1) .. (l-1)*lV]; |
---|
| 766 | w_overlap = w_overlap[1 .. (l-2)*lV]; |
---|
[5482cda] | 767 | } |
---|
[e39e193] | 768 | if (v_overlap == w_overlap && !lpLmDivides(G, v * lpVarAt(w, l - 1))) { |
---|
[5482cda] | 769 | UG[i,j] = 1; |
---|
| 770 | } |
---|
[c8fd40] | 771 | kill v; kill w; kill v_overlap; kill w_overlap; |
---|
[4d9f75e] | 772 | } kill j; |
---|
| 773 | } kill i; |
---|
[5482cda] | 774 | if (size(#) > 0) { |
---|
| 775 | if (typeof(#[1]) == "int") { |
---|
[7b12a3] | 776 | if (#[1] != 0) { |
---|
[5482cda] | 777 | list ret = UG; |
---|
[2802b10] | 778 | ret[2] = SW; // the vertices |
---|
[5482cda] | 779 | return (ret); |
---|
| 780 | } |
---|
| 781 | } |
---|
| 782 | } |
---|
| 783 | return (UG); |
---|
| 784 | } |
---|
[7e51648] | 785 | example |
---|
| 786 | { |
---|
[7b12a3] | 787 | "EXAMPLE:"; echo = 2; |
---|
| 788 | ring r = 0,(x,y,z),dp; |
---|
[fceb4e] | 789 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
[7b12a3] | 790 | setring R; // sets basering to Letterplace ring |
---|
[6a4f0d] | 791 | ideal I = x*y, x*z, z*y, z*z; |
---|
[7b12a3] | 792 | lpUfGraph(I); |
---|
| 793 | lpUfGraph(I,1); |
---|
| 794 | } |
---|
[5482cda] | 795 | |
---|
| 796 | static proc maxDeg(ideal G) |
---|
| 797 | { |
---|
| 798 | int l = 0; |
---|
| 799 | for (int i = 1; i <= size(G); i++) { // find the max degree in G |
---|
| 800 | int d = deg(G[i]); |
---|
| 801 | if (d > l) { |
---|
| 802 | l = d; |
---|
| 803 | } |
---|
[4d9f75e] | 804 | kill d; |
---|
| 805 | } kill i; |
---|
[5482cda] | 806 | return (l); |
---|
| 807 | } |
---|
| 808 | |
---|
[c8fd40] | 809 | static proc lpStandardWords(ideal G, int length) |
---|
| 810 | "ASSUME: G is simplified |
---|
| 811 | " |
---|
| 812 | { |
---|
| 813 | if (length < 0) { |
---|
| 814 | return (delete(ideal(0), 1)); // no standard words |
---|
| 815 | } |
---|
| 816 | |
---|
| 817 | ideal words = maxideal(length); |
---|
| 818 | for (int i = ncols(words); i >= 1; i--) { |
---|
[e39e193] | 819 | if (lpLmDivides(G, words[i])) { |
---|
[c8fd40] | 820 | words = delete(words, i); |
---|
| 821 | } |
---|
| 822 | } kill i; |
---|
| 823 | return (words); |
---|
| 824 | } |
---|
| 825 | |
---|
[5482cda] | 826 | static proc ivStandardWords(list G, int length) |
---|
| 827 | "ASSUME: G is simplified |
---|
| 828 | " |
---|
| 829 | { |
---|
| 830 | if (length <= 0) { |
---|
| 831 | list words; |
---|
| 832 | if (length == 0 && !ivdivides(G,0)) { |
---|
| 833 | words[1] = 0; // iv = 0 means monom = 1 |
---|
| 834 | } |
---|
| 835 | return (words); // no standard words |
---|
| 836 | } |
---|
[921f32] | 837 | int lV = lpVarBlockSize(basering); // variable count |
---|
[5482cda] | 838 | list prevWords = ivStandardWords(G, length - 1); |
---|
| 839 | list words; |
---|
| 840 | for (int i = 1; i <= lV; i++) { |
---|
| 841 | for (int j = 1; j <= size(prevWords); j++) { |
---|
| 842 | intvec word = prevWords[j]; |
---|
| 843 | word[length] = i; |
---|
| 844 | // assumes that G is simplified! |
---|
| 845 | if (!ivdivides(G, word)) { |
---|
| 846 | words = insert(words, word); |
---|
| 847 | } |
---|
[4d9f75e] | 848 | kill word; |
---|
| 849 | } kill j; |
---|
| 850 | } kill i; |
---|
[5482cda] | 851 | return (words); |
---|
| 852 | } |
---|
| 853 | |
---|
| 854 | static proc ivStandardWordsUpToLength(list G, int length) |
---|
| 855 | "ASSUME: G is simplified |
---|
| 856 | " |
---|
| 857 | { |
---|
| 858 | list words = ivStandardWords(G,0); |
---|
| 859 | if (size(words) == 0) {return (words)} |
---|
| 860 | for (int i = 1; i <= length; i++) { |
---|
| 861 | words = words + ivStandardWords(G, i); |
---|
[4d9f75e] | 862 | } kill i; |
---|
[5482cda] | 863 | return (words); |
---|
| 864 | } |
---|
| 865 | |
---|
| 866 | static proc ivdivides(list G, intvec iv) { |
---|
| 867 | for (int k = 1; k <= size(G); k++) { |
---|
| 868 | if (isIF(G[k], iv)) { |
---|
| 869 | return (1); |
---|
| 870 | } else { |
---|
| 871 | if (k == size(G)) { |
---|
| 872 | return (0); |
---|
| 873 | } |
---|
| 874 | } |
---|
[4d9f75e] | 875 | } kill k; |
---|
[b61362] | 876 | return (0); |
---|
[5482cda] | 877 | } |
---|
| 878 | |
---|
[4d9f75e] | 879 | proc lpGkDim(ideal G) |
---|
| 880 | "USAGE: lpGkDim(G); G an ideal in a letterplace ring |
---|
[5482cda] | 881 | RETURN: int |
---|
| 882 | PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> |
---|
[dfa15b] | 883 | -1 means positive infinite |
---|
[5482cda] | 884 | ASSUME: - basering is a Letterplace ring |
---|
[dfa15b] | 885 | - G is a Groebner basis |
---|
[5482cda] | 886 | " |
---|
| 887 | { |
---|
[4d9f75e] | 888 | G = lead(G); |
---|
| 889 | G = simplify(G, 2+4+8); |
---|
| 890 | |
---|
| 891 | // check special case 1 |
---|
| 892 | int l = 0; |
---|
| 893 | for (int i = 1; i <= size(G); i++) { |
---|
| 894 | // find the max degree in G |
---|
| 895 | int d = deg(G[i]); |
---|
| 896 | if (d > l) { |
---|
| 897 | l = d; |
---|
| 898 | } |
---|
| 899 | |
---|
| 900 | // also if G is the whole ring return minus infinity |
---|
| 901 | if (leadmonom(G[i]) == 1) { |
---|
[c8fd40] | 902 | ERROR("GK-Dim not defined for 0-ring") |
---|
[4d9f75e] | 903 | } |
---|
| 904 | kill d; |
---|
| 905 | } kill i; |
---|
[6fac22] | 906 | // if longest word has length 1, or G is the zero ideal, we handle it as a special case |
---|
| 907 | if (l == 1 || size(G) == 0) { |
---|
[921f32] | 908 | int n = lpVarBlockSize(basering); // variable count |
---|
[4d9f75e] | 909 | int k = size(G); |
---|
| 910 | if (k == n) { // V = {1} no edges |
---|
| 911 | return(0); |
---|
| 912 | } |
---|
| 913 | if (k == n-1) { // V = {1} with loop |
---|
| 914 | return(1); |
---|
| 915 | } |
---|
| 916 | if (k <= n-2) { // V = {1} with more than one loop |
---|
| 917 | return(-1); |
---|
[5482cda] | 918 | } |
---|
| 919 | } |
---|
| 920 | |
---|
[c8fd40] | 921 | dbprint("computing Ufnarovskii graph"); |
---|
[4d9f75e] | 922 | intmat UG = lpUfGraph(G); |
---|
[ecdeb5] | 923 | if (printlevel >= voice + 1) { |
---|
| 924 | UG; |
---|
| 925 | } |
---|
[4d9f75e] | 926 | |
---|
| 927 | // check special case 2 |
---|
| 928 | intmat zero[nrows(UG)][ncols(UG)]; |
---|
| 929 | if (UG == zero) { |
---|
| 930 | return (0); |
---|
[5482cda] | 931 | } |
---|
[4d9f75e] | 932 | |
---|
| 933 | // check special case 3 |
---|
[c8fd40] | 934 | dbprint("topological sorting of Ufnarovskii graph"); |
---|
[4d9f75e] | 935 | UG = topologicalSort(UG); |
---|
[ecdeb5] | 936 | if (printlevel >= voice + 1) { |
---|
| 937 | UG; |
---|
| 938 | } |
---|
[4d9f75e] | 939 | |
---|
[c8fd40] | 940 | dbprint("check if Ufnarovskii graph is DAG"); |
---|
[4d9f75e] | 941 | if (imIsUpRightTriangle(UG)) { |
---|
| 942 | UG = eliminateZerosUpTriangle(UG); |
---|
| 943 | if (ncols(UG) == 0 || nrows(UG) == 0) { // when the diagonal was zero |
---|
| 944 | return (0) |
---|
| 945 | } |
---|
[c8fd40] | 946 | dbprint("DAG detected, using URTNZD growth alg"); |
---|
[4d9f75e] | 947 | return(UfGraphURTNZDGrowth(UG)); |
---|
| 948 | } |
---|
| 949 | |
---|
| 950 | // otherwise count cycles in the Ufnarovskij Graph |
---|
[c8fd40] | 951 | dbprint("not a DAG, using regular growth alg"); |
---|
[4d9f75e] | 952 | return(UfGraphGrowth(UG)); |
---|
[5482cda] | 953 | } |
---|
| 954 | example |
---|
| 955 | { |
---|
| 956 | "EXAMPLE:"; echo = 2; |
---|
| 957 | ring r = 0,(x,y,z),dp; |
---|
[fceb4e] | 958 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
[5482cda] | 959 | R; |
---|
| 960 | setring R; // sets basering to Letterplace ring |
---|
[6a4f0d] | 961 | ideal I = z;//an example of infinite GK dimension |
---|
[5482cda] | 962 | lpGkDim(I); |
---|
[6a4f0d] | 963 | I = x,y,z; // gkDim = 0 |
---|
[5482cda] | 964 | lpGkDim(I); |
---|
[6a4f0d] | 965 | I = x*y, x*z, z*y, z*z;//gkDim = 2 |
---|
[5482cda] | 966 | lpGkDim(I); |
---|
[4aa50a] | 967 | ideal G = y*x - x*y, z*x - x*z, z*y - y*z; G = std(G); |
---|
[7492c8] | 968 | G; |
---|
| 969 | lpGkDim(G); // 3, as expected for K[x,y,z] |
---|
[5482cda] | 970 | } |
---|
| 971 | |
---|
| 972 | proc lpGlDimBound(ideal G) |
---|
| 973 | "USAGE: lpGlDimBound(I); I an ideal |
---|
| 974 | RETURN: int, an upper bound for the global dimension, -1 means infinity |
---|
| 975 | PURPOSE: computing an upper bound for the global dimension |
---|
[b4ab792] | 976 | ASSUME: - basering is a Letterplace ring, G is a reduced Groebner Basis |
---|
[5482cda] | 977 | EXAMPLE: example lpGlDimBound; shows example |
---|
| 978 | NOTE: if I = LM(I), then the global dimension is equal the Gelfand |
---|
[5edf31] | 979 | Kirillov dimension if it is finite |
---|
| 980 | Global dimension should be 0 for A/G = K and 1 for A/G = K<x1...xn> |
---|
[5482cda] | 981 | " |
---|
| 982 | { |
---|
| 983 | G = simplify(G,2); // remove zero generators |
---|
| 984 | // NOTE: Gl should be 0 for A/G = K and 1 for A/G = K<x1...xn> |
---|
| 985 | // G1 contains generators with single variable in LM |
---|
| 986 | ideal G1; |
---|
| 987 | for (int i = 1; i <= size(G); i++) { |
---|
| 988 | if (ord(G[i]) < 2) { // single variable in LM |
---|
| 989 | G1 = insertGenerator(G1,G[i]); |
---|
| 990 | } |
---|
[4d9f75e] | 991 | } kill i; |
---|
[5482cda] | 992 | G1 = simplify(G1,2); // remove zero generators |
---|
| 993 | |
---|
| 994 | // G = NF(G,G1) |
---|
| 995 | for (int i = 1; i <= ncols(G); i++) { // do not use size() here |
---|
| 996 | G[i] = lpNF(G[i],G1); |
---|
[4d9f75e] | 997 | } kill i; |
---|
[5482cda] | 998 | G = simplify(G,2); // remove zero generators |
---|
| 999 | |
---|
| 1000 | // delete variables in LM(G1) from the ring |
---|
| 1001 | def save = basering; |
---|
[04d263] | 1002 | def R = basering; |
---|
[5482cda] | 1003 | if (size(G1) > 0) { |
---|
| 1004 | while (size(G1) > 0) { |
---|
[921f32] | 1005 | if (lpVarBlockSize(R) > 1) { |
---|
[04d263] | 1006 | def @R = R - string(G1[1]); |
---|
| 1007 | R = @R; |
---|
| 1008 | kill @R; |
---|
| 1009 | setring R; |
---|
| 1010 | /* ring R = lpDelVar(lp2iv(G1[1])[1]); // TODO replace with proper method */ |
---|
[5482cda] | 1011 | ideal G1 = imap(save,G1); |
---|
| 1012 | G1 = simplify(G1, 2); // remove zero generators |
---|
| 1013 | } else { |
---|
| 1014 | // only the field is left (no variables) |
---|
| 1015 | return(0); |
---|
| 1016 | } |
---|
| 1017 | } |
---|
| 1018 | ideal G = imap(save, G); // put this here, because when save == R this call would make G = 0 |
---|
| 1019 | } |
---|
| 1020 | |
---|
| 1021 | // Li p. 184 if G = LM(G), then I = LM(I) and thus glDim = gkDim if it's finite |
---|
| 1022 | for (int i = 1; i <= size(G); i++) { |
---|
| 1023 | if (G[i] != lead(G[i])) { |
---|
| 1024 | break; |
---|
| 1025 | } else { |
---|
| 1026 | if (i == size(G)) { // if last iteration |
---|
| 1027 | int gkDim = lpGkDim(G); |
---|
| 1028 | if (gkDim >= 0) { |
---|
| 1029 | return (gkDim); |
---|
| 1030 | } |
---|
[4d9f75e] | 1031 | kill gkDim; |
---|
[5482cda] | 1032 | } |
---|
| 1033 | } |
---|
[4d9f75e] | 1034 | } kill i; |
---|
[5482cda] | 1035 | |
---|
| 1036 | intmat GNC = lpGraphOfNChains(G); |
---|
| 1037 | |
---|
| 1038 | // assuming GNC is connected |
---|
| 1039 | |
---|
| 1040 | // TODO: maybe loop+cycle checking could be done more efficiently? |
---|
| 1041 | if (!imHasLoops(GNC) && imIsUpRightTriangle(topologicalSort(GNC))) { |
---|
| 1042 | // GNC is a DAG |
---|
| 1043 | intmat GNCk = GNC; |
---|
| 1044 | intmat zero[1][ncols(GNCk)]; |
---|
| 1045 | int k = 1; |
---|
| 1046 | // while first row isn't empty |
---|
| 1047 | while (GNCk[1,1..(ncols(GNCk))] != zero[1,1..(ncols(zero))]) { |
---|
| 1048 | GNCk = GNCk * GNC; |
---|
| 1049 | k++; |
---|
| 1050 | } |
---|
| 1051 | // k-1 = number of edges in longest path starting from 1 |
---|
| 1052 | return (k-1); |
---|
| 1053 | } else { |
---|
| 1054 | // GNC contains loops/cycles => there is always an n-chain |
---|
| 1055 | return (-1); // infinity |
---|
| 1056 | } |
---|
| 1057 | } |
---|
| 1058 | example |
---|
| 1059 | { |
---|
| 1060 | "EXAMPLE:"; echo = 2; |
---|
| 1061 | ring r = 0,(x,y),dp; |
---|
[fceb4e] | 1062 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
[5482cda] | 1063 | setring R; // sets basering to Letterplace ring |
---|
[7492c8] | 1064 | ideal G = x*x, y*y,x*y*x; // it is a monomial Groebner basis |
---|
[4aa50a] | 1065 | lpGlDimBound(G); |
---|
[7492c8] | 1066 | ideal H = y*x - x*y; H = std(H); // H is a Groebner basis |
---|
| 1067 | lpGlDimBound(H); // gl dim of K[x,y] is 2, as expected |
---|
[5482cda] | 1068 | } |
---|
| 1069 | |
---|
| 1070 | static proc imHasLoops(intmat A) { |
---|
| 1071 | int n = ncols(A); |
---|
[c723156] | 1072 | for (int i = 1; i <= n; i++) { |
---|
[5482cda] | 1073 | if (A[i,i] == 1) { |
---|
| 1074 | return (1); |
---|
| 1075 | } |
---|
[4d9f75e] | 1076 | } kill i; |
---|
[5482cda] | 1077 | return (0); |
---|
| 1078 | } |
---|
| 1079 | |
---|
| 1080 | static proc lpGraphOfNChains(ideal G) // G must be reduced |
---|
| 1081 | { |
---|
| 1082 | list LG = lpId2ivLi(lead(G)); |
---|
[921f32] | 1083 | int n = lpVarBlockSize(basering); |
---|
[04d263] | 1084 | int degbound = lpDegBound(basering); |
---|
[5482cda] | 1085 | |
---|
| 1086 | list V; |
---|
| 1087 | for (int i = 0; i <= n; i++) { |
---|
| 1088 | V[i+1] = i; // add 1 and all variables |
---|
[4d9f75e] | 1089 | } kill i; |
---|
[5482cda] | 1090 | for (int i = 1; i <= size(LG); i++) { |
---|
| 1091 | intvec u = LG[i]; |
---|
| 1092 | for (int j = 2; j <= size(u); j++) { |
---|
| 1093 | intvec v = u[j..size(u)]; |
---|
| 1094 | if (!contains(V, v)) { |
---|
| 1095 | V = insert(V, v, size(V)); // add subword j..size |
---|
| 1096 | } |
---|
[4d9f75e] | 1097 | kill v; |
---|
| 1098 | } kill j; |
---|
| 1099 | kill u; |
---|
| 1100 | } kill i; |
---|
[5482cda] | 1101 | int nV = size(V); |
---|
| 1102 | intmat GNC[nV][nV]; // graph of n-chains |
---|
| 1103 | |
---|
| 1104 | // for vertex 1 |
---|
| 1105 | for (int i = 2; i <= n + 1; i++) { |
---|
| 1106 | GNC[1,i] = 1; // 1 has an edge to all variables |
---|
[4d9f75e] | 1107 | } kill i; |
---|
[5482cda] | 1108 | |
---|
| 1109 | // for the other vertices |
---|
| 1110 | for (int i = 2; i <= nV; i++) { |
---|
| 1111 | for (int j = 2; j <= nV; j++) { |
---|
| 1112 | intvec uv = V[i],V[j]; |
---|
| 1113 | |
---|
| 1114 | if (contains(LG, uv)) { |
---|
| 1115 | GNC[i,j] = 1; |
---|
| 1116 | } else { |
---|
| 1117 | // Li p. 177 |
---|
| 1118 | // search for a right divisor 'w' of uv in G |
---|
| 1119 | // then check if G doesn't divide the subword uv-1 |
---|
| 1120 | |
---|
| 1121 | // look for a right divisor in LG |
---|
| 1122 | for (int k = 1; k <= size(LG); k++) { |
---|
| 1123 | if (isSF(LG[k], uv)) { |
---|
| 1124 | // w = LG[k] |
---|
| 1125 | if(!ivdivides(LG, uv[1..(size(uv)-1)])) { |
---|
| 1126 | // G doesn't divide uv-1 |
---|
| 1127 | GNC[i,j] = 1; |
---|
| 1128 | break; |
---|
| 1129 | } |
---|
| 1130 | } |
---|
[4d9f75e] | 1131 | } kill k; |
---|
[5482cda] | 1132 | } |
---|
[4d9f75e] | 1133 | kill uv; |
---|
| 1134 | } kill j; |
---|
| 1135 | } kill i; |
---|
[5482cda] | 1136 | |
---|
| 1137 | return(GNC); |
---|
| 1138 | } |
---|
| 1139 | |
---|
| 1140 | static proc contains(list L, def item) |
---|
| 1141 | { |
---|
| 1142 | for (int i = 1; i <= size(L); i++) { |
---|
| 1143 | if (L[i] == item) { |
---|
| 1144 | return (1); |
---|
| 1145 | } |
---|
[4d9f75e] | 1146 | } kill i; |
---|
[5482cda] | 1147 | return (0); |
---|
| 1148 | } |
---|
| 1149 | |
---|
| 1150 | proc lpSubstitute(poly f, ideal s1, ideal s2, list #) |
---|
[ccef1e] | 1151 | "USAGE: lpSubstitute(f,s1,s2[,G]); f poly, s1 list (ideal) of variables |
---|
[5edf31] | 1152 | to replace, s2 list (ideal) of polynomials to replace with, G optional ideal to |
---|
| 1153 | reduce with. |
---|
[5482cda] | 1154 | RETURN: poly, the substituted polynomial |
---|
| 1155 | ASSUME: - basering is a Letterplace ring |
---|
[ccef1e] | 1156 | - s1 contains a subset of the set of variables |
---|
| 1157 | - s2 and s1 are of the same size |
---|
| 1158 | - G is a Groebner basis, |
---|
| 1159 | - the current ring has a sufficient degbound (which also can be calculated with lpCalcSubstDegBound()) |
---|
| 1160 | NOTE: the procedure implements the image of a polynomial f |
---|
| 1161 | under an endomorphism of a free algebra, defined by s1 and s2: |
---|
| 1162 | variables, not present in s1, are left unchanged; |
---|
| 1163 | variable s1[k] is mapped to a polynomial s2[k]. |
---|
| 1164 | - An optional ideal G extends the endomorphism as above to the morphism into the factor algebra K<X>/G. |
---|
[5482cda] | 1165 | EXAMPLE: example lpSubstitute; shows examples |
---|
| 1166 | " |
---|
| 1167 | { |
---|
| 1168 | ideal G; |
---|
| 1169 | if (size(#) > 0) { |
---|
| 1170 | if (typeof(#[1])=="ideal") { |
---|
| 1171 | G = #[1]; |
---|
| 1172 | } |
---|
| 1173 | } |
---|
| 1174 | |
---|
| 1175 | poly fs; |
---|
| 1176 | for (int i = 1; i <= size(f); i++) { |
---|
| 1177 | poly fis = leadcoef(f[i]); |
---|
| 1178 | intvec ivfi = lp2iv(f[i]); |
---|
| 1179 | for (int j = 1; j <= size(ivfi); j++) { |
---|
| 1180 | int varindex = ivfi[j]; |
---|
[8a57d4] | 1181 | if (varindex > 0) { |
---|
| 1182 | int subindex = lpIndexOf(s1, var(varindex)); |
---|
| 1183 | if (subindex > 0) { |
---|
| 1184 | s2[subindex] = lpNF(s2[subindex],G); |
---|
[de5dbc] | 1185 | fis = fis * s2[subindex]; |
---|
[8a57d4] | 1186 | } else { |
---|
[de5dbc] | 1187 | fis = fis * lpNF(iv2lp(varindex),G); |
---|
[8a57d4] | 1188 | } |
---|
| 1189 | /*fis = lpNF(fis,G);*/ |
---|
| 1190 | kill subindex; |
---|
[5482cda] | 1191 | } |
---|
[8a57d4] | 1192 | kill varindex; |
---|
[4d9f75e] | 1193 | } kill j; |
---|
[42d919] | 1194 | kill ivfi; |
---|
[5482cda] | 1195 | fs = fs + fis; |
---|
[42d919] | 1196 | kill fis; |
---|
| 1197 | } |
---|
| 1198 | kill i; |
---|
[5482cda] | 1199 | fs = lpNF(fs, G); |
---|
| 1200 | return (fs); |
---|
| 1201 | } |
---|
[7e51648] | 1202 | example |
---|
| 1203 | { |
---|
| 1204 | "EXAMPLE:"; echo = 2; |
---|
[5482cda] | 1205 | ring r = 0,(x,y,z),dp; |
---|
[fceb4e] | 1206 | def R = freeAlgebra(r, 4); |
---|
[5482cda] | 1207 | setring R; |
---|
[6a4f0d] | 1208 | ideal G = x*y; // optional |
---|
| 1209 | poly f = 3*x*x+y*x; |
---|
| 1210 | ideal s1 = x, y; |
---|
[ccef1e] | 1211 | ideal s2 = y*z*z, x; // i.e. x --> yzz and y --> x |
---|
[5482cda] | 1212 | // the substitution probably needs a higher degbound |
---|
[16610f] | 1213 | int minDegBound = lpCalcSubstDegBound(f,s1,s2); |
---|
[ccef1e] | 1214 | minDegBound; // thus the bound needs to be increased |
---|
| 1215 | setring r; // back to original r |
---|
[fceb4e] | 1216 | def R1 = freeAlgebra(r, minDegBound); |
---|
[5482cda] | 1217 | setring R1; |
---|
[ccef1e] | 1218 | lpSubstitute(imap(R,f), imap(R,s1), imap(R,s2)); |
---|
| 1219 | // the last parameter is optional; above it was G=<xy> |
---|
| 1220 | // the output will be reduced with respect to G |
---|
[5482cda] | 1221 | lpSubstitute(imap(R,f), imap(R,s1), imap(R,s2), imap(R,G)); |
---|
[ccef1e] | 1222 | } |
---|
[d41266] | 1223 | |
---|
[ccef1e] | 1224 | // another example: |
---|
| 1225 | /* |
---|
[d41266] | 1226 | //////// EXAMPLE B //////// |
---|
[5482cda] | 1227 | ring r = 0,(x,y,z),dp; |
---|
[fceb4e] | 1228 | def R = freeAlgebra(r, 4); |
---|
[5482cda] | 1229 | setring R; |
---|
| 1230 | |
---|
[6a4f0d] | 1231 | poly f = 3*x*x+y*x; |
---|
| 1232 | poly g = z*x+y; |
---|
| 1233 | poly h = 7*x*z+x; |
---|
[5482cda] | 1234 | ideal I = f,g,h; |
---|
[6a4f0d] | 1235 | ideal s1 = x, y; |
---|
| 1236 | ideal s2 = y*z*z, x; |
---|
[5482cda] | 1237 | |
---|
[16610f] | 1238 | int minDegBound = lpCalcSubstDegBound(I,s1,s2); |
---|
[5482cda] | 1239 | setring r; |
---|
[fceb4e] | 1240 | def R1 = freeAlgebra(r, minDegBound); |
---|
[5482cda] | 1241 | setring R1; |
---|
| 1242 | |
---|
| 1243 | ideal I = imap(R,I); |
---|
| 1244 | ideal s1 = imap(R,s1); |
---|
| 1245 | ideal s2 = imap(R,s2); |
---|
| 1246 | for (int i = 1; i <= size(I); i++) { |
---|
| 1247 | lpSubstitute(I[i], s1, s2); |
---|
| 1248 | } |
---|
[ccef1e] | 1249 | */ |
---|
[5482cda] | 1250 | |
---|
| 1251 | static proc lpIndexOf(ideal I, poly p) { |
---|
| 1252 | for (int i = 1; i <= size(I); i++) { |
---|
| 1253 | if (I[i] == p) { |
---|
| 1254 | return (i); |
---|
| 1255 | } |
---|
[4d9f75e] | 1256 | } kill i; |
---|
[5482cda] | 1257 | return (-1); |
---|
| 1258 | } |
---|
| 1259 | |
---|
| 1260 | static proc ivIndexOf(list L, intvec iv) { |
---|
| 1261 | for (int i = 1; i <= size(L); i++) { |
---|
| 1262 | if (L[i] == iv) { |
---|
| 1263 | return (i); |
---|
| 1264 | } |
---|
[4d9f75e] | 1265 | } kill i; |
---|
[5482cda] | 1266 | return (-1); |
---|
| 1267 | } |
---|
| 1268 | |
---|
| 1269 | |
---|
[16610f] | 1270 | static proc lpCalcSubstDegBoundSingle(poly f, ideal s1, ideal s2) |
---|
| 1271 | "USAGE: lpCalcSubstDegBoundSingle(f,s1,s2); f letterplace polynomial, s1 list (ideal) of variables |
---|
[5edf31] | 1272 | to replace, s2 list (ideal) of polynomials to replace with |
---|
[5482cda] | 1273 | RETURN: int, the min degbound required to perform the substitution |
---|
| 1274 | ASSUME: - basering is a Letterplace ring |
---|
[16610f] | 1275 | EXAMPLE: example lpCalcSubstDegBoundSingle; shows examples |
---|
[5482cda] | 1276 | " |
---|
| 1277 | { |
---|
| 1278 | int maxDegBound = 0; |
---|
| 1279 | for (int i = 1; i <= size(f); i++) { |
---|
| 1280 | intvec ivfi = lp2iv(f[i]); |
---|
| 1281 | int tmpDegBound; |
---|
| 1282 | for (int j = 1; j <= size(ivfi); j++) { |
---|
| 1283 | int varindex = ivfi[j]; |
---|
[8a57d4] | 1284 | if (varindex > 0) { |
---|
| 1285 | int subindex = lpIndexOf(s1, var(varindex)); |
---|
| 1286 | if (subindex > 0) { |
---|
| 1287 | tmpDegBound = tmpDegBound + deg(s2[subindex]); |
---|
| 1288 | } else { |
---|
| 1289 | tmpDegBound = tmpDegBound + 1; |
---|
| 1290 | } |
---|
| 1291 | kill subindex; |
---|
[5482cda] | 1292 | } |
---|
[8a57d4] | 1293 | kill varindex; |
---|
[4d9f75e] | 1294 | } kill j; |
---|
[5482cda] | 1295 | if (tmpDegBound > maxDegBound) { |
---|
| 1296 | maxDegBound = tmpDegBound; |
---|
| 1297 | } |
---|
[4d9f75e] | 1298 | kill ivfi; kill tmpDegBound; |
---|
| 1299 | } kill i; |
---|
[5482cda] | 1300 | |
---|
| 1301 | // increase degbound by 50% when ideal is provided |
---|
| 1302 | // needed for lpNF |
---|
[634a32] | 1303 | maxDegBound = maxDegBound + (maxDegBound div 2); |
---|
[5482cda] | 1304 | |
---|
| 1305 | return (maxDegBound); |
---|
| 1306 | } |
---|
[7e51648] | 1307 | example |
---|
| 1308 | { |
---|
[16610f] | 1309 | // see lpCalcSubstDegBound() |
---|
[d41266] | 1310 | } |
---|
[5482cda] | 1311 | |
---|
[16610f] | 1312 | proc lpCalcSubstDegBound(ideal I, ideal s1, ideal s2) |
---|
| 1313 | "USAGE: lpCalcSubstDegBound(I,s1,s2); I ideal of polynomials, s1 ideal of variables to replace, s2 ideal of polynomials to replace with |
---|
[5482cda] | 1314 | RETURN: int, the min degbound required to perform all of the substitutions |
---|
| 1315 | ASSUME: - basering is a Letterplace ring |
---|
[16610f] | 1316 | EXAMPLE: example lpCalcSubstDegBound; shows examples |
---|
[d41266] | 1317 | NOTE: convenience method |
---|
[5482cda] | 1318 | " |
---|
| 1319 | { |
---|
| 1320 | int maxDegBound = 0; |
---|
| 1321 | for (int i = 1; i <= size(I); i++) { |
---|
[16610f] | 1322 | int tmpDegBound = lpCalcSubstDegBoundSingle(I[i], s1, s2, #); |
---|
[5482cda] | 1323 | if (tmpDegBound > maxDegBound) { |
---|
| 1324 | maxDegBound = tmpDegBound; |
---|
| 1325 | } |
---|
[4d9f75e] | 1326 | kill tmpDegBound; |
---|
| 1327 | } kill i; |
---|
[5482cda] | 1328 | return (maxDegBound); |
---|
| 1329 | } |
---|
[7e51648] | 1330 | example |
---|
| 1331 | { |
---|
[16610f] | 1332 | "EXAMPLE:"; echo = 2; |
---|
| 1333 | ring r = 0,(x,y,z),dp; |
---|
[fceb4e] | 1334 | def R = freeAlgebra(r, 4); |
---|
[16610f] | 1335 | setring R; |
---|
| 1336 | ideal I = 3*x*x+y*x, x*y*x - z; |
---|
| 1337 | ideal s1 = x, y; // z --> z |
---|
| 1338 | ideal s2 = y*z*z, x; // i.e. x --> yzz and y --> x |
---|
| 1339 | // the substitution probably needs a higher degbound |
---|
| 1340 | lpCalcSubstDegBound(I,s1,s2); |
---|
| 1341 | lpCalcSubstDegBound(I[1],s1,s2); |
---|
[d41266] | 1342 | } |
---|
[5482cda] | 1343 | |
---|
| 1344 | static proc isSF(intvec S, intvec I) |
---|
| 1345 | " |
---|
| 1346 | PURPOSE: |
---|
| 1347 | checks, if a word S is a suffix of another word I |
---|
| 1348 | " |
---|
| 1349 | { |
---|
| 1350 | int n = size(S); |
---|
| 1351 | if (n <= 0 || S == 0) {return(1);} |
---|
| 1352 | int m = size(I); |
---|
| 1353 | if (m < n) {return(0);} |
---|
| 1354 | intvec IS = I[(m-n+1)..m]; |
---|
| 1355 | if (IS == S) {return(1);} |
---|
| 1356 | else {return(0);} |
---|
| 1357 | } |
---|
| 1358 | |
---|
| 1359 | static proc isIF(intvec IF, intvec I) |
---|
| 1360 | " |
---|
| 1361 | PURPOSE: |
---|
| 1362 | checks, if a word IF is an infix of another word I |
---|
| 1363 | " |
---|
| 1364 | { |
---|
| 1365 | int n = size(IF); |
---|
| 1366 | int m = size(I); |
---|
| 1367 | |
---|
| 1368 | if (n <= 0 || IF == 0) {return(1);} |
---|
| 1369 | if (m < n) {return(0);} |
---|
| 1370 | |
---|
| 1371 | for (int i = 0; (n + i) <= m; i++){ |
---|
| 1372 | intvec IIF = I[(1 + i)..(n + i)]; |
---|
| 1373 | if (IIF == IF) { |
---|
| 1374 | return(1); |
---|
| 1375 | } |
---|
[4d9f75e] | 1376 | kill IIF; |
---|
| 1377 | } kill i; |
---|
[5482cda] | 1378 | return(0); |
---|
| 1379 | } |
---|
[704cba] | 1380 | |
---|
[04d263] | 1381 | // no longer working with new interface and new orderings |
---|
| 1382 | /* // TODO: use original ring attrib to create a new letterplace ring */ |
---|
| 1383 | /* // removes a variable from a letterplace ring (a bit of a hack) */ |
---|
| 1384 | /* static proc lpDelVar(int index) { */ |
---|
[921f32] | 1385 | /* int lV = lpVarBlockSize(basering); // number of variables in the main block */ |
---|
[04d263] | 1386 | /* int d = lpDegBound(basering); // degree bround */ |
---|
| 1387 | /* list LR = ringlist(basering); */ |
---|
| 1388 | |
---|
| 1389 | /* if (!(index >= 1 && index <= lV)) { return (basering); } // invalid index */ |
---|
| 1390 | |
---|
| 1391 | /* // remove frome the variable list */ |
---|
| 1392 | /* for (int i = (d-1)*lV + index; i >= 1; i = i - lV) { */ |
---|
| 1393 | /* LR[2] = delete(LR[2], i); */ |
---|
| 1394 | /* } kill i; */ |
---|
| 1395 | |
---|
| 1396 | /* // remove from a ordering */ |
---|
| 1397 | /* intvec aiv = LR[3][1][2]; */ |
---|
| 1398 | /* aiv = aiv[1..(d*lV-d)]; */ |
---|
| 1399 | /* LR[3][1][2] = aiv; */ |
---|
| 1400 | |
---|
| 1401 | /* // remove block orderings */ |
---|
| 1402 | /* int del = (lV - index); */ |
---|
| 1403 | /* int cnt = -1; */ |
---|
| 1404 | /* for (int i = size(LR[3]); i >= 2; i--) { */ |
---|
| 1405 | /* if (LR[3][i][2] != 0) { */ |
---|
| 1406 | /* for (int j = size(LR[3][i][2]); j >= 1; j--) { */ |
---|
| 1407 | /* cnt++; // next 1 */ |
---|
| 1408 | /* if (cnt%lV == del) { */ |
---|
| 1409 | /* // delete */ |
---|
| 1410 | /* if (size(LR[3][i][2]) > 1) { // if we have more than one element left, delete one */ |
---|
| 1411 | /* LR[3][i][2] = delete(LR[3][i][2],j); */ |
---|
| 1412 | /* } else { // otherwise delete the whole block */ |
---|
| 1413 | /* LR[3] = delete(LR[3], i); */ |
---|
| 1414 | /* break; */ |
---|
| 1415 | /* } */ |
---|
| 1416 | /* } */ |
---|
| 1417 | /* } kill j; */ |
---|
| 1418 | /* } */ |
---|
| 1419 | /* } kill i; */ |
---|
| 1420 | |
---|
| 1421 | /* def R = setLetterplaceAttributes(ring(LR),d,lV-1); */ |
---|
| 1422 | /* return (R); */ |
---|
| 1423 | /* } */ |
---|
| 1424 | /* example */ |
---|
| 1425 | /* { */ |
---|
| 1426 | /* "EXAMPLE:"; echo = 2; */ |
---|
| 1427 | /* ring r = 0,(x,y,z),dp; */ |
---|
[fceb4e] | 1428 | /* def A = freeAlgebra(r, 3); */ |
---|
[04d263] | 1429 | /* setring A; A; */ |
---|
| 1430 | /* def R = lpDelVar(2); setring R; R; */ |
---|
| 1431 | /* } */ |
---|