Source code

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