Source code

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