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.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 logger.debug("pi = {}, pj = {}", pi, pj); 153 154 S = red.SPolynomial(pi, pj); 155 if (S.isZERO()) { 156 pair.setZero(); 157 continue; 158 } 159 if (debug) { 160 logger.info("ht(S) = {}", S.leadingExpVector()); 161 } 162 163 H = redRec.normalformRecursive(G, S); 164 if (H.isZERO()) { 165 pair.setZero(); 166 continue; 167 } 168 if (debug) { 169 logger.info("ht(H) = {}", H.leadingExpVector()); 170 } 171 H = engine.recursivePrimitivePart(H); 172 H = H.abs(); 173 if (H.isConstant()) { 174 G.clear(); 175 G.add(H); 176 return G; // since no threads are activated 177 } 178 if (debug) { 179 logger.debug("H = {}", H); 180 } 181 if (H.length() > 0) { 182 //l++; 183 G.add(H); 184 pairlist.put(H); 185 } 186 } 187 logger.debug("#sequential list = {}", G.size()); 188 G = minimalGB(G); 189 logger.info("{}", pairlist); 190 return G; 191 } 192 193 194 /** 195 * Minimal ordered Groebner basis. 196 * @param Gp a Groebner base. 197 * @return a reduced Groebner base of Gp. 198 */ 199 @Override 200 public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) { 201 List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp); 202 if (G.size() <= 1) { 203 return G; 204 } 205 // remove top reducible polynomials 206 GenPolynomial<GenPolynomial<C>> a; 207 List<GenPolynomial<GenPolynomial<C>>> F; 208 F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size()); 209 while (G.size() > 0) { 210 a = G.remove(0); 211 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 212 // drop polynomial 213 if (debug) { 214 System.out.println("dropped " + a); 215 List<GenPolynomial<GenPolynomial<C>>> ff; 216 ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G); 217 ff.addAll(F); 218 a = redRec.normalformRecursive(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 = redRec.normalformRecursive(G, a); 239 a = engine.recursivePrimitivePart(a); //a.monic(); was not required 240 a = a.abs(); 241 //a = redRec.normalformRecursive( F, a ); 242 G.add(a); // adds as last 243 i++; 244 } 245 Collections.reverse(G); // undo reverse 246 return G; 247 } 248 249 250 /** 251 * Groebner base simple test. 252 * @param modv module variable number. 253 * @param F recursive polynomial list. 254 * @return true, if F is a Groebner base, else false. 255 */ 256 @Override 257 public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) { 258 if (F == null || F.isEmpty()) { 259 return true; 260 } 261 GenPolynomial<GenPolynomial<C>> pi, pj, s, h; 262 ExpVector ei, ej, eij; 263 for (int i = 0; i < F.size(); i++) { 264 pi = F.get(i); 265 ei = pi.leadingExpVector(); 266 for (int j = i + 1; j < F.size(); j++) { 267 pj = F.get(j); 268 ej = pj.leadingExpVector(); 269 if (!red.moduleCriterion(modv, ei, ej)) { 270 continue; 271 } 272 eij = ei.lcm(ej); 273 if (!red.criterion4(ei, ej, eij)) { 274 continue; 275 } 276 //if (!criterion3(i, j, eij, F)) { 277 // continue; 278 //} 279 s = red.SPolynomial(pi, pj); 280 if (s.isZERO()) { 281 continue; 282 } 283 //System.out.println("i, j = " + i + ", " + j); 284 h = redRec.normalformRecursive(F, s); 285 if (!h.isZERO()) { 286 logger.info("no GB: pi = {}, pj = {}", pi, pj); 287 logger.info("s = {}, h = {}", s, h); 288 return false; 289 } 290 } 291 } 292 return true; 293 } 294 295}