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