001 /*
002 * $Id: SolvableReductionAbstract.java 3452 2010-12-27 12:48:08Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.Iterator;
009 import java.util.List;
010 import java.util.Map;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.poly.ExpVector;
015 import edu.jas.poly.GenSolvablePolynomial;
016
017 import edu.jas.structure.RingElem;
018
019
020 /**
021 * Solvable polynomial Reduction abstract class.
022 * Implements common left, right S-Polynomial, left normalform and
023 * left irreducible set.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028 public abstract class SolvableReductionAbstract<C extends RingElem<C>>
029 implements SolvableReduction<C> {
030
031 private static final Logger logger = Logger.getLogger(SolvableReductionAbstract.class);
032 private boolean debug = logger.isDebugEnabled();
033
034
035 /**
036 * Constructor.
037 */
038 public SolvableReductionAbstract() {
039 }
040
041
042 /**
043 * Left S-Polynomial.
044 * @param Ap solvable polynomial.
045 * @param Bp solvable polynomial.
046 * @return left-spol(Ap,Bp) the left S-polynomial of Ap and Bp.
047 */
048 public GenSolvablePolynomial<C>
049 leftSPolynomial(GenSolvablePolynomial<C> Ap,
050 GenSolvablePolynomial<C> Bp) {
051 if ( logger.isInfoEnabled() ) {
052 if ( Bp == null || Bp.isZERO() ) {
053 if ( Ap != null ) {
054 return Ap.ring.getZERO();
055 } else {
056 return null;
057 }
058 }
059 if ( Ap == null || Ap.isZERO() ) {
060 return Bp.ring.getZERO();
061 }
062 if ( ! Ap.ring.equals( Bp.ring ) ) {
063 logger.error("rings not equal");
064 }
065 }
066 Map.Entry<ExpVector,C> ma = Ap.leadingMonomial();
067 Map.Entry<ExpVector,C> mb = Bp.leadingMonomial();
068
069 ExpVector e = ma.getKey();
070 ExpVector f = mb.getKey();
071
072 ExpVector g = e.lcm(f);
073 ExpVector e1 = g.subtract(e);
074 ExpVector f1 = g.subtract(f);
075
076 C a = ma.getValue();
077 C b = mb.getValue();
078
079 GenSolvablePolynomial<C> App = Ap.multiplyLeft( b, e1 );
080 GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft( a, f1 );
081 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
082 return Cp;
083 }
084
085
086 /**
087 * S-Polynomial with recording.
088 * @param S recording matrix, is modified.
089 * @param i index of Ap in basis list.
090 * @param Ap a polynomial.
091 * @param j index of Bp in basis list.
092 * @param Bp a polynomial.
093 * @return leftSpol(Ap, Bp), the left S-Polynomial for Ap and Bp.
094 */
095 public GenSolvablePolynomial<C>
096 leftSPolynomial(List<GenSolvablePolynomial<C>> S,
097 int i,
098 GenSolvablePolynomial<C> Ap,
099 int j,
100 GenSolvablePolynomial<C> Bp) {
101 if ( debug /*logger.isInfoEnabled()*/ ) {
102 if ( Bp == null || Bp.isZERO() ) {
103 throw new ArithmeticException("Spol B is zero");
104 }
105 if ( Ap == null || Ap.isZERO() ) {
106 throw new ArithmeticException("Spol A is zero");
107 }
108 if ( ! Ap.ring.equals( Bp.ring ) ) {
109 logger.error("rings not equal");
110 }
111 }
112 Map.Entry<ExpVector,C> ma = Ap.leadingMonomial();
113 Map.Entry<ExpVector,C> mb = Bp.leadingMonomial();
114
115 ExpVector e = ma.getKey();
116 ExpVector f = mb.getKey();
117
118 ExpVector g = e.lcm(f);
119 ExpVector e1 = g.subtract(e);
120 ExpVector f1 = g.subtract(f);
121
122 C a = ma.getValue();
123 C b = mb.getValue();
124
125 GenSolvablePolynomial<C> App = Ap.multiplyLeft( b, e1 );
126 GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft( a, f1 );
127 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>)App.subtract(Bpp);
128
129 GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
130 GenSolvablePolynomial<C> As = (GenSolvablePolynomial<C>)zero.sum( b.negate(), e1 );
131 GenSolvablePolynomial<C> Bs = (GenSolvablePolynomial<C>)zero.sum( a, f1 );
132 S.set( i, As );
133 S.set( j, Bs );
134 return Cp;
135 }
136
137
138 /**
139 * Left Normalform Set.
140 * @param Ap solvable polynomial list.
141 * @param Pp solvable polynomial list.
142 * @return list of left-nf(a) with respect to Pp for all a in Ap.
143 */
144 public List<GenSolvablePolynomial<C>>
145 leftNormalform(List<GenSolvablePolynomial<C>> Pp,
146 List<GenSolvablePolynomial<C>> Ap) {
147 if ( Pp == null || Pp.isEmpty() ) {
148 return Ap;
149 }
150 if ( Ap == null || Ap.isEmpty() ) {
151 return Ap;
152 }
153 ArrayList<GenSolvablePolynomial<C>> red
154 = new ArrayList<GenSolvablePolynomial<C>>();
155 for ( GenSolvablePolynomial<C> A : Ap ) {
156 A = leftNormalform( Pp, A );
157 red.add( A );
158 }
159 return red;
160 }
161
162
163 /**
164 * Left irreducible set.
165 * @param Pp solvable polynomial list.
166 * @return a list P of solvable polynomials which are in normalform wrt. P.
167 */
168 public List<GenSolvablePolynomial<C>>
169 leftIrreducibleSet(List<GenSolvablePolynomial<C>> Pp) {
170 ArrayList<GenSolvablePolynomial<C>> P
171 = new ArrayList<GenSolvablePolynomial<C>>();
172 for ( GenSolvablePolynomial<C> a : Pp ) {
173 if ( a.length() != 0 ) {
174 a = (GenSolvablePolynomial<C>)a.monic();
175 P.add( a );
176 }
177 }
178 int l = P.size();
179 if ( l <= 1 ) return P;
180
181 int irr = 0;
182 ExpVector e;
183 ExpVector f;
184 GenSolvablePolynomial<C> a;
185 Iterator<GenSolvablePolynomial<C>> it;
186 logger.debug("irr = ");
187 while ( irr != l ) {
188 it = P.listIterator();
189 a = it.next();
190 P.remove(0);
191 e = a.leadingExpVector();
192 a = leftNormalform( P, a );
193 logger.debug(String.valueOf(irr));
194 if ( a.length() == 0 ) { l--;
195 if ( l <= 1 ) { return P; }
196 } else {
197 f = a.leadingExpVector();
198 if ( f .signum() == 0 ) {
199 P = new ArrayList<GenSolvablePolynomial<C>>();
200 P.add( (GenSolvablePolynomial<C>)a.monic() );
201 return P;
202 }
203 if ( e.equals( f ) ) {
204 irr++;
205 } else {
206 irr = 0; a = (GenSolvablePolynomial<C>)a.monic();
207 }
208 P.add( a );
209 }
210 }
211 //System.out.println();
212 return P;
213 }
214
215
216 /**
217 * Is reduction of normal form.
218 * @param row recording matrix.
219 * @param Pp a solvable polynomial list for reduction.
220 * @param Ap a solvable polynomial.
221 * @param Np nf(Pp,Ap), a left normal form of Ap wrt. Pp.
222 * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
223 */
224
225 public boolean
226 isLeftReductionNF(List<GenSolvablePolynomial<C>> row,
227 List<GenSolvablePolynomial<C>> Pp,
228 GenSolvablePolynomial<C> Ap,
229 GenSolvablePolynomial<C> Np) {
230 if ( row == null && Pp == null ) {
231 if ( Ap == null ) {
232 return Np == null;
233 }
234 return Ap.equals(Np);
235 }
236 if ( row == null && Pp != null ) {
237 return false;
238 }
239 if ( row != null && Pp == null ) {
240 return false;
241 }
242 if ( row.size() != Pp.size() ) {
243 return false;
244 }
245 GenSolvablePolynomial<C> t = Np;
246 GenSolvablePolynomial<C> r;
247 GenSolvablePolynomial<C> p;
248 for ( int m = 0; m < Pp.size(); m++ ) {
249 r = row.get(m);
250 p = Pp.get(m);
251 if ( r != null && p != null ) {
252 if ( t == null ) {
253 t = r.multiply(p);
254 } else {
255 t = (GenSolvablePolynomial<C>)t.sum( r.multiply(p) );
256 }
257 }
258 //System.out.println("r = " + r );
259 //System.out.println("p = " + p );
260 }
261 if ( debug ) {
262 logger.info("t = " + t );
263 logger.info("a = " + Ap );
264 }
265 if ( t == null ) {
266 if ( Ap == null ) {
267 return true;
268 } else {
269 return Ap.isZERO();
270 }
271 } else {
272 t = (GenSolvablePolynomial<C>)t.subtract( Ap );
273 return t.isZERO();
274 }
275 }
276
277
278 /**
279 * Right S-Polynomial.
280 * @param Ap solvable polynomial.
281 * @param Bp solvable polynomial.
282 * @return right-spol(Ap,Bp) the right S-polynomial of Ap and Bp.
283 */
284 public GenSolvablePolynomial<C>
285 rightSPolynomial(GenSolvablePolynomial<C> Ap,
286 GenSolvablePolynomial<C> Bp) {
287 if ( logger.isInfoEnabled() ) {
288 if ( Bp == null || Bp.isZERO() ) {
289 if ( Ap != null ) {
290 return Ap.ring.getZERO();
291 } else {
292 return null;
293 }
294 }
295 if ( Ap == null || Ap.isZERO() ) {
296 return Bp.ring.getZERO();
297 }
298 if ( ! Ap.ring.equals( Bp.ring ) ) {
299 logger.error("rings not equal");
300 }
301 }
302 ExpVector e = Ap.leadingExpVector();
303 ExpVector f = Bp.leadingExpVector();
304
305 ExpVector g = e.lcm(f);
306 ExpVector e1 = g.subtract(e);
307 ExpVector f1 = g.subtract(f);
308
309 GenSolvablePolynomial<C> App = Ap.multiply( e1 );
310 GenSolvablePolynomial<C> Bpp = Bp.multiply( f1 );
311
312 C a = App.leadingBaseCoefficient();
313 C b = Bpp.leadingBaseCoefficient();
314 App = App.multiply( b );
315 Bpp = Bpp.multiply( a );
316
317 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
318 return Cp;
319 }
320
321 }