001 /*
002 * $Id: OrderedMinPairlist.java 3418 2010-12-19 17:54:17Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.BitSet;
009 import java.util.Iterator;
010 import java.util.LinkedList;
011 import java.util.Map;
012 import java.util.TreeMap;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019 import edu.jas.poly.GenSolvablePolynomialRing;
020 import 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
030 public 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 remCount++; // count only real pairs
194 }
195 return pair;
196 }
197
198
199 /**
200 * GB criterium 3.
201 * @return true if the S-polynomial(i,j) is required.
202 */
203 public boolean criterion3(int i, int j, ExpVector eij) {
204 // assert i < j;
205 boolean s;
206 s = red.get( j ).get(i);
207 if ( ! s ) {
208 logger.warn("c3.s false for " + j + " " + i);
209 return s;
210 }
211 s = true;
212 boolean m;
213 GenPolynomial<C> A;
214 ExpVector ek;
215 for ( int k = 0; k < P.size(); k++ ) {
216 A = P.get( k );
217 ek = A.leadingExpVector();
218 m = eij.multipleOf(ek) && eij.compareTo(ek) != 0;
219 if ( m ) {
220 if ( k < i ) {
221 // System.out.println("k < i "+k+" "+i);
222 s = red.get( i ).get(k)
223 || red.get( j ).get(k);
224 }
225 if ( i < k && k < j ) {
226 // System.out.println("i < k < j "+i+" "+k+" "+j);
227 s = red.get( k ).get(i)
228 || red.get( j ).get(k);
229 }
230 if ( j < k ) {
231 //System.out.println("j < k "+j+" "+k);
232 s = red.get( k ).get(i)
233 || red.get( k ).get(j);
234 }
235 //System.out.println("s."+k+" = " + s);
236 if ( ! s ) return s;
237 }
238 }
239 return true;
240 }
241
242 }