Source code

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