001/* 002 * $Id: StandardBaseSeq.java 5280 2015-07-30 16:18:15Z kredel $ 003 */ 004 005package edu.jas.ps; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.poly.ExpVector; 014import edu.jas.structure.RingElem; 015 016 017/** 018 * Standard Base sequential algorithm. Implements Standard bases and GB test. 019 * <b>Note: </b> Currently the term order is fixed to the order defined by the 020 * iterator over exponent vectors <code>ExpVectorIterator</code>. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class StandardBaseSeq<C extends RingElem<C>> 026/*todo: extends StandardBaseAbstract<C>*/{ 027 028 029 private static final Logger logger = Logger.getLogger(StandardBaseSeq.class); 030 031 032 private final boolean debug = logger.isDebugEnabled(); 033 034 035 /** 036 * Reduction engine. 037 */ 038 public final ReductionSeq<C> red; 039 040 041 /** 042 * Constructor. 043 */ 044 public StandardBaseSeq() { 045 //super(); 046 this(new ReductionSeq<C>()); 047 } 048 049 050 /** 051 * Constructor. 052 * @param red Reduction engine 053 */ 054 public StandardBaseSeq(ReductionSeq<C> red) { 055 this.red = red; //super(red); 056 } 057 058 059 /** 060 * Normalize power series list. 061 * @param A list of power series. 062 * @return list of power series with zeros removed and ones/units reduced. 063 */ 064 public List<MultiVarPowerSeries<C>> normalizeZerosOnes(List<MultiVarPowerSeries<C>> A) { 065 if (A == null) { 066 return A; 067 } 068 List<MultiVarPowerSeries<C>> N = new ArrayList<MultiVarPowerSeries<C>>(A.size()); 069 if (A.isEmpty()) { 070 return N; 071 } 072 for (MultiVarPowerSeries<C> p : A) { 073 if (p == null || p.isZERO()) { 074 continue; 075 } 076 if (p.isUnit()) { 077 N.clear(); 078 N.add(p.ring.getONE()); 079 return N; 080 } 081 N.add(p.abs()); 082 } 083 //N.trimToSize(); 084 return N; 085 } 086 087 088 /** 089 * Standard base test. 090 * @param F power series list. 091 * @return true, if F is a Standard base, else false. 092 */ 093 public boolean isSTD(List<MultiVarPowerSeries<C>> F) { 094 return isSTD(0, F); 095 } 096 097 098 /** 099 * Standard base test. 100 * @param modv module variable number. 101 * @param F power series list. 102 * @return true, if F is a Standard base, else false. 103 */ 104 public boolean isSTD(int modv, List<MultiVarPowerSeries<C>> F) { 105 if (F == null) { 106 return true; 107 } 108 MultiVarPowerSeries<C> pi, pj, s, h; 109 for (int i = 0; i < F.size(); i++) { 110 pi = F.get(i); 111 for (int j = i + 1; j < F.size(); j++) { 112 pj = F.get(j); 113 if (!red.moduleCriterion(modv, pi, pj)) { 114 continue; 115 } 116 // if ( ! red.criterion4( pi, pj ) ) { 117 // continue; 118 // } 119 s = red.SPolynomial(pi, pj); 120 if (s.isZERO()) { 121 continue; 122 } 123 h = red.normalform(F, s); 124 if (!h.isZERO()) { 125 System.out.println("pi = " + pi + ", pj = " + pj); 126 System.out.println("s = " + s + ", h = " + h); 127 return false; 128 } 129 } 130 } 131 return true; 132 } 133 134 135 /** 136 * Standard base using pairlist class. 137 * @param F power series list. 138 * @return STD(F) a Standard base of F. 139 */ 140 public List<MultiVarPowerSeries<C>> STD(List<MultiVarPowerSeries<C>> F) { 141 return STD(0, F); 142 } 143 144 145 /** 146 * Standard base using pairlist class. 147 * @param modv module variable number. 148 * @param F power series list. 149 * @return STD(F) a Standard base of F. 150 */ 151 public List<MultiVarPowerSeries<C>> STD(int modv, List<MultiVarPowerSeries<C>> F) { 152 List<MultiVarPowerSeries<C>> G = normalizeZerosOnes(F); 153 G = PSUtil.<C> monic(G); 154 if (G.size() <= 1) { 155 return G; 156 } 157 MultiVarPowerSeriesRing<C> ring = G.get(0).ring; 158 if (!ring.coFac.isField()) { 159 throw new IllegalArgumentException("coefficients not from a field"); 160 } 161 OrderedPairlist<C> pairlist = new OrderedPairlist<C>(modv, ring); //strategy.create( modv, ring ); 162 pairlist.put(G); 163 164 /* 165 MultiVarPowerSeries<C> p = null; 166 List<MultiVarPowerSeries<C>> G = new ArrayList<MultiVarPowerSeries<C>>(); 167 OrderedPairlist<C> pairlist = null; 168 int l = F.size(); 169 ListIterator<MultiVarPowerSeries<C>> it = F.listIterator(); 170 while (it.hasNext()) { 171 p = it.next(); 172 if (!p.isZERO()) { 173 //p = p.monic(); 174 if (p.isUnit()) { 175 G.clear(); 176 G.add(p); 177 return G; // since no threads are activated 178 } 179 G.add(p); 180 if (pairlist == null) { 181 pairlist = new OrderedPairlist<C>(modv, p.ring); 182 if (!p.ring.coFac.isField()) { 183 throw new IllegalArgumentException("coefficients not from a field"); 184 } 185 } 186 // putOne not required 187 pairlist.put(p); 188 } else { 189 l--; 190 } 191 } 192 if (l <= 1) { 193 return G; // since no threads are activated 194 } 195 */ 196 logger.info("start " + pairlist); 197 198 Pair<C> pair; 199 MultiVarPowerSeries<C> pi, pj, S, H; 200 while (pairlist.hasNext()) { 201 pair = pairlist.removeNext(); 202 //logger.debug("pair = " + pair); 203 if (pair == null) { 204 continue; 205 } 206 pi = pair.pi; 207 pj = pair.pj; 208 if ( /*false &&*/debug) { 209 logger.debug("pi = " + pi); 210 logger.debug("pj = " + pj); 211 } 212 213 S = red.SPolynomial(pi, pj); 214 //S.setTruncate(p.ring.truncate()); // ?? 215 if (S.isZERO()) { 216 pair.setZero(); 217 continue; 218 } 219 if (logger.isInfoEnabled()) { 220 ExpVector es = S.orderExpVector(); 221 logger.info("ht(S) = " + es.toString(S.ring.vars) + ", " + es); // + ", S = " + S); 222 } 223 224 //long t = System.currentTimeMillis(); 225 H = red.normalform(G, S); 226 if (H.isZERO()) { 227 pair.setZero(); 228 continue; 229 } 230 //t = System.currentTimeMillis() - t; 231 //System.out.println("time = " + t); 232 if (logger.isInfoEnabled()) { 233 ExpVector eh = H.orderExpVector(); 234 logger.info("ht(H) = " + eh.toString(S.ring.vars) + ", " + eh); // + ", coeff(HT(H)) = " + H.coefficient(eh)); 235 } 236 237 //H = H.monic(); 238 if (H.isUnit()) { 239 G.clear(); 240 G.add(H); 241 return G; // since no threads are activated 242 } 243 if (logger.isDebugEnabled()) { 244 logger.info("H = " + H); 245 } 246 //if (!H.isZERO()) { 247 //l++; 248 G.add(H); 249 pairlist.put(H); 250 //} 251 } 252 logger.debug("#sequential list = " + G.size()); 253 G = minimalSTD(G); 254 logger.info("" + pairlist); 255 return G; 256 } 257 258 259 /** 260 * Minimal ordered Standard basis. 261 * @param Gp a Standard base. 262 * @return a minimal Standard base of Gp, not auto reduced. 263 */ 264 public List<MultiVarPowerSeries<C>> minimalSTD(List<MultiVarPowerSeries<C>> Gp) { 265 if (Gp == null || Gp.size() <= 1) { 266 return Gp; 267 } 268 // remove zero power series 269 List<MultiVarPowerSeries<C>> G = new ArrayList<MultiVarPowerSeries<C>>(Gp.size()); 270 for (MultiVarPowerSeries<C> a : Gp) { 271 if (a != null && !a.isZERO()) { // always true in GB() 272 // make positive a = a.abs(); ? 273 a = a.monic(); 274 G.add(a); 275 } 276 } 277 if (G.size() <= 1) { 278 return G; 279 } 280 // remove top reducible power series 281 MultiVarPowerSeries<C> a; 282 List<MultiVarPowerSeries<C>> F = new ArrayList<MultiVarPowerSeries<C>>(G.size()); 283 while (G.size() > 0) { 284 a = G.remove(0); 285 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 286 // drop power series 287 if (debug) { 288 System.out.println("dropped " + a); 289 List<MultiVarPowerSeries<C>> ff = new ArrayList<MultiVarPowerSeries<C>>(G); 290 ff.addAll(F); 291 a = red.normalform(ff, a); 292 if (!a.isZERO()) { 293 System.out.println("error, nf(a) " + a); 294 } 295 } 296 } else { 297 F.add(a); 298 } 299 } 300 G = F; 301 // power series not reduced 302 return G; 303 } 304 305}