001/* 002 * $Id: DGroebnerBaseSeq.java 4099 2012-08-12 18:49:36Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.ListIterator; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.poly.GenPolynomial; 015import edu.jas.structure.RingElem; 016 017 018/** 019 * D-Groebner Base sequential algorithm. Implements D-Groebner bases and GB 020 * test. <b>Note:</b> Minimal reduced GBs are not unique. see BWK, section 10.1. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class DGroebnerBaseSeq<C extends RingElem<C>> extends GroebnerBaseAbstract<C> { 026 027 028 private static final Logger logger = Logger.getLogger(DGroebnerBaseSeq.class); 029 030 031 private final boolean debug = logger.isDebugEnabled(); 032 033 034 /** 035 * Reduction engine. 036 */ 037 protected DReduction<C> dred; // shadow super.red ?? 038 039 040 /** 041 * Constructor. 042 */ 043 public DGroebnerBaseSeq() { 044 this(new DReductionSeq<C>()); 045 } 046 047 048 /** 049 * Constructor. 050 * @param dred D-Reduction engine 051 */ 052 public DGroebnerBaseSeq(DReduction<C> dred) { 053 super(dred); 054 this.dred = dred; 055 assert this.dred == super.red; 056 } 057 058 059 /** 060 * D-Groebner base test. 061 * @param modv module variable number. 062 * @param F polynomial list. 063 * @return true, if F is a D-Groebner base, else false. 064 */ 065 @Override 066 public boolean isGB(int modv, List<GenPolynomial<C>> F) { 067 GenPolynomial<C> pi, pj, s, d; 068 for (int i = 0; i < F.size(); i++) { 069 pi = F.get(i); 070 for (int j = i + 1; j < F.size(); j++) { 071 pj = F.get(j); 072 if (!red.moduleCriterion(modv, pi, pj)) { 073 continue; 074 } 075 d = dred.GPolynomial(pi, pj); 076 if (!d.isZERO()) { 077 // better check for top reduction only 078 d = red.normalform(F, d); 079 } 080 if (!d.isZERO()) { 081 System.out.println("d-pol(" + i + "," + j + ") != 0: " + d); 082 return false; 083 } 084 // works ok 085 if (!red.criterion4(pi, pj)) { 086 continue; 087 } 088 s = red.SPolynomial(pi, pj); 089 if (!s.isZERO()) { 090 s = red.normalform(F, s); 091 } 092 if (!s.isZERO()) { 093 System.out.println("s-pol(" + i + "," + j + ") != 0: " + s); 094 return false; 095 } 096 } 097 } 098 return true; 099 } 100 101 102 /** 103 * D-Groebner base using pairlist class. 104 * @param modv module variable number. 105 * @param F polynomial list. 106 * @return GB(F) a D-Groebner base of F. 107 */ 108 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 109 GenPolynomial<C> p; 110 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 111 OrderedDPairlist<C> pairlist = null; 112 int l = F.size(); 113 ListIterator<GenPolynomial<C>> it = F.listIterator(); 114 while (it.hasNext()) { 115 p = it.next(); 116 if (!p.isZERO()) { 117 p = p.abs(); // not monic 118 if (p.isONE()) { 119 G.clear(); 120 G.add(p); 121 return G; // since no threads are activated 122 } 123 G.add(p); //G.add( 0, p ); //reverse list 124 if (pairlist == null) { 125 pairlist = new OrderedDPairlist<C>(modv, p.ring); 126 } 127 // putOne not required 128 pairlist.put(p); 129 } else { 130 l--; 131 } 132 } 133 if (l <= 1) { 134 return G; // since no threads are activated 135 } 136 137 Pair<C> pair; 138 GenPolynomial<C> pi; 139 GenPolynomial<C> pj; 140 GenPolynomial<C> S; 141 GenPolynomial<C> D; 142 GenPolynomial<C> H; 143 //int len = G.size(); 144 //System.out.println("len = " + len); 145 while (pairlist.hasNext()) { 146 pair = pairlist.removeNext(); 147 //System.out.println("pair = " + pair); 148 if (pair == null) 149 continue; 150 151 pi = pair.pi; 152 pj = pair.pj; 153 if (debug) { 154 logger.debug("pi = " + pi); 155 logger.debug("pj = " + pj); 156 } 157 158 // D-polynomial case ---------------------- 159 D = dred.GPolynomial(pi, pj); 160 //System.out.println("D_d = " + D); 161 if (!D.isZERO() && !red.isTopReducible(G, D)) { 162 H = red.normalform(G, D); 163 if (H.isONE()) { 164 G.clear(); 165 G.add(H); 166 return G; // since no threads are activated 167 } 168 if (!H.isZERO()) { 169 logger.info("Dred = " + H); 170 l++; 171 G.add(H); 172 pairlist.put(H); 173 } 174 } 175 176 // S-polynomial case ----------------------- 177 if (pair.getUseCriterion3() && pair.getUseCriterion4()) { 178 S = red.SPolynomial(pi, pj); 179 //System.out.println("S_d = " + S); 180 if (S.isZERO()) { 181 pair.setZero(); 182 continue; 183 } 184 if (logger.isDebugEnabled()) { 185 logger.debug("ht(S) = " + S.leadingExpVector()); 186 } 187 188 H = red.normalform(G, S); 189 if (H.isZERO()) { 190 pair.setZero(); 191 continue; 192 } 193 if (logger.isDebugEnabled()) { 194 logger.debug("ht(H) = " + H.leadingExpVector()); 195 } 196 197 if (H.isONE()) { 198 G.clear(); 199 G.add(H); 200 return G; // since no threads are activated 201 } 202 if (logger.isDebugEnabled()) { 203 logger.debug("H = " + H); 204 } 205 if (!H.isZERO()) { 206 logger.info("Sred = " + H); 207 //len = G.size(); 208 l++; 209 G.add(H); 210 pairlist.put(H); 211 } 212 } 213 } 214 logger.debug("#sequential list = " + G.size()); 215 G = minimalGB(G); 216 logger.info("" + pairlist); 217 return G; 218 } 219 220}