Source code

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