001/* 002 * $Id$ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.List; 011import java.util.Random; 012 013import org.apache.logging.log4j.Logger; 014import org.apache.logging.log4j.LogManager; 015 016import edu.jas.fd.SGCDFactory; 017import edu.jas.fd.GreatestCommonDivisorAbstract; 018import edu.jas.gb.SolvableGroebnerBaseAbstract; 019import edu.jas.gbufd.SGBFactory; 020import edu.jas.gbufd.SolvableSyzygyAbstract; 021import edu.jas.gbufd.SolvableSyzygySeq; 022import edu.jas.kern.StringUtil; 023import edu.jas.poly.GenPolynomial; 024import edu.jas.poly.GenSolvablePolynomial; 025import edu.jas.poly.GenSolvablePolynomialRing; 026import edu.jas.poly.PolynomialList; 027import edu.jas.structure.GcdRingElem; 028import edu.jas.structure.QuotPairFactory; 029import edu.jas.structure.RingFactory; 030 031 032/** 033 * SolvableLocalResidue ring factory for SolvableLocalResidue based on 034 * GenSolvablePolynomial with GcdRingElem interface. Objects of this class are 035 * immutable. It represents the "classical quotient ring modulo an ideal". 036 * @author Heinz Kredel 037 */ 038public class SolvableLocalResidueRing<C extends GcdRingElem<C>> implements 039 RingFactory<SolvableLocalResidue<C>>, 040 QuotPairFactory<GenPolynomial<C>, SolvableLocalResidue<C>> { 041 042 043 // Can not extend SolvableLocalRing or SolvableQuotientRing 044 // because of different constructor semantics. 045 046 047 private static final Logger logger = LogManager.getLogger(SolvableLocalResidueRing.class); 048 049 050 private static final boolean debug = logger.isDebugEnabled(); 051 052 053 /** 054 * Solvable polynomial ring of the factory. 055 */ 056 public final GenSolvablePolynomialRing<C> ring; 057 058 059 /** 060 * Solvable polynomial ideal for the reduction. 061 */ 062 public final SolvableIdeal<C> ideal; 063 064 065 /** 066 * Syzygy engine of the factory. 067 */ 068 public final SolvableSyzygyAbstract<C> engine; 069 070 071 /** 072 * FD engine of the factory. 073 */ 074 public final GreatestCommonDivisorAbstract<C> fdengine; 075 076 077 /** 078 * Groebner base engine. 079 */ 080 protected final SolvableGroebnerBaseAbstract<C> bb; 081 082 083 /** 084 * Indicator if this ring is a field. 085 */ 086 protected int isField = -1; // initially unknown 087 088 089 /** 090 * The constructor creates a SolvableLocalResidueRing object from a 091 * SolvableIdeal. 092 * @param i ideal in solvable polynomial ring. 093 */ 094 public SolvableLocalResidueRing(SolvableIdeal<C> i) { 095 if (i == null) { 096 throw new IllegalArgumentException("ideal may not be null"); 097 } 098 ring = i.getRing(); 099 ideal = i.GB(); // cheap if isGB 100 if (ideal.isONE()) { 101 throw new IllegalArgumentException("ideal may not be 1"); 102 } 103 if (ideal.isMaximal()) { 104 isField = 1; 105 //} else if (ideal.isPrime()) { 106 // isField = 1; 107 } else { 108 //isField = 0; 109 logger.warn("ideal not maximal and not known to be prime"); 110 //throw new IllegalArgumentException("ideal must be prime or maximal"); 111 } 112 engine = new SolvableSyzygySeq<C>(ring.coFac); 113 //fdengine = SGCDFactory.<C> getImplementation(ring.coFac); 114 fdengine = SGCDFactory.<C> getFakeImplementation(ring.coFac); 115 bb = SGBFactory.getImplementation(ring.coFac); //new SolvableGroebnerBaseSeq<C>(); 116 logger.debug("solvable local residue ring constructed"); 117 } 118 119 120 /** 121 * Factory for base elements. 122 */ 123 public GenSolvablePolynomialRing<C> pairFactory() { 124 return ring; 125 } 126 127 128 /** 129 * Create from numerator. 130 */ 131 @SuppressWarnings("unchecked") 132 public SolvableLocalResidue<C> create(GenPolynomial<C> n) { 133 return new SolvableLocalResidue<C>(this, (GenSolvablePolynomial<C>) n); 134 } 135 136 137 /** 138 * Create from numerator, denominator pair. 139 */ 140 @SuppressWarnings("unchecked") 141 public SolvableLocalResidue<C> create(GenPolynomial<C> n, GenPolynomial<C> d) { 142 return new SolvableLocalResidue<C>(this, (GenSolvablePolynomial<C>) n, (GenSolvablePolynomial<C>) d); 143 } 144 145 146 /** 147 * Is this structure finite or infinite. 148 * @return true if this structure is finite, else false. 149 */ 150 public boolean isFinite() { 151 return ring.isFinite() && bb.commonZeroTest(ideal.getList()) <= 0; 152 } 153 154 155 /** 156 * Copy SolvableLocalResidue element c. 157 * @param c 158 * @return a copy of c. 159 */ 160 public SolvableLocalResidue<C> copy(SolvableLocalResidue<C> c) { 161 return new SolvableLocalResidue<C>(c.ring, c.num, c.den, true); 162 } 163 164 165 /** 166 * Get the zero element. 167 * @return 0 as SolvableLocalResidue. 168 */ 169 public SolvableLocalResidue<C> getZERO() { 170 return new SolvableLocalResidue<C>(this, ring.getZERO()); 171 } 172 173 174 /** 175 * Get the one element. 176 * @return 1 as SolvableLocalResidue. 177 */ 178 public SolvableLocalResidue<C> getONE() { 179 return new SolvableLocalResidue<C>(this, ring.getONE()); 180 } 181 182 183 /** 184 * Get a list of the generating elements. 185 * @return list of generators for the algebraic structure. 186 */ 187 public List<SolvableLocalResidue<C>> generators() { 188 List<GenSolvablePolynomial<C>> pgens = PolynomialList.<C> castToSolvableList(ring.generators()); 189 List<SolvableLocalResidue<C>> gens = new ArrayList<SolvableLocalResidue<C>>(pgens.size() * 2 - 1); 190 GenSolvablePolynomial<C> one = ring.getONE(); 191 for (GenSolvablePolynomial<C> p : pgens) { 192 SolvableLocalResidue<C> q = new SolvableLocalResidue<C>(this, p); 193 if (!q.isZERO() && !gens.contains(q)) { 194 gens.add(q); 195 if (!p.isONE() && !ideal.contains(p)) { 196 q = new SolvableLocalResidue<C>(this, one, p); 197 gens.add(q); 198 } 199 } 200 } 201 return gens; 202 } 203 204 205 /** 206 * Query if this ring is commutative. 207 * @return true if this ring is commutative, else false. 208 */ 209 public boolean isCommutative() { 210 return ring.isCommutative(); 211 } 212 213 214 /** 215 * Query if this ring is associative. 216 * @return true if this ring is associative, else false. 217 */ 218 @SuppressWarnings("unused") 219 public boolean isAssociative() { 220 if (!ring.isAssociative()) { 221 return false; 222 } 223 SolvableLocalResidue<C> Xi, Xj, Xk, p, q; 224 List<SolvableLocalResidue<C>> gens = generators(); 225 int ngen = gens.size(); 226 for (int i = 0; i < ngen; i++) { 227 Xi = gens.get(i); 228 for (int j = i + 1; j < ngen; j++) { 229 Xj = gens.get(j); 230 for (int k = j + 1; k < ngen; k++) { 231 Xk = gens.get(k); 232 if (Xi.num.degree() == 0 && Xj.num.degree() == 0 && Xk.num.degree() == 0 && 233 Xi.den.degree() == 0 && Xj.den.degree() == 0 && Xk.den.degree() == 0) { 234 //System.out.println("lr degree == 0"); 235 continue; // skip all base elements 236 } 237 try { 238 p = Xk.multiply(Xj).multiply(Xi); 239 q = Xk.multiply(Xj.multiply(Xi)); 240 } catch (IllegalArgumentException e) { 241 e.printStackTrace(); 242 continue; // ignore undefined multiplication 243 } 244 if (p.num.equals(q.num) && p.den.equals(q.den)) { // short cut 245 continue; 246 } 247 if (!p.equals(q)) { 248 //System.out.println("lr assoc: p = " + p.toScript()); 249 //System.out.println("lr assoc: q = " + q.toScript()); 250 //System.out.println("lr assoc: Xk = " + Xk.toScript() + ", Xj = " + Xj.toScript() + ", Xi = " + Xi.toScript()); 251 logger.info("Xk = {}, Xj = {}, Xi = {}", Xk, Xj, Xi); 252 logger.info("p = ( Xk * Xj ) * Xi = {}", p); 253 logger.info("q = Xk * ( Xj * Xi ) = {}", q); 254 return false; 255 } 256 } 257 } 258 } 259 return true; 260 } 261 262 263 /** 264 * Query if this ring is a field. 265 * @return true. 266 */ 267 public boolean isField() { 268 if (isField > 0) { 269 return true; 270 } 271 if (isField == 0) { 272 return false; 273 } 274 // not reached 275 return false; 276 } 277 278 279 /** 280 * Characteristic of this ring. 281 * @return characteristic of this ring. 282 */ 283 public java.math.BigInteger characteristic() { 284 return ring.characteristic(); 285 } 286 287 288 /** 289 * Get a SolvableLocalResidue element from a BigInteger value. 290 * @param a BigInteger. 291 * @return a SolvableLocalResidue. 292 */ 293 public SolvableLocalResidue<C> fromInteger(java.math.BigInteger a) { 294 return new SolvableLocalResidue<C>(this, ring.fromInteger(a)); 295 } 296 297 298 /** 299 * Get a SolvableLocalResidue element from a long value. 300 * @param a long. 301 * @return a SolvableLocalResidue. 302 */ 303 public SolvableLocalResidue<C> fromInteger(long a) { 304 return new SolvableLocalResidue<C>(this, ring.fromInteger(a)); 305 } 306 307 308 /** 309 * Get the String representation as RingFactory. 310 */ 311 @Override 312 public String toString() { 313 return "SolvableLocalResidueRing[ " + ideal.toString() + " ]"; 314 } 315 316 317 /** 318 * Get a scripting compatible string representation. 319 * @return script compatible representation for this ElemFactory. 320 */ 321 @Override 322 public String toScript() { 323 // Python case 324 return "SLR(" + ideal.list.toScript() + ")"; 325 } 326 327 328 /** 329 * Comparison with any other object. 330 */ 331 @Override 332 @SuppressWarnings("unchecked") 333 public boolean equals(Object b) { 334 if (!(b instanceof SolvableLocalResidueRing)) { 335 return false; 336 } 337 SolvableLocalResidueRing<C> a = null; 338 try { 339 a = (SolvableLocalResidueRing<C>) b; 340 } catch (ClassCastException e) { 341 } 342 if (a == null) { 343 return false; 344 } 345 return ring.equals(a.ring); 346 } 347 348 349 /** 350 * Hash code for this quotient ring. 351 */ 352 @Override 353 public int hashCode() { 354 int h; 355 h = ideal.hashCode(); 356 return h; 357 } 358 359 360 /** 361 * SolvableLocalResidue random. 362 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 363 * @return a random quotient element. 364 */ 365 public SolvableLocalResidue<C> random(int n) { 366 GenSolvablePolynomial<C> r = ring.random(n).monic(); 367 r = ideal.normalform(r); 368 GenSolvablePolynomial<C> s; 369 do { 370 s = ring.random(n).monic(); 371 s = ideal.normalform(s); 372 } while (s.isZERO()); 373 return new SolvableLocalResidue<C>(this, r, s, false); 374 } 375 376 377 /** 378 * Generate a random quotient. 379 * @param k bitsize of random coefficients. 380 * @param l number of terms. 381 * @param d maximal degree in each variable. 382 * @param q density of nozero exponents. 383 * @return a random quotient. 384 */ 385 public SolvableLocalResidue<C> random(int k, int l, int d, float q) { 386 GenSolvablePolynomial<C> r = ring.random(k, l, d, q).monic(); 387 r = ideal.normalform(r); 388 GenSolvablePolynomial<C> s; 389 do { 390 s = ring.random(k, l, d, q).monic(); 391 s = ideal.normalform(s); 392 } while (s.isZERO()); 393 return new SolvableLocalResidue<C>(this, r, s, false); 394 } 395 396 397 /** 398 * SolvableLocalResidue random. 399 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 400 * @param rnd is a source for random bits. 401 * @return a random quotient element. 402 */ 403 public SolvableLocalResidue<C> random(int n, Random rnd) { 404 GenSolvablePolynomial<C> r = ring.random(n, rnd).monic(); 405 r = ideal.normalform(r); 406 GenSolvablePolynomial<C> s; 407 do { 408 s = ring.random(n, rnd).monic(); 409 s = ideal.normalform(s); 410 } while (s.isZERO()); 411 return new SolvableLocalResidue<C>(this, r, s, false); 412 } 413 414 415 /** 416 * Parse SolvableLocalResidue from String. Syntax: 417 * "{ polynomial | polynomial }" or "{ polynomial }" or 418 * " polynomial | polynomial " or " polynomial " 419 * @param s String. 420 * @return SolvableLocalResidue from s. 421 */ 422 public SolvableLocalResidue<C> parse(String s) { 423 int i = s.indexOf("{"); 424 if (i >= 0) { 425 s = s.substring(i + 1); 426 } 427 i = s.lastIndexOf("}"); 428 if (i >= 0) { 429 s = s.substring(0, i); 430 } 431 i = s.indexOf("|"); 432 if (i < 0) { 433 GenSolvablePolynomial<C> n = ring.parse(s); 434 return new SolvableLocalResidue<C>(this, n); 435 } 436 String s1 = s.substring(0, i); 437 String s2 = s.substring(i + 1); 438 GenSolvablePolynomial<C> n = ring.parse(s1); 439 GenSolvablePolynomial<C> d = ring.parse(s2); 440 return new SolvableLocalResidue<C>(this, n, d); 441 } 442 443 444 /** 445 * Parse SolvableLocalResidue from Reader. 446 * @param r Reader. 447 * @return next SolvableLocalResidue from r. 448 */ 449 public SolvableLocalResidue<C> parse(Reader r) { 450 String s = StringUtil.nextPairedString(r, '{', '}'); 451 return parse(s); 452 } 453 454}