001/* 002 * $Id: WordGroebnerBasePseudoSeq.java 5054 2015-01-01 11:03:35Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.gb.OrderedWordPairlist; 014import edu.jas.gb.WordGroebnerBaseAbstract; 015import edu.jas.gb.WordPair; 016import edu.jas.gb.WordPairList; 017import edu.jas.poly.GenWordPolynomial; 018import edu.jas.poly.GenWordPolynomialRing; 019import edu.jas.structure.GcdRingElem; 020import edu.jas.structure.RingFactory; 021 022 023/** 024 * Non-commutative word Groebner Base sequential algorithm. Implements Groebner 025 * bases and GB test. Coefficients can for example be integers or (commutative) 026 * univariate polynomials. 027 * @param <C> coefficient type 028 * @author Heinz Kredel 029 */ 030 031public class WordGroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends WordGroebnerBaseAbstract<C> { 032 033 034 private static final Logger logger = Logger.getLogger(WordGroebnerBasePseudoSeq.class); 035 036 037 private final boolean debug = logger.isDebugEnabled(); 038 039 040 /** 041 * Coefficient ring factory. 042 */ 043 protected final RingFactory<C> cofac; 044 045 046 /** 047 * Constructor. 048 * @param rf coefficient ring factory. 049 */ 050 public WordGroebnerBasePseudoSeq(RingFactory<C> rf) { 051 this(rf, new WordPseudoReductionSeq<C>()); 052 } 053 054 055 /** 056 * Constructor. 057 * @param rf coefficient ring factory. 058 * @param red Reduction engine 059 */ 060 public WordGroebnerBasePseudoSeq(RingFactory<C> rf, WordPseudoReductionSeq<C> red) { 061 this(rf, red, new OrderedWordPairlist<C>()); 062 } 063 064 065 /** 066 * Constructor. 067 * @param rf coefficient ring factory. 068 * @param red Reduction engine 069 * @param pl pair selection strategy 070 */ 071 public WordGroebnerBasePseudoSeq(RingFactory<C> rf, WordPseudoReductionSeq<C> red, WordPairList<C> pl) { 072 super(red, pl); 073 cofac = rf; 074 if (!cofac.isCommutative()) { 075 logger.warn("reduction not correct for " + cofac.toScript()); 076 } 077 //engine = GCDFactory.<C> getImplementation(rf); 078 //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf ); 079 } 080 081 082 /** 083 * Word Groebner base using word pairlist class. 084 * @param F word polynomial list. 085 * @return GB(F) a finite non-commutative Groebner base of F, if it exists. 086 */ 087 @Override 088 public List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F) { 089 List<GenWordPolynomial<C>> G = normalizeZerosOnes(F); 090 //G = PolyUtil.<C> wordMonic(G); 091 G = basePrimitivePart(G); 092 if (G.size() <= 1) { 093 return G; 094 } 095 GenWordPolynomialRing<C> ring = G.get(0).ring; 096 if (!ring.coFac.isCommutative()) { 097 throw new IllegalArgumentException("coefficient ring not commutative"); 098 } 099 //Collections.sort(G); 100 OrderedWordPairlist<C> pairlist = (OrderedWordPairlist<C>) strategy.create(ring); 101 pairlist.put(G); 102 logger.info("start " + pairlist); 103 104 WordPair<C> pair; 105 GenWordPolynomial<C> pi; 106 GenWordPolynomial<C> pj; 107 List<GenWordPolynomial<C>> S; 108 GenWordPolynomial<C> H; 109 while (pairlist.hasNext()) { 110 pair = pairlist.removeNext(); 111 //logger.debug("pair = " + pair); 112 if (pair == null) { 113 continue; 114 } 115 pi = pair.pi; 116 pj = pair.pj; 117 if (debug) { 118 logger.info("pi = " + pi + ", pj = " + pj); 119 //logger.info("pj = " + pj); 120 } 121 122 S = red.SPolynomials(pi, pj); 123 if (S.isEmpty()) { 124 continue; 125 } 126 for (GenWordPolynomial<C> s : S) { 127 if (s.isZERO()) { 128 //pair.setZero(); 129 continue; 130 } 131 if (debug) { 132 logger.info("ht(S) = " + s.leadingWord()); 133 } 134 boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord()); 135 //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t); 136 //if ( !t ) { 137 // continue; 138 //} 139 140 H = red.normalform(G, s); 141 if (debug) { 142 //logger.info("pair = " + pair); 143 //logger.info("ht(S) = " + S.monic()); //.leadingWord() ); 144 logger.info("ht(H) = " + H.monic()); //.leadingWord() ); 145 } 146 if (H.isZERO()) { 147 //pair.setZero(); 148 continue; 149 } 150 if (!t) { 151 logger.info("criterion3(" + pair.i + "," + pair.j + ") wrong: " + s.leadingWord() 152 + " --> " + H.leadingWord()); 153 } 154 155 //H = H.monic(); 156 H = basePrimitivePart(H); 157 H = H.abs(); 158 if (debug) { 159 logger.info("ht(H) = " + H.leadingWord()); 160 } 161 if (H.isONE()) { 162 G.clear(); 163 G.add(H); 164 return G; // since no threads are activated 165 } 166 if (debug) { 167 logger.info("H = " + H); 168 } 169 if (H.length() > 0) { 170 //l++; 171 G.add(H); 172 pairlist.put(H); 173 } 174 } 175 } 176 //logger.info("#sequential list = " + G.size()); 177 G = minimalGB(G); 178 logger.info("" + pairlist); 179 //Collections.sort(G); 180 //Collections.reverse(G); 181 return G; 182 } 183 184 185 /** 186 * GenWordPolynomial base coefficient content. 187 * @param P GenWordPolynomial. 188 * @return cont(P). 189 */ 190 public C baseContent(GenWordPolynomial<C> P) { 191 if (P == null) { 192 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 193 } 194 if (P.isZERO()) { 195 return P.ring.getZEROCoefficient(); 196 } 197 C d = null; 198 for (C c : P.getMap().values()) { 199 if (d == null) { 200 d = c; 201 } else { 202 d = d.gcd(c); 203 } 204 if (d.isONE()) { 205 return d; 206 } 207 } 208 if (d.signum() < 0) { 209 d = d.negate(); 210 } 211 return d; 212 } 213 214 215 /** 216 * GenWordPolynomial base coefficient primitive part. 217 * @param P GenWordPolynomial. 218 * @return pp(P). 219 */ 220 public GenWordPolynomial<C> basePrimitivePart(GenWordPolynomial<C> P) { 221 if (P == null) { 222 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 223 } 224 if (P.isZERO()) { 225 return P; 226 } 227 C d = baseContent(P); 228 if (d.isONE()) { 229 return P; 230 } 231 GenWordPolynomial<C> pp = P.divide(d); 232 if (debug) { 233 GenWordPolynomial<C> p = pp.multiply(d); 234 if (!p.equals(P)) { 235 throw new ArithmeticException("pp(p)*cont(p) != p: "); 236 } 237 } 238 return pp; 239 } 240 241 242 /** 243 * List of GenWordPolynomial base coefficient primitive part. 244 * @param F list of GenWordPolynomials. 245 * @return pp(F). 246 */ 247 public List<GenWordPolynomial<C>> basePrimitivePart(List<GenWordPolynomial<C>> F) { 248 if (F == null || F.isEmpty()) { 249 return F; 250 } 251 List<GenWordPolynomial<C>> Pp = new ArrayList<GenWordPolynomial<C>>(F.size()); 252 for (GenWordPolynomial<C> f : F) { 253 GenWordPolynomial<C> p = basePrimitivePart(f); 254 Pp.add(p); 255 } 256 return Pp; 257 } 258 259}