Source code

001/*
002 * $Id: EReductionSeq.java 5935 2018-09-30 11:47:20Z kredel $
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.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Polynomial E-Reduction sequential use algorithm. Implements normalform.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class EReductionSeq<C extends RingElem<C>> extends DReductionSeq<C> implements EReduction<C> {
027
028
029    private static final Logger logger = LogManager.getLogger(DReductionSeq.class);
030
031
032    /**
033     * Constructor.
034     */
035    public EReductionSeq() {
036    }
037
038
039    /**
040     * Is top reducible.
041     * @param A polynomial.
042     * @param P polynomial list.
043     * @return true if A is top reducible with respect to P.
044     */
045    //SuppressWarnings("unchecked") // not jet working
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        GenPolynomial<C> R = Ap.ring.getZERO();
182        //GenPolynomial<C> T = Ap.ring.getZERO();
183        GenPolynomial<C> Q = null;
184        GenPolynomial<C> S = Ap;
185        //try { // required to avoid a compiler error in the while loop
186        while (S.length() > 0) {
187            boolean mt = false;
188            m = S.leadingMonomial();
189            e = m.getKey();
190            a = m.getValue();
191            for (i = 0; i < l; i++) {
192                mt = e.multipleOf(htl[i]);
193                if (mt) {
194                    f = e.subtract(htl[i]);
195                    //logger.info("red div = " + f);
196                    r = a.remainder(lbc[i]);
197                    b = a.divide(lbc[i]);
198                    if (f == null) { // compiler produced this case
199                        System.out.println("f = null: " + e + ", " + htl[i]);
200                        Q = p[i].multiply(b);
201                    } else {
202                        Q = p[i].multiply(b, f);
203                    }
204                    S = S.subtract(Q); // ok also with reductum
205                    //System.out.println(" r = " + r);
206                    a = r;
207                    if (r.isZERO()) {
208                        break;
209                    }
210                }
211            }
212            if (!a.isZERO()) { //! mt ) { 
213                //logger.debug("irred");
214                R = R.sum(a, e);
215                //S = S.subtract( a, e ); 
216                S = S.reductum();
217            }
218            //System.out.println(" R = " + R);
219            //System.out.println(" S = " + S);
220        }
221        //} catch (Exception ex) {
222        //    System.out.println("R = " + R);
223        //    System.out.println("S = " + S);
224        //    System.out.println("f = " + f + ", " + e + ", " + htl[i]);
225        //    System.out.println("a = " + a + ", " + b + ", " + r + ", " + lbc[i]);
226        //    //throw ex;
227        //    return T;
228        //}
229        return R.abs();
230    }
231
232
233    /**
234     * Normalform with recording.
235     * @param row recording matrix, is modified.
236     * @param Pp a polynomial list for reduction.
237     * @param Ap a polynomial.
238     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
239     */
240    @Override
241    @SuppressWarnings("unchecked")
242    // not jet working
243    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
244                    GenPolynomial<C> Ap) {
245        if (Pp == null || Pp.isEmpty()) {
246            return Ap;
247        }
248        if (Ap == null || Ap.isZERO()) {
249            return Ap;
250        }
251        throw new UnsupportedOperationException("not jet implemented");
252        /*
253        int l = Pp.size();
254        GenPolynomial<C>[] P = new GenPolynomial[l];
255        synchronized (Pp) {
256            //P = Pp.toArray();
257            for ( int i = 0; i < Pp.size(); i++ ) {
258                P[i] = Pp.get(i);
259            }
260        }
261        ExpVector[] htl = new ExpVector[ l ];
262        Object[] lbc = new Object[ l ]; // want <C>
263        GenPolynomial<C>[] p = new GenPolynomial[ l ];
264        Map.Entry<ExpVector,C> m;
265        int j = 0;
266        int i;
267        for ( i = 0; i < l; i++ ) { 
268            p[i] = P[i];
269            m = p[i].leadingMonomial();
270            if ( m != null ) { 
271                p[j] = p[i];
272                htl[j] = m.getKey();
273                lbc[j] = m.getValue();
274                j++;
275            }
276        }
277        l = j;
278        ExpVector e;
279        C a;
280        boolean mt = false;
281        GenPolynomial<C> zero = Ap.ring.getZERO();
282        GenPolynomial<C> R = Ap.ring.getZERO();
283
284        GenPolynomial<C> fac = null;
285        // GenPolynomial<C> T = null;
286        GenPolynomial<C> Q = null;
287        GenPolynomial<C> S = Ap;
288        while ( S.length() > 0 ) { 
289            m = S.leadingMonomial();
290            e = m.getKey();
291            a = m.getValue();
292            for ( i = 0; i < l; i++ ) {
293                mt =  e.multipleOf( htl[i] );
294                if ( mt ) break; 
295            }
296            if ( ! mt ) { 
297                //logger.debug("irred");
298                R = R.sum( a, e );
299                S = S.subtract( a, e ); 
300                // System.out.println(" S = " + S);
301            } else { 
302                e =  e.subtract( htl[i] );
303                //logger.info("red div = " + e);
304                C c = (C)lbc[i];
305                a = a.divide( c );
306                Q = p[i].multiply( a, e );
307                S = S.subtract( Q );
308                fac = row.get(i);
309                if ( fac == null ) {
310                    fac = zero.sum( a, e );
311                } else {
312                    fac = fac.sum( a, e );
313                }
314                row.set(i,fac);
315            }
316        }
317        return R;
318        */
319    }
320
321
322    /**
323     * Irreducible set.
324     * @param Pp polynomial list.
325     * @return a list P of polynomials which are in normalform wrt. P.
326     */
327    @Override
328    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
329        ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
330        if (Pp == null) {
331            return null;
332        }
333        for (GenPolynomial<C> a : Pp) {
334            if (!a.isZERO()) {
335                P.add(a);
336            }
337        }
338        int l = P.size();
339        if (l <= 1)
340            return P;
341
342        int irr = 0;
343        ExpVector e;
344        ExpVector f;
345        C c;
346        C d;
347        GenPolynomial<C> a;
348        //Iterator<GenPolynomial<C>> it;
349        logger.debug("irr = ");
350        while (irr != l) {
351            //it = P.listIterator(); 
352            //a = P.get(0); //it.next();
353            a = P.remove(0);
354            e = a.leadingExpVector();
355            c = a.leadingBaseCoefficient();
356            a = normalform(P, a);
357            logger.debug(String.valueOf(irr));
358            if (a.isZERO()) {
359                l--;
360                if (l <= 1) {
361                    return P;
362                }
363            } else {
364                f = a.leadingExpVector();
365                d = a.leadingBaseCoefficient();
366                if (e.equals(f) && c.equals(d)) {
367                    irr++;
368                } else {
369                    irr = 0;
370                }
371                P.add(a);
372            }
373        }
374        //System.out.println();
375        return P;
376    }
377
378}