001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011
012import org.apache.logging.log4j.LogManager;
013import org.apache.logging.log4j.Logger;
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Polynomial E-Reduction sequential use algorithm. Implements normalform.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class EReductionSeq<C extends RingElem<C>> extends DReductionSeq<C> implements EReduction<C> {
028
029
030    private static final Logger logger = LogManager.getLogger(DReductionSeq.class);
031
032
033    /**
034     * Constructor.
035     */
036    public EReductionSeq() {
037    }
038
039
040    /**
041     * Is top reducible.
042     * @param A polynomial.
043     * @param P polynomial list.
044     * @return true if A is top reducible with respect to P.
045     */
046    @Override
047    public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
048        if (P == null || P.isEmpty()) {
049            return false;
050        }
051        if (A == null || A.isZERO()) {
052            return false;
053        }
054        boolean mt = false;
055        ExpVector e = A.leadingExpVector();
056        C a = A.leadingBaseCoefficient();
057        for (GenPolynomial<C> p : P) {
058            mt = e.multipleOf(p.leadingExpVector());
059            if (mt) {
060                C b = p.leadingBaseCoefficient();
061                C r = a.remainder(b);
062                mt = !r.equals(a);
063                if (mt) {
064                    return true;
065                }
066            }
067        }
068        return false;
069    }
070
071
072    /**
073     * Is in Normalform.
074     * @param Ap polynomial.
075     * @param Pp polynomial list.
076     * @return true if Ap is in normalform with respect to Pp.
077     */
078    @SuppressWarnings("unchecked")
079    @Override
080    public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
081        if (Pp == null || Pp.isEmpty()) {
082            return true;
083        }
084        if (Ap == null || Ap.isZERO()) {
085            return true;
086        }
087        int l;
088        GenPolynomial<C>[] P;
089        synchronized (Pp) {
090            l = Pp.size();
091            P = new GenPolynomial[l];
092            //P = Pp.toArray();
093            for (int i = 0; i < Pp.size(); i++) {
094                P[i] = Pp.get(i);
095            }
096        }
097        ExpVector[] htl = new ExpVector[l];
098        C[] lbc = (C[]) new RingElem[l]; // want <C>
099        GenPolynomial<C>[] p = new GenPolynomial[l];
100        Map.Entry<ExpVector, C> m;
101        int i;
102        int j = 0;
103        for (i = 0; i < l; i++) {
104            p[i] = P[i];
105            m = p[i].leadingMonomial();
106            if (m != null) {
107                p[j] = p[i];
108                htl[j] = m.getKey();
109                lbc[j] = m.getValue();
110                j++;
111            }
112        }
113        l = j;
114        boolean mt = false;
115        Map<ExpVector, C> Am = Ap.getMap();
116        for (Map.Entry<ExpVector, C> me : Am.entrySet()) {
117            ExpVector e = me.getKey();
118            C a = me.getValue(); //Am.get(e);
119            for (i = 0; i < l; i++) {
120                mt = e.multipleOf(htl[i]);
121                if (mt) {
122                    C r = a.remainder(lbc[i]);
123                    mt = !r.equals(a);
124                    if (mt) {
125                        return false;
126                    }
127                }
128            }
129        }
130        return true;
131    }
132
133
134    /**
135     * Normalform using e-reduction.
136     * @param Ap polynomial.
137     * @param Pp polynomial list.
138     * @return e-nf(Ap) with respect to Pp.
139     */
140    @SuppressWarnings("unchecked")
141    @Override
142    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
143        if (Pp == null || Pp.isEmpty()) {
144            return Ap;
145        }
146        if (Ap == null || Ap.isZERO()) {
147            return Ap;
148        }
149        int l;
150        GenPolynomial<C>[] P;
151        synchronized (Pp) {
152            l = Pp.size();
153            P = (GenPolynomial<C>[]) new GenPolynomial[l];
154            //P = Pp.toArray();
155            for (int i = 0; i < Pp.size(); i++) {
156                P[i] = Pp.get(i); //.abs();
157            }
158        }
159        Map.Entry<ExpVector, C> m;
160        ExpVector[] htl = new ExpVector[l];
161        C[] lbc = (C[]) new RingElem[l]; // want <C>
162        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
163        int i;
164        int j = 0;
165        for (i = 0; i < l; i++) {
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 = null;
177        ExpVector f = null;
178        C a = null;
179        C b = null;
180        C r = null;
181        GenPolynomialRing<C> pfac = Ap.ring;
182        GenPolynomial<C> R = pfac.getZERO();
183        //GenPolynomial<C> T = pfac.getZERO();
184        GenPolynomial<C> Q = null;
185        GenPolynomial<C> S = Ap;
186        //try { // required to avoid a compiler error in the while loop
187        while (S.length() > 0) {
188            boolean mt = false;
189            m = S.leadingMonomial();
190            e = m.getKey();
191            a = m.getValue();
192            for (i = 0; i < l; i++) {
193                mt = e.multipleOf(htl[i]);
194                if (mt) {
195                    f = e.subtract(htl[i]);
196                    //logger.info("red div = {}", f);
197                    r = a.remainder(lbc[i]);
198                    b = a.divide(lbc[i]);
199                    if (f == null) { // compiler produced this case ??? still ?
200                        System.out.println("f = null: " + e + ", " + htl[i]);
201                        Q = p[i].multiply(b);
202                    } else {
203                        Q = p[i].multiply(b, f);
204                    }
205                    S = S.subtract(Q); // ok also with reductum
206                    //System.out.println(" r = " + r);
207                    a = r;
208                    if (r.isZERO()) {
209                        break;
210                    }
211                }
212            }
213            if (!a.isZERO()) { //! mt ) {
214                //logger.debug("irred");
215                R = R.sum(a, e);
216                //S = S.subtract( a, e ); 
217                S = S.reductum();
218            }
219            //System.out.println(" R = " + R);
220            //System.out.println(" S = " + S);
221        }
222        return R; //.abs(); not ok with e-reduction
223    }
224
225
226    /**
227     * Normalform with recording.
228     * @param row recording matrix, is modified.
229     * @param Pp a polynomial list for reduction.
230     * @param Ap a polynomial.
231     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
232     */
233    @Override
234    @SuppressWarnings("unchecked")
235    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
236                    GenPolynomial<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        GenPolynomial<C>[] P;
245        synchronized (Pp) {
246            l = Pp.size();
247            P = (GenPolynomial<C>[]) new GenPolynomial[l];
248            //P = Pp.toArray();
249            for (int i = 0; i < Pp.size(); i++) {
250                P[i] = Pp.get(i); //.abs();
251            }
252        }
253        ExpVector[] htl = new ExpVector[l];
254        C[] lbc = (C[]) new RingElem[l]; // want <C>
255        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
256        Map.Entry<ExpVector, C> m;
257        int j = 0;
258        int i;
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 = null;
271        ExpVector f = null;
272        C a = null;
273        C b = null;
274        C r = null;
275        GenPolynomialRing<C> pfac = Ap.ring;
276        GenPolynomial<C> R = pfac.getZERO();
277        GenPolynomial<C> zero = pfac.getZERO();
278        //System.out.println("row_in = " + row);
279
280        GenPolynomial<C> fac = null;
281        // GenPolynomial<C> T = null;
282        GenPolynomial<C> Q = null;
283        GenPolynomial<C> S = Ap;
284        while (S.length() > 0) {
285            boolean mt = false;
286            m = S.leadingMonomial();
287            e = m.getKey();
288            a = m.getValue();
289            //System.out.println("e = " + e);
290            for (i = 0; i < l; i++) {
291                mt = e.multipleOf(htl[i]);
292                if (mt) {
293                    f = e.subtract(htl[i]);
294                    //logger.info("red div = {}", f);
295                    r = a.remainder(lbc[i]);
296                    b = a.divide(lbc[i]);
297                    //if (f == null) { // compiler produced this case ??? still ?
298                    //    System.out.println("f = null: " + e + ", " + htl[i]);
299                    //    f = pfac.evzero;
300                    //}
301                    Q = p[i].multiply(b, f);
302                    S = S.subtract(Q);
303                    fac = row.get(i);
304                    if (fac == null) {
305                        fac = zero.sum(b, f);
306                    } else {
307                        fac = fac.sum(b, f);
308                    }
309                    row.set(i, fac);
310                    //System.out.println("i = " + i);
311                    //System.out.println("r = " + r);
312                    a = r;
313                    if (r.isZERO()) {
314                        break;
315                    }
316                }
317            }
318            if (!a.isZERO()) { //! mt ) {
319                //logger.debug("irred");
320                R = R.sum(a, e);
321                S = S.subtract(a, e);
322                //??S = S.reductum();
323            }
324        }
325        return R;
326    }
327
328
329    /**
330     * Irreducible set.
331     * @param Pp polynomial list.
332     * @return a list P of polynomials which are in normalform wrt. P.
333     */
334    @Override
335    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
336        ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
337        if (Pp == null) {
338            return null;
339        }
340        for (GenPolynomial<C> a : Pp) {
341            if (!a.isZERO()) {
342                P.add(a);
343            }
344        }
345        int l = P.size();
346        if (l <= 1)
347            return P;
348
349        int irr = 0;
350        ExpVector e;
351        ExpVector f;
352        C c;
353        C d;
354        GenPolynomial<C> a;
355        //Iterator<GenPolynomial<C>> it;
356        logger.debug("irr = ");
357        while (irr != l) {
358            //it = P.listIterator(); 
359            //a = P.get(0); //it.next();
360            a = P.remove(0);
361            e = a.leadingExpVector();
362            c = a.leadingBaseCoefficient();
363            a = normalform(P, a);
364            logger.debug(String.valueOf(irr));
365            if (a.isZERO()) {
366                l--;
367                if (l <= 1) {
368                    return P;
369                }
370            } else {
371                f = a.leadingExpVector();
372                d = a.leadingBaseCoefficient();
373                if (e.equals(f) && c.equals(d)) {
374                    irr++;
375                } else {
376                    irr = 0;
377                }
378                P.add(a);
379            }
380        }
381        //System.out.println();
382        return P;
383    }
384
385
386    // inherit is okay:
387    //public boolean isReductionNF(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap,
388    //                 GenPolynomial<C> Np) {
389
390}