001/* 002 * $Id$ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.List; 009 010import org.apache.logging.log4j.Logger; 011import org.apache.logging.log4j.LogManager; 012 013import edu.jas.kern.LocalTimeStatus; 014import edu.jas.poly.GenWordPolynomial; 015import edu.jas.poly.GenWordPolynomialRing; 016import edu.jas.poly.PolyUtil; 017import edu.jas.structure.RingElem; 018 019 020/** 021 * Non-commutative word Groebner Base sequential algorithm. Implements 022 * Groebner bases and GB test. Run-time for GB computation is limited 023 * to 20 seconds. To change this limit use 024 * <pre> 025 * wbb.timestatus.setLimit(newLimit); 026 * </pre> 027 * or decativate it for infinite running time 028 * <pre> 029 * wbb.timestatus.setNotActive(); 030 * </pre> 031 * @param <C> coefficient type 032 * @author Heinz Kredel 033 */ 034 035public class WordGroebnerBaseSeq<C extends RingElem<C>> extends WordGroebnerBaseAbstract<C> { 036 037 038 private static final Logger logger = LogManager.getLogger(WordGroebnerBaseSeq.class); 039 040 041 private static final boolean debug = logger.isDebugEnabled(); 042 043 044 public final LocalTimeStatus timestatus; 045 046 047 /** 048 * Constructor. 049 */ 050 public WordGroebnerBaseSeq() { 051 super(); 052 timestatus = new LocalTimeStatus(true, 20*1000, false); 053 } 054 055 056 /** 057 * Constructor. 058 * @param red Reduction engine 059 */ 060 public WordGroebnerBaseSeq(WordReduction<C> red) { 061 super(red); 062 timestatus = new LocalTimeStatus(true, 20*1000, false); 063 } 064 065 066 /** 067 * Constructor. 068 * @param red Reduction engine 069 * @param pl pair selection strategy 070 */ 071 public WordGroebnerBaseSeq(WordReduction<C> red, WordPairList<C> pl) { 072 super(red, pl); 073 timestatus = new LocalTimeStatus(true, 20*1000, false); 074 } 075 076 077 /** 078 * Word Groebner base using word pairlist class. 079 * @param F word polynomial list. 080 * @return GB(F) a finite non-commutative Groebner base of F, if it exists. 081 */ 082 @Override 083 public List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F) { 084 List<GenWordPolynomial<C>> G = normalizeZerosOnes(F); 085 G = PolyUtil.<C> wordMonic(G); 086 if (G.size() <= 1) { 087 return G; 088 } 089 GenWordPolynomialRing<C> ring = G.get(0).ring; 090 if (!ring.coFac.isField()) { 091 throw new IllegalArgumentException("coefficients not from a field"); 092 } 093 //Collections.sort(G); 094 OrderedWordPairlist<C> pairlist = (OrderedWordPairlist<C>) strategy.create(ring); 095 pairlist.put(G); 096 logger.info("start {}", pairlist); 097 timestatus.restart(); 098 //if (timestatus.isActive()) { 099 // throw new RuntimeException("timestatus: " + timestatus); 100 //} 101 102 WordPair<C> pair; 103 GenWordPolynomial<C> pi; 104 GenWordPolynomial<C> pj; 105 List<GenWordPolynomial<C>> S; 106 GenWordPolynomial<C> H; 107 int infin = 0; 108 while (pairlist.hasNext()) { 109 pair = pairlist.removeNext(); 110 //logger.debug("pair = {}", pair); 111 if (pair == null) { 112 continue; 113 } 114 pi = pair.pi; 115 pj = pair.pj; 116 if (debug) { 117 logger.info("pi = {}, pj = {}", pi, pj); 118 } 119 120 S = red.SPolynomials(pi, pj); 121 if (S.isEmpty()) { 122 continue; 123 } 124 for (GenWordPolynomial<C> s : S) { 125 if (s.isZERO()) { 126 //pair.setZero(); 127 continue; 128 } 129 if (debug) { 130 logger.info("ht(S) = {}", s.leadingWord()); 131 } 132 boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord()); 133 //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t); 134 //if ( !t ) { 135 // continue; 136 //} 137 138 H = red.normalform(G, s); 139 if (debug) { 140 //logger.info("pair = {}", pair); 141 //logger.info("ht(S) = {}", S.monic()); //.leadingWord() ); 142 logger.info("ht(H) = {}", H.monic()); //.leadingWord() ); 143 } 144 if (H.isZERO()) { 145 //pair.setZero(); 146 continue; 147 } 148 if (!t) { 149 logger.info("criterion3({},{}) wrong: {} --> {}", pair.i, pair.j, s.leadingWord(), H.leadingWord()); 150 } 151 152 H = H.monic(); 153 if (debug) { 154 logger.info("ht(H) = {}", H.leadingWord()); 155 } 156 if (H.isONE()) { 157 G.clear(); 158 G.add(H); 159 return G; // since no threads are activated 160 } 161 if (debug) { 162 logger.info("H = {}", H); 163 } 164 if (H.length() > 0) { 165 //l++; 166 G.add(H); 167 pairlist.put(H); 168 } 169 if (H.degree() > 9) { 170 //System.out.println("deg(H): " + H.degree()); 171 //logger.warn("word GB too high degree {}", H.degree()); 172 timestatus.checkTime("word GB degree > 9: " + H.degree()); 173 } 174 175 if (s.leadingWord().dependencyOnVariables().equals(H.leadingWord().dependencyOnVariables())) { 176 logger.info("LT depend: {} --> {}", s.leadingWord().dependencyOnVariables(), H.leadingWord().dependencyOnVariables()); 177 logger.info("LT depend: {} --> {}", s, H); 178 infin++; 179 if (infin > 500) { 180 //System.out.println("deg(H): " + H.degree()); 181 //throw new RuntimeException("no convergence in word GB: " + infin); 182 timestatus.checkTime("no convergence in word GB: > 500: " + infin); 183 } 184 } 185 } 186 } 187 //logger.info("#sequential list = {}", G.size()); 188 G = minimalGB(G); 189 logger.info("end {}", pairlist); 190 //Collections.sort(G); 191 //Collections.reverse(G); 192 return G; 193 } 194 195}