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