001/* 002 * $Id: RGroebnerBaseSeq.java 4116 2012-08-19 13:26:25Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.gb.GroebnerBaseAbstract; 015import edu.jas.gb.Pair; 016import edu.jas.poly.ExpVector; 017import edu.jas.poly.GenPolynomial; 018import edu.jas.structure.RegularRingElem; 019 020 021/** 022 * Regular ring Groebner Base sequential algorithm. Implements R-Groebner bases 023 * and GB test. 024 * @param <C> coefficient type 025 * @author Heinz Kredel 026 */ 027 028public class RGroebnerBaseSeq<C extends RegularRingElem<C>> extends GroebnerBaseAbstract<C> { 029 030 031 private static final Logger logger = Logger.getLogger(RGroebnerBaseSeq.class); 032 033 034 private final boolean debug = logger.isDebugEnabled(); 035 036 037 /** 038 * Reduction engine. 039 */ 040 protected RReduction<C> rred; // shadow super.red ?? 041 042 043 /** 044 * Constructor. 045 */ 046 public RGroebnerBaseSeq() { 047 this(new RReductionSeq<C>()); 048 } 049 050 051 /** 052 * Constructor. 053 * @param rred R-Reduction engine 054 */ 055 public RGroebnerBaseSeq(RReduction<C> rred) { 056 super(rred); 057 this.rred = rred; 058 assert super.red == this.rred; 059 } 060 061 062 /** 063 * R-Groebner base test. 064 * @param modv module variable number. 065 * @param F polynomial list. 066 * @return true, if F is a R-Groebner base, else false. 067 */ 068 @Override 069 public boolean isGB(int modv, List<GenPolynomial<C>> F) { 070 if (F == null) { 071 return true; 072 } 073 if (!rred.isBooleanClosed(F)) { 074 if (debug) { 075 logger.debug("not boolean closed"); 076 } 077 return false; 078 } 079 GenPolynomial<C> pi, pj, s; 080 for (int i = 0; i < F.size(); i++) { 081 pi = F.get(i); 082 for (int j = i + 1; j < F.size(); j++) { 083 pj = F.get(j); 084 if (!red.moduleCriterion(modv, pi, pj)) { 085 continue; 086 } 087 // red.criterion4 not applicable 088 s = red.SPolynomial(pi, pj); 089 if (s.isZERO()) { 090 continue; 091 } 092 s = red.normalform(F, s); 093 if (!s.isZERO()) { 094 if (debug) { 095 logger.debug("p" + i + " = " + pi); 096 logger.debug("p" + j + " = " + pj); 097 logger.debug("s-pol = " + red.SPolynomial(pi, pj)); 098 logger.debug("s-pol(" + i + "," + j + ") != 0: " + s); 099 } 100 return false; 101 } 102 } 103 } 104 return true; 105 } 106 107 108 /** 109 * R-Groebner base using pairlist class. 110 * @param modv module variable number. 111 * @param F polynomial list. 112 * @return GB(F) a R-Groebner base of F. 113 */ 114 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 115 /* boolean closure */ 116 List<GenPolynomial<C>> bcF = rred.reducedBooleanClosure(F); 117 logger.info("#bcF-#F = " + (bcF.size() - F.size())); 118 F = bcF; 119 /* normalize input */ 120 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 121 OrderedRPairlist<C> pairlist = null; 122 for (GenPolynomial<C> p : F) { 123 if (!p.isZERO()) { 124 p = p.monic(); //p.abs(); // not monic, monic if boolean closed 125 if (p.isONE()) { 126 G.clear(); 127 G.add(p); 128 return G; // since boolean closed and no threads are activated 129 } 130 G.add(p); //G.add( 0, p ); //reverse list 131 if (pairlist == null) { 132 pairlist = new OrderedRPairlist<C>(modv, p.ring); 133 } 134 // putOne not required 135 pairlist.put(p); 136 } 137 } 138 if (G.size() <= 1) { 139 return G; // since boolean closed and no threads are activated 140 } 141 /* loop on critical pairs */ 142 Pair<C> pair; 143 GenPolynomial<C> pi; 144 GenPolynomial<C> pj; 145 GenPolynomial<C> S; 146 //GenPolynomial<C> D; 147 GenPolynomial<C> H; 148 List<GenPolynomial<C>> bcH; 149 //int len = G.size(); 150 //System.out.println("len = " + len); 151 while (pairlist.hasNext()) { 152 pair = pairlist.removeNext(); 153 //System.out.println("pair = " + pair); 154 if (pair == null) 155 continue; 156 157 pi = pair.pi; 158 pj = pair.pj; 159 if (logger.isDebugEnabled()) { 160 logger.debug("pi = " + pi); 161 logger.debug("pj = " + pj); 162 } 163 if (!red.moduleCriterion(modv, pi, pj)) { 164 continue; 165 } 166 167 // S-polynomial ----------------------- 168 // Criterion3() Criterion4() not applicable 169 S = red.SPolynomial(pi, pj); 170 if (S.isZERO()) { 171 pair.setZero(); 172 continue; 173 } 174 if (logger.isDebugEnabled()) { 175 logger.debug("ht(S) = " + S.leadingExpVector()); 176 } 177 178 H = red.normalform(G, S); 179 if (H.isZERO()) { 180 pair.setZero(); 181 continue; 182 } 183 //H = H.monic(); // only for boolean closed H 184 if (logger.isDebugEnabled()) { 185 logger.debug("ht(H) = " + H.leadingExpVector()); 186 } 187 188 if (H.isONE()) { // mostly useless 189 G.clear(); 190 G.add(H); 191 return G; // not boolean closed ok, since no threads are activated 192 } 193 if (logger.isDebugEnabled()) { 194 logger.debug("H = " + H); 195 } 196 if (!H.isZERO()) { 197 logger.info("Sred = " + H); 198 //len = G.size(); 199 bcH = rred.reducedBooleanClosure(G, H); 200 logger.info("#bcH = " + bcH.size()); 201 for (GenPolynomial<C> h : bcH) { 202 h = h.monic(); // monic() ok, since boolean closed 203 G.add(h); 204 pairlist.put(h); 205 } 206 if (debug) { 207 if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) { 208 logger.info("H != 0 but: " + pair); 209 } 210 } 211 } 212 } 213 logger.debug("#sequential list = " + G.size()); 214 G = minimalGB(G); 215 //G = red.irreducibleSet(G); 216 logger.info("" + pairlist); 217 return G; 218 } 219 220 221 /** 222 * Minimal ordered Groebner basis. 223 * @param Gp a Groebner base. 224 * @return a reduced Groebner base of Gp. 225 */ 226 @Override 227 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) { 228 if (Gp == null || Gp.size() <= 1) { 229 return Gp; 230 } 231 // remove zero polynomials 232 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size()); 233 for (GenPolynomial<C> a : Gp) { 234 if (a != null && !a.isZERO()) { // always true in GB() 235 // already positive a = a.abs(); 236 G.add(a); 237 } 238 } 239 //if (G.size() <= 1) { 240 //wg monic do not return G; 241 //} 242 // remove top reducible polynomials 243 GenPolynomial<C> a, b; 244 List<GenPolynomial<C>> F; 245 List<GenPolynomial<C>> bcH; 246 F = new ArrayList<GenPolynomial<C>>(G.size()); 247 while (G.size() > 0) { 248 a = G.remove(0); 249 b = a; 250 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 251 // drop polynomial 252 if (logger.isInfoEnabled()) { 253 List<GenPolynomial<C>> ff; 254 ff = new ArrayList<GenPolynomial<C>>(G); 255 ff.addAll(F); 256 a = red.normalform(ff, a); 257 if (!a.isZERO()) { // happens 258 logger.info("minGB not zero " + a); 259 bcH = rred.reducedBooleanClosure(G, a); 260 if (bcH.size() > 1) { // never happend so far 261 System.out.println("minGB not bc: bcH size = " + bcH.size()); 262 F.add(b); // do not replace, stay with b 263 } else { 264 //System.out.println("minGB add bc(a): a = " + a + ", bc(a) = " + bcH.get(0)); 265 F.addAll(bcH); 266 } 267 } else { 268 //System.out.println("minGB dropped " + b); 269 } 270 } 271 } else { 272 F.add(a); 273 } 274 } 275 G = F; 276 //if (G.size() <= 1) { 277 // wg monic return G; 278 //} 279 Collections.reverse(G); // important for lex GB 280 // reduce remaining polynomials 281 int len = G.size(); 282 int el = 0; 283 while (el < len) { 284 a = G.remove(0); 285 b = a; 286 //System.out.println("doing " + a.length()); 287 a = red.normalform(G, a); 288 bcH = rred.reducedBooleanClosure(G, a); 289 if (bcH.size() > 1) { 290 System.out.println("minGB not bc: bcH size = " + bcH.size()); 291 G.add(b); // do not reduce 292 } else { 293 G.addAll(bcH); 294 } 295 el++; 296 } 297 // make monic if possible 298 F = new ArrayList<GenPolynomial<C>>(G.size()); 299 for (GenPolynomial<C> p : G) { 300 a = p.monic().abs(); 301 if (p.length() != a.length()) { 302 System.out.println("minGB not bc: #p != #a: a = " + a + ", p = " + p); 303 a = p; // dont make monic for now 304 } 305 F.add(a); 306 } 307 G = F; 308 309 /* stratify: collect polynomials with equal leading terms */ 310 ExpVector e, f; 311 F = new ArrayList<GenPolynomial<C>>(G.size()); 312 for (int i = 0; i < G.size(); i++) { 313 a = G.get(i); 314 if (a == null || a.isZERO()) { 315 continue; 316 } 317 e = a.leadingExpVector(); 318 for (int j = i + 1; j < G.size(); j++) { 319 b = G.get(j); 320 if (b == null || b.isZERO()) { 321 continue; 322 } 323 f = b.leadingExpVector(); 324 if (e.equals(f)) { 325 //System.out.println("minGB e == f: " + a + ", " + b); 326 a = a.sum(b); 327 G.set(j, null); 328 } 329 } 330 F.add(a); 331 } 332 G = F; 333 334 /* info on boolean algebra element blocks 335 Map<C,List<GenPolynomial<C>>> bd = new TreeMap<C,List<GenPolynomial<C>>>(); 336 for ( GenPolynomial<C> p : G ) { 337 C cf = p.leadingBaseCoefficient(); 338 cf = cf.idempotent(); 339 List<GenPolynomial<C>> block = bd.get( cf ); 340 if ( block == null ) { 341 block = new ArrayList<GenPolynomial<C>>(); 342 } 343 block.add( p ); 344 bd.put( cf, block ); 345 } 346 System.out.println("\nminGB bd:"); 347 for( C k: bd.keySet() ) { 348 System.out.println("\nkey = " + k + ":"); 349 System.out.println("val = " + bd.get(k)); 350 } 351 System.out.println(); 352 */ 353 return G; 354 } 355 356}