001/* 002 * $Id: SolvableLocalResidueRing.java 5280 2015-07-30 16:18:15Z kredel $ 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.log4j.Logger; 014 015import edu.jas.gb.SolvableGroebnerBaseAbstract; 016import edu.jas.gbufd.SGBFactory; 017import edu.jas.gbufd.SolvableSyzygyAbstract; 018import edu.jas.gbufd.SolvableSyzygySeq; 019import edu.jas.kern.StringUtil; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenSolvablePolynomial; 022import edu.jas.poly.GenSolvablePolynomialRing; 023import edu.jas.poly.PolynomialList; 024import edu.jas.structure.GcdRingElem; 025import edu.jas.structure.QuotPairFactory; 026import edu.jas.structure.RingFactory; 027 028 029/** 030 * SolvableLocalResidue ring factory for SolvableLocalResidue based on 031 * GenSolvablePolynomial with GcdRingElem interface. Objects of this class are 032 * immutable. It represents the "classical quotient ring modulo an ideal". 033 * @author Heinz Kredel 034 */ 035public class SolvableLocalResidueRing<C extends GcdRingElem<C>> implements 036 RingFactory<SolvableLocalResidue<C>>, 037 QuotPairFactory<GenPolynomial<C>, SolvableLocalResidue<C>> { 038 039 040 // Can not extend SolvableLocalRing or SolvableQuotientRing 041 // because of different constructor semantics. 042 043 044 private static final Logger logger = Logger.getLogger(SolvableLocalResidueRing.class); 045 046 047 private final boolean debug = logger.isDebugEnabled(); 048 049 050 /** 051 * Solvable polynomial ring of the factory. 052 */ 053 public final GenSolvablePolynomialRing<C> ring; 054 055 056 /** 057 * Solvable polynomial ideal for the reduction. 058 */ 059 public final SolvableIdeal<C> ideal; 060 061 062 /** 063 * Syzygy engine of the factory. 064 */ 065 public final SolvableSyzygyAbstract<C> engine; 066 067 068 /** 069 * Groebner base engine. 070 */ 071 protected final SolvableGroebnerBaseAbstract<C> bb; 072 073 074 /** 075 * Indicator if this ring is a field. 076 */ 077 protected int isField = -1; // initially unknown 078 079 080 /** 081 * The constructor creates a SolvableLocalResidueRing object from a 082 * SolvableIdeal. 083 * @param i ideal in solvable polynomial ring. 084 */ 085 public SolvableLocalResidueRing(SolvableIdeal<C> i) { 086 if (i == null) { 087 throw new IllegalArgumentException("ideal may not be null"); 088 } 089 ring = i.getRing(); 090 ideal = i.GB(); // cheap if isGB 091 if (ideal.isONE()) { 092 throw new IllegalArgumentException("ideal may not be 1"); 093 } 094 if (ideal.isMaximal()) { 095 isField = 1; 096 //} else if (ideal.isPrime()) { 097 // isField = 1; 098 } else { 099 //isField = 0; 100 logger.warn("ideal not maximal and not known to be prime"); 101 //throw new IllegalArgumentException("ideal must be prime or maximal"); 102 } 103 engine = new SolvableSyzygySeq<C>(ring.coFac); 104 bb = SGBFactory.getImplementation(ring.coFac); //new SolvableGroebnerBaseSeq<C>(); 105 logger.debug("solvable local residue ring constructed"); 106 } 107 108 109 /** 110 * Factory for base elements. 111 */ 112 public GenSolvablePolynomialRing<C> pairFactory() { 113 return ring; 114 } 115 116 117 /** 118 * Create from numerator. 119 */ 120 @SuppressWarnings("unchecked") 121 public SolvableLocalResidue<C> create(GenPolynomial<C> n) { 122 return new SolvableLocalResidue<C>(this, (GenSolvablePolynomial<C>) n); 123 } 124 125 126 /** 127 * Create from numerator, denominator pair. 128 */ 129 @SuppressWarnings("unchecked") 130 public SolvableLocalResidue<C> create(GenPolynomial<C> n, GenPolynomial<C> d) { 131 return new SolvableLocalResidue<C>(this, (GenSolvablePolynomial<C>) n, (GenSolvablePolynomial<C>) d); 132 } 133 134 135 /** 136 * Is this structure finite or infinite. 137 * @return true if this structure is finite, else false. 138 */ 139 public boolean isFinite() { 140 return ring.isFinite() && bb.commonZeroTest(ideal.getList()) <= 0; 141 } 142 143 144 /** 145 * Copy SolvableLocalResidue element c. 146 * @param c 147 * @return a copy of c. 148 */ 149 public SolvableLocalResidue<C> copy(SolvableLocalResidue<C> c) { 150 return new SolvableLocalResidue<C>(c.ring, c.num, c.den, true); 151 } 152 153 154 /** 155 * Get the zero element. 156 * @return 0 as SolvableLocalResidue. 157 */ 158 public SolvableLocalResidue<C> getZERO() { 159 return new SolvableLocalResidue<C>(this, ring.getZERO()); 160 } 161 162 163 /** 164 * Get the one element. 165 * @return 1 as SolvableLocalResidue. 166 */ 167 public SolvableLocalResidue<C> getONE() { 168 return new SolvableLocalResidue<C>(this, ring.getONE()); 169 } 170 171 172 /** 173 * Get a list of the generating elements. 174 * @return list of generators for the algebraic structure. 175 */ 176 public List<SolvableLocalResidue<C>> generators() { 177 List<GenSolvablePolynomial<C>> pgens = PolynomialList.<C> castToSolvableList(ring.generators()); 178 List<SolvableLocalResidue<C>> gens = new ArrayList<SolvableLocalResidue<C>>(pgens.size() * 2 - 1); 179 GenSolvablePolynomial<C> one = ring.getONE(); 180 for (GenSolvablePolynomial<C> p : pgens) { 181 SolvableLocalResidue<C> q = new SolvableLocalResidue<C>(this, p); 182 if (!q.isZERO() && !gens.contains(q)) { 183 gens.add(q); 184 if (!p.isONE() && !ideal.contains(p)) { 185 q = new SolvableLocalResidue<C>(this, one, p); 186 gens.add(q); 187 } 188 } 189 } 190 return gens; 191 } 192 193 194 /** 195 * Query if this ring is commutative. 196 * @return true if this ring is commutative, else false. 197 */ 198 public boolean isCommutative() { 199 return ring.isCommutative(); 200 } 201 202 203 /** 204 * Query if this ring is associative. 205 * @return true if this ring is associative, else false. 206 */ 207 @SuppressWarnings("unused") 208 public boolean isAssociative() { 209 if (!ring.isAssociative()) { 210 return false; 211 } 212 SolvableLocalResidue<C> Xi, Xj, Xk, p, q; 213 List<SolvableLocalResidue<C>> gens = generators(); 214 int ngen = gens.size(); 215 for (int i = 0; i < ngen; i++) { 216 Xi = gens.get(i); 217 for (int j = i + 1; j < ngen; j++) { 218 Xj = gens.get(j); 219 for (int k = j + 1; k < ngen; k++) { 220 Xk = gens.get(k); 221 if (Xi.num.degree() == 0 && Xj.num.degree() == 0 && Xk.num.degree() == 0 && 222 Xi.den.degree() == 0 && Xj.den.degree() == 0 && Xk.den.degree() == 0) { 223 //System.out.println("lr degree == 0"); 224 continue; // skip all base elements 225 } 226 try { 227 p = Xk.multiply(Xj).multiply(Xi); 228 q = Xk.multiply(Xj.multiply(Xi)); 229 } catch (IllegalArgumentException e) { 230 e.printStackTrace(); 231 continue; // ignore undefined multiplication 232 } 233 if (p.num.equals(q.num) && p.den.equals(q.den)) { // short cut 234 continue; 235 // } else { 236 // int s = p.num.length() + q.num.length() + p.den.length() + q.den.length(); 237 // if (s > 5) { 238 // System.out.println("lr assoc: p = " + p.toScript()); 239 // System.out.println("lr assoc: q = " + q.toScript()); 240 // System.out.println("lr assoc: Xk = " + Xk.toScript() + ", Xj = " + Xj.toScript() + ", Xi = " + Xi.toScript()); 241 // System.out.println("lr size = " + s); 242 // continue; 243 // } 244 } 245 if (!p.equals(q)) { 246 if (true || debug) { 247 System.out.println("lr assoc: p = " + p.toScript()); 248 System.out.println("lr assoc: q = " + q.toScript()); 249 System.out.println("lr assoc: Xk = " + Xk.toScript() + ", Xj = " + Xj.toScript() + ", Xi = " + Xi.toScript()); 250 logger.info("Xk = " + Xk + ", Xj = " + Xj + ", Xi = " + Xi); 251 logger.info("p = ( Xk * Xj ) * Xi = " + p); 252 logger.info("q = Xk * ( Xj * Xi ) = " + q); 253 } 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}