Source code

001/*
002 * $Id: RPseudoReductionSeq.java 4061 2012-07-27 12:03:20Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.List;
009import java.util.Map;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.poly.ExpVector;
014import edu.jas.poly.GenPolynomial;
015import edu.jas.structure.RegularRingElem;
016
017
018/**
019 * Polynomial regular ring pseudo reduction sequential use algorithm. Implements
020 * fraction free normalform algorithm.
021 * @param <C> coefficient type
022 * @author Heinz Kredel
023 */
024
025public class RPseudoReductionSeq<C extends RegularRingElem<C>> extends RReductionSeq<C> implements
026                RPseudoReduction<C> {
027
028
029    private static final Logger logger = Logger.getLogger(RPseudoReductionSeq.class);
030
031
032    private final boolean debug = logger.isDebugEnabled();
033
034
035    /**
036     * Constructor.
037     */
038    public RPseudoReductionSeq() {
039    }
040
041
042    /**
043     * Normalform using r-reduction.
044     * @param Ap polynomial.
045     * @param Pp polynomial list.
046     * @return r-nf(Ap) with respect to Pp.
047     */
048    @Override
049    @SuppressWarnings("unchecked")
050    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
051        if (Pp == null || Pp.isEmpty()) {
052            return Ap;
053        }
054        if (Ap == null || Ap.isZERO()) {
055            return Ap;
056        }
057        int l;
058        GenPolynomial<C>[] P;
059        synchronized (Pp) {
060            l = Pp.size();
061            P = (GenPolynomial<C>[]) new GenPolynomial[l];
062            //P = Pp.toArray();
063            for (int i = 0; i < Pp.size(); i++) {
064                P[i] = Pp.get(i);
065            }
066        }
067        //System.out.println("l = " + l);
068        Map.Entry<ExpVector, C> m;
069        ExpVector[] htl = new ExpVector[l];
070        C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
071        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
072        int i;
073        int j = 0;
074        for (i = 0; i < l; i++) {
075            if (P[i] == null) {
076                continue;
077            }
078            p[i] = P[i].abs();
079            m = p[i].leadingMonomial();
080            if (m != null) {
081                p[j] = p[i];
082                htl[j] = m.getKey();
083                lbc[j] = m.getValue();
084                j++;
085            }
086        }
087        l = j;
088        ExpVector e, f;
089        C a;
090        C r = null;
091        boolean mt = false;
092        GenPolynomial<C> R = Ap.ring.getZERO();
093        GenPolynomial<C> Q = null;
094        GenPolynomial<C> S = Ap;
095        while (S.length() > 0) {
096            m = S.leadingMonomial();
097            e = m.getKey();
098            a = m.getValue();
099            //System.out.println("--a = " + a);
100            for (i = 0; i < l; i++) {
101                mt = e.multipleOf(htl[i]);
102                if (mt) {
103                    C c = lbc[i];
104                    //r = a.idempotent().multiply( c.idempotent() );
105                    r = a.idempotentAnd(c);
106                    mt = !r.isZERO(); // && mt
107                    if (mt) {
108                        f = e.subtract(htl[i]);
109                        if (a.remainder(c).isZERO()) { //c.isUnit() ) {
110                            a = a.divide(c);
111                            if (a.isZERO()) {
112                                throw new ArithmeticException("a.isZERO()");
113                            }
114                        } else {
115                            c = c.fillOne();
116                            S = S.multiply(c);
117                            R = R.multiply(c);
118                        }
119                        Q = p[i].multiply(a, f);
120                        S = S.subtract(Q);
121
122                        f = S.leadingExpVector();
123                        if (!e.equals(f)) {
124                            a = Ap.ring.coFac.getZERO();
125                            break;
126                        }
127                        a = S.leadingBaseCoefficient();
128                    }
129                }
130            }
131            if (!a.isZERO()) { //! mt ) { 
132                //logger.debug("irred");
133                R = R.sum(a, e);
134                S = S.reductum();
135            }
136        }
137        return R.abs(); // not monic if not boolean closed
138    }
139
140
141    /**
142     * Normalform using r-reduction.
143     * @param Pp polynomial list.
144     * @param Ap polynomial.
145     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
146     *         for Ap.
147     */
148    @SuppressWarnings("unchecked")
149    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
150        if (Ap == null) {
151            return null;
152        }
153        C mfac = Ap.ring.getONECoefficient();
154        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
155        if (Pp == null || Pp.isEmpty()) {
156            return pf;
157        }
158        if (Ap.isZERO()) {
159            return pf;
160        }
161        int l;
162        GenPolynomial<C>[] P;
163        synchronized (Pp) {
164            l = Pp.size();
165            P = (GenPolynomial<C>[]) new GenPolynomial[l];
166            //P = Pp.toArray();
167            for (int i = 0; i < Pp.size(); i++) {
168                P[i] = Pp.get(i);
169            }
170        }
171        //System.out.println("l = " + l);
172        Map.Entry<ExpVector, C> m;
173        ExpVector[] htl = new ExpVector[l];
174        C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
175        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
176        int i;
177        int j = 0;
178        for (i = 0; i < l; i++) {
179            if (P[i] == null) {
180                continue;
181            }
182            p[i] = P[i].abs();
183            m = p[i].leadingMonomial();
184            if (m != null) {
185                p[j] = p[i];
186                htl[j] = m.getKey();
187                lbc[j] = m.getValue();
188                j++;
189            }
190        }
191        l = j;
192        ExpVector e, f;
193        C a;
194        C r = null;
195        boolean mt = false;
196        GenPolynomial<C> R = Ap.ring.getZERO();
197        GenPolynomial<C> Q = null;
198        GenPolynomial<C> S = Ap;
199        while (S.length() > 0) {
200            m = S.leadingMonomial();
201            e = m.getKey();
202            a = m.getValue();
203            //System.out.println("--a = " + a);
204            for (i = 0; i < l; i++) {
205                mt = e.multipleOf(htl[i]);
206                if (mt) {
207                    C c = lbc[i];
208                    //r = a.idempotent().multiply( c.idempotent() );
209                    r = a.idempotentAnd(c);
210                    mt = !r.isZERO(); // && mt
211                    if (mt) {
212                        f = e.subtract(htl[i]);
213                        if (a.remainder(c).isZERO()) { //c.isUnit() ) {
214                            a = a.divide(c);
215                            if (a.isZERO()) {
216                                throw new ArithmeticException("a.isZERO()");
217                            }
218                        } else {
219                            c = c.fillOne();
220                            S = S.multiply(c);
221                            R = R.multiply(c);
222                            mfac = mfac.multiply(c);
223                        }
224                        Q = p[i].multiply(a, f);
225                        S = S.subtract(Q);
226
227                        f = S.leadingExpVector();
228                        if (!e.equals(f)) {
229                            a = Ap.ring.coFac.getZERO();
230                            break;
231                        }
232                        a = S.leadingBaseCoefficient();
233                    }
234                }
235            }
236            if (!a.isZERO()) { //! mt ) { 
237                //logger.debug("irred");
238                R = R.sum(a, e);
239                S = S.reductum();
240            }
241        }
242        pf = new PseudoReductionEntry<C>(R, mfac); //.abs(); // not monic if not boolean closed
243        return pf;
244    }
245
246
247    /**
248     * Normalform with recording. <b>Note:</b> Only meaningfull if all divisions
249     * are exact. Compute first the multiplication factor <code>m</code> with
250     * <code>normalform(Pp,Ap,m)</code>, then call this method with
251     * <code>normalform(row,Pp,m*Ap)</code>.
252     * @param row recording matrix, is modified.
253     * @param Pp a polynomial list for reduction.
254     * @param Ap a polynomial.
255     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
256     */
257    @Override
258    @SuppressWarnings("unchecked")
259    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
260                    GenPolynomial<C> Ap) {
261        if (Pp == null || Pp.isEmpty()) {
262            return Ap;
263        }
264        if (Ap == null || Ap.isZERO()) {
265            return Ap;
266        }
267        int l;
268        GenPolynomial<C>[] P;
269        synchronized (Pp) {
270            l = Pp.size();
271            P = (GenPolynomial<C>[]) new GenPolynomial[l];
272            //P = Pp.toArray();
273            for (int i = 0; i < Pp.size(); i++) {
274                P[i] = Pp.get(i);
275            }
276        }
277        //System.out.println("l = " + l);
278        Map.Entry<ExpVector, C> m;
279        ExpVector[] htl = new ExpVector[l];
280        C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
281        GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
282        int i;
283        int j = 0;
284        for (i = 0; i < l; i++) {
285            p[i] = P[i];
286            m = p[i].leadingMonomial();
287            if (m != null) {
288                p[j] = p[i];
289                htl[j] = m.getKey();
290                lbc[j] = m.getValue();
291                j++;
292            }
293        }
294        l = j;
295        ExpVector e, f;
296        C a, b;
297        C r = null;
298        boolean mt = false;
299        GenPolynomial<C> fac = null;
300        GenPolynomial<C> zero = Ap.ring.getZERO();
301        GenPolynomial<C> R = Ap.ring.getZERO();
302        GenPolynomial<C> Q = null;
303        GenPolynomial<C> S = Ap;
304        while (S.length() > 0) {
305            m = S.leadingMonomial();
306            e = m.getKey();
307            a = m.getValue();
308            for (i = 0; i < l; i++) {
309                mt = e.multipleOf(htl[i]);
310                if (mt) {
311                    C c = lbc[i];
312                    //r = a.idempotent().multiply( c.idempotent() );
313                    r = a.idempotentAnd(c);
314                    //System.out.println("r = " + r);
315                    mt = !r.isZERO(); // && mt
316                    if (mt) {
317                        b = a.remainder(c);
318                        if (b.isZERO()) {
319                            a = a.divide(c);
320                            if (a.isZERO()) {
321                                throw new ArithmeticException("a.isZERO()");
322                            }
323                        } else {
324                            c = c.fillOne();
325                            S = S.multiply(c);
326                            R = R.multiply(c);
327                        }
328                        f = e.subtract(htl[i]);
329                        if (debug) {
330                            logger.info("red div = " + f);
331                        }
332                        Q = p[i].multiply(a, f);
333                        S = S.subtract(Q); // not ok with reductum
334
335                        fac = row.get(i);
336                        if (fac == null) {
337                            fac = zero.sum(a, f);
338                        } else {
339                            fac = fac.sum(a, f);
340                        }
341                        row.set(i, fac);
342
343                        f = S.leadingExpVector();
344                        if (!e.equals(f)) {
345                            a = Ap.ring.coFac.getZERO();
346                            break;
347                        }
348                        a = S.leadingBaseCoefficient();
349                    }
350                }
351            }
352            if (!a.isZERO()) { //! mt ) { 
353                //logger.debug("irred");
354                R = R.sum(a, e);
355                S = S.reductum();
356            }
357        }
358        return R; //.abs(); // not monic if not boolean closed
359    }
360
361
362    /*
363     * -------- boolean closure stuff -----------------------------------------
364     * -------- is all in superclass
365     */
366
367}