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