Source code

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