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