Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011
012import org.apache.logging.log4j.LogManager;
013import org.apache.logging.log4j.Logger;
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * Polynomial D-Reduction sequential use algorithm. Implements normalform.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028public class DReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements DReduction<C> {
029
030
031    private static final Logger logger = LogManager.getLogger(DReductionSeq.class);
032
033
034    //private static final boolean debug = logger.isDebugEnabled();
035
036
037    /**
038     * Constructor.
039     */
040    public DReductionSeq() {
041    }
042
043
044    /**
045     * Is top reducible.
046     * @param A polynomial.
047     * @param P polynomial list.
048     * @return true if A is top reducible with respect to P.
049     */
050    @Override
051    public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
052        if (P == null || P.isEmpty()) {
053            return false;
054        }
055        if (A == null || A.isZERO()) {
056            return false;
057        }
058        boolean mt = false;
059        ExpVector e = A.leadingExpVector();
060        C a = A.leadingBaseCoefficient();
061        for (GenPolynomial<C> p : P) {
062            mt = e.multipleOf(p.leadingExpVector());
063            if (mt) {
064                C b = p.leadingBaseCoefficient();
065                C r = a.remainder(b);
066                mt = r.isZERO();
067                if (mt) {
068                    return true;
069                }
070            }
071        }
072        return false;
073    }
074
075
076    /**
077     * Is in Normalform.
078     * @param Ap polynomial.
079     * @param Pp polynomial list.
080     * @return true if Ap is in normalform with respect to Pp.
081     */
082    @SuppressWarnings("unchecked")
083    @Override
084    public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
085        if (Pp == null || Pp.isEmpty()) {
086            return true;
087        }
088        if (Ap == null || Ap.isZERO()) {
089            return true;
090        }
091        int l;
092        GenPolynomial<C>[] P;
093        synchronized (Pp) {
094            l = Pp.size();
095            P = new GenPolynomial[l];
096            //P = Pp.toArray();
097            for (int i = 0; i < Pp.size(); i++) {
098                P[i] = Pp.get(i);
099            }
100        }
101        ExpVector[] htl = new ExpVector[l];
102        C[] lbc = (C[]) new RingElem[l]; // want <C>
103        GenPolynomial<C>[] p = new GenPolynomial[l];
104        Map.Entry<ExpVector, C> m;
105        int i;
106        int j = 0;
107        for (i = 0; i < l; i++) {
108            p[i] = P[i];
109            m = p[i].leadingMonomial();
110            if (m != null) {
111                p[j] = p[i];
112                htl[j] = m.getKey();
113                lbc[j] = m.getValue();
114                j++;
115            }
116        }
117        l = j;
118        boolean mt = false;
119        Map<ExpVector, C> Am = Ap.getMap();
120        for (Map.Entry<ExpVector, C> me : Am.entrySet()) {
121            ExpVector e = me.getKey();
122            C a = me.getValue(); //Am.get(e);
123            for (i = 0; i < l; i++) {
124                mt = e.multipleOf(htl[i]);
125                if (mt) {
126                    C r = a.remainder(lbc[i]);
127                    mt = r.isZERO();
128                    if (mt) {
129                        return false;
130                    }
131                }
132            }
133        }
134        return true;
135    }
136
137
138    /**
139     * Normalform using d-reduction.
140     * @param Ap polynomial.
141     * @param Pp polynomial list.
142     * @return d-nf(Ap) with respect to Pp.
143     */
144    @SuppressWarnings("unchecked")
145    @Override
146    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
147        if (Pp == null || Pp.isEmpty()) {
148            return Ap;
149        }
150        if (Ap == null || Ap.isZERO()) {
151            return Ap;
152        }
153        int l;
154        GenPolynomial<C>[] P;
155        synchronized (Pp) {
156            l = Pp.size();
157            P = (GenPolynomial<C>[]) new GenPolynomial[l];
158            //P = Pp.toArray();
159            for (int i = 0; i < Pp.size(); i++) {
160                P[i] = Pp.get(i); //.abs();
161            }
162        }
163        //System.out.println("l = " + l);
164        Map.Entry<ExpVector, C> m;
165        ExpVector[] htl = new ExpVector[l];
166        C[] lbc = (C[]) new RingElem[l]; // want <C>
167        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
168        int i;
169        int j = 0;
170        for (i = 0; i < l; i++) {
171            p[i] = P[i];
172            m = p[i].leadingMonomial();
173            if (m != null) {
174                p[j] = p[i];
175                htl[j] = m.getKey();
176                lbc[j] = m.getValue();
177                j++;
178            }
179        }
180        l = j;
181        ExpVector e;
182        C a;
183        C r = null;
184        boolean mt = false;
185        GenPolynomial<C> R = Ap.ring.getZERO();
186        GenPolynomial<C> Q = null;
187        GenPolynomial<C> S = Ap;
188        while (S.length() > 0) {
189            m = S.leadingMonomial();
190            e = m.getKey();
191            a = m.getValue();
192            for (i = 0; i < l; i++) {
193                mt = e.multipleOf(htl[i]);
194                if (mt) {
195                    r = a.remainder(lbc[i]);
196                    mt = r.isZERO(); // && mt
197                }
198                if (mt)
199                    break;
200            }
201            if (!mt) {
202                //logger.debug("irred");
203                R = R.sum(a, e);
204                //S = S.subtract( a, e ); 
205                S = S.reductum();
206                //System.out.println(" S = " + S);
207            } else {
208                //logger.info("red div = {}", e);
209                ExpVector f = e.subtract(htl[i]);
210                C b = a.divide(lbc[i]);
211                // r == 0: R = R.sum(r, e);
212                Q = p[i].multiply(b, f);
213                S = S.reductum().subtract(Q.reductum()); // ok also with reductum
214            }
215        }
216        return R.abs(); // ok with d-reduction
217    }
218
219
220    /**
221     * S-Polynomial.
222     * @param Ap polynomial.
223     * @param Bp polynomial.
224     * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
225     */
226    @Override
227    public GenPolynomial<C> SPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
228        if (logger.isInfoEnabled()) {
229            if (Bp == null || Bp.isZERO()) {
230                return Ap.ring.getZERO();
231            }
232            if (Ap == null || Ap.isZERO()) {
233                return Bp.ring.getZERO();
234            }
235            if (!Ap.ring.equals(Bp.ring)) {
236                logger.error("rings not equal");
237            }
238        }
239        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
240        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
241
242        ExpVector e = ma.getKey();
243        ExpVector f = mb.getKey();
244
245        ExpVector g = e.lcm(f);
246        ExpVector e1 = g.subtract(e);
247        ExpVector f1 = g.subtract(f);
248
249        C a = ma.getValue();
250        C b = mb.getValue();
251
252        //c = lcm(a,b)
253        C c = a.gcd(b);
254        C m = a.multiply(b);
255        C l = m.divide(c);
256        C a1 = l.divide(a);
257        C b1 = l.divide(b);
258
259        //Cp = a1 e1 * A - b1 f1 * B
260        GenPolynomial<C> Cp = Ap.scaleSubtractMultiple(a1, e1, b1, f1, Bp);
261        return Cp;
262    }
263
264
265    /**
266     * G-Polynomial.
267     * @param Ap polynomial.
268     * @param Bp polynomial.
269     * @return gpol(Ap,Bp) the g-polynomial of Ap and Bp.
270     */
271    @Override
272    public GenPolynomial<C> GPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
273        if (logger.isInfoEnabled()) {
274            if (Bp == null || Bp.isZERO()) {
275                return Ap.ring.getZERO();
276            }
277            if (Ap == null || Ap.isZERO()) {
278                return Bp.ring.getZERO();
279            }
280            if (!Ap.ring.equals(Bp.ring)) {
281                logger.error("rings not equal");
282            }
283        }
284        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
285        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
286
287        ExpVector e = ma.getKey();
288        ExpVector f = mb.getKey();
289
290        ExpVector g = e.lcm(f);
291        ExpVector e1 = g.subtract(e);
292        ExpVector f1 = g.subtract(f);
293
294        C a = ma.getValue();
295        C b = mb.getValue();
296
297        C[] c = a.egcd(b); // c[0] = c[1] a + c[2] b
298        //System.out.println("egcd[0] " + c[0]);
299        //Cp = c[1] e1 * A + c[2] f1 * B = c[1] e1 * A - (-c[2]) f1 * B
300        GenPolynomial<C> Cp = Ap.scaleSubtractMultiple(c[1], e1, c[2].negate(), f1, Bp);
301        return Cp; // .negate() -
302    }
303
304
305    /**
306     * S-Polynomial with recording.
307     * @param row recording vector, is modified.
308     * @param i index of Ap in basis list.
309     * @param Ap a polynomial.
310     * @param j index of Bp in basis list.
311     * @param Bp a polynomial.
312     * @return spol(Ap, Bp), the s-Polynomial for Ap and Bp.
313     */
314    @Override
315    public GenPolynomial<C> SPolynomial(List<GenPolynomial<C>> row, int i, GenPolynomial<C> Ap, int j,
316                    GenPolynomial<C> Bp) {
317        if (logger.isInfoEnabled()) {
318            if (Bp == null || Bp.isZERO()) {
319                return Ap.ring.getZERO();
320            }
321            if (Ap == null || Ap.isZERO()) {
322                return Bp.ring.getZERO();
323            }
324            if (!Ap.ring.equals(Bp.ring)) {
325                logger.error("rings not equal");
326            }
327            //if ((row.get(i) != null && !row.get(i).isZERO()) || (row.get(j) != null && !row.get(j).isZERO())) {
328            //    throw new IllegalArgumentException("row(i), row(j): " + row.get(i) + ", " + row.get(j));
329            //}
330        }
331        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
332        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
333
334        ExpVector e = ma.getKey();
335        ExpVector f = mb.getKey();
336
337        ExpVector g = e.lcm(f);
338        ExpVector e1 = g.subtract(e);
339        ExpVector f1 = g.subtract(f);
340
341        C a = ma.getValue();
342        C b = mb.getValue();
343
344        //c = lcm(a,b)
345        C c = a.gcd(b);
346        C m = a.multiply(b);
347        C l = m.divide(c);
348        C a1 = l.divide(a);
349        C b1 = l.divide(b);
350        //Cp = a1 e1 * A - b1 f1 * B
351        GenPolynomial<C> Cp = Ap.scaleSubtractMultiple(a1, e1, b1, f1, Bp);
352
353        GenPolynomial<C> zero = Ap.ring.getZERO();
354        GenPolynomial<C> As = zero.sum(a1, e1); /*not correct .negate()*/
355        GenPolynomial<C> Bs = zero.sum(b1.negate(), f1); /*correct */
356        row.set(i, As);
357        row.set(j, Bs);
358        return Cp;
359    }
360
361
362    /**
363     * G-Polynomial with recording.
364     * @param row recording matrix, is modified.
365     * @param i index of Ap in basis list.
366     * @param Ap a polynomial.
367     * @param j index of Bp in basis list.
368     * @param Bp a polynomial.
369     * @return gpol(Ap, Bp), the g-Polynomial for Ap and Bp.
370     */
371    @Override
372    public GenPolynomial<C> GPolynomial(List<GenPolynomial<C>> row, int i, GenPolynomial<C> Ap, int j,
373                    GenPolynomial<C> Bp) {
374        if (logger.isInfoEnabled()) {
375            if (Bp == null || Bp.isZERO()) {
376                return Ap.ring.getZERO();
377            }
378            if (Ap == null || Ap.isZERO()) {
379                return Bp.ring.getZERO();
380            }
381            if (!Ap.ring.equals(Bp.ring)) {
382                logger.error("rings not equal");
383            }
384            //if ((row.get(i) != null && !row.get(i).isZERO()) || (row.get(j) != null && !row.get(j).isZERO())) {
385            //    throw new IllegalArgumentException("row(i), row(j): " + row.get(i) + ", " + row.get(j));
386            //}
387        }
388        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
389        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
390
391        ExpVector e = ma.getKey();
392        ExpVector f = mb.getKey();
393
394        ExpVector g = e.lcm(f);
395        ExpVector e1 = g.subtract(e);
396        ExpVector f1 = g.subtract(f);
397
398        C a = ma.getValue();
399        C b = mb.getValue();
400
401        C[] c = a.egcd(b); // c[0] = c[1] a + c[2] b
402        //System.out.println("egcd[0] " + c[0]);
403        //Cp = c[1] e1 * A + c[2] f1 * B = c[1] e1 * A - (-c[2]) f1 * B
404        GenPolynomial<C> Cp = Ap.scaleSubtractMultiple(c[1], e1, c[2].negate(), f1, Bp);
405
406        GenPolynomial<C> zero = Ap.ring.getZERO();
407        GenPolynomial<C> As = zero.sum(c[1], e1); // .negate() -
408        GenPolynomial<C> Bs = zero.sum(c[2], f1); // .negate() -
409        row.set(i, As);
410        row.set(j, Bs);
411        return Cp; // .negate() -
412    }
413
414
415    /**
416     * GB criterium 4. Use only for commutative polynomial rings. This version
417     * works also for d-Groebner bases.
418     * @param A polynomial.
419     * @param B polynomial.
420     * @param e = lcm(ht(A),ht(B))
421     * @return true if the S-polynomial(i,j) is required, else false.
422     */
423    @Override
424    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e) {
425        if (logger.isInfoEnabled()) {
426            if (!A.ring.equals(B.ring)) {
427                logger.error("rings equal");
428            }
429            if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
430                logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
431                return true;
432            }
433        }
434        ExpVector ei = A.leadingExpVector();
435        ExpVector ej = B.leadingExpVector();
436        ExpVector g = ei.sum(ej);
437        // boolean t =  g == e ;
438        ExpVector h = g.subtract(e);
439        int s = h.signum();
440        if (s == 0) { // disjoint ht
441            C a = A.leadingBaseCoefficient();
442            C b = B.leadingBaseCoefficient();
443            C d = a.gcd(b);
444            if (d.isONE()) { // disjoint hc
445                //System.out.println("d1 = " + d + ", a = " + a + ", b = " + b);
446                return false; // can skip pair
447            }
448        }
449        return true; //! ( s == 0 );
450    }
451
452
453    /**
454     * GB criterium 4. Use only for commutative polynomial rings. This version
455     * works also for d-Groebner bases.
456     * @param A polynomial.
457     * @param B polynomial.
458     * @return true if the S-polynomial(i,j) is required, else false.
459     */
460    @Override
461    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B) {
462        if (logger.isInfoEnabled()) {
463            if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
464                logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
465                return true;
466            }
467        }
468        ExpVector ei = A.leadingExpVector();
469        ExpVector ej = B.leadingExpVector();
470        ExpVector g = ei.sum(ej);
471        ExpVector e = ei.lcm(ej);
472        //        boolean t =  g == e ;
473        ExpVector h = g.subtract(e);
474        int s = h.signum();
475        if (s == 0) { // disjoint ht
476            C a = A.leadingBaseCoefficient();
477            C b = B.leadingBaseCoefficient();
478            C d = a.gcd(b);
479            if (d.isONE()) { // disjoint hc
480                return false; // can skip pair
481            }
482        }
483        return true; //! ( s == 0 );
484    }
485
486
487    /**
488     * Normalform with recording.
489     * @param row recording matrix, is modified.
490     * @param Pp a polynomial list for reduction.
491     * @param Ap a polynomial.
492     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
493     */
494    @SuppressWarnings("unchecked")
495    @Override
496    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
497                    GenPolynomial<C> Ap) {
498        if (Pp == null || Pp.isEmpty()) {
499            return Ap;
500        }
501        if (Ap == null || Ap.isZERO()) {
502            return Ap;
503        }
504        int l;
505        GenPolynomial<C>[] P;
506        synchronized (Pp) {
507            l = Pp.size();
508            P = (GenPolynomial<C>[]) new GenPolynomial[l];
509            //P = Pp.toArray();
510            for (int i = 0; i < Pp.size(); i++) {
511                P[i] = Pp.get(i);
512            }
513        }
514        ExpVector[] htl = new ExpVector[l];
515        C[] lbc = (C[]) new RingElem[l]; // want <C>
516        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
517        Map.Entry<ExpVector, C> m;
518        int j = 0;
519        int i;
520        for (i = 0; i < l; i++) {
521            p[i] = P[i];
522            m = p[i].leadingMonomial();
523            if (m != null) {
524                p[j] = p[i];
525                htl[j] = m.getKey();
526                lbc[j] = m.getValue();
527                j++;
528            }
529        }
530        l = j;
531        ExpVector e = null;
532        ExpVector f = null;
533        C a = null;
534        C b = null;
535        C r = null;
536        GenPolynomialRing<C> pfac = Ap.ring;
537        GenPolynomial<C> R = pfac.getZERO();
538        GenPolynomial<C> zero = pfac.getZERO();
539
540        GenPolynomial<C> fac = null;
541        // GenPolynomial<C> T = null;
542        GenPolynomial<C> Q = null;
543        GenPolynomial<C> S = Ap;
544        while (S.length() > 0) {
545            boolean mt = false;
546            m = S.leadingMonomial();
547            e = m.getKey();
548            a = m.getValue();
549            for (i = 0; i < l; i++) {
550                mt = e.multipleOf(htl[i]);
551                if (mt) {
552                    r = a.remainder(lbc[i]);
553                    mt = r.isZERO();
554                }
555                if (mt)
556                    break;
557            }
558            if (!mt) {
559                //logger.debug("irred");
560                R = R.sum(a, e);
561                S = S.subtract(a, e);
562                //System.out.println("a = " + a + ", e = " + e);
563            } else {
564                //logger.info("red div = {}", e);
565                f = e.subtract(htl[i]);
566                b = a.divide(lbc[i]);
567                //System.out.println("b = " + b + ", f = " + f);
568                // r == 0: R = R.sum(r, f);
569                Q = p[i].multiply(b, f);
570                S = S.reductum().subtract(Q.reductum()); // ok also with reductum
571                fac = row.get(i);
572                if (fac == null) {
573                    fac = zero.sum(b, f);
574                } else {
575                    fac = fac.sum(b, f);
576                }
577                row.set(i, fac);
578            }
579        }
580        return R;
581    }
582
583
584    /**
585     * Irreducible set.
586     * @param Pp polynomial list.
587     * @return a list P of polynomials which are in normalform wrt. P.
588     */
589    @Override
590    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
591        ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
592        if (Pp == null) {
593            return null;
594        }
595        for (GenPolynomial<C> a : Pp) {
596            if (!a.isZERO()) {
597                P.add(a);
598            }
599        }
600        int l = P.size();
601        if (l <= 1)
602            return P;
603
604        int irr = 0;
605        ExpVector e;
606        ExpVector f;
607        GenPolynomial<C> a;
608        logger.debug("irr = ");
609        while (irr != l) {
610            a = P.remove(0);
611            e = a.leadingExpVector();
612            a = normalform(P, a);
613            logger.debug(String.valueOf(irr));
614            if (a.isZERO()) {
615                l--;
616                if (l <= 1) {
617                    return P;
618                }
619            } else {
620                f = a.leadingExpVector();
621                if (e.equals(f)) {
622                    irr++;
623                } else {
624                    irr = 0;
625                }
626                P.add(a);
627            }
628        }
629        //System.out.println();
630        return P;
631    }
632
633
634    // inherit is okay:
635    //public boolean isReductionNF(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap,
636    //                 GenPolynomial<C> Np) {
637
638}