001/* 002 * $Id: GroebnerBaseSeqIter.java 5364 2015-12-26 12:36:37Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010// import java.util.Collections; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.poly.GenPolynomial; 015import edu.jas.poly.GenPolynomialRing; 016import edu.jas.poly.OrderedPolynomialList; 017import edu.jas.poly.PolyUtil; 018import edu.jas.structure.RingElem; 019 020 021/** 022 * Groebner Base sequential iterative algorithm. Implements Groebner bases and 023 * GB test. 024 * @param <C> coefficient type 025 * @author Heinz Kredel 026 * 027 * @see edu.jas.application.GBAlgorithmBuilder 028 * @see edu.jas.gbufd.GBFactory 029 */ 030 031public class GroebnerBaseSeqIter<C extends RingElem<C>> extends GroebnerBaseAbstract<C> { 032 033 034 private static final Logger logger = Logger.getLogger(GroebnerBaseSeqIter.class); 035 036 037 private final boolean debug = logger.isDebugEnabled(); 038 039 040 /** 041 * Constructor. 042 */ 043 public GroebnerBaseSeqIter() { 044 super(); 045 } 046 047 048 /** 049 * Constructor. 050 * @param red Reduction engine 051 */ 052 public GroebnerBaseSeqIter(Reduction<C> red) { 053 super(red); 054 } 055 056 057 /** 058 * Constructor. 059 * @param pl pair selection strategy 060 */ 061 public GroebnerBaseSeqIter(PairList<C> pl) { 062 super(pl); 063 } 064 065 066 /** 067 * Constructor. 068 * @param red Reduction engine 069 * @param pl pair selection strategy 070 */ 071 public GroebnerBaseSeqIter(Reduction<C> red, PairList<C> pl) { 072 super(red, pl); 073 } 074 075 076 /** 077 * Groebner base using pairlist class, iterative algorithm. 078 * @param modv module variable number. 079 * @param F polynomial list. 080 * @return GB(F) a Groebner base of F. 081 */ 082 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 083 List<GenPolynomial<C>> G = normalizeZerosOnes(F); 084 G = PolyUtil.<C> monic(G); 085 if (G.size() <= 1) { 086 return G; 087 } 088 // sort, no reverse 089 G = OrderedPolynomialList.<C> sort(G); 090 //no: Collections.reverse(G); 091 logger.info("G-sort = " + G); 092 List<GenPolynomial<C>> Gp = new ArrayList<GenPolynomial<C>>(); 093 for (GenPolynomial<C> p : G) { 094 if (debug) { 095 logger.info("p = " + p); 096 } 097 Gp = GB(modv, Gp, p); 098 //System.out.println("GB(Gp+p) = " + Gp); 099 if (Gp.size() > 0) { 100 if (Gp.get(0).isONE()) { 101 return Gp; 102 } 103 } 104 } 105 return Gp; 106 } 107 108 109 /** 110 * Groebner base using pairlist class. 111 * @param modv module variable number. 112 * @param G polynomial list of a Groebner base. 113 * @param f polynomial. 114 * @return GB(G,f) a Groebner base of G+(f). 115 */ 116 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> G, GenPolynomial<C> f) { 117 List<GenPolynomial<C>> F = new ArrayList<GenPolynomial<C>>(G); 118 GenPolynomial<C> g = f.monic(); 119 if (F.isEmpty()) { 120 F.add(g); 121 return F; 122 } 123 if (g.isZERO()) { 124 return F; 125 } 126 if (g.isONE()) { 127 F.clear(); 128 F.add(g); 129 return F; 130 } 131 GenPolynomialRing<C> ring = F.get(0).ring; 132 if (!ring.coFac.isField()) { 133 throw new IllegalArgumentException("coefficients not from a field"); 134 } 135 G = F; 136 PairList<C> pairlist = strategy.create(modv, ring); 137 pairlist.setList(G); 138 G.add(g); 139 pairlist.put(g); 140 logger.info("start " + pairlist); 141 142 Pair<C> pair; 143 GenPolynomial<C> pi, pj, S, H; 144 while (pairlist.hasNext()) { 145 pair = pairlist.removeNext(); 146 //logger.debug("pair = " + pair); 147 if (pair == null) { 148 continue; 149 } 150 pi = pair.pi; 151 pj = pair.pj; 152 if ( /*false &&*/debug) { 153 logger.debug("pi = " + pi); 154 logger.debug("pj = " + pj); 155 } 156 157 S = red.SPolynomial(pi, pj); 158 if (S.isZERO()) { 159 pair.setZero(); 160 continue; 161 } 162 if (debug) { 163 logger.debug("ht(S) = " + S.leadingExpVector()); 164 } 165 166 H = red.normalform(G, S); 167 if (debug) { 168 //logger.info("pair = " + pair); 169 //logger.info("ht(S) = " + S.monic()); //.leadingExpVector() ); 170 logger.info("ht(H) = " + H.monic()); //.leadingExpVector() ); 171 } 172 if (H.isZERO()) { 173 pair.setZero(); 174 continue; 175 } 176 H = H.monic(); 177 if (debug) { 178 logger.info("ht(H) = " + H.leadingExpVector()); 179 } 180 181 H = H.monic(); 182 if (H.isONE()) { 183 G.clear(); 184 G.add(H); 185 pairlist.putOne(); 186 logger.info("end " + pairlist); 187 return G; // since no threads are activated 188 } 189 if (debug) { 190 logger.info("H = " + H); 191 } 192 if (H.length() > 0) { 193 //l++; 194 G.add(H); 195 pairlist.put(H); 196 } 197 } 198 logger.debug("#sequential list = " + G.size()); 199 G = minimalGB(G); 200 logger.info("end " + pairlist); 201 return G; 202 } 203 204}