Source code

001/*
002 * $Id: PseudoReductionSeq.java 5243 2015-05-01 12:42:10Z 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.ReductionAbstract;
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.PolyUtil;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
022 * polynomials must not be from a field, i.e. the fraction free reduction is
023 * implemented. Implements normalform.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028public class PseudoReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements
029                PseudoReduction<C> {
030
031
032    private static final Logger logger = Logger.getLogger(PseudoReductionSeq.class);
033
034
035    private final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public PseudoReductionSeq() {
042    }
043
044
045    /**
046     * Normalform.
047     * @param Ap polynomial.
048     * @param Pp polynomial list.
049     * @return nf(Ap) with respect to Pp.
050     */
051    @SuppressWarnings("unchecked")
052    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
053        if (Pp == null || Pp.isEmpty()) {
054            return Ap;
055        }
056        if (Ap == null || Ap.isZERO()) {
057            return Ap;
058        }
059        Map.Entry<ExpVector, C> m;
060        GenPolynomial<C>[] P = new GenPolynomial[0];
061        synchronized (Pp) {
062            P = Pp.toArray(P);
063        }
064        int l = P.length;
065        ExpVector[] htl = new ExpVector[l];
066        C[] lbc = (C[]) new RingElem[l];
067        GenPolynomial<C>[] p = new GenPolynomial[l];
068        int i;
069        int j = 0;
070        for (i = 0; i < l; i++) {
071            if (P[i] == null) {
072                continue;
073            }
074            p[i] = P[i];
075            m = p[i].leadingMonomial();
076            if (m != null) {
077                p[j] = p[i];
078                htl[j] = m.getKey();
079                lbc[j] = m.getValue();
080                j++;
081            }
082        }
083        l = j;
084        ExpVector e;
085        C a;
086        boolean mt = false;
087        GenPolynomial<C> R = Ap.ring.getZERO().copy();
088
089        GenPolynomial<C> S = Ap.copy();
090        while (S.length() > 0) {
091            m = S.leadingMonomial();
092            e = m.getKey();
093            a = m.getValue();
094            for (i = 0; i < l; i++) {
095                mt = e.multipleOf(htl[i]);
096                if (mt)
097                    break;
098            }
099            if (!mt) {
100                //logger.debug("irred");
101                //R = R.sum(a, e);
102                //S = S.subtract(a, e);
103                R.doPutToMap(e, a);
104                S.doRemoveFromMap(e, a);
105                //System.out.println(" S = " + S);
106            } else {
107                e = e.subtract(htl[i]);
108                //logger.info("red div = " + e);
109                @SuppressWarnings("cast")
110                C c = (C) lbc[i];
111                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
112                    a = a.divide(c);
113                    S = S.subtractMultiple(a, e, p[i]);
114                } else {
115                    R = R.multiply(c);
116                    //S = S.multiply(c);
117                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
118                }
119                //Q = p[i].multiply(a, e);
120                //S = S.subtract(Q);
121            }
122        }
123        return R;
124    }
125
126
127    /**
128     * Normalform recursive.
129     * @param Ap recursive polynomial.
130     * @param Pp recursive polynomial list.
131     * @return nf(Ap) with respect to Pp.
132     */
133    @SuppressWarnings("cast")
134    public GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp,
135                    GenPolynomial<GenPolynomial<C>> Ap) {
136        if (Pp == null || Pp.isEmpty()) {
137            return Ap;
138        }
139        if (Ap == null || Ap.isZERO()) {
140            return Ap;
141        }
142        Map.Entry<ExpVector, GenPolynomial<C>> m;
143        GenPolynomial<GenPolynomial<C>>[] P = new GenPolynomial[0];
144        synchronized (Pp) {
145            P = Pp.toArray(P);
146        }
147        int l = P.length;
148        ExpVector[] htl = new ExpVector[l];
149        GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l];
150        GenPolynomial<GenPolynomial<C>>[] p = new GenPolynomial[l];
151        int i;
152        int j = 0;
153        for (i = 0; i < l; i++) {
154            if (P[i] == null) {
155                continue;
156            }
157            p[i] = P[i];
158            m = p[i].leadingMonomial();
159            if (m != null) {
160                p[j] = p[i];
161                htl[j] = m.getKey();
162                lbc[j] = m.getValue();
163                j++;
164            }
165        }
166        l = j;
167        ExpVector e, f;
168        GenPolynomial<C> a, b;
169        boolean mt = false;
170        GenPolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy();
171
172        GenPolynomial<GenPolynomial<C>> S = Ap.copy();
173        while (S.length() > 0) {
174            m = S.leadingMonomial();
175            e = m.getKey();
176            a = m.getValue();
177            for (i = 0; i < l; i++) {
178                mt = e.multipleOf(htl[i]);
179                if (mt)
180                    break;
181            }
182            if (!mt) {
183                //logger.debug("irred");
184                //R = R.sum(a, e);
185                //S = S.subtract(a, e);
186                R.doPutToMap(e, a);
187                S.doRemoveFromMap(e, a);
188                //System.out.println(" S = " + S);
189            } else {
190                f = e.subtract(htl[i]);
191                if (debug) {
192                    logger.info("red div = " + f);
193                    //logger.info("red a = " + a);
194                }
195                GenPolynomial<C> c = (GenPolynomial<C>) lbc[i];
196                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
197                if (PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) { //c.isUnit() ) {
198                    if (debug) {
199                        logger.info("red c = " + c);
200                    }
201                    //a = a.divide(c);
202                    b = PolyUtil.<C> basePseudoDivide(a, c);
203                    GenPolynomial<GenPolynomial<C>> Sp = S.subtractMultiple(b, f, p[i]);
204                    if (e.equals(Sp.leadingExpVector())) { // TODO: avoid
205                        //throw new RuntimeException("degree not descending");
206                        logger.info("degree not descending: S = " + S + ", Sp = " + Sp);
207                        R = R.multiply(c);
208                        //S = S.multiply(c);
209                        Sp = S.scaleSubtractMultiple(c, a, f, p[i]);
210                    }
211                    S = Sp;
212                } else {
213                    R = R.multiply(c);
214                    //S = S.multiply(c);
215                    S = S.scaleSubtractMultiple(c, a, f, p[i]);
216                }
217                //Q = p[i].multiply(a, e);
218                //S = S.subtract(Q);
219            }
220        }
221        return R;
222    }
223
224
225    /**
226     * Normalform with recording. <b>Note:</b> Only meaningful if all divisions
227     * are exact. Compute first the multiplication factor <code>m</code> with
228     * <code>normalform(Pp,Ap,m)</code>, then call this method with
229     * <code>normalform(row,Pp,m*Ap)</code>.
230     * @param row recording matrix, is modified.
231     * @param Pp a polynomial list for reduction.
232     * @param Ap a polynomial.
233     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
234     */
235    @SuppressWarnings("unchecked")
236    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
237                    GenPolynomial<C> Ap) {
238        if (Pp == null || Pp.isEmpty()) {
239            return Ap;
240        }
241        if (Ap == null || Ap.isZERO()) {
242            return Ap;
243        }
244        GenPolynomial<C>[] P = new GenPolynomial[0];
245        synchronized (Pp) {
246            P = Pp.toArray(P);
247        }
248        int l = P.length;
249        ExpVector[] htl = new ExpVector[l];
250        Object[] lbc = new Object[l]; // want C 
251        GenPolynomial<C>[] p = new GenPolynomial[l];
252        Map.Entry<ExpVector, C> m;
253        int j = 0;
254        int i;
255        for (i = 0; i < l; i++) {
256            p[i] = P[i];
257            m = p[i].leadingMonomial();
258            if (m != null) {
259                p[j] = p[i];
260                htl[j] = m.getKey();
261                lbc[j] = m.getValue();
262                j++;
263            }
264        }
265        l = j;
266        ExpVector e;
267        C a;
268        boolean mt = false;
269        GenPolynomial<C> zero = Ap.ring.getZERO();
270        GenPolynomial<C> R = Ap.ring.getZERO().copy();
271        GenPolynomial<C> fac = null;
272        GenPolynomial<C> S = Ap.copy();
273        while (S.length() > 0) {
274            m = S.leadingMonomial();
275            e = m.getKey();
276            a = m.getValue();
277            for (i = 0; i < l; i++) {
278                mt = e.multipleOf(htl[i]);
279                if (mt)
280                    break;
281            }
282            if (!mt) {
283                //logger.debug("irred");
284                //R = R.sum(a, e);
285                //S = S.subtract(a, e);
286                R.doPutToMap(e, a);
287                S.doRemoveFromMap(e, a);
288                // System.out.println(" S = " + S);
289            } else {
290                e = e.subtract(htl[i]);
291                //logger.info("red div = " + e);
292                C c = (C) lbc[i];
293                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
294                    a = a.divide(c);
295                    S = S.subtractMultiple(a, e, p[i]);
296                    //System.out.print("|");
297                } else {
298                    //System.out.print("*");
299                    R = R.multiply(c);
300                    //S = S.multiply(c);
301                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
302                }
303                //Q = p[i].multiply(a, e);
304                //S = S.subtract(Q);
305                fac = row.get(i);
306                if (fac == null) {
307                    fac = zero.sum(a, e);
308                } else {
309                    fac = fac.sum(a, e);
310                }
311                row.set(i, fac);
312            }
313        }
314        return R;
315    }
316
317
318    /**
319     * Normalform.
320     * @param Pp polynomial list.
321     * @param Ap polynomial.
322     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
323     *         for Ap.
324     */
325    @SuppressWarnings("unchecked")
326    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
327        if (Ap == null) {
328            return null;
329        }
330        C mfac = Ap.ring.getONECoefficient();
331        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
332        if (Pp == null || Pp.isEmpty()) {
333            return pf;
334        }
335        if (Ap.isZERO()) {
336            return pf;
337        }
338        Map.Entry<ExpVector, C> m;
339        GenPolynomial<C>[] P = new GenPolynomial[0];
340        synchronized (Pp) {
341            P = Pp.toArray(P);
342        }
343        int l = P.length;
344        ExpVector[] htl = new ExpVector[l];
345        C[] lbc = (C[]) new RingElem[l]; // want C[] 
346        GenPolynomial<C>[] p = new GenPolynomial[l];
347        int i;
348        int j = 0;
349        for (i = 0; i < l; i++) {
350            if (P[i] == null) {
351                continue;
352            }
353            p[i] = P[i];
354            m = p[i].leadingMonomial();
355            if (m != null) {
356                p[j] = p[i];
357                htl[j] = m.getKey();
358                lbc[j] = m.getValue();
359                j++;
360            }
361        }
362        l = j;
363        ExpVector e;
364        C a;
365        boolean mt = false;
366        GenPolynomial<C> R = Ap.ring.getZERO().copy();
367
368        GenPolynomial<C> S = Ap.copy();
369        while (S.length() > 0) {
370            m = S.leadingMonomial();
371            e = m.getKey();
372            a = m.getValue();
373            for (i = 0; i < l; i++) {
374                mt = e.multipleOf(htl[i]);
375                if (mt)
376                    break;
377            }
378            if (!mt) {
379                //logger.debug("irred");
380                //R = R.sum(a, e);
381                //S = S.subtract(a, e);
382                R.doPutToMap(e, a);
383                S.doRemoveFromMap(e, a);
384                //System.out.println(" S = " + S);
385            } else {
386                e = e.subtract(htl[i]);
387                //logger.info("red div = " + e);
388                C c = lbc[i];
389                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
390                    a = a.divide(c);
391                    S = S.subtractMultiple(a, e, p[i]);
392                } else {
393                    mfac = mfac.multiply(c);
394                    R = R.multiply(c);
395                    //S = S.multiply(c);
396                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
397                }
398                //Q = p[i].multiply(a, e);
399                //S = S.subtract(Q);
400            }
401        }
402        if (logger.isInfoEnabled()) {
403            logger.info("multiplicative factor = " + mfac);
404        }
405        pf = new PseudoReductionEntry<C>(R, mfac);
406        return pf;
407    }
408
409}