Source code

001/*
002 * $Id: EReductionSeq.java 4115 2012-08-19 13:18:59Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.log4j.Logger;
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017
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 = Logger.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    //SuppressWarnings("unchecked") // not jet working
047    @Override
048    public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
049        if (P == null || P.isEmpty()) {
050            return false;
051        }
052        if (A == null || A.isZERO()) {
053            return false;
054        }
055        boolean mt = false;
056        ExpVector e = A.leadingExpVector();
057        C a = A.leadingBaseCoefficient();
058        for (GenPolynomial<C> p : P) {
059            mt = e.multipleOf(p.leadingExpVector());
060            if (mt) {
061                C b = p.leadingBaseCoefficient();
062                C r = a.remainder(b);
063                mt = !r.equals(a);
064                if (mt) {
065                    return true;
066                }
067            }
068        }
069        return false;
070    }
071
072
073    /**
074     * Is in Normalform.
075     * @param Ap polynomial.
076     * @param Pp polynomial list.
077     * @return true if Ap is in normalform with respect to Pp.
078     */
079    @SuppressWarnings("unchecked")
080    @Override
081    public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
082        if (Pp == null || Pp.isEmpty()) {
083            return true;
084        }
085        if (Ap == null || Ap.isZERO()) {
086            return true;
087        }
088        int l;
089        GenPolynomial<C>[] P;
090        synchronized (Pp) {
091            l = Pp.size();
092            P = new GenPolynomial[l];
093            //P = Pp.toArray();
094            for (int i = 0; i < Pp.size(); i++) {
095                P[i] = Pp.get(i);
096            }
097        }
098        ExpVector[] htl = new ExpVector[l];
099        C[] lbc = (C[]) new RingElem[l]; // want <C>
100        GenPolynomial<C>[] p = new GenPolynomial[l];
101        Map.Entry<ExpVector, C> m;
102        int i;
103        int j = 0;
104        for (i = 0; i < l; i++) {
105            p[i] = P[i];
106            m = p[i].leadingMonomial();
107            if (m != null) {
108                p[j] = p[i];
109                htl[j] = m.getKey();
110                lbc[j] = m.getValue();
111                j++;
112            }
113        }
114        l = j;
115        boolean mt = false;
116        Map<ExpVector, C> Am = Ap.getMap();
117        for (Map.Entry<ExpVector,C> me : Am.entrySet()) {
118            ExpVector e = me.getKey();
119            C a = me.getValue(); //Am.get(e);
120            for (i = 0; i < l; i++) {
121                mt = e.multipleOf(htl[i]);
122                if (mt) {
123                    C r = a.remainder(lbc[i]);
124                    mt = !r.equals(a);
125                    if (mt) {
126                        return false;
127                    }
128                }
129            }
130        }
131        return true;
132    }
133
134
135    /**
136     * Normalform using e-reduction.
137     * @param Ap polynomial.
138     * @param Pp polynomial list.
139     * @return e-nf(Ap) with respect to Pp.
140     */
141    @SuppressWarnings("unchecked")
142    @Override
143    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
144        if (Pp == null || Pp.isEmpty()) {
145            return Ap;
146        }
147        if (Ap == null || Ap.isZERO()) {
148            return Ap;
149        }
150        int l;
151        GenPolynomial<C>[] P;
152        synchronized (Pp) {
153            l = Pp.size();
154            P = (GenPolynomial<C>[]) new GenPolynomial[l];
155            //P = Pp.toArray();
156            for (int i = 0; i < Pp.size(); i++) {
157                P[i] = Pp.get(i).abs();
158            }
159        }
160        Map.Entry<ExpVector, C> m;
161        ExpVector[] htl = new ExpVector[l];
162        C[] lbc = (C[]) new RingElem[l]; // want <C>
163        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
164        int i;
165        int j = 0;
166        for (i = 0; i < l; i++) {
167            p[i] = P[i];
168            m = p[i].leadingMonomial();
169            if (m != null) {
170                p[j] = p[i];
171                htl[j] = m.getKey();
172                lbc[j] = m.getValue();
173                j++;
174            }
175        }
176        l = j;
177        ExpVector e = null;
178        ExpVector f = null;
179        C a = null;
180        C b = null;
181        C r = null;
182        GenPolynomial<C> R = Ap.ring.getZERO();
183        GenPolynomial<C> T = Ap.ring.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
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        //} catch (Exception ex) {
223        //    System.out.println("R = " + R);
224        //    System.out.println("S = " + S);
225        //    System.out.println("f = " + f + ", " + e + ", " + htl[i]);
226        //    System.out.println("a = " + a + ", " + b + ", " + r + ", " + lbc[i]);
227        //    //throw ex;
228        //    return T;
229        //}
230        return R.abs();
231    }
232
233
234    /**
235     * Normalform with recording.
236     * @param row recording matrix, is modified.
237     * @param Pp a polynomial list for reduction.
238     * @param Ap a polynomial.
239     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
240     */
241    @Override
242    @SuppressWarnings("unchecked")
243    // not jet working
244    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
245            GenPolynomial<C> Ap) {
246        if (Pp == null || Pp.isEmpty()) {
247            return Ap;
248        }
249        if (Ap == null || Ap.isZERO()) {
250            return Ap;
251        }
252        throw new UnsupportedOperationException("not jet implemented");
253        /*
254        int l = Pp.size();
255        GenPolynomial<C>[] P = new GenPolynomial[l];
256        synchronized (Pp) {
257            //P = Pp.toArray();
258            for ( int i = 0; i < Pp.size(); i++ ) {
259                P[i] = Pp.get(i);
260            }
261        }
262        ExpVector[] htl = new ExpVector[ l ];
263        Object[] lbc = new Object[ l ]; // want <C>
264        GenPolynomial<C>[] p = new GenPolynomial[ l ];
265        Map.Entry<ExpVector,C> m;
266        int j = 0;
267        int i;
268        for ( i = 0; i < l; i++ ) { 
269            p[i] = P[i];
270            m = p[i].leadingMonomial();
271            if ( m != null ) { 
272                p[j] = p[i];
273                htl[j] = m.getKey();
274                lbc[j] = m.getValue();
275                j++;
276            }
277        }
278        l = j;
279        ExpVector e;
280        C a;
281        boolean mt = false;
282        GenPolynomial<C> zero = Ap.ring.getZERO();
283        GenPolynomial<C> R = Ap.ring.getZERO();
284
285        GenPolynomial<C> fac = null;
286        // GenPolynomial<C> T = null;
287        GenPolynomial<C> Q = null;
288        GenPolynomial<C> S = Ap;
289        while ( S.length() > 0 ) { 
290            m = S.leadingMonomial();
291            e = m.getKey();
292            a = m.getValue();
293            for ( i = 0; i < l; i++ ) {
294                mt =  e.multipleOf( htl[i] );
295                if ( mt ) break; 
296            }
297            if ( ! mt ) { 
298                //logger.debug("irred");
299                R = R.sum( a, e );
300                S = S.subtract( a, e ); 
301                // System.out.println(" S = " + S);
302                //throw new RuntimeException("Syzygy no GB");
303            } else { 
304                e =  e.subtract( htl[i] );
305                //logger.info("red div = " + e);
306                C c = (C)lbc[i];
307                a = a.divide( c );
308                Q = p[i].multiply( a, e );
309                S = S.subtract( Q );
310                fac = row.get(i);
311                if ( fac == null ) {
312                    fac = zero.sum( a, e );
313                } else {
314                    fac = fac.sum( a, e );
315                }
316                row.set(i,fac);
317            }
318        }
319        return R;
320        */
321    }
322
323
324    /**
325     * Irreducible set.
326     * @param Pp polynomial list.
327     * @return a list P of polynomials which are in normalform wrt. P.
328     */
329    @Override
330    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
331        ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
332        if (Pp == null) {
333            return null;
334        }
335        for (GenPolynomial<C> a : Pp) {
336            if (!a.isZERO()) {
337                P.add(a);
338            }
339        }
340        int l = P.size();
341        if (l <= 1)
342            return P;
343
344        int irr = 0;
345        ExpVector e;
346        ExpVector f;
347        C c;
348        C d;
349        GenPolynomial<C> a;
350        Iterator<GenPolynomial<C>> it;
351        logger.debug("irr = ");
352        while (irr != l) {
353            //it = P.listIterator(); 
354            //a = P.get(0); //it.next();
355            a = P.remove(0);
356            e = a.leadingExpVector();
357            c = a.leadingBaseCoefficient();
358            a = normalform(P, a);
359            logger.debug(String.valueOf(irr));
360            if (a.isZERO()) {
361                l--;
362                if (l <= 1) {
363                    return P;
364                }
365            } else {
366                f = a.leadingExpVector();
367                d = a.leadingBaseCoefficient();
368                if (e.equals(f) && c.equals(d)) {
369                    irr++;
370                } else {
371                    irr = 0;
372                }
373                P.add(a);
374            }
375        }
376        //System.out.println();
377        return P;
378    }
379
380}