Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.logging.log4j.LogManager;
012import org.apache.logging.log4j.Logger;
013
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.Monomial;
016import edu.jas.poly.GenSolvablePolynomial;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Solvable polynomial Reduction algorithm. Implements left, right normalform.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class SolvableReductionSeq<C extends RingElem<C>> extends SolvableReductionAbstract<C> {
027
028
029    private static final Logger logger = LogManager.getLogger(SolvableReductionSeq.class);
030
031
032    /**
033     * Constructor.
034     */
035    public SolvableReductionSeq() {
036    }
037
038
039    /**
040     * Left Normalform.
041     * @param Ap solvable polynomial.
042     * @param Pp solvable polynomial list.
043     * @return left-nf(Ap) with respect to Pp.
044     */
045    @SuppressWarnings("unchecked")
046    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
047                    GenSolvablePolynomial<C> Ap) {
048        if (Pp == null || Pp.isEmpty()) {
049            return Ap;
050        }
051        if (Ap == null || Ap.isZERO()) {
052            return Ap;
053        }
054        Map.Entry<ExpVector, C> m;
055        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
056        synchronized (Pp) {
057            P = Pp.toArray(P);
058        }
059        int l = P.length;
060        int i;
061        ExpVector[] htl = new ExpVector[l];
062        //C[] lbc = (C[]) new RingElem[l];
063        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
064        int j = 0;
065        for (i = 0; i < l; i++) {
066            if (P[i] == null) {
067                continue;
068            }
069            p[i] = P[i];
070            m = p[i].leadingMonomial();
071            if (m != null) {
072                p[j] = p[i];
073                htl[j] = m.getKey();
074                //lbc[j] = m.getValue();
075                j++;
076            }
077        }
078        l = j;
079        ExpVector e; //, f;
080        C a, b;
081        boolean mt = false;
082        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
083        GenSolvablePolynomial<C> Q = null;
084        GenSolvablePolynomial<C> S = Ap.copy();
085        GenSolvablePolynomial<C> Sp;
086        while (S.length() > 0) {
087            m = S.leadingMonomial();
088            e = m.getKey();
089            logger.debug("red, e = {}", e);
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                    fac = Ap.ring.valueOf(a, e);
216                } else {
217                    //fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
218                    fac.doAddTo(a, e);
219                }
220                row.set(i, fac);
221            }
222        }
223        return R;
224    }
225
226
227    /**
228     * Right Normalform.
229     * @param Ap solvable polynomial.
230     * @param Pp solvable polynomial list.
231     * @return right-nf(Ap) with respect to Pp.
232     */
233    @SuppressWarnings({ "cast", "unchecked" })
234    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
235                    GenSolvablePolynomial<C> Ap) {
236        if (Pp == null || Pp.isEmpty()) {
237            return Ap;
238        }
239        if (Ap == null || Ap.isZERO()) {
240            return Ap;
241        }
242        int l;
243        Map.Entry<ExpVector, C> m;
244        GenSolvablePolynomial<C>[] P;
245        synchronized (Pp) {
246            l = Pp.size();
247            P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
248            //P = Pp.toArray();
249            for (int j = 0; j < Pp.size(); j++) {
250                P[j] = Pp.get(j);
251            }
252        }
253        int i;
254        ExpVector[] htl = new ExpVector[l];
255        //C[] lbc = (C[]) new RingElem[l];
256        GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
257        int j = 0;
258        for (i = 0; i < l; i++) {
259            p[i] = P[i];
260            m = p[i].leadingMonomial();
261            if (m != null) {
262                p[j] = p[i];
263                htl[j] = m.getKey();
264                //lbc[j] = m.getValue();
265                j++;
266            }
267        }
268        l = j;
269        ExpVector e;
270        C a;
271        boolean mt = false;
272        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
273
274        //GenSolvablePolynomial<C> T = null;
275        GenSolvablePolynomial<C> Q = null;
276        GenSolvablePolynomial<C> S = Ap.copy();
277        while (S.length() > 0) {
278            m = S.leadingMonomial();
279            e = m.getKey();
280            //logger.info("red = {}", e);
281            a = m.getValue();
282            for (i = 0; i < l; i++) {
283                mt = e.multipleOf(htl[i]);
284                if (mt)
285                    break;
286            }
287            if (!mt) {
288                //logger.debug("irred");
289                R.doPutToMap(e, a);
290                S.doRemoveFromMap(e, a);
291                // System.out.println(" S = " + S);
292            } else {
293                //logger.debug("red");
294                ExpVector d = e.subtract(htl[i]);
295                //a = a.divide( (C)lbc[i] );
296                Q = p[i].multiply(d); // p_i * (b d) TODO
297                C b = a.divide(Q.leadingBaseCoefficient());
298                Q = Q.multiply(b); // p_i * (b d) !!
299                if (!S.leadingMonomial().equals(Q.leadingMonomial()) ) {
300                    logger.info("S = " + S + ", Q = " + Q);
301                    logger.error("right reduction with un-equal leading terms: " + S.ring.toScript());
302                    //throw new UnsupportedOperationException("right reduction undefined ");
303                    //and treat as irreducible
304                    R.doPutToMap(e, a);
305                    S.doRemoveFromMap(e, a);
306                } else {
307                    S = (GenSolvablePolynomial<C>) S.subtract(Q);
308                }
309            }
310        }
311        return R;
312    }
313
314
315    /**
316     * RightNormalform with recording.
317     * @param row recording matrix, is modified.
318     * @param Pp a polynomial list for reduction.
319     * @param Ap a polynomial.
320     * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp.
321     */
322    @SuppressWarnings({ "cast", "unchecked" })
323    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row,
324                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
325        if (Pp == null || Pp.isEmpty()) {
326            return Ap;
327        }
328        if (Ap == null || Ap.isZERO()) {
329            return Ap;
330        }
331        int l = Pp.size();
332        GenSolvablePolynomial<C>[] P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
333        synchronized (Pp) {
334            //P = Pp.toArray();
335            for (int i = 0; i < Pp.size(); i++) {
336                P[i] = Pp.get(i);
337            }
338        }
339        ExpVector[] htl = new ExpVector[l];
340        //C[] lbc = (C[]) new RingElem[l];
341        GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
342        Map.Entry<ExpVector, C> m;
343        int j = 0;
344        int i;
345        for (i = 0; i < l; i++) {
346            p[i] = P[i];
347            m = p[i].leadingMonomial();
348            if (m != null) {
349                p[j] = p[i];
350                htl[j] = m.getKey();
351                //lbc[j] = m.getValue();
352                j++;
353            }
354        }
355        l = j;
356        ExpVector e;
357        C a;
358        boolean mt = false;
359        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
360        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
361
362        GenSolvablePolynomial<C> fac = null;
363        // GenSolvablePolynomial<C> T = null;
364        GenSolvablePolynomial<C> Q = null;
365        GenSolvablePolynomial<C> S = Ap.copy();
366        while (S.length() > 0) {
367            m = S.leadingMonomial();
368            e = m.getKey();
369            a = m.getValue();
370            for (i = 0; i < l; i++) {
371                mt = e.multipleOf(htl[i]);
372                if (mt)
373                    break;
374            }
375            if (!mt) {
376                //logger.debug("irred");
377                //R = (GenSolvablePolynomial<C>) R.sum(a, e);
378                //S = (GenSolvablePolynomial<C>) S.subtract(a, e);
379                R.doPutToMap(e, a);
380                S.doRemoveFromMap(e, a);
381            } else {
382                e = e.subtract(htl[i]);
383                //logger.info("red div = {}", e);
384                //a = a.divide( (C)lbc[i] );
385                //Q = p[i].multiply( a, e );
386                Q = p[i].multiply(e); // p_i * (a e) TODO
387                a = a.divide(Q.leadingBaseCoefficient());
388                Q = Q.multiply(a); // p_i * (e a)
389                ExpVector g1 = S.leadingExpVector();
390                S = (GenSolvablePolynomial<C>) S.subtract(Q);
391                //S = S.subtractMultiple(Q, a);
392                ExpVector g2 = S.leadingExpVector();
393                if (g1.equals(g2)) {
394                    throw new RuntimeException("g1.equals(g2): " + g1 + ", a = " + a + ", lc(S) = "
395                                    + S.leadingBaseCoefficient());
396                }
397                fac = row.get(i);
398                if (fac == null) {
399                    //fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
400                    fac = Ap.ring.valueOf(a, e);
401                } else {
402                    //fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
403                    fac.doAddTo(a, e);
404                }
405                row.set(i, fac);
406            }
407        }
408        return R;
409    }
410
411}