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