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