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