001/* 002 * $Id: OrderedSyzPairlist.java 4249 2012-10-14 10:13:04Z 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 LinkedList<Pair<C>> ignored = npl.remove(ei); 188 } 189 // skip by criterion 4: 190 if (useCriterion4) { 191 es = new ArrayList<ExpVector>(npl.size()); 192 for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) { 193 ExpVector ei = me.getKey(); 194 LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei ); 195 //System.out.println("exl = " + exl ); 196 boolean c = true; 197 for (Pair<C> pair : exl) { 198 c = c && reduction.criterion4(pair.pi, pair.pj, pair.e); 199 } 200 if (c) { 201 if (exl.size() > 1) { 202 Pair<C> pair = exl.getFirst(); // or exl.getLast(); 203 exl.clear(); 204 exl.add(pair); 205 //npl.put(ei,exl); 206 } 207 } else { 208 if (!es.contains(ei)) { 209 es.add(ei); 210 } 211 } 212 } 213 //System.out.println("npl.skip c4 = " + es); 214 for (ExpVector ei : es) { 215 LinkedList<Pair<C>> ignored = npl.remove(ei); 216 } 217 } 218 // add to existing pairlist: 219 //System.out.println("npl.put new = " + npl.keySet() ); 220 for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) { 221 ExpVector ei = me.getKey(); 222 LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei ); 223 for (Pair<C> pair : exl) { 224 red.get(pair.j).set(pair.i); 225 } 226 LinkedList<Pair<C>> ex = pairlist.get(ei); // wrong in findbugs 227 if (ex != null) { 228 exl.addAll(ex); // add new pairs first 229 ex = exl; 230 //ex.addAll(exl); // add old pairs first 231 } else { 232 ex = exl; 233 } 234 pairlist.put(ei, ex); // replace ex 235 } 236 return P.size() - 1; 237 } 238 239 240 /** 241 * Remove the next required pair from the pairlist and reduction matrix. 242 * Appy the criterions 3 and 4 to see if the S-polynomial is required. 243 * @return the next pair if one exists, otherwise null. 244 */ 245 @Override 246 public synchronized Pair<C> removeNext() { 247 if (oneInGB) { 248 return null; 249 } 250 Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator(); 251 Pair<C> pair = null; 252 //boolean c = false; 253 int i, j; 254 while (ip.hasNext()) { 255 Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next(); 256 ExpVector g = me.getKey(); 257 LinkedList<Pair<C>> xl = me.getValue(); 258 if (logger.isInfoEnabled()) 259 logger.info("g = " + g); 260 pair = null; 261 while (xl.size() > 0) { 262 pair = xl.removeFirst(); // xl is also modified in pairlist 263 i = pair.i; 264 j = pair.j; 265 //System.out.println("pair.remove = " + pair ); 266 if (!red.get(j).get(i)) { // should not happen 267 System.out.println("c_red.get(" + j + ").get(" + i + ") = " + g); 268 pair = null; 269 continue; 270 } 271 red.get(j).clear(i); 272 break; 273 } 274 if (xl.size() == 0) { 275 ip.remove(); // = pairlist.remove( g ); 276 } 277 if (pair != null) { 278 break; 279 } 280 } 281 if ( pair != null ) { 282 remCount++; // count only real pairs 283 if ( logger.isDebugEnabled() ) { 284 logger.info("pair(" + pair.j + "," + pair.i + ")"); 285 } 286 } 287 return pair; 288 } 289 290 291 /** 292 * GB criterium 3. 293 * @return true if the S-polynomial(i,j) is required. 294 */ 295 @Override 296 public boolean criterion3(int i, int j, ExpVector eij) { 297 throw new UnsupportedOperationException("not used in " + this.getClass().getName()); 298 } 299 300}