001 /*
002 * $Id: OrderedDPairlist.java 3417 2010-12-19 16:24:24Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.Iterator;
008 import java.util.LinkedList;
009 import java.util.Map;
010 import org.apache.log4j.Logger;
011
012 import edu.jas.poly.ExpVector;
013 import edu.jas.poly.GenPolynomial;
014 import edu.jas.poly.GenPolynomialRing;
015 import edu.jas.structure.RingElem;
016
017 /**
018 * Pair list management for d-Groebner bases.
019 * Implemented using GenPolynomial, TreeMap and BitSet.
020 * @author Heinz Kredel
021 */
022
023 public class OrderedDPairlist<C extends RingElem<C> >
024 extends OrderedPairlist<C> {
025
026 private static final Logger logger = Logger.getLogger(OrderedDPairlist.class);
027
028 protected final DReduction<C> dreduction;
029
030
031 /**
032 * Constructor for OrderedDPairlist.
033 * @param r polynomial factory.
034 */
035 public OrderedDPairlist(GenPolynomialRing<C> r) {
036 this(0,r);
037 }
038
039
040 /**
041 * Constructor for OrderedDPairlist.
042 * @param m number of module variables.
043 * @param r polynomial factory.
044 */
045 public OrderedDPairlist(int m, GenPolynomialRing<C> r) {
046 super(m,r);
047 dreduction = new DReductionSeq<C>();
048 }
049
050
051 /**
052 * Create a new PairList.
053 * @param r polynomial ring.
054 */
055 public PairList<C> create(GenPolynomialRing<C> r) {
056 return new OrderedDPairlist<C>(r);
057 }
058
059
060 /**
061 * Create a new PairList.
062 * @param m number of module variables.
063 * @param r polynomial ring.
064 */
065 public PairList<C> create(int m, GenPolynomialRing<C> r) {
066 return new OrderedDPairlist<C>(m,r);
067 }
068
069
070 /**
071 * Remove the next required pair from the pairlist and reduction matrix.
072 * The results of the application of the criterions 3 and 4 to see if the S-polynomial
073 * is required are recorded in the Pair.
074 * @return the next pair if one exists, otherwise null.
075 */
076 @Override
077 public synchronized Pair<C> removeNext() {
078 if ( oneInGB ) {
079 return null;
080 }
081 Iterator< Map.Entry<ExpVector,LinkedList<Pair<C>>> > ip
082 = pairlist.entrySet().iterator();
083
084 Pair<C> pair = null;
085 boolean c = false;
086 int i, j;
087
088 if ( ip.hasNext() ) {
089 Map.Entry<ExpVector,LinkedList<Pair<C>>> me = ip.next();
090 ExpVector g = me.getKey();
091 LinkedList<Pair<C>> xl = me.getValue();
092 if ( logger.isInfoEnabled() ) {
093 logger.info("g = " + g);
094 }
095 pair = null;
096 if ( xl.size() > 0 ) {
097 pair = xl.removeFirst();
098 // xl is also modified in pairlist
099 i = pair.i;
100 j = pair.j;
101 // System.out.println("pair(" + j + "," +i+") ");
102 if ( useCriterion4 ) {
103 c = dreduction.criterion4( pair.pi, pair.pj, g );
104 } else {
105 c = true;
106 }
107 pair.setUseCriterion4(c);
108 //System.out.println("c4 = " + c);
109 if ( c ) {
110 c = criterion3( i, j, g );
111 //System.out.println("c3 = " + c);
112 pair.setUseCriterion3(c);
113 }
114 red.get( j ).clear(i); // set(i,false) jdk1.4
115 }
116 if ( xl.size() == 0 ) {
117 ip.remove(); // = pairlist.remove( g );
118 }
119 }
120 remCount++; // count pairs
121 return pair;
122 }
123
124
125 /**
126 * GB criterium 3 with coefficient division test.
127 * @return true if the S-polynomial(i,j) is required.
128 */
129 @Override
130 public boolean criterion3(int i, int j, ExpVector eij) {
131 // assert i < j;
132 boolean s;
133 s = red.get( j ).get(i);
134 if ( ! s ) {
135 logger.warn("c3.s false for " + j + " " + i);
136 return s;
137 }
138 s = true;
139 boolean m;
140 GenPolynomial<C> A;
141 ExpVector ek;
142 C ci = P.get(i).leadingBaseCoefficient();
143 C cj = P.get(j).leadingBaseCoefficient();
144 C c = ci.gcd(cj);
145 for ( int k = 0; k < P.size(); k++ ) {
146 A = P.get( k );
147 ek = A.leadingExpVector();
148 m = eij.multipleOf(ek);
149 if ( m ) {
150 C ck = A.leadingBaseCoefficient();
151 C r = c.remainder(ck);
152 m = r.isZERO();
153 }
154 if ( m ) {
155 if ( k < i ) {
156 // System.out.println("k < i "+k+" "+i);
157 s = red.get( i ).get(k)
158 || red.get( j ).get(k);
159 }
160 if ( i < k && k < j ) {
161 // System.out.println("i < k < j "+i+" "+k+" "+j);
162 s = red.get( k ).get(i)
163 || red.get( j ).get(k);
164 }
165 if ( j < k ) {
166 //System.out.println("j < k "+j+" "+k);
167 s = red.get( k ).get(i)
168 || red.get( k ).get(j);
169 }
170 //System.out.println("s."+k+" = " + s);
171 if ( ! s ) return s;
172 }
173 }
174 return true;
175 }
176
177 }