Source code

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