001/* 002 * $Id: OrderedMinPairlist.java 4334 2012-12-28 11:49:57Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007import java.util.ArrayList; 008import java.util.BitSet; 009import java.util.Iterator; 010import java.util.LinkedList; 011import java.util.Map; 012import java.util.TreeMap; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.poly.ExpVector; 017import edu.jas.poly.GenPolynomial; 018import edu.jas.poly.GenPolynomialRing; 019import edu.jas.poly.GenSolvablePolynomialRing; 020import edu.jas.structure.RingElem; 021 022/** 023 * Pair list management. 024 * The original Buchberger algorithm with criterions 025 * using early pair exclusion. 026 * Implemented using GenPolynomial, TreeMap and BitSet. 027 * @author Heinz Kredel 028 */ 029 030public class OrderedMinPairlist<C extends RingElem<C> > extends OrderedPairlist<C> { 031 032 private static final Logger logger = Logger.getLogger(OrderedMinPairlist.class); 033 034 035 /** 036 * Constructor. 037 */ 038 public OrderedMinPairlist() { 039 super(); 040 } 041 042 043 /** 044 * Constructor. 045 * @param r polynomial factory. 046 */ 047 public OrderedMinPairlist(GenPolynomialRing<C> r) { 048 this(0,r); 049 } 050 051 052 /** 053 * Constructor. 054 * @param m number of module variables. 055 * @param r polynomial factory. 056 */ 057 public OrderedMinPairlist(int m, GenPolynomialRing<C> r) { 058 super(m,r); 059 } 060 061 062 /** 063 * Create a new PairList. 064 * @param r polynomial ring. 065 */ 066 public PairList<C> create(GenPolynomialRing<C> r) { 067 return new OrderedMinPairlist<C>(r); 068 } 069 070 071 /** 072 * Create a new PairList. 073 * @param m number of module variables. 074 * @param r polynomial ring. 075 */ 076 public PairList<C> create(int m, GenPolynomialRing<C> r) { 077 return new OrderedMinPairlist<C>(m,r); 078 } 079 080 081 /** 082 * Put one Polynomial to the pairlist and reduction matrix. 083 * @param p polynomial. 084 * @return the index of the added polynomial. 085 */ 086 public synchronized int put(GenPolynomial<C> p) { 087 putCount++; 088 if ( oneInGB ) { 089 return P.size()-1; 090 } 091 ExpVector e = p.leadingExpVector(); 092 int l = P.size(); 093 BitSet redi = new BitSet(); 094 redi.set( 0, l ); // [0..l-1] = true 095 red.add( redi ); 096 P.add( p ); 097 for ( int j = 0; j < l; j++ ) { 098 GenPolynomial<C> pj = P.get(j); 099 ExpVector f = pj.leadingExpVector(); 100 if ( moduleVars > 0 ) { 101 if ( !reduction.moduleCriterion( moduleVars, e, f) ) { 102 red.get(j).clear(l); 103 continue; // skip pair 104 } 105 } 106 ExpVector g = e.lcm( f ); 107 //System.out.println("g = " + g); 108 Pair<C> pair = new Pair<C>( pj, p, j, l); 109 boolean c = true; 110 if ( useCriterion4 ) { 111 c = reduction.criterion4( pair.pi, pair.pj, g ); 112 } 113 //System.out.println("c4 = " + c); 114 if ( c ) { 115 c = criterion3( j, l, g ); 116 //System.out.println("c3 = " + c); 117 } 118 if ( !c ) { // skip pair 119 red.get(j).clear(l); 120 //System.out.println("c_skip = " + g); 121 continue; 122 } 123 //multiple pairs under same keys -> list of pairs 124 LinkedList<Pair<C>> xl = pairlist.get( g ); 125 if ( xl == null ) { 126 xl = new LinkedList<Pair<C>>(); 127 } 128 //xl.addLast( pair ); // first or last ? 129 xl.addFirst( pair ); // first or last ? better for d- e-GBs 130 pairlist.put( g, xl ); 131 } 132 // System.out.println("pairlist.keys@put = " + pairlist.keySet() ); 133 return P.size()-1; 134 } 135 136 137 /** 138 * Remove the next required pair from the pairlist and reduction matrix. 139 * Appy the criterions 3 and 4 to see if the S-polynomial is required. 140 * @return the next pair if one exists, otherwise null. 141 */ 142 public synchronized Pair<C> removeNext() { 143 if ( oneInGB ) { 144 return null; 145 } 146 Iterator< Map.Entry<ExpVector,LinkedList<Pair<C>>> > ip 147 = pairlist.entrySet().iterator(); 148 149 Pair<C> pair = null; 150 boolean c = false; 151 int i, j; 152 153 while ( !c && ip.hasNext() ) { 154 Map.Entry<ExpVector,LinkedList<Pair<C>>> me = ip.next(); 155 ExpVector g = me.getKey(); 156 LinkedList<Pair<C>> xl = me.getValue(); 157 if ( logger.isInfoEnabled() ) { 158 logger.info("g = " + g); 159 } 160 pair = null; 161 while ( !c && xl.size() > 0 ) { 162 pair = xl.removeFirst(); 163 // xl is also modified in pairlist 164 i = pair.i; 165 j = pair.j; 166 // System.out.println("pair(" + j + "," +i+") "); 167 if ( !red.get(j).get(i) ) { 168 System.out.println("c_y = " + g); // + ", " + red.get(j).get(i)); 169 continue; 170 } 171 c = true; 172 if ( useCriterion4 ) { 173 c = reduction.criterion4( pair.pi, pair.pj, g ); 174 } 175 //System.out.println("c4_x = " + c); 176 if ( c ) { 177 c = criterion3( i, j, g ); 178 //System.out.println("c3_x = " + c); 179 } 180 if ( !c ) { 181 //System.out.println("c_x = " + g); 182 } 183 red.get( j ).clear(i); // set(i,false) jdk1.4 184 } 185 if ( xl.size() == 0 ) { 186 ip.remove(); 187 // = pairlist.remove( g ); 188 } 189 } 190 if ( ! c ) { 191 pair = null; 192 } else { 193 pair.maxIndex(P.size()-1); 194 remCount++; // count only real pairs 195 if ( logger.isDebugEnabled() ) { 196 logger.info("pair(" + pair.j + "," + pair.i + ")"); 197 } 198 } 199 return pair; 200 } 201 202 203 /** 204 * GB criterium 3. 205 * @return true if the S-polynomial(i,j) is required. 206 */ 207 public boolean criterion3(int i, int j, ExpVector eij) { 208 // assert i < j; 209 boolean s; 210 s = red.get( j ).get(i); 211 if ( ! s ) { 212 logger.warn("c3.s false for " + j + " " + i); 213 return s; 214 } 215 s = true; 216 boolean m; 217 GenPolynomial<C> A; 218 ExpVector ek; 219 for ( int k = 0; k < P.size(); k++ ) { 220 A = P.get( k ); 221 ek = A.leadingExpVector(); 222 m = eij.multipleOf(ek) && eij.compareTo(ek) != 0; 223 if ( m ) { 224 if ( k < i ) { 225 // System.out.println("k < i "+k+" "+i); 226 s = red.get( i ).get(k) 227 || red.get( j ).get(k); 228 } 229 if ( i < k && k < j ) { 230 // System.out.println("i < k < j "+i+" "+k+" "+j); 231 s = red.get( k ).get(i) 232 || red.get( j ).get(k); 233 } 234 if ( j < k ) { 235 //System.out.println("j < k "+j+" "+k); 236 s = red.get( k ).get(i) 237 || red.get( k ).get(j); 238 } 239 //System.out.println("s."+k+" = " + s); 240 if ( ! s ) return s; 241 } 242 } 243 return true; 244 } 245 246}