Source code

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