001/* 002 * $Id: WordGroebnerBaseSeq.java 5305 2015-08-23 20:38:09Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.List; 009 010import org.apache.log4j.Logger; 011 012import edu.jas.poly.GenWordPolynomial; 013import edu.jas.poly.GenWordPolynomialRing; 014import edu.jas.poly.PolyUtil; 015import edu.jas.structure.RingElem; 016 017 018/** 019 * Non-commutative word Groebner Base sequential algorithm. Implements Groebner 020 * bases and GB test. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class WordGroebnerBaseSeq<C extends RingElem<C>> extends WordGroebnerBaseAbstract<C> { 026 027 028 private static final Logger logger = Logger.getLogger(WordGroebnerBaseSeq.class); 029 030 031 private final boolean debug = logger.isDebugEnabled(); 032 033 034 /** 035 * Constructor. 036 */ 037 public WordGroebnerBaseSeq() { 038 super(); 039 } 040 041 042 /** 043 * Constructor. 044 * @param red Reduction engine 045 */ 046 public WordGroebnerBaseSeq(WordReduction<C> red) { 047 super(red); 048 } 049 050 051 /** 052 * Constructor. 053 * @param red Reduction engine 054 * @param pl pair selection strategy 055 */ 056 public WordGroebnerBaseSeq(WordReduction<C> red, WordPairList<C> pl) { 057 super(red, pl); 058 } 059 060 061 /** 062 * Word Groebner base using word pairlist class. 063 * @param F word polynomial list. 064 * @return GB(F) a finite non-commutative Groebner base of F, if it exists. 065 */ 066 @Override 067 public List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F) { 068 List<GenWordPolynomial<C>> G = normalizeZerosOnes(F); 069 G = PolyUtil.<C> wordMonic(G); 070 if (G.size() <= 1) { 071 return G; 072 } 073 GenWordPolynomialRing<C> ring = G.get(0).ring; 074 if (!ring.coFac.isField()) { 075 throw new IllegalArgumentException("coefficients not from a field"); 076 } 077 //Collections.sort(G); 078 OrderedWordPairlist<C> pairlist = (OrderedWordPairlist<C>) strategy.create(ring); 079 pairlist.put(G); 080 logger.info("start " + pairlist); 081 082 WordPair<C> pair; 083 GenWordPolynomial<C> pi; 084 GenWordPolynomial<C> pj; 085 List<GenWordPolynomial<C>> S; 086 GenWordPolynomial<C> H; 087 while (pairlist.hasNext()) { 088 pair = pairlist.removeNext(); 089 //logger.debug("pair = " + pair); 090 if (pair == null) { 091 continue; 092 } 093 pi = pair.pi; 094 pj = pair.pj; 095 if (debug) { 096 logger.info("pi = " + pi + ", pj = " + pj); 097 //logger.info("pj = " + pj); 098 } 099 100 S = red.SPolynomials(pi, pj); 101 if (S.isEmpty()) { 102 continue; 103 } 104 for (GenWordPolynomial<C> s : S) { 105 if (s.isZERO()) { 106 //pair.setZero(); 107 continue; 108 } 109 if (debug) { 110 logger.info("ht(S) = " + s.leadingWord()); 111 } 112 boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord()); 113 //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t); 114 //if ( !t ) { 115 // continue; 116 //} 117 118 H = red.normalform(G, s); 119 if (debug) { 120 //logger.info("pair = " + pair); 121 //logger.info("ht(S) = " + S.monic()); //.leadingWord() ); 122 logger.info("ht(H) = " + H.monic()); //.leadingWord() ); 123 } 124 if (H.isZERO()) { 125 //pair.setZero(); 126 continue; 127 } 128 if (!t) { 129 logger.info("criterion3(" + pair.i + "," + pair.j + ") wrong: " + s.leadingWord() 130 + " --> " + H.leadingWord()); 131 } 132 133 H = H.monic(); 134 if (debug) { 135 logger.info("ht(H) = " + H.leadingWord()); 136 } 137 if (H.isONE()) { 138 G.clear(); 139 G.add(H); 140 return G; // since no threads are activated 141 } 142 if (debug) { 143 logger.info("H = " + H); 144 } 145 if (H.length() > 0) { 146 //l++; 147 G.add(H); 148 pairlist.put(H); 149 } 150 } 151 } 152 //logger.info("#sequential list = " + G.size()); 153 G = minimalGB(G); 154 logger.info("end " + pairlist); 155 //Collections.sort(G); 156 //Collections.reverse(G); 157 return G; 158 } 159 160}