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