001/* 002 * $Id: SolvableSyzygyAbstract.java 5267 2015-07-27 17:57:50Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.List; 011import java.util.Map; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.gb.Reduction; 016import edu.jas.gb.ReductionSeq; 017import edu.jas.gb.SolvableReduction; 018import edu.jas.gb.SolvableReductionSeq; 019import edu.jas.poly.ExpVector; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenSolvablePolynomial; 022import edu.jas.poly.GenSolvablePolynomialRing; 023import edu.jas.poly.ModuleList; 024import edu.jas.poly.PolynomialList; 025import edu.jas.structure.GcdRingElem; 026import edu.jas.structure.RingElem; 027import edu.jas.vector.BasicLinAlg; 028 029 030/** 031 * Syzygy abstract class for solvable polynomials. Implements Syzygy 032 * computations and tests. 033 * @param <C> coefficient type 034 * @author Heinz Kredel 035 */ 036 037public abstract class SolvableSyzygyAbstract<C extends GcdRingElem<C>> implements SolvableSyzygy<C> { 038 039 040 private static final Logger logger = Logger.getLogger(SolvableSyzygyAbstract.class); 041 042 043 private final boolean debug = logger.isDebugEnabled(); 044 045 046 /** 047 * Solvable reduction engine. 048 */ 049 public final SolvableReduction<C> sred; 050 051 052 /** 053 * Reduction engine. 054 */ 055 protected Reduction<C> red; 056 057 058 /** 059 * Linear algebra engine. 060 */ 061 protected BasicLinAlg<GenPolynomial<C>> blas; 062 063 064 /** 065 * Constructor. 066 */ 067 public SolvableSyzygyAbstract() { 068 red = new ReductionSeq<C>(); 069 sred = new SolvableReductionSeq<C>(); 070 blas = new BasicLinAlg<GenPolynomial<C>>(); 071 } 072 073 074 /** 075 * Left syzygy for left Groebner base. 076 * @param F a Groebner base. 077 * @return leftSyz(F), a basis for the left module of syzygies for F. 078 */ 079 public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(List<GenSolvablePolynomial<C>> F) { 080 return leftZeroRelations(0, F); 081 } 082 083 084 /** 085 * Left syzygy for left Groebner base. 086 * @param modv number of module variables. 087 * @param F a Groebner base. 088 * @return leftSyz(F), a basis for the left module of syzygies for F. 089 */ 090 public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(int modv, List<GenSolvablePolynomial<C>> F) { 091 List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>(); 092 ArrayList<GenSolvablePolynomial<C>> S = new ArrayList<GenSolvablePolynomial<C>>(F.size()); 093 for (int i = 0; i < F.size(); i++) { 094 S.add(null); 095 } 096 GenSolvablePolynomial<C> pi, pj, s, h, zero; 097 zero = null; 098 for (int i = 0; i < F.size(); i++) { 099 pi = F.get(i); 100 if (zero == null) { 101 zero = pi.ring.getZERO(); 102 } 103 for (int j = i + 1; j < F.size(); j++) { 104 pj = F.get(j); 105 //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj); 106 107 if (!red.moduleCriterion(modv, pi, pj)) { 108 continue; 109 } 110 // if ( ! red.criterion4( pi, pj ) ) continue; 111 List<GenSolvablePolynomial<C>> row = new ArrayList<GenSolvablePolynomial<C>>(S); 112 s = sred.leftSPolynomial(row, i, pi, j, pj); 113 //logger.info("row = " + row); 114 if (s.isZERO()) { 115 Z.add(row); 116 continue; 117 } 118 119 h = sred.leftNormalform(row, F, s); 120 if (!h.isZERO()) { 121 throw new ArithmeticException("Syzygy no leftGB"); 122 } 123 if (logger.isDebugEnabled()) { 124 logger.info("row = " + row); 125 } 126 Z.add(row); 127 } 128 } 129 // set null to zero 130 for (List<GenSolvablePolynomial<C>> vr : Z) { 131 for (int j = 0; j < vr.size(); j++) { 132 if (vr.get(j) == null) { 133 vr.set(j, zero); 134 } 135 } 136 } 137 return Z; 138 } 139 140 141 /** 142 * Left syzygy for left module Groebner base. 143 * @param M a Groebner base. 144 * @return leftSyz(M), a basis for the left module of syzygies for M. 145 */ 146 @SuppressWarnings("unchecked") 147 public ModuleList<C> leftZeroRelations(ModuleList<C> M) { 148 ModuleList<C> N = null; 149 if (M == null || M.list == null) { 150 return N; 151 } 152 if (M.rows == 0 || M.cols == 0) { 153 return N; 154 } 155 GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO(); 156 //logger.info("zero = " + zero); 157 158 //ModuleList<C> Np = null; 159 PolynomialList<C> F = M.getPolynomialList(); 160 int modv = M.cols; // > 0 161 logger.info("modv = " + modv); 162 List<List<GenSolvablePolynomial<C>>> G = leftZeroRelations(modv, F.castToSolvableList()); 163 //if (G == null) { 164 // return N; 165 //} 166 List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>(); 167 for (int i = 0; i < G.size(); i++) { 168 List<GenSolvablePolynomial<C>> Gi = G.get(i); 169 List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>(); 170 //System.out.println("\nG("+i+") = " + G.get(i)); 171 for (int j = 0; j < Gi.size(); j++) { 172 //System.out.println("\nG("+i+","+j+") = " + Gi.get(j)); 173 GenSolvablePolynomial<C> p = Gi.get(j); 174 if (p != null) { 175 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring); 176 //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() ); 177 if (r.size() == 0) { 178 Zi.add(zero); 179 } else if (r.size() == 1) { 180 GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0]; 181 Zi.add(vi); 182 } else { // will not happen 183 throw new RuntimeException("Map.size() > 1 = " + r.size()); 184 } 185 } 186 } 187 //System.out.println("\nZ("+i+") = " + Zi); 188 Z.add(Zi); 189 } 190 N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z); 191 //System.out.println("\n\nN = " + N); 192 return N; 193 } 194 195 196 /** 197 * Right syzygy module from Groebner base. 198 * @param F a solvable polynomial list, a Groebner base. 199 * @return syz(F), a basis for the module of right syzygies for F. 200 */ 201 public List<List<GenSolvablePolynomial<C>>> rightZeroRelations(List<GenSolvablePolynomial<C>> F) { 202 return rightZeroRelations(0, F); 203 } 204 205 206 /** 207 * Right syzygy module from Groebner base. 208 * @param modv number of module variables. 209 * @param F a solvable polynomial list, a Groebner base. 210 * @return syz(F), a basis for the module of right syzygies for F. 211 */ 212 @SuppressWarnings("unchecked") 213 public List<List<GenSolvablePolynomial<C>>> rightZeroRelations(int modv, List<GenSolvablePolynomial<C>> F) { 214 GenSolvablePolynomialRing<C> ring = null; 215 for (GenSolvablePolynomial<C> p : F) { 216 if (p != null) { 217 ring = p.ring; 218 break; 219 } 220 } 221 List<List<GenSolvablePolynomial<C>>> Z; 222 if (ring == null) { // all null 223 Z = new ArrayList<List<GenSolvablePolynomial<C>>>(1); 224 Z.add(F); 225 return Z; 226 } 227 //System.out.println("ring to reverse = " + ring.toScript()); 228 GenSolvablePolynomialRing<C> rring = ring.reverse(true); 229 GenSolvablePolynomial<C> q; 230 List<GenSolvablePolynomial<C>> rF; 231 rF = new ArrayList<GenSolvablePolynomial<C>>(F.size()); 232 for (GenSolvablePolynomial<C> p : F) { 233 if (p != null) { 234 q = (GenSolvablePolynomial<C>) p.reverse(rring); 235 rF.add(q); 236 } 237 } 238 if (debug) { 239 PolynomialList<C> pl = new PolynomialList<C>(rring, rF); 240 logger.info("reversed problem = " + pl.toScript()); 241 } 242 List<List<GenSolvablePolynomial<C>>> rZ = leftZeroRelations(modv, rF); 243 if (debug) { 244 boolean isit = isLeftZeroRelation(rZ, rF); 245 logger.debug("isLeftZeroRelation = " + isit); 246 } 247 GenSolvablePolynomialRing<C> oring = rring.reverse(true); 248 if (debug) { 249 logger.debug("ring == oring: " + ring.equals(oring)); 250 } 251 ring = oring; 252 Z = new ArrayList<List<GenSolvablePolynomial<C>>>(rZ.size()); 253 for (List<GenSolvablePolynomial<C>> z : rZ) { 254 if (z == null) { 255 continue; 256 } 257 List<GenSolvablePolynomial<C>> s; 258 s = new ArrayList<GenSolvablePolynomial<C>>(z.size()); 259 for (GenSolvablePolynomial<C> p : z) { 260 if (p != null) { 261 q = (GenSolvablePolynomial<C>) p.reverse(ring); 262 s.add(q); 263 } 264 } 265 Z.add(s); 266 } 267 return Z; 268 } 269 270 271 /** 272 * Right syzygy for right module Groebner base. 273 * @param M a Groebner base. 274 * @return rightSyz(M), a basis for the right module of syzygies for M. 275 */ 276 @SuppressWarnings("unchecked") 277 public ModuleList<C> rightZeroRelations(ModuleList<C> M) { 278 ModuleList<C> N = null; 279 if (M == null || M.list == null) { 280 return N; 281 } 282 if (M.rows == 0 || M.cols == 0) { 283 return N; 284 } 285 GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO(); 286 //logger.info("zero = " + zero); 287 288 //ModuleList<C> Np = null; 289 PolynomialList<C> F = M.getPolynomialList(); 290 int modv = M.cols; // > 0 291 logger.info("modv = " + modv); 292 List<List<GenSolvablePolynomial<C>>> G = rightZeroRelations(modv, F.castToSolvableList()); 293 //if (G == null) { 294 // return N; 295 //} 296 List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>(); 297 for (int i = 0; i < G.size(); i++) { 298 List<GenSolvablePolynomial<C>> Gi = G.get(i); 299 List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>(); 300 //System.out.println("\nG("+i+") = " + G.get(i)); 301 for (int j = 0; j < Gi.size(); j++) { 302 //System.out.println("\nG("+i+","+j+") = " + Gi.get(j)); 303 GenSolvablePolynomial<C> p = Gi.get(j); 304 if (p != null) { 305 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring); 306 //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() ); 307 if (r.size() == 0) { 308 Zi.add(zero); 309 } else if (r.size() == 1) { 310 GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0]; 311 Zi.add(vi); 312 } else { // will not happen 313 throw new RuntimeException("Map.size() > 1 = " + r.size()); 314 } 315 } 316 } 317 //System.out.println("\nZ("+i+") = " + Zi); 318 Z.add(Zi); 319 } 320 N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z); 321 //System.out.println("\n\nN = " + N); 322 return N; 323 } 324 325 326 /** 327 * Test if left syzygy. 328 * @param Z list of sysygies. 329 * @param F a polynomial list. 330 * @return true, if Z is a list of left syzygies for F, else false. 331 */ 332 public boolean isLeftZeroRelation(List<List<GenSolvablePolynomial<C>>> Z, List<GenSolvablePolynomial<C>> F) { 333 List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F); 334 for (List<GenSolvablePolynomial<C>> row : Z) { 335 // p has wrong type: 336 GenPolynomial<C> p = blas.scalarProduct(PolynomialList.<C> castToList(row), Fp); 337 if (p == null) { 338 continue; 339 } 340 if (!p.isZERO()) { 341 logger.info("is not ZeroRelation = " + p); 342 return false; 343 } 344 } 345 return true; 346 } 347 348 349 /** 350 * Test if right syzygy. 351 * @param Z list of sysygies. 352 * @param F a polynomial list. 353 * @return true, if Z is a list of right syzygies for F, else false. 354 */ 355 public boolean isRightZeroRelation(List<List<GenSolvablePolynomial<C>>> Z, 356 List<GenSolvablePolynomial<C>> F) { 357 List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F); 358 for (List<GenSolvablePolynomial<C>> row : Z) { 359 List<GenPolynomial<C>> yrow = PolynomialList.<C> castToList(row); 360 // p has wrong type: 361 GenPolynomial<C> p = blas.scalarProduct(Fp, yrow); // param order 362 if (p == null) { 363 continue; 364 } 365 if (!p.isZERO()) { 366 logger.info("is not ZeroRelation = " + p); 367 return false; 368 } 369 } 370 return true; 371 } 372 373 374 /** 375 * Test if left sysygy of modules 376 * @param Z list of sysygies. 377 * @param F a module list. 378 * @return true, if Z is a list of left syzygies for F, else false. 379 */ 380 public boolean isLeftZeroRelation(ModuleList<C> Z, ModuleList<C> F) { 381 if (Z == null || Z.list == null) { 382 return true; 383 } 384 for (List<GenPolynomial<C>> row : Z.list) { 385 List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, F.list); 386 if (!blas.isZero(zr)) { 387 logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr); 388 return false; 389 } 390 } 391 return true; 392 } 393 394 395 /** 396 * Test if right sysygy of modules 397 * @param Z list of sysygies. 398 * @param F a module list. 399 * @return true, if Z is a list of right syzygies for F, else false. 400 */ 401 public boolean isRightZeroRelation(ModuleList<C> Z, ModuleList<C> F) { 402 if (Z == null || Z.list == null) { 403 return true; 404 } 405 for (List<GenPolynomial<C>> row : Z.list) { 406 List<GenPolynomial<C>> zr = blas.rightScalarProduct(row, F.list); 407 //List<GenPolynomial<C>> zr = blas.scalarProduct(row,F.list); 408 if (!blas.isZero(zr)) { 409 logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr); 410 return false; 411 } 412 } 413 return true; 414 } 415 416 417 /** 418 * Left syzygy module from arbitrary base. 419 * @param F a solvable polynomial list. 420 * @return syz(F), a basis for the module of left syzygies for F. 421 */ 422 public List<List<GenSolvablePolynomial<C>>> leftZeroRelationsArbitrary(List<GenSolvablePolynomial<C>> F) { 423 return leftZeroRelationsArbitrary(0, F); 424 } 425 426 427 /** 428 * Left syzygy for arbitrary left module base. 429 * @param M an arbitrary base. 430 * @return leftSyz(M), a basis for the left module of syzygies for M. 431 */ 432 @SuppressWarnings("unchecked") 433 public ModuleList<C> leftZeroRelationsArbitrary(ModuleList<C> M) { 434 ModuleList<C> N = null; 435 if (M == null || M.list == null) { 436 return N; 437 } 438 if (M.rows == 0 || M.cols == 0) { 439 return N; 440 } 441 GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO(); 442 //logger.info("zero = " + zero); 443 444 //ModuleList<C> Np = null; 445 PolynomialList<C> F = M.getPolynomialList(); 446 int modv = M.cols; // > 0 447 logger.info("modv = " + modv); 448 List<List<GenSolvablePolynomial<C>>> G = leftZeroRelationsArbitrary(modv, F.castToSolvableList()); 449 if (G == null) { 450 return N; 451 } 452 List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>(); 453 for (int i = 0; i < G.size(); i++) { 454 List<GenSolvablePolynomial<C>> Gi = G.get(i); 455 List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>(); 456 //System.out.println("\nG("+i+") = " + G.get(i)); 457 for (int j = 0; j < Gi.size(); j++) { 458 //System.out.println("\nG("+i+","+j+") = " + Gi.get(j)); 459 GenSolvablePolynomial<C> p = Gi.get(j); 460 if (p != null) { 461 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring); 462 //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() ); 463 if (r.size() == 0) { 464 Zi.add(zero); 465 } else if (r.size() == 1) { 466 GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0]; 467 Zi.add(vi); 468 } else { // will not happen 469 throw new RuntimeException("Map.size() > 1 = " + r.size()); 470 } 471 } 472 } 473 //System.out.println("\nZ("+i+") = " + Zi); 474 Z.add(Zi); 475 } 476 N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z); 477 //System.out.println("\n\nN = " + N); 478 return N; 479 } 480 481 482 /** 483 * Right syzygy module from arbitrary base. 484 * @param F a solvable polynomial list. 485 * @return syz(F), a basis for the module of right syzygies for F. 486 */ 487 public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(List<GenSolvablePolynomial<C>> F) { 488 return rightZeroRelationsArbitrary(0, F); 489 } 490 491 492 /** 493 * Right syzygy module from arbitrary base. 494 * @param modv number of module variables. 495 * @param F a solvable polynomial list. 496 * @return syz(F), a basis for the module of right syzygies for F. 497 */ 498 @SuppressWarnings("unchecked") 499 public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(int modv, 500 List<GenSolvablePolynomial<C>> F) { 501 GenSolvablePolynomialRing<C> ring = null; 502 for (GenSolvablePolynomial<C> p : F) { 503 if (p != null) { 504 ring = p.ring; 505 break; 506 } 507 } 508 List<List<GenSolvablePolynomial<C>>> Z; 509 if (ring == null) { // all null 510 Z = new ArrayList<List<GenSolvablePolynomial<C>>>(1); 511 Z.add(F); 512 return Z; 513 } 514 GenSolvablePolynomialRing<C> rring = ring.reverse(true); 515 GenSolvablePolynomial<C> q; 516 List<GenSolvablePolynomial<C>> rF; 517 rF = new ArrayList<GenSolvablePolynomial<C>>(F.size()); 518 for (GenSolvablePolynomial<C> p : F) { 519 if (p != null) { 520 q = (GenSolvablePolynomial<C>) p.reverse(rring); 521 rF.add(q); 522 } 523 } 524 if (debug) { 525 PolynomialList<C> pl = new PolynomialList<C>(rring, rF); 526 logger.info("reversed problem = " + pl.toScript()); 527 } 528 List<List<GenSolvablePolynomial<C>>> rZ = leftZeroRelationsArbitrary(modv, rF); 529 if (debug) { 530 ModuleList<C> pl = new ModuleList<C>(rring, rZ); 531 logger.info("reversed syzygies = " + pl.toScript()); 532 boolean isit = isLeftZeroRelation(rZ, rF); 533 logger.info("isLeftZeroRelation = " + isit); 534 } 535 GenSolvablePolynomialRing<C> oring = rring.reverse(true); 536 if (debug) { 537 logger.info("ring == oring: " + ring.equals(oring)); 538 } 539 ring = oring; 540 Z = new ArrayList<List<GenSolvablePolynomial<C>>>(rZ.size()); 541 for (List<GenSolvablePolynomial<C>> z : rZ) { 542 if (z == null) { 543 continue; 544 } 545 List<GenSolvablePolynomial<C>> s; 546 s = new ArrayList<GenSolvablePolynomial<C>>(z.size()); 547 for (GenSolvablePolynomial<C> p : z) { 548 if (p != null) { 549 q = (GenSolvablePolynomial<C>) p.reverse(ring); 550 s.add(q); 551 //System.out.println("p = " + p + "\nreverse(p) = " + q); 552 } 553 } 554 Z.add(s); 555 } 556 return Z; 557 } 558 559 560 /** 561 * Right syzygy for arbitrary base. 562 * @param M an arbitray base. 563 * @return rightSyz(M), a basis for the right module of syzygies for M. 564 */ 565 @SuppressWarnings("unchecked") 566 public ModuleList<C> rightZeroRelationsArbitrary(ModuleList<C> M) { 567 ModuleList<C> N = null; 568 if (M == null || M.list == null) { 569 return N; 570 } 571 if (M.rows == 0 || M.cols == 0) { 572 return N; 573 } 574 GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO(); 575 //logger.info("zero = " + zero); 576 577 //ModuleList<C> Np = null; 578 PolynomialList<C> F = M.getPolynomialList(); 579 int modv = M.cols; // > 0 580 logger.info("modv = " + modv); 581 List<List<GenSolvablePolynomial<C>>> G = rightZeroRelationsArbitrary(modv, F.castToSolvableList()); 582 //if (G == null) { 583 // return N; 584 //} 585 List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>(); 586 for (int i = 0; i < G.size(); i++) { 587 List<GenSolvablePolynomial<C>> Gi = G.get(i); 588 List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>(); 589 //System.out.println("G("+i+") = " + Gi); 590 for (int j = 0; j < Gi.size(); j++) { 591 GenSolvablePolynomial<C> p = Gi.get(j); 592 //System.out.println("G("+i+","+j+") = " + p); 593 if (p != null) { 594 Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring); 595 //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() ); 596 if (r.size() == 0) { 597 Zi.add(zero); 598 } else if (r.size() == 1) { 599 GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0]; 600 Zi.add(vi); 601 } else { // will not happen 602 logger.error("p = " + p + ", r = " + r); 603 throw new RuntimeException("Map.size() > 1 = " + r.size()); 604 } 605 } 606 } 607 //System.out.println("\nZ("+i+") = " + Zi); 608 Z.add(Zi); 609 } 610 N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z); 611 //System.out.println("\n\nN = " + N); 612 return N; 613 } 614 615 616 /** 617 * Test left Ore condition. 618 * @param a solvable polynomial 619 * @param b solvable polynomial 620 * @param oc = [p,q] two solvable polynomials 621 * @return true if p*a = q*b, else false 622 */ 623 public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, 624 GenSolvablePolynomial<C>[] oc) { 625 GenSolvablePolynomial<C> c = oc[0].multiply(a); 626 GenSolvablePolynomial<C> d = oc[1].multiply(b); 627 return c.equals(d); 628 } 629 630 631 /** 632 * Test right Ore condition. 633 * @param a solvable polynomial 634 * @param b solvable polynomial 635 * @param oc = [p,q] two solvable polynomials 636 * @return true if a*p = b*q, else false 637 */ 638 public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, 639 GenSolvablePolynomial<C>[] oc) { 640 GenSolvablePolynomial<C> c = a.multiply(oc[0]); 641 GenSolvablePolynomial<C> d = b.multiply(oc[1]); 642 return c.equals(d); 643 } 644 645 646 /** 647 * Left simplifier. Method of Apel & Lassner (1987). 648 * @param a solvable polynomial 649 * @param b solvable polynomial 650 * @return [p,q] with a/b = p/q and q is minimal and monic 651 */ 652 public abstract GenSolvablePolynomial<C>[] leftSimplifier(GenSolvablePolynomial<C> a, 653 GenSolvablePolynomial<C> b); 654 655 656 /** 657 * Comparison like SolvableLocal or SolvableQuotient. 658 * @param num SolvablePolynomial. 659 * @param den SolvablePolynomial. 660 * @param n SolvablePolynomial. 661 * @param d SolvablePolynomial. 662 * @return sign((num/den)-(n/d)). 663 */ 664 public int compare(GenSolvablePolynomial<C> num, GenSolvablePolynomial<C> den, 665 GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) { 666 if (n == null || n.isZERO()) { 667 return num.signum(); 668 } 669 if (num.isZERO()) { 670 return -n.signum(); 671 } 672 // assume sign(den,b.den) > 0 673 int s1 = num.signum(); 674 int s2 = n.signum(); 675 int t = (s1 - s2) / 2; 676 if (t != 0) { 677 System.out.println("compareTo: t = " + t); 678 //return t; 679 } 680 if (den.compareTo(d) == 0) { 681 return num.compareTo(n); 682 } 683 GenSolvablePolynomial<C> r, s; 684 // if (den.isONE()) { } 685 // if (b.den.isONE()) { } 686 GenSolvablePolynomial<C>[] oc = leftOreCond(den, d); 687 if (debug) { 688 System.out.println("oc[0] den =<>= oc[1] d: (" + oc[0] + ") (" + den + ") = (" + oc[1] + ") (" 689 + d + ")"); 690 } 691 //System.out.println("oc[0] = " + oc[0]); 692 //System.out.println("oc[1] = " + oc[1]); 693 r = oc[0].multiply(num); 694 s = oc[1].multiply(n); 695 logger.info("compare: r = " + r + ", s = " + s); 696 return r.compareTo(s); 697 } 698 699} 700 701 702/** 703 * Container for module resolution components. 704 * @param <C> coefficient type 705 */ 706class SolvResPart<C extends RingElem<C>> implements Serializable { 707 708 709 public final ModuleList<C> module; 710 711 712 public final ModuleList<C> GB; 713 714 715 public final ModuleList<C> syzygy; 716 717 718 /** 719 * SolvResPart. 720 * @param m a module list. 721 * @param g a module list GB. 722 * @param z a syzygy module list. 723 */ 724 public SolvResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) { 725 module = m; 726 GB = g; 727 syzygy = z; 728 } 729 730 731 /** 732 * toString. 733 */ 734 @Override 735 public String toString() { 736 StringBuffer s = new StringBuffer("SolvResPart(\n"); 737 s.append("module = " + module); 738 s.append("\n GB = " + GB); 739 s.append("\n syzygy = " + syzygy); 740 s.append(")"); 741 return s.toString(); 742 } 743} 744 745 746/** 747 * Container for polynomial resolution components. 748 * @param <C> coefficient type 749 */ 750class SolvResPolPart<C extends RingElem<C>> implements Serializable { 751 752 753 public final PolynomialList<C> ideal; 754 755 756 public final PolynomialList<C> GB; 757 758 759 public final ModuleList<C> syzygy; 760 761 762 /** 763 * SolvResPolPart. 764 * @param m a polynomial list. 765 * @param g a polynomial list GB. 766 * @param z a syzygy module list. 767 */ 768 public SolvResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) { 769 ideal = m; 770 GB = g; 771 syzygy = z; 772 } 773 774 775 /** 776 * toString. 777 */ 778 @Override 779 public String toString() { 780 StringBuffer s = new StringBuffer("SolvResPolPart(\n"); 781 s.append("ideal = " + ideal); 782 s.append("\n GB = " + GB); 783 s.append("\n syzygy = " + syzygy); 784 s.append(")"); 785 return s.toString(); 786 } 787 788}