001/*
002 * $Id: DReductionSeq.java 5869 2018-07-20 15:53:10Z kredel $
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.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Polynomial D-Reduction sequential use algorithm. Implements normalform.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class DReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements DReduction<C> {
028
029
030    private static final Logger logger = LogManager.getLogger(DReductionSeq.class);
031
032
033    //private static final boolean debug = logger.isDebugEnabled();
034
035
036    /**
037     * Constructor.
038     */
039    public DReductionSeq() {
040    }
041
042
043    /**
044     * Is top reducible.
045     * @param A polynomial.
046     * @param P polynomial list.
047     * @return true if A is top reducible with respect to P.
048     */
049    //SuppressWarnings("unchecked") // not jet working
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    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
146        if (Pp == null || Pp.isEmpty()) {
147            return Ap;
148        }
149        if (Ap == null || Ap.isZERO()) {
150            return Ap;
151        }
152        int l;
153        GenPolynomial<C>[] P;
154        synchronized (Pp) {
155            l = Pp.size();
156            P = (GenPolynomial<C>[]) new GenPolynomial[l];
157            //P = Pp.toArray();
158            for (int i = 0; i < Pp.size(); i++) {
159                P[i] = Pp.get(i).abs();
160            }
161        }
162        //System.out.println("l = " + l);
163        Map.Entry<ExpVector, C> m;
164        ExpVector[] htl = new ExpVector[l];
165        C[] lbc = (C[]) new RingElem[l]; // want <C>
166        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
167        int i;
168        int j = 0;
169        for (i = 0; i < l; i++) {
170            p[i] = P[i];
171            m = p[i].leadingMonomial();
172            if (m != null) {
173                p[j] = p[i];
174                htl[j] = m.getKey();
175                lbc[j] = m.getValue();
176                j++;
177            }
178        }
179        l = j;
180        ExpVector e;
181        C a;
182        C r = null;
183        boolean mt = false;
184        GenPolynomial<C> R = Ap.ring.getZERO();
185        GenPolynomial<C> Q = null;
186        GenPolynomial<C> S = Ap;
187        while (S.length() > 0) {
188            m = S.leadingMonomial();
189            e = m.getKey();
190            a = m.getValue();
191            for (i = 0; i < l; i++) {
192                mt = e.multipleOf(htl[i]);
193                if (mt) {
194                    r = a.remainder(lbc[i]);
195                    mt = r.isZERO(); // && mt
196                }
197                if (mt)
198                    break;
199            }
200            if (!mt) {
201                //logger.debug("irred");
202                R = R.sum(a, e);
203                //S = S.subtract( a, e ); 
204                S = S.reductum();
205                //System.out.println(" S = " + S);
206            } else {
207                //logger.info("red div = " + e);
208                ExpVector f = e.subtract(htl[i]);
209                C b = a.divide(lbc[i]);
210                R = R.sum(r, e);
211                Q = p[i].multiply(b, f);
212                S = S.reductum().subtract(Q.reductum()); // ok also with reductum
213            }
214        }
215        return R.abs();
216    }
217
218
219    /**
220     * S-Polynomial.
221     * @param Ap polynomial.
222     * @param Bp polynomial.
223     * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
224     */
225    @Override
226    public GenPolynomial<C> SPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
227        if (logger.isInfoEnabled()) {
228            if (Bp == null || Bp.isZERO()) {
229                return Ap.ring.getZERO();
230            }
231            if (Ap == null || Ap.isZERO()) {
232                return Bp.ring.getZERO();
233            }
234            if (!Ap.ring.equals(Bp.ring)) {
235                logger.error("rings not equal");
236            }
237        }
238        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
239        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
240
241        ExpVector e = ma.getKey();
242        ExpVector f = mb.getKey();
243
244        ExpVector g = e.lcm(f);
245        ExpVector e1 = g.subtract(e);
246        ExpVector f1 = g.subtract(f);
247
248        C a = ma.getValue();
249        C b = mb.getValue();
250        C c = a.gcd(b);
251        C m = a.multiply(b);
252        C l = m.divide(c); // = lcm(a,b)
253
254        C a1 = l.divide(a);
255        C b1 = l.divide(b);
256
257        GenPolynomial<C> App = Ap.multiply(a1, e1);
258        GenPolynomial<C> Bpp = Bp.multiply(b1, f1);
259        GenPolynomial<C> Cp = App.subtract(Bpp);
260        return Cp;
261    }
262
263
264    /**
265     * G-Polynomial.
266     * @param Ap polynomial.
267     * @param Bp polynomial.
268     * @return gpol(Ap,Bp) the g-polynomial of Ap and Bp.
269     */
270    public GenPolynomial<C> GPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
271        if (logger.isInfoEnabled()) {
272            if (Bp == null || Bp.isZERO()) {
273                return Ap.ring.getZERO();
274            }
275            if (Ap == null || Ap.isZERO()) {
276                return Bp.ring.getZERO();
277            }
278            if (!Ap.ring.equals(Bp.ring)) {
279                logger.error("rings not equal");
280            }
281        }
282        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
283        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
284
285        ExpVector e = ma.getKey();
286        ExpVector f = mb.getKey();
287
288        ExpVector g = e.lcm(f);
289        ExpVector e1 = g.subtract(e);
290        ExpVector f1 = g.subtract(f);
291
292        C a = ma.getValue();
293        C b = mb.getValue();
294        C[] c = a.egcd(b);
295
296        //System.out.println("egcd[0] " + c[0]);
297
298        GenPolynomial<C> App = Ap.multiply(c[1], e1);
299        GenPolynomial<C> Bpp = Bp.multiply(c[2], f1);
300        GenPolynomial<C> Cp = App.sum(Bpp);
301        return Cp;
302    }
303
304
305    /**
306     * D-Polynomial with recording.
307     * @param S recording matrix, 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 gpol(Ap, Bp), the g-Polynomial for Ap and Bp.
313     */
314    public GenPolynomial<C> GPolynomial(List<GenPolynomial<C>> S, int i, GenPolynomial<C> Ap, int j,
315                    GenPolynomial<C> Bp) {
316        throw new UnsupportedOperationException("not yet implemented");
317    }
318
319
320    /**
321     * GB criterium 4. Use only for commutative polynomial rings. This version
322     * works also for d-Groebner bases.
323     * @param A polynomial.
324     * @param B polynomial.
325     * @param e = lcm(ht(A),ht(B))
326     * @return true if the S-polynomial(i,j) is required, else false.
327     */
328    @Override
329    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e) {
330        if (logger.isInfoEnabled()) {
331            if (!A.ring.equals(B.ring)) {
332                logger.error("rings equal");
333            }
334            if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
335                logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
336                return true;
337            }
338        }
339        ExpVector ei = A.leadingExpVector();
340        ExpVector ej = B.leadingExpVector();
341        ExpVector g = ei.sum(ej);
342        // boolean t =  g == e ;
343        ExpVector h = g.subtract(e);
344        int s = h.signum();
345        if (s == 0) { // disjoint ht
346            C a = A.leadingBaseCoefficient();
347            C b = B.leadingBaseCoefficient();
348            C d = a.gcd(b);
349            if (d.isONE()) { // disjoint hc
350                //System.out.println("d1 = " + d + ", a = " + a + ", b = " + b);
351                return false; // can skip pair
352            }
353        }
354        return true; //! ( s == 0 );
355    }
356
357
358    /**
359     * GB criterium 4. Use only for commutative polynomial rings. This version
360     * works also for d-Groebner bases.
361     * @param A polynomial.
362     * @param B polynomial.
363     * @return true if the S-polynomial(i,j) is required, else false.
364     */
365    @Override
366    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B) {
367        if (logger.isInfoEnabled()) {
368            if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
369                logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
370                return true;
371            }
372        }
373        ExpVector ei = A.leadingExpVector();
374        ExpVector ej = B.leadingExpVector();
375        ExpVector g = ei.sum(ej);
376        ExpVector e = ei.lcm(ej);
377        //        boolean t =  g == e ;
378        ExpVector h = g.subtract(e);
379        int s = h.signum();
380        if (s == 0) { // disjoint ht
381            C a = A.leadingBaseCoefficient();
382            C b = B.leadingBaseCoefficient();
383            C d = a.gcd(b);
384            if (d.isONE()) { // disjoint hc
385                return false; // can skip pair
386            }
387        }
388        return true; //! ( s == 0 );
389    }
390
391
392    /**
393     * Normalform with recording.
394     * @param row recording matrix, is modified.
395     * @param Pp a polynomial list for reduction.
396     * @param Ap a polynomial.
397     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
398     */
399    @SuppressWarnings("unchecked")
400    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
401                    GenPolynomial<C> Ap) {
402        if (Pp == null || Pp.isEmpty()) {
403            return Ap;
404        }
405        if (Ap == null || Ap.isZERO()) {
406            return Ap;
407        }
408        throw new UnsupportedOperationException("not yet implemented");
409        /*
410        int l = Pp.size();
411        GenPolynomial<C>[] P = new GenPolynomial[l];
412        synchronized (Pp) {
413            //P = Pp.toArray();
414            for ( int i = 0; i < Pp.size(); i++ ) {
415                P[i] = Pp.get(i);
416            }
417        }
418        ExpVector[] htl = new ExpVector[ l ];
419        Object[] lbc = new Object[ l ]; // want <C>
420        GenPolynomial<C>[] p = new GenPolynomial[ l ];
421        Map.Entry<ExpVector,C> m;
422        int j = 0;
423        int i;
424        for ( i = 0; i < l; i++ ) { 
425            p[i] = P[i];
426            m = p[i].leadingMonomial();
427            if ( m != null ) { 
428                p[j] = p[i];
429                htl[j] = m.getKey();
430                lbc[j] = m.getValue();
431                j++;
432            }
433        }
434        l = j;
435        ExpVector e;
436        C a;
437        boolean mt = false;
438        GenPolynomial<C> zero = Ap.ring.getZERO();
439        GenPolynomial<C> R = Ap.ring.getZERO();
440
441        GenPolynomial<C> fac = null;
442        // GenPolynomial<C> T = null;
443        GenPolynomial<C> Q = null;
444        GenPolynomial<C> S = Ap;
445        while ( S.length() > 0 ) { 
446            m = S.leadingMonomial();
447            e = m.getKey();
448            a = m.getValue();
449            for ( i = 0; i < l; i++ ) {
450                mt =  e.multipleOf( htl[i] );
451                if ( mt ) break; 
452            }
453            if ( ! mt ) { 
454                //logger.debug("irred");
455                R = R.sum( a, e );
456                S = S.subtract( a, e ); 
457                // System.out.println(" S = " + S);
458            } else { 
459                e =  e.subtract( htl[i] );
460                //logger.info("red div = " + e);
461                C c = (C)lbc[i];
462                a = a.divide( c );
463                Q = p[i].multiply( a, e );
464                S = S.subtract( Q );
465                fac = row.get(i);
466                if ( fac == null ) {
467                    fac = zero.sum( a, e );
468                } else {
469                    fac = fac.sum( a, e );
470                }
471                row.set(i,fac);
472            }
473        }
474        return R;
475        */
476    }
477
478
479    /**
480     * Irreducible set.
481     * @param Pp polynomial list.
482     * @return a list P of polynomials which are in normalform wrt. P.
483     */
484    @Override
485    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
486        ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
487        if (Pp == null) {
488            return null;
489        }
490        for (GenPolynomial<C> a : Pp) {
491            if (!a.isZERO()) {
492                P.add(a);
493            }
494        }
495        int l = P.size();
496        if (l <= 1)
497            return P;
498
499        int irr = 0;
500        ExpVector e;
501        ExpVector f;
502        GenPolynomial<C> a;
503        logger.debug("irr = ");
504        while (irr != l) {
505            a = P.remove(0);
506            e = a.leadingExpVector();
507            a = normalform(P, a);
508            logger.debug(String.valueOf(irr));
509            if (a.isZERO()) {
510                l--;
511                if (l <= 1) {
512                    return P;
513                }
514            } else {
515                f = a.leadingExpVector();
516                if (e.equals(f)) {
517                    irr++;
518                } else {
519                    irr = 0;
520                }
521                P.add(a);
522            }
523        }
524        //System.out.println();
525        return P;
526    }
527
528}