001/* 002 * $Id: GroebnerBasePseudoRecSeq.java 5870 2018-07-20 15:56:23Z 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.logging.log4j.Logger; 013import org.apache.logging.log4j.LogManager; 014 015import edu.jas.gb.GroebnerBaseAbstract; 016import edu.jas.gb.OrderedPairlist; 017import edu.jas.gb.Pair; 018import edu.jas.gb.PairList; 019import edu.jas.poly.ExpVector; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenPolynomialRing; 022import edu.jas.structure.GcdRingElem; 023import edu.jas.structure.RingFactory; 024import edu.jas.ufd.GCDFactory; 025import edu.jas.ufd.GreatestCommonDivisorAbstract; 026 027 028/** 029 * Groebner Base with pseudo reduction sequential algorithm for integral 030 * function coefficients. Implements polynomial fraction free coefficients 031 * Groebner bases. Coefficients can for example be 032 * (commutative) multivariate polynomials. 033 * @param <C> base coefficient type 034 * @author Heinz Kredel 035 * 036 * @see edu.jas.application.GBAlgorithmBuilder 037 * @see edu.jas.gbufd.GBFactory 038 */ 039 040public class GroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends 041 GroebnerBaseAbstract<GenPolynomial<C>> { 042 043 044 private static final Logger logger = LogManager.getLogger(GroebnerBasePseudoRecSeq.class); 045 046 047 private static final boolean debug = logger.isDebugEnabled(); 048 049 050 /** 051 * Greatest common divisor engine for coefficient content and primitive 052 * parts. 053 */ 054 protected final GreatestCommonDivisorAbstract<C> engine; 055 056 057 /** 058 * Pseudo reduction engine. 059 */ 060 protected final PseudoReduction<C> redRec; 061 062 063 /** 064 * Pseudo reduction engine. 065 */ 066 protected final PseudoReduction<GenPolynomial<C>> red; 067 068 069 /** 070 * Coefficient ring factory. 071 */ 072 protected final RingFactory<GenPolynomial<C>> cofac; 073 074 075 /** 076 * Base coefficient ring factory. 077 */ 078 protected final RingFactory<C> baseCofac; 079 080 081 /** 082 * Constructor. 083 * @param rf coefficient ring factory. 084 */ 085 public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) { 086 this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, new OrderedPairlist<GenPolynomial<C>>( 087 new GenPolynomialRing<GenPolynomial<C>>(rf, 1))); // 1=hack 088 } 089 090 091 /** 092 * Constructor. 093 * @param rf coefficient ring factory. 094 * @param pl pair selection strategy 095 */ 096 public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, PairList<GenPolynomial<C>> pl) { 097 this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, pl); 098 } 099 100 101 /** 102 * Constructor. 103 * @param red pseudo reduction engine. <b>Note:</b> red must be an instance 104 * of PseudoReductionSeq. 105 * @param rf coefficient ring factory. 106 * @param pl pair selection strategy 107 */ 108 @SuppressWarnings("unchecked") 109 public GroebnerBasePseudoRecSeq(PseudoReduction<GenPolynomial<C>> red, RingFactory<GenPolynomial<C>> rf, 110 PairList<GenPolynomial<C>> pl) { 111 super(red, pl); 112 this.red = red; 113 this.redRec = (PseudoReduction<C>) (PseudoReduction) red; 114 cofac = rf; 115 GenPolynomialRing<C> rp = (GenPolynomialRing<C>) cofac; 116 baseCofac = rp.coFac; 117 //engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( baseCofac ); 118 //not used: 119 engine = GCDFactory.<C> getProxy(baseCofac); 120 } 121 122 123 /** 124 * Groebner base using pairlist class. 125 * @param modv module variable number. 126 * @param F polynomial list. 127 * @return GB(F) a Groebner base of F. 128 */ 129 //@Override 130 public List<GenPolynomial<GenPolynomial<C>>> GB(int modv, List<GenPolynomial<GenPolynomial<C>>> F) { 131 List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F); 132 G = engine.recursivePrimitivePart(G); 133 if (G.size() <= 1) { 134 return G; 135 } 136 GenPolynomialRing<GenPolynomial<C>> ring = G.get(0).ring; 137 if (ring.coFac.isField()) { // remove ? 138 throw new IllegalArgumentException("coefficients from a field"); 139 } 140 PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring); 141 pairlist.put(G); 142 143 Pair<GenPolynomial<C>> pair; 144 GenPolynomial<GenPolynomial<C>> pi, pj, S, H; 145 while (pairlist.hasNext()) { 146 pair = pairlist.removeNext(); 147 if (pair == null) 148 continue; 149 150 pi = pair.pi; 151 pj = pair.pj; 152 if (debug) { 153 logger.debug("pi = " + pi); 154 logger.debug("pj = " + pj); 155 } 156 157 S = red.SPolynomial(pi, pj); 158 if (S.isZERO()) { 159 pair.setZero(); 160 continue; 161 } 162 if (debug) { 163 logger.info("ht(S) = " + S.leadingExpVector()); 164 } 165 166 H = redRec.normalformRecursive(G, S); 167 if (H.isZERO()) { 168 pair.setZero(); 169 continue; 170 } 171 if (debug) { 172 logger.info("ht(H) = " + H.leadingExpVector()); 173 } 174 H = engine.recursivePrimitivePart(H); 175 H = H.abs(); 176 if (H.isConstant()) { 177 G.clear(); 178 G.add(H); 179 return G; // since no threads are activated 180 } 181 if (debug) { 182 logger.debug("H = " + H); 183 } 184 if (H.length() > 0) { 185 //l++; 186 G.add(H); 187 pairlist.put(H); 188 } 189 } 190 logger.debug("#sequential list = " + G.size()); 191 G = minimalGB(G); 192 logger.info("" + pairlist); 193 return G; 194 } 195 196 197 /** 198 * Minimal ordered Groebner basis. 199 * @param Gp a Groebner base. 200 * @return a reduced Groebner base of Gp. 201 */ 202 @Override 203 public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) { 204 List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp); 205 if (G.size() <= 1) { 206 return G; 207 } 208 // remove top reducible polynomials 209 GenPolynomial<GenPolynomial<C>> a; 210 List<GenPolynomial<GenPolynomial<C>>> F; 211 F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size()); 212 while (G.size() > 0) { 213 a = G.remove(0); 214 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 215 // drop polynomial 216 if (debug) { 217 System.out.println("dropped " + a); 218 List<GenPolynomial<GenPolynomial<C>>> ff; 219 ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G); 220 ff.addAll(F); 221 a = redRec.normalformRecursive(ff, a); 222 if (!a.isZERO()) { 223 System.out.println("error, nf(a) " + a); 224 } 225 } 226 } else { 227 F.add(a); 228 } 229 } 230 G = F; 231 if (G.size() <= 1) { 232 return G; 233 } 234 Collections.reverse(G); // important for lex GB 235 // reduce remaining polynomials 236 int len = G.size(); 237 int i = 0; 238 while (i < len) { 239 a = G.remove(0); 240 //System.out.println("doing " + a.length()); 241 a = redRec.normalformRecursive(G, a); 242 a = engine.recursivePrimitivePart(a); //a.monic(); was not required 243 a = a.abs(); 244 //a = redRec.normalformRecursive( F, a ); 245 G.add(a); // adds as last 246 i++; 247 } 248 Collections.reverse(G); // undo reverse 249 return G; 250 } 251 252 253 /** 254 * Groebner base simple test. 255 * @param modv module variable number. 256 * @param F recursive polynomial list. 257 * @return true, if F is a Groebner base, else false. 258 */ 259 @Override 260 public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) { 261 if (F == null || F.isEmpty()) { 262 return true; 263 } 264 GenPolynomial<GenPolynomial<C>> pi, pj, s, h; 265 ExpVector ei, ej, eij; 266 for (int i = 0; i < F.size(); i++) { 267 pi = F.get(i); 268 ei = pi.leadingExpVector(); 269 for (int j = i + 1; j < F.size(); j++) { 270 pj = F.get(j); 271 ej = pj.leadingExpVector(); 272 if (!red.moduleCriterion(modv, ei, ej)) { 273 continue; 274 } 275 eij = ei.lcm(ej); 276 if (!red.criterion4(ei, ej, eij)) { 277 continue; 278 } 279 //if (!criterion3(i, j, eij, F)) { 280 // continue; 281 //} 282 s = red.SPolynomial(pi, pj); 283 if (s.isZERO()) { 284 continue; 285 } 286 //System.out.println("i, j = " + i + ", " + j); 287 h = redRec.normalformRecursive(F, s); 288 if (!h.isZERO()) { 289 logger.info("no GB: pi = " + pi + ", pj = " + pj); 290 logger.info("s = " + s + ", h = " + h); 291 return false; 292 } 293 } 294 } 295 return true; 296 } 297 298}