001/* 002 * $Id: OrderedSyzPairlist.java 4964 2014-10-17 19:43:31Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.BitSet; 010import java.util.Iterator; 011import java.util.LinkedList; 012import java.util.List; 013import java.util.Map; 014import java.util.SortedMap; 015import java.util.TreeMap; 016 017import org.apache.log4j.Logger; 018 019import edu.jas.poly.ExpVector; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenPolynomialRing; 022import edu.jas.structure.RingElem; 023 024 025/** 026 * Pair list management. For the Buchberger algorithm following the syzygy 027 * criterions by Gebauer & Möller. Implemented using GenPolynomial, 028 * TreeMap and BitSet. 029 * @author Heinz Kredel 030 */ 031 032public class OrderedSyzPairlist<C extends RingElem<C>> extends OrderedPairlist<C> { 033 034 035 private static final Logger logger = Logger.getLogger(OrderedSyzPairlist.class); 036 037 038 /** 039 * Constructor. 040 */ 041 public OrderedSyzPairlist() { 042 super(); 043 } 044 045 046 /** 047 * Constructor. 048 * @param r polynomial factory. 049 */ 050 public OrderedSyzPairlist(GenPolynomialRing<C> r) { 051 this(0, r); 052 } 053 054 055 /** 056 * Constructor. 057 * @param m number of module variables. 058 * @param r polynomial factory. 059 */ 060 public OrderedSyzPairlist(int m, GenPolynomialRing<C> r) { 061 super(m, r); 062 } 063 064 065 /** 066 * Create a new PairList. 067 * @param r polynomial ring. 068 */ 069 @Override 070 public PairList<C> create(GenPolynomialRing<C> r) { 071 return new OrderedSyzPairlist<C>(r); 072 } 073 074 075 /** 076 * Create a new PairList. 077 * @param m number of module variables. 078 * @param r polynomial ring. 079 */ 080 @Override 081 public PairList<C> create(int m, GenPolynomialRing<C> r) { 082 return new OrderedSyzPairlist<C>(m, r); 083 } 084 085 086 /** 087 * Put one Polynomial to the pairlist and reduction matrix. Removes all 088 * unnecessary pairs identified by the syzygy criterion and criterion 4. 089 * @param p polynomial. 090 * @return the index of the added polynomial. 091 */ 092 @Override 093 public synchronized int put(GenPolynomial<C> p) { 094 putCount++; 095 if (oneInGB) { 096 return P.size() - 1; 097 } 098 ExpVector e = p.leadingExpVector(); 099 int ps = P.size(); 100 BitSet redi = new BitSet(); // all zeros 101 //redi.set( 0, ps ); // [0..ps-1] = true, i.e. all ones 102 red.add(redi); 103 P.add(p); 104 // remove from existing pairs: 105 List<ExpVector> es = new ArrayList<ExpVector>(); 106 for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : pairlist.entrySet()) { 107 ExpVector g = me.getKey(); 108 if (moduleVars > 0) { 109 if (!reduction.moduleCriterion(moduleVars, e, g)) { 110 continue; // skip pair 111 } 112 } 113 ExpVector ge = g.lcm(e); 114 LinkedList<Pair<C>> ll = me.getValue(); 115 if (g.compareTo(ge) == 0) { 116 LinkedList<Pair<C>> lle = new LinkedList<Pair<C>>(); 117 for (Pair<C> pair : ll) { 118 ExpVector eil = pair.pi.leadingExpVector().lcm(e); 119 if (g.compareTo(eil) == 0) { 120 continue; 121 } 122 ExpVector ejl = pair.pj.leadingExpVector().lcm(e); 123 if (g.compareTo(ejl) == 0) { 124 continue; 125 } 126 // g == ge && g != eil && g != ejl 127 red.get(pair.j).clear(pair.i); 128 lle.add(pair); 129 } 130 if (lle.size() > 0) { 131 for (Pair<C> pair : lle) { 132 ll.remove(pair); 133 } 134 if (!es.contains(g)) { 135 es.add(g); 136 } 137 } 138 } 139 } 140 for (ExpVector ei : es) { 141 LinkedList<Pair<C>> ll = pairlist.get(ei); 142 if (ll != null && ll.size() == 0) { 143 ll = pairlist.remove(ei); 144 } 145 } 146 // generate new pairs: 147 SortedMap<ExpVector, LinkedList<Pair<C>>> npl = new TreeMap<ExpVector, LinkedList<Pair<C>>>( 148 ring.tord.getAscendComparator()); 149 for (int j = 0; j < ps; j++) { 150 GenPolynomial<C> pj = P.get(j); 151 ExpVector f = pj.leadingExpVector(); 152 if (moduleVars > 0) { 153 if (!reduction.moduleCriterion(moduleVars, e, f)) { 154 //red.get(j).clear(l); 155 continue; // skip pair 156 } 157 } 158 ExpVector g = e.lcm(f); 159 Pair<C> pair = new Pair<C>(pj, p, j, ps); 160 //System.out.println("pair.new = " + pair); 161 //multiple pairs under same keys -> list of pairs 162 LinkedList<Pair<C>> xl = npl.get(g); 163 if (xl == null) { 164 xl = new LinkedList<Pair<C>>(); 165 } 166 //xl.addLast( pair ); // first or last ? 167 xl.addFirst(pair); // first or last ? better for d- e-GBs 168 npl.put(g, xl); 169 } 170 //System.out.println("npl.new = " + npl.keySet()); 171 // skip by divisibility: 172 es = new ArrayList<ExpVector>(npl.size()); 173 for (ExpVector eil : npl.keySet()) { 174 for (ExpVector ejl : npl.keySet()) { 175 if (eil.compareTo(ejl) == 0) { 176 continue; 177 } 178 if (eil.multipleOf(ejl)) { 179 if (!es.contains(eil)) { 180 es.add(eil); 181 } 182 } 183 } 184 } 185 //System.out.println("npl.skip div = " + es); 186 for (ExpVector ei : es) { 187 @SuppressWarnings("unused") 188 LinkedList<Pair<C>> ignored = npl.remove(ei); 189 } 190 // skip by criterion 4: 191 if (useCriterion4) { 192 es = new ArrayList<ExpVector>(npl.size()); 193 for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) { 194 ExpVector ei = me.getKey(); 195 LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei ); 196 //System.out.println("exl = " + exl ); 197 boolean c = true; 198 for (Pair<C> pair : exl) { 199 c = c && reduction.criterion4(pair.pi, pair.pj, pair.e); 200 } 201 if (c) { 202 if (exl.size() > 1) { 203 Pair<C> pair = exl.getFirst(); // or exl.getLast(); 204 exl.clear(); 205 exl.add(pair); 206 //npl.put(ei,exl); 207 } 208 } else { 209 if (!es.contains(ei)) { 210 es.add(ei); 211 } 212 } 213 } 214 //System.out.println("npl.skip c4 = " + es); 215 for (ExpVector ei : es) { 216 @SuppressWarnings("unused") 217 LinkedList<Pair<C>> ignored = npl.remove(ei); 218 } 219 } 220 // add to existing pairlist: 221 //System.out.println("npl.put new = " + npl.keySet() ); 222 for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) { 223 ExpVector ei = me.getKey(); 224 LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei ); 225 for (Pair<C> pair : exl) { 226 red.get(pair.j).set(pair.i); 227 } 228 LinkedList<Pair<C>> ex = pairlist.get(ei); // wrong in findbugs 229 if (ex != null) { 230 exl.addAll(ex); // add new pairs first 231 ex = exl; 232 //ex.addAll(exl); // add old pairs first 233 } else { 234 ex = exl; 235 } 236 pairlist.put(ei, ex); // replace ex 237 } 238 return P.size() - 1; 239 } 240 241 242 /** 243 * Remove the next required pair from the pairlist and reduction matrix. 244 * Appy the criterions 3 and 4 to see if the S-polynomial is required. 245 * @return the next pair if one exists, otherwise null. 246 */ 247 @Override 248 public synchronized Pair<C> removeNext() { 249 if (oneInGB) { 250 return null; 251 } 252 Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator(); 253 Pair<C> pair = null; 254 //boolean c = false; 255 int i, j; 256 while (ip.hasNext()) { 257 Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next(); 258 ExpVector g = me.getKey(); 259 LinkedList<Pair<C>> xl = me.getValue(); 260 if (logger.isInfoEnabled()) 261 logger.info("g = " + g); 262 pair = null; 263 while (xl.size() > 0) { 264 pair = xl.removeFirst(); // xl is also modified in pairlist 265 i = pair.i; 266 j = pair.j; 267 //System.out.println("pair.remove = " + pair ); 268 if (!red.get(j).get(i)) { // should not happen 269 System.out.println("c_red.get(" + j + ").get(" + i + ") = " + g); 270 pair = null; 271 continue; 272 } 273 red.get(j).clear(i); 274 break; 275 } 276 if (xl.size() == 0) { 277 ip.remove(); // = pairlist.remove( g ); 278 } 279 if (pair != null) { 280 break; 281 } 282 } 283 if (pair != null) { 284 pair.maxIndex(P.size() - 1); 285 remCount++; // count only real pairs 286 if (logger.isDebugEnabled()) { 287 logger.info("pair(" + pair.j + "," + pair.i + ")"); 288 } 289 } 290 return pair; 291 } 292 293 294 /** 295 * GB criterium 3. 296 * @return true if the S-polynomial(i,j) is required. 297 */ 298 @Override 299 public boolean criterion3(int i, int j, ExpVector eij) { 300 throw new UnsupportedOperationException("not used in " + this.getClass().getName()); 301 } 302 303}