001/* 002 * $Id: OrderedRPairlist.java 3652 2011-06-02 18:17:04Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007import java.util.Iterator; 008import java.util.LinkedList; 009import java.util.Map; 010import org.apache.log4j.Logger; 011 012import edu.jas.gb.OrderedPairlist; 013import edu.jas.gb.Pair; 014import edu.jas.poly.ExpVector; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import 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 025public 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}