Source code

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