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