001/* 002 * $Id$ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011 012import org.apache.logging.log4j.Logger; 013import org.apache.logging.log4j.LogManager; 014 015import edu.jas.gb.OrderedPairlist; 016import edu.jas.gb.Pair; 017import edu.jas.gb.PairList; 018import edu.jas.gb.SolvableExtendedGB; 019import edu.jas.gb.SolvableGroebnerBaseAbstract; 020import edu.jas.poly.GenSolvablePolynomial; 021import edu.jas.poly.GenSolvablePolynomialRing; 022import edu.jas.poly.RecSolvablePolynomialRing; 023import edu.jas.poly.QLRSolvablePolynomialRing; 024import edu.jas.poly.GenPolynomial; 025import edu.jas.poly.GenPolynomialRing; 026import edu.jas.poly.PolynomialList; 027import edu.jas.structure.QuotPair; 028import edu.jas.structure.GcdRingElem; 029import edu.jas.structure.RingFactory; 030import edu.jas.ufd.GCDFactory; 031import edu.jas.ufd.GreatestCommonDivisorAbstract; 032import edu.jas.ufd.GreatestCommonDivisorFake; 033 034 035/** 036 * Solvable Groebner Base with pseudo reduction sequential algorithm. Implements 037 * coefficient fraction free Groebner bases. Coefficients can for example be 038 * integers or (commutative) univariate polynomials. 039 * @param <C> coefficient type 040 * @author Heinz Kredel 041 * 042 * @see edu.jas.application.GBAlgorithmBuilder 043 * @see edu.jas.gbufd.GBFactory 044 */ 045 046public class SolvableGroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends SolvableGroebnerBaseAbstract<C> { 047 048 049 private static final Logger logger = LogManager.getLogger(SolvableGroebnerBasePseudoSeq.class); 050 051 052 private static final boolean debug = logger.isDebugEnabled(); 053 054 055 /** 056 * Greatest common divisor engine for coefficient content and primitive 057 * parts. 058 */ 059 protected final GreatestCommonDivisorAbstract<C> engine; 060 061 062 /** 063 * Pseudo reduction engine. 064 */ 065 protected final SolvablePseudoReduction<C> sred; 066 067 068 /** 069 * Coefficient ring factory. 070 */ 071 protected final RingFactory<C> cofac; 072 073 074 /** 075 * Constructor. 076 * @param rf coefficient ring factory. 077 */ 078 public SolvableGroebnerBasePseudoSeq(RingFactory<C> rf) { 079 this(new SolvablePseudoReductionSeq<C>(), rf, new OrderedPairlist<C>()); 080 } 081 082 083 /** 084 * Constructor. 085 * @param rf coefficient ring factory. 086 * @param pl pair selection strategy 087 */ 088 public SolvableGroebnerBasePseudoSeq(RingFactory<C> rf, PairList<C> pl) { 089 this(new SolvablePseudoReductionSeq<C>(), rf, pl); 090 } 091 092 093 /** 094 * Constructor. 095 * @param red pseudo reduction engine. <b>Note:</b> red must be an instance 096 * of PseudoReductionSeq. 097 * @param rf coefficient ring factory. 098 * @param pl pair selection strategy 099 */ 100 @SuppressWarnings("unchecked") 101 public SolvableGroebnerBasePseudoSeq(SolvablePseudoReduction<C> red, RingFactory<C> rf, PairList<C> pl) { 102 super(red, pl); 103 this.sred = red; 104 GenSolvablePolynomialRing<C> ring = (GenSolvablePolynomialRing<C>) pl.getRing(); 105 cofac = rf; 106 if (!cofac.isCommutative()) { 107 logger.warn("right reduction not correct for {}", cofac); //.toScript() 108 engine = new GreatestCommonDivisorFake<C>(); // only for Ore conditions 109 //System.out.println("stack trace = "); 110 //Exception e = new RuntimeException("get stack trace"); 111 //e.printStackTrace(); 112 } else if (ring instanceof QLRSolvablePolynomialRing) { // others ? 113 // check that also coeffTable is empty for recursive solvable poly ring 114 QLRSolvablePolynomialRing qring = (QLRSolvablePolynomialRing) ring; 115 RecSolvablePolynomialRing<C> rring = qring.polCoeff; 116 if (!rring.coeffTable.isEmpty()) { 117 logger.warn("right reduction not correct for {}", rring.coeffTable); 118 engine = new GreatestCommonDivisorFake<C>(); // only for Ore conditions 119 } else { 120 engine = GCDFactory.<C> getImplementation(cofac); 121 } 122 } else { 123 engine = GCDFactory.<C> getProxy(cofac); 124 } 125 } 126 127 128 /** 129 * Left Groebner base using pairlist class. 130 * @param modv module variable number. 131 * @param F polynomial list. 132 * @return GB(F) a Groebner base of F. 133 */ 134 @Override 135 public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) { 136 List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F); 137 G = PolynomialList.<C> castToSolvableList(engine.basePrimitivePart(PolynomialList.<C> castToList(G))); 138 if (G.size() <= 1) { 139 return G; 140 } 141 GenSolvablePolynomialRing<C> ring = G.get(0).ring; 142 if (ring.coFac.isField()) { // remove ? 143 throw new IllegalArgumentException("coefficients from a field"); 144 } 145 PairList<C> pairlist = strategy.create(modv, ring); 146 pairlist.put(PolynomialList.<C> castToList(G)); 147 148 Pair<C> pair; 149 GenSolvablePolynomial<C> pi, pj, S, H; 150 while (pairlist.hasNext()) { 151 pair = pairlist.removeNext(); 152 if (pair == null) 153 continue; 154 155 pi = (GenSolvablePolynomial<C>) pair.pi; 156 pj = (GenSolvablePolynomial<C>) pair.pj; 157 if (debug) { 158 logger.debug("pi = {}", pi); 159 logger.debug("pj = {}", pj); 160 } 161 162 S = sred.leftSPolynomial(pi, pj); 163 if (S.isZERO()) { 164 pair.setZero(); 165 continue; 166 } 167 logger.debug("ht(S) = {}", S.leadingExpVector()); 168 169 H = sred.leftNormalform(G, S); 170 if (H.isZERO()) { 171 pair.setZero(); 172 continue; 173 } 174 logger.debug("ht(H) = {}", H.leadingExpVector()); 175 H = (GenSolvablePolynomial<C>) engine.basePrimitivePart(H); 176 H = (GenSolvablePolynomial<C>) H.abs(); 177 if (H.isConstant()) { 178 G.clear(); 179 G.add(H); 180 return G; // since no threads are activated 181 } 182 logger.debug("H = {}", H); 183 if (H.length() > 0) { 184 G.add(H); 185 pairlist.put(H); 186 } 187 } 188 logger.debug("#sequential list = {}", G.size()); 189 G = leftMinimalGB(G); 190 logger.info("{}", pairlist); 191 return G; 192 } 193 194 195 /** 196 * Minimal ordered Solvable Groebner basis. 197 * @param Gp a Solvable Groebner base. 198 * @return a reduced Solvable Groebner base of Gp. 199 */ 200 @Override 201 public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) { 202 List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(Gp); 203 if (G.size() <= 1) { 204 return G; 205 } 206 // remove top reducible polynomials 207 GenSolvablePolynomial<C> a; 208 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(G.size()); 209 while (G.size() > 0) { 210 a = G.remove(0); 211 if (sred.isTopReducible(G, a) || sred.isTopReducible(F, a)) { 212 // drop polynomial 213 if (debug) { 214 System.out.println("dropped " + a); 215 List<GenSolvablePolynomial<C>> ff; 216 ff = new ArrayList<GenSolvablePolynomial<C>>(G); 217 ff.addAll(F); 218 a = sred.leftNormalform(ff, a); 219 if (!a.isZERO()) { 220 System.out.println("error, nf(a) " + a); 221 } 222 } 223 } else { 224 F.add(a); 225 } 226 } 227 G = F; 228 if (G.size() <= 1) { 229 return G; 230 } 231 Collections.reverse(G); // important for lex GB 232 // reduce remaining polynomials 233 int len = G.size(); 234 int i = 0; 235 while (i < len) { 236 a = G.remove(0); 237 //System.out.println("doing " + a.length()); 238 a = sred.leftNormalform(G, a); 239 a = (GenSolvablePolynomial<C>) engine.basePrimitivePart(a); //a.monic(); not possible 240 a = (GenSolvablePolynomial<C>) a.abs(); 241 //a = sred.normalform( F, a ); 242 G.add(a); // adds as last 243 i++; 244 } 245 return G; 246 } 247 248 249 /** 250 * Twosided Solvable Groebner base using pairlist class. 251 * @param modv number of module variables. 252 * @param Fp solvable polynomial list. 253 * @return tsGB(Fp) a twosided Groebner base of Fp. 254 */ 255 @Override 256 public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) { 257 List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(Fp); 258 G = PolynomialList.<C> castToSolvableList(engine.basePrimitivePart(PolynomialList.<C> castToList(G))); 259 if (G.size() < 1) { // two-sided! 260 return G; 261 } 262 //System.out.println("G = " + G); 263 GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null 264 if (ring.coFac.isField()) { // remove ? 265 throw new IllegalArgumentException("coefficients from a field"); 266 } 267 // add also coefficient generators 268 List<GenSolvablePolynomial<C>> X; 269 X = PolynomialList.castToSolvableList(ring.generators(modv)); 270 logger.info("right multipliers = {}", X); 271 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(G.size() * (1 + X.size())); 272 F.addAll(G); 273 logger.info("right multiply: F = {}", F); 274 GenSolvablePolynomial<C> p, x, q; 275 for (int i = 0; i < F.size(); i++) { // F changes 276 p = F.get(i); 277 for (int j = 0; j < X.size(); j++) { 278 x = X.get(j); 279 q = p.multiply(x); 280 logger.info("right multiply: p = {}, x = {}, q = {}", p, x, q); 281 q = sred.leftNormalform(F, q); 282 if (!q.isZERO()) { 283 q = (GenSolvablePolynomial<C>) engine.basePrimitivePart(q); 284 q = (GenSolvablePolynomial<C>) q.abs(); 285 logger.info("right multiply: red(q) = {}", q); 286 F.add(q); 287 } 288 } 289 } 290 G = F; 291 //System.out.println("G generated = " + G); 292 PairList<C> pairlist = strategy.create(modv, ring); 293 pairlist.put(PolynomialList.<C> castToList(G)); 294 295 Pair<C> pair; 296 GenSolvablePolynomial<C> pi, pj, S, H; 297 while (pairlist.hasNext()) { 298 pair = pairlist.removeNext(); 299 if (pair == null) { 300 continue; 301 } 302 303 pi = (GenSolvablePolynomial<C>) pair.pi; 304 pj = (GenSolvablePolynomial<C>) pair.pj; 305 if (debug) { 306 logger.debug("pi = {}", pi); 307 logger.debug("pj = {}", pj); 308 } 309 310 S = sred.leftSPolynomial(pi, pj); 311 if (S.isZERO()) { 312 pair.setZero(); 313 continue; 314 } 315 logger.debug("ht(S) = {}", S.leadingExpVector()); 316 317 H = sred.leftNormalform(G, S); 318 if (H.isZERO()) { 319 pair.setZero(); 320 continue; 321 } 322 logger.debug("ht(H) = {}", H.leadingExpVector()); 323 324 H = (GenSolvablePolynomial<C>) engine.basePrimitivePart(H); 325 H = (GenSolvablePolynomial<C>) H.abs(); 326 if (H.isONE()) { 327 G.clear(); 328 G.add(H); 329 return G; // since no threads are activated 330 } 331 logger.debug("H = {}", H); 332 if (H.length() > 0) { 333 G.add(H); 334 pairlist.put(H); 335 for (int j = 0; j < X.size(); j++) { 336 x = X.get(j); 337 p = H.multiply(x); 338 p = sred.leftNormalform(G, p); 339 if (!p.isZERO()) { 340 p = (GenSolvablePolynomial<C>) engine.basePrimitivePart(p); 341 p = (GenSolvablePolynomial<C>) p.abs(); 342 if (p.isONE()) { 343 G.clear(); 344 G.add(p); 345 return G; // since no threads are activated 346 } 347 G.add(p); 348 pairlist.put(p); 349 } 350 } 351 } 352 } 353 logger.debug("#sequential list = {}", G.size()); 354 G = leftMinimalGB(G); 355 logger.info("{}", pairlist); 356 return G; 357 } 358 359}