Source code

001/*
002 * $Id: SolvablePseudoReductionSeq.java 5870 2018-07-20 15:56:23Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.gb.SolvableReductionAbstract;
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.structure.GcdRingElem;
022
023
024/**
025 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
026 * polynomials must not be from a field, i.e. the fraction free reduction is
027 * implemented. Implements normalform.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class SolvablePseudoReductionSeq<C extends GcdRingElem<C>> extends SolvableReductionAbstract<C>
033                implements SolvablePseudoReduction<C> {
034
035
036    private static final Logger logger = LogManager.getLogger(SolvablePseudoReductionSeq.class);
037
038
039    private static final boolean debug = logger.isDebugEnabled();
040
041
042    /**
043     * Constructor.
044     */
045    public SolvablePseudoReductionSeq() {
046    }
047
048
049    /**
050     * Left normalform.
051     * @param Ap polynomial.
052     * @param Pp polynomial list.
053     * @return nf(Ap) with respect to Pp.
054     */
055    @SuppressWarnings("unchecked")
056    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
057                    GenSolvablePolynomial<C> Ap) {
058        if (Pp == null || Pp.isEmpty()) {
059            return Ap;
060        }
061        if (Ap == null || Ap.isZERO()) {
062            return Ap;
063        }
064        Map.Entry<ExpVector, C> m;
065        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
066        synchronized (Pp) {
067            P = Pp.toArray(P);
068        }
069        int l = P.length;
070        ExpVector[] htl = new ExpVector[l];
071        //C[] lbc = (C[]) new GcdRingElem[l];
072        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
073        int i;
074        int j = 0;
075        for (i = 0; i < l; i++) {
076            if (P[i] == null) {
077                continue;
078            }
079            p[i] = P[i];
080            m = p[i].leadingMonomial();
081            if (m != null) {
082                p[j] = p[i];
083                htl[j] = m.getKey();
084                //lbc[j] = m.getValue();
085                j++;
086            }
087        }
088        l = j;
089        ExpVector e;
090        C a;
091        boolean mt = false;
092        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
093        GenSolvablePolynomial<C> Q = null;
094        GenSolvablePolynomial<C> S = Ap.copy();
095        while (S.length() > 0) {
096            m = S.leadingMonomial();
097            e = m.getKey();
098            a = m.getValue();
099            for (i = 0; i < l; i++) {
100                mt = e.multipleOf(htl[i]);
101                if (mt)
102                    break;
103            }
104            if (!mt) {
105                //logger.debug("irred");
106                //R = R.sum(a, e);
107                //S = S.subtract(a, e);
108                R.doPutToMap(e, a);
109                S.doRemoveFromMap(e, a);
110                //System.out.println(" S = " + S);
111            } else {
112                e = e.subtract(htl[i]);
113                //logger.info("red div = " + e);
114                Q = p[i].multiplyLeft(e);
115                C c = Q.leadingBaseCoefficient();
116                ExpVector g = S.leadingExpVector();
117                C ap = a;
118                if (a.remainder(c).isZERO()) { // && !c.isConstant()) {
119                    a = a.divide(c);
120                    S = S.subtractMultiple(a, Q);
121                } else {
122                    R = R.multiplyLeft(c);
123                    S = S.scaleSubtractMultiple(c, a, Q);
124                }
125                ExpVector h = S.leadingExpVector();
126                if (g.equals(h)) { // Ore condition not fulfilled
127                    logger.info("g==h: g = " + g + ", c = " + c);
128                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c);
129                }
130            }
131        }
132        return R;
133    }
134
135
136    /**
137     * Left normalform recursive.
138     * @param Ap recursive polynomial.
139     * @param Pp recursive polynomial list.
140     * @return nf(Ap) with respect to Pp.
141     */
142    @SuppressWarnings({ "unchecked" })
143    public GenSolvablePolynomial<GenPolynomial<C>> leftNormalformRecursive(
144                    List<GenSolvablePolynomial<GenPolynomial<C>>> Pp,
145                    GenSolvablePolynomial<GenPolynomial<C>> Ap) {
146        if (Pp == null || Pp.isEmpty()) {
147            return Ap;
148        }
149        if (Ap == null || Ap.isZERO()) {
150            return Ap;
151        }
152        Map.Entry<ExpVector, GenPolynomial<C>> m;
153        GenSolvablePolynomial<GenPolynomial<C>>[] P = new GenSolvablePolynomial[0];
154        synchronized (Pp) {
155            P = Pp.toArray(P);
156        }
157        int l = P.length;
158        ExpVector[] htl = new ExpVector[l];
159        //GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l];
160        GenSolvablePolynomial<GenPolynomial<C>>[] p = new GenSolvablePolynomial[l];
161        int i;
162        int j = 0;
163        for (i = 0; i < l; i++) {
164            if (P[i] == null) {
165                continue;
166            }
167            p[i] = P[i];
168            m = p[i].leadingMonomial();
169            if (m != null) {
170                p[j] = p[i];
171                htl[j] = m.getKey();
172                //lbc[j] = m.getValue();
173                j++;
174            }
175        }
176        l = j;
177        ExpVector e, f;
178        GenPolynomial<C> a, b;
179        boolean mt = false;
180        GenSolvablePolynomialRing<GenPolynomial<C>> ring = Ap.ring;
181        final boolean commCoeff = ring.coFac.isCommutative();
182        final SolvableSyzygyAbstract<C> ssy;
183        if (commCoeff) {
184            ssy = null;
185        } else {
186            ssy = new SolvableSyzygySeq<C>(((GenPolynomialRing<C>) ring.coFac).coFac);
187        }
188        GenSolvablePolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
189        GenSolvablePolynomial<GenPolynomial<C>> Q = null;
190        GenSolvablePolynomial<GenPolynomial<C>> S = Ap.copy();
191        //GenSolvablePolynomial<GenPolynomial<C>> Sp = null;
192        while (S.length() > 0) {
193            m = S.leadingMonomial();
194            e = m.getKey();
195            a = m.getValue();
196            for (i = 0; i < l; i++) {
197                mt = e.multipleOf(htl[i]);
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                R.doPutToMap(e, a);
206                S.doRemoveFromMap(e, a);
207                //System.out.println(" S = " + S);
208            } else {
209                f = e.subtract(htl[i]);
210                if (debug) {
211                    logger.info("red div = " + f);
212                    //logger.info("red a = " + a);
213                }
214                Q = p[i].multiplyLeft(f);
215                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
216                ExpVector g = S.leadingExpVector();
217                GenPolynomial<C> ap = a;
218                if (commCoeff) {
219                    GenPolynomial<C> c = Q.leadingBaseCoefficient();
220                    if (!c.isConstant() && PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) {
221                        //a = a.divide(c);
222                        b = PolyUtil.<C> basePseudoDivide(a, c);
223                        if (a.equals(b.multiply(c))) {
224                            S = S.subtractMultiple(b, Q);
225                        } else {
226                            R = R.multiplyLeft(c);
227                            S = S.scaleSubtractMultiple(c, a, Q);
228                        }
229                    } else {
230                        R = R.multiplyLeft(c);
231                        S = S.scaleSubtractMultiple(c, a, Q);
232                    }
233                } else { // use Ore condition
234                    GenSolvablePolynomial<C> cs = (GenSolvablePolynomial<C>) Q.leadingBaseCoefficient();
235                    GenSolvablePolynomial<C> as = (GenSolvablePolynomial<C>) a;
236                    GenPolynomial<C>[] ore = ssy.leftOreCond(cs, as);
237                    //System.out.println("cs = " + cs + ", as = " + as);
238                    //System.out.println("ore[0] = " + ore[0] + "\nore[1] = " + ore[1]);
239                    R = R.multiplyLeft(ore[1]);
240                    S = S.scaleSubtractMultiple(ore[1], ore[0], Q);
241                }
242                ExpVector h = S.leadingExpVector();
243                if (g.equals(h)) { // ! Ore cond
244                    logger.info("g==h: g = " + g);
245                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap);
246                }
247            }
248        }
249        //System.out.println("Ap = " + Ap + ", R = " + R);
250        return R;
251    }
252
253
254    /**
255     * Left normalform with recording. <b>Note:</b> Only meaningful if all
256     * divisions are exact. Compute first the multiplication factor
257     * <code>m</code> with <code>normalform(Pp,Ap,m)</code>, then call this
258     * method with <code>normalform(row,Pp,m*Ap)</code>.
259     * @param row recording matrix, is modified.
260     * @param Pp a polynomial list for reduction.
261     * @param Ap a polynomial.
262     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
263     */
264    @SuppressWarnings("unchecked")
265    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
266                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
267        if (Pp == null || Pp.isEmpty()) {
268            return Ap;
269        }
270        if (Ap == null || Ap.isZERO()) {
271            return Ap;
272        }
273        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
274        synchronized (Pp) {
275            P = Pp.toArray(P);
276        }
277        int l = P.length;
278        ExpVector[] htl = new ExpVector[l];
279        //C[] lbc = (C[]) new GcdRingElem[l];
280        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
281        Map.Entry<ExpVector, C> m;
282        int j = 0;
283        int i;
284        for (i = 0; i < l; i++) {
285            p[i] = P[i];
286            m = p[i].leadingMonomial();
287            if (m != null) {
288                p[j] = p[i];
289                htl[j] = m.getKey();
290                //lbc[j] = m.getValue();
291                j++;
292            }
293        }
294        l = j;
295        ExpVector e;
296        C a;
297        boolean mt = false;
298        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
299        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
300        GenSolvablePolynomial<C> Q = null;
301        GenSolvablePolynomial<C> fac = null;
302        GenSolvablePolynomial<C> S = Ap.copy();
303        while (S.length() > 0) {
304            m = S.leadingMonomial();
305            e = m.getKey();
306            a = m.getValue();
307            for (i = 0; i < l; i++) {
308                mt = e.multipleOf(htl[i]);
309                if (mt)
310                    break;
311            }
312            if (!mt) {
313                //logger.debug("irred");
314                //R = R.sum(a, e);
315                //S = S.subtract(a, e);
316                R.doPutToMap(e, a);
317                S.doRemoveFromMap(e, a);
318                // System.out.println(" S = " + S);
319                //throw new RuntimeException("Syzygy no GB");
320            } else {
321                e = e.subtract(htl[i]);
322                //logger.info("red div = " + e);
323                Q = p[i].multiplyLeft(e);
324                C c = Q.leadingBaseCoefficient();
325                ExpVector g = S.leadingExpVector();
326                C ap = a;
327                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
328                    a = a.divide(c);
329                    S = S.subtractMultiple(a, Q);
330                    //System.out.print("|");
331                } else {
332                    //System.out.print("*");
333                    R = R.multiplyLeft(c);
334                    S = S.scaleSubtractMultiple(c, a, Q);
335                }
336                ExpVector h = S.leadingExpVector();
337                if (g.equals(h)) { // Ore condition not fulfilled
338                    System.out.println("g = " + g + ", h = " + h);
339                    System.out.println("c*ap = " + c.multiply(ap) + ", ap*c = " + ap.multiply(c));
340                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c);
341                }
342                //Q = p[i].multiply(a, e);
343                //S = S.subtract(Q);
344                fac = row.get(i);
345                if (fac == null) {
346                    fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
347                } else { // doAddTo ??
348                    fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
349                }
350                row.set(i, fac);
351            }
352        }
353        return R;
354    }
355
356
357    /**
358     * Left normalform with factor.
359     * @param Pp polynomial list.
360     * @param Ap polynomial.
361     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
362     *         for Ap.
363     */
364    @SuppressWarnings("unchecked")
365    public PseudoReductionEntry<C> leftNormalformFactor(List<GenSolvablePolynomial<C>> Pp,
366                    GenSolvablePolynomial<C> Ap) {
367        if (Ap == null) {
368            return null;
369        }
370        C mfac = Ap.ring.getONECoefficient();
371        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
372        if (Pp == null || Pp.isEmpty()) {
373            return pf;
374        }
375        if (Ap.isZERO()) {
376            return pf;
377        }
378        Map.Entry<ExpVector, C> m;
379        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
380        synchronized (Pp) {
381            P = Pp.toArray(P);
382        }
383        int l = P.length;
384        ExpVector[] htl = new ExpVector[l];
385        //C[] lbc = (C[]) new GcdRingElem[l]; 
386        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
387        int i;
388        int j = 0;
389        for (i = 0; i < l; i++) {
390            if (P[i] == null) {
391                continue;
392            }
393            p[i] = P[i];
394            m = p[i].leadingMonomial();
395            if (m != null) {
396                p[j] = p[i];
397                htl[j] = m.getKey();
398                //lbc[j] = m.getValue();
399                j++;
400            }
401        }
402        l = j;
403        ExpVector e;
404        C a;
405        boolean mt = false;
406        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
407        GenSolvablePolynomial<C> Q = null;
408        GenSolvablePolynomial<C> S = Ap.copy();
409        while (S.length() > 0) {
410            m = S.leadingMonomial();
411            e = m.getKey();
412            a = m.getValue();
413            for (i = 0; i < l; i++) {
414                mt = e.multipleOf(htl[i]);
415                if (mt)
416                    break;
417            }
418            if (!mt) {
419                //logger.debug("irred");
420                //R = R.sum(a, e);
421                //S = S.subtract(a, e);
422                R.doPutToMap(e, a);
423                S.doRemoveFromMap(e, a);
424                //System.out.println(" S = " + S);
425            } else {
426                e = e.subtract(htl[i]);
427                //logger.info("red div = " + e);
428                Q = p[i].multiplyLeft(e);
429                C c = Q.leadingBaseCoefficient();
430                ExpVector g = S.leadingExpVector();
431                C ap = a;
432                if (a.remainder(c).isZERO()) {
433                    a = a.divide(c);
434                    S = S.subtractMultiple(a, Q);
435                } else {
436                    mfac = c.multiply(mfac); // left
437                    R = R.multiplyLeft(c);
438                    S = S.scaleSubtractMultiple(c, a, Q);
439                }
440                ExpVector h = S.leadingExpVector();
441                if (g.equals(h)) { // Ore condition not fulfilled
442                    logger.info("g==h: g = " + g + ", c = " + c);
443                    throw new RuntimeException("g==h: a = " + a + ", ap = " + ap);
444                }
445            }
446        }
447        if (logger.isDebugEnabled()) {
448            logger.info("multiplicative factor = " + mfac);
449        }
450        pf = new PseudoReductionEntry<C>(R, mfac);
451        return pf;
452    }
453
454
455    /**
456     * Right normalform.
457     * @param Ap polynomial.
458     * @param Pp polynomial list.
459     * @return nf(Ap) with respect to Pp. 
460     */
461    @SuppressWarnings({ "unchecked" })
462    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
463                    GenSolvablePolynomial<C> Ap) {
464        if (Pp == null || Pp.isEmpty()) {
465            return Ap;
466        }
467        if (Ap == null || Ap.isZERO()) {
468            return Ap;
469        }
470        Map.Entry<ExpVector, C> m;
471        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
472        synchronized (Pp) {
473            P = Pp.toArray(P);
474        }
475        int l = P.length;
476        ExpVector[] htl = new ExpVector[l];
477        //C[] lbc = (C[]) new GcdRingElem[l];
478        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
479        int i;
480        int j = 0;
481        for (i = 0; i < l; i++) {
482            if (P[i] == null) {
483                continue;
484            }
485            p[i] = P[i];
486            m = p[i].leadingMonomial();
487            if (m != null) {
488                p[j] = p[i];
489                htl[j] = m.getKey();
490                //lbc[j] = m.getValue();
491                j++;
492            }
493        }
494        l = j;
495        ExpVector e;
496        C a;
497        boolean mt = false;
498        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
499        GenSolvablePolynomial<C> Q = null;
500        GenSolvablePolynomial<C> S = Ap.copy();
501        while (S.length() > 0) {
502            m = S.leadingMonomial();
503            e = m.getKey();
504            a = m.getValue();
505            for (i = 0; i < l; i++) {
506                mt = e.multipleOf(htl[i]);
507                if (mt)
508                    break;
509            }
510            if (!mt) {
511                //logger.debug("irred");
512                //R = R.sum(a, e);
513                //S = S.subtract(a, e);
514                R.doPutToMap(e, a);
515                S.doRemoveFromMap(e, a);
516                //System.out.println(" S = " + S);
517            } else {
518                e = e.subtract(htl[i]);
519                //logger.info("red div = " + e);
520                // need pi * a * e, but only pi * e * a or a * pi * e available
521                Q = p[i].multiply(e);
522                assert Q.multiply(a).equals(Q.multiplyLeft(a));
523                C c = Q.leadingBaseCoefficient();
524                ExpVector g = S.leadingExpVector();
525                C ap = a;
526                if (a.remainder(c).isZERO()) {
527                    a = a.divide(c); // left?
528                    //S = S.subtractMultiple(Q,a);
529                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
530                } else {
531                    R = R.multiply(c);
532                    S = S.multiply(c);
533                    //S = S.scaleSubtractMultiple(c, Q, a);
534                    S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a));
535                }
536                ExpVector h = S.leadingExpVector();
537                if (g.equals(h)) { // Ore condition not fulfilled
538                    logger.info("g==h: g = " + g + ", c = " + c);
539                    throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap);
540                }
541            }
542        }
543        //System.out.println("R = " + R);
544        return R;
545    }
546
547
548    /**
549     * Right normalform recursive.
550     * @param Ap recursive polynomial.
551     * @param Pp recursive polynomial list.
552     * @return nf(Ap) with respect to Pp. <b>Note: </b> not implemented;
553     */
554    public GenSolvablePolynomial<GenPolynomial<C>> rightNormalformRecursive(
555                    List<GenSolvablePolynomial<GenPolynomial<C>>> Pp,
556                    GenSolvablePolynomial<GenPolynomial<C>> Ap) {
557        if (Pp == null || Ap == null) {
558            throw new IllegalArgumentException("Pp or Ap == null not supported");
559        }
560        throw new UnsupportedOperationException(); // TODO
561    }
562
563
564    /**
565     * Left normalform with recording. <b>Note:</b> Only meaningful if all
566     * divisions are exact. Compute first the multiplication factor
567     * <code>m</code> with <code>normalform(Pp,Ap,m)</code>, then call this
568     * method with <code>normalform(row,Pp,m*Ap)</code>.
569     * @param row recording matrix, is modified.
570     * @param Pp a polynomial list for reduction.
571     * @param Ap a polynomial.
572     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. <b>Note: </b> not
573     *         implemented;
574     */
575    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row,
576                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
577        if (row == null || Pp == null || Ap == null) {
578            throw new IllegalArgumentException("row, Pp or Ap == null not supported");
579        }
580        throw new UnsupportedOperationException(); // TODO
581    }
582
583
584    /**
585     * Right normalform with multiplication factor.
586     * @param Pp polynomial list.
587     * @param Ap polynomial.
588     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
589     *         for Ap. <b>Note: </b> not implemented;
590     */
591    public PseudoReductionEntry<C> rightNormalformFactor(List<GenSolvablePolynomial<C>> Pp,
592                    GenSolvablePolynomial<C> Ap) {
593        if (Pp == null || Ap == null) {
594            throw new IllegalArgumentException("Pp or Ap == null not supported");
595        }
596        throw new UnsupportedOperationException(); // TODO
597    }
598
599}