001/* 002 * $Id: GroebnerBasePseudoSeq.java 4290 2012-11-04 14:47:45Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011import java.util.ListIterator; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.gb.GroebnerBaseAbstract; 016import edu.jas.gb.Pair; 017import edu.jas.gb.PairList; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.structure.GcdRingElem; 020import edu.jas.structure.RingFactory; 021import edu.jas.ufd.GCDFactory; 022import edu.jas.ufd.GreatestCommonDivisorAbstract; 023 024 025/** 026 * Groebner Base with pseudo reduction sequential algorithm. Implements 027 * coefficient fraction free Groebner bases. 028 * @param <C> coefficient type 029 * @author Heinz Kredel 030 * 031 * @see edu.jas.application.GBAlgorithmBuilder 032 * @see edu.jas.gbufd.GBFactory 033 */ 034 035public class GroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> { 036 037 038 private static final Logger logger = Logger.getLogger(GroebnerBasePseudoSeq.class); 039 040 041 private final boolean debug = logger.isDebugEnabled(); 042 043 044 /** 045 * Greatest common divisor engine for coefficient content and primitive 046 * parts. 047 */ 048 protected final GreatestCommonDivisorAbstract<C> engine; 049 050 051 /** 052 * Pseudo reduction engine. 053 */ 054 protected final PseudoReduction<C> red; 055 056 057 /** 058 * Coefficient ring factory. 059 */ 060 protected final RingFactory<C> cofac; 061 062 063 /** 064 * Constructor. 065 * @param rf coefficient ring factory. 066 */ 067 public GroebnerBasePseudoSeq(RingFactory<C> rf) { 068 this(new PseudoReductionSeq<C>(), rf); 069 } 070 071 072 /** 073 * Constructor. 074 * @param red pseudo reduction engine. 075 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance 076 * of PseudoReductionSeq. 077 */ 078 public GroebnerBasePseudoSeq(PseudoReduction<C> red, RingFactory<C> rf) { 079 super(red); 080 this.red = red; 081 cofac = rf; 082 engine = GCDFactory.<C> getImplementation(rf); 083 //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf ); 084 } 085 086 087 /** 088 * Groebner base using pairlist class. 089 * @param modv module variable number. 090 * @param F polynomial list. 091 * @return GB(F) a Groebner base of F. 092 */ 093 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 094 GenPolynomial<C> p; 095 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 096 PairList<C> pairlist = null; 097 int l = F.size(); 098 ListIterator<GenPolynomial<C>> it = F.listIterator(); 099 while (it.hasNext()) { 100 p = it.next(); 101 if (p.length() > 0) { 102 p = engine.basePrimitivePart(p); //p.monic(); 103 p = p.abs(); 104 if (p.isConstant()) { 105 G.clear(); 106 G.add(p); 107 return G; // since no threads are activated 108 } 109 G.add(p); 110 if (pairlist == null) { 111 //pairlist = new OrderedPairlist<C>(modv, p.ring); 112 pairlist = strategy.create(modv, p.ring); 113 } 114 // putOne not required 115 pairlist.put(p); 116 } else { 117 l--; 118 } 119 } 120 if (l <= 1) { 121 return G; // since no threads are activated 122 } 123 124 Pair<C> pair; 125 GenPolynomial<C> pi; 126 GenPolynomial<C> pj; 127 GenPolynomial<C> S; 128 GenPolynomial<C> H; 129 while (pairlist.hasNext()) { 130 pair = pairlist.removeNext(); 131 if (pair == null) 132 continue; 133 134 pi = pair.pi; 135 pj = pair.pj; 136 if (debug) { 137 logger.debug("pi = " + pi); 138 logger.debug("pj = " + pj); 139 } 140 141 S = red.SPolynomial(pi, pj); 142 if (S.isZERO()) { 143 pair.setZero(); 144 continue; 145 } 146 if (debug) { 147 logger.debug("ht(S) = " + S.leadingExpVector()); 148 } 149 150 H = red.normalform(G, S); 151 if (H.isZERO()) { 152 pair.setZero(); 153 continue; 154 } 155 if (debug) { 156 logger.debug("ht(H) = " + H.leadingExpVector()); 157 } 158 H = engine.basePrimitivePart(H); //H.monic(); 159 H = H.abs(); 160 if (H.isConstant()) { 161 G.clear(); 162 G.add(H); 163 return G; // since no threads are activated 164 } 165 if (logger.isDebugEnabled()) { 166 logger.debug("H = " + H); 167 } 168 if (H.length() > 0) { 169 l++; 170 G.add(H); 171 pairlist.put(H); 172 } 173 } 174 logger.debug("#sequential list = " + G.size()); 175 G = minimalGB(G); 176 logger.info("" + pairlist); 177 return G; 178 } 179 180 181 /** 182 * Minimal ordered Groebner basis. 183 * @param Gp a Groebner base. 184 * @return a reduced Groebner base of Gp. 185 */ 186 @Override 187 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) { 188 if (Gp == null || Gp.size() <= 1) { 189 return Gp; 190 } 191 // remove zero polynomials 192 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size()); 193 for (GenPolynomial<C> a : Gp) { 194 if (a != null && !a.isZERO()) { // always true in GB() 195 // already positive a = a.abs(); 196 G.add(a); 197 } 198 } 199 if (G.size() <= 1) { 200 return G; 201 } 202 // remove top reducible polynomials 203 GenPolynomial<C> a; 204 List<GenPolynomial<C>> F; 205 F = new ArrayList<GenPolynomial<C>>(G.size()); 206 while (G.size() > 0) { 207 a = G.remove(0); 208 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 209 // drop polynomial 210 if (debug) { 211 System.out.println("dropped " + a); 212 List<GenPolynomial<C>> ff; 213 ff = new ArrayList<GenPolynomial<C>>(G); 214 ff.addAll(F); 215 a = red.normalform(ff, a); 216 if (!a.isZERO()) { 217 System.out.println("error, nf(a) " + a); 218 } 219 } 220 } else { 221 F.add(a); 222 } 223 } 224 G = F; 225 if (G.size() <= 1) { 226 return G; 227 } 228 Collections.reverse(G); // important for lex GB 229 // reduce remaining polynomials 230 int len = G.size(); 231 int i = 0; 232 while (i < len) { 233 a = G.remove(0); 234 //System.out.println("doing " + a.length()); 235 a = red.normalform(G, a); 236 a = engine.basePrimitivePart(a); //a.monic(); was not required 237 a = a.abs(); 238 //a = red.normalform( F, a ); 239 G.add(a); // adds as last 240 i++; 241 } 242 return G; 243 } 244 245}