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