Source code

001/*
002 * $Id: PseudoReductionSeq.java 4290 2012-11-04 14:47:45Z 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.gb.ReductionAbstract;
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
021 * polynomials must not be from a field, i.e. the fraction free reduction is
022 * implemented. Implements normalform.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class PseudoReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements
028                PseudoReduction<C> {
029
030
031    private static final Logger logger = Logger.getLogger(PseudoReductionSeq.class);
032
033
034    /**
035     * Constructor.
036     */
037    public PseudoReductionSeq() {
038    }
039
040
041    /**
042     * Normalform.
043     * @param Ap polynomial.
044     * @param Pp polynomial list.
045     * @return nf(Ap) with respect to Pp.
046     */
047    @SuppressWarnings("unchecked")
048    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
049        if (Pp == null || Pp.isEmpty()) {
050            return Ap;
051        }
052        if (Ap == null || Ap.isZERO()) {
053            return Ap;
054        }
055        Map.Entry<ExpVector, C> m;
056        GenPolynomial<C>[] P = new GenPolynomial[0];
057        synchronized (Pp) {
058            P = Pp.toArray(P);
059        }
060        int l = P.length;
061        ExpVector[] htl = new ExpVector[l];
062        C[] lbc = (C[]) new RingElem[l];
063        GenPolynomial<C>[] p = new GenPolynomial[l];
064        int i;
065        int j = 0;
066        for (i = 0; i < l; i++) {
067            if (P[i] == null) {
068                continue;
069            }
070            p[i] = P[i];
071            m = p[i].leadingMonomial();
072            if (m != null) {
073                p[j] = p[i];
074                htl[j] = m.getKey();
075                lbc[j] = m.getValue();
076                j++;
077            }
078        }
079        l = j;
080        ExpVector e;
081        C a;
082        boolean mt = false;
083        GenPolynomial<C> R = Ap.ring.getZERO().copy();
084
085        GenPolynomial<C> S = Ap.copy();
086        while (S.length() > 0) {
087            m = S.leadingMonomial();
088            e = m.getKey();
089            a = m.getValue();
090            for (i = 0; i < l; i++) {
091                mt = e.multipleOf(htl[i]);
092                if (mt)
093                    break;
094            }
095            if (!mt) {
096                //logger.debug("irred");
097                //R = R.sum(a, e);
098                //S = S.subtract(a, e);
099                R.doPutToMap(e, a);
100                S.doRemoveFromMap(e, a);
101                //System.out.println(" S = " + S);
102            } else {
103                e = e.subtract(htl[i]);
104                //logger.info("red div = " + e);
105                @SuppressWarnings("cast")
106                C c = (C) lbc[i];
107                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
108                    a = a.divide(c);
109                    S = S.subtractMultiple(a, e, p[i]);
110                } else {
111                    R = R.multiply(c);
112                    //S = S.multiply(c);
113                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
114                }
115                //Q = p[i].multiply(a, e);
116                //S = S.subtract(Q);
117            }
118        }
119        return R;
120    }
121
122
123    /**
124     * Normalform.
125     * @param Pp polynomial list.
126     * @param Ap polynomial.
127     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
128     *         for Ap.
129     */
130    @SuppressWarnings("unchecked")
131    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
132        if (Ap == null) {
133            return null;
134        }
135        C mfac = Ap.ring.getONECoefficient();
136        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
137        if (Pp == null || Pp.isEmpty()) {
138            return pf;
139        }
140        if (Ap.isZERO()) {
141            return pf;
142        }
143        Map.Entry<ExpVector, C> m;
144        GenPolynomial<C>[] P = new GenPolynomial[0];
145        synchronized (Pp) {
146            P = Pp.toArray(P);
147        }
148        int l = P.length;
149        ExpVector[] htl = new ExpVector[l];
150        C[] lbc = (C[]) new RingElem[l]; // want C[] 
151        GenPolynomial<C>[] p = new GenPolynomial[l];
152        int i;
153        int j = 0;
154        for (i = 0; i < l; i++) {
155            if (P[i] == null) {
156                continue;
157            }
158            p[i] = P[i];
159            m = p[i].leadingMonomial();
160            if (m != null) {
161                p[j] = p[i];
162                htl[j] = m.getKey();
163                lbc[j] = m.getValue();
164                j++;
165            }
166        }
167        l = j;
168        ExpVector e;
169        C a;
170        boolean mt = false;
171        GenPolynomial<C> R = Ap.ring.getZERO().copy();
172
173        GenPolynomial<C> S = Ap.copy();
174        while (S.length() > 0) {
175            m = S.leadingMonomial();
176            e = m.getKey();
177            a = m.getValue();
178            for (i = 0; i < l; i++) {
179                mt = e.multipleOf(htl[i]);
180                if (mt)
181                    break;
182            }
183            if (!mt) {
184                //logger.debug("irred");
185                //R = R.sum(a, e);
186                //S = S.subtract(a, e);
187                R.doPutToMap(e, a);
188                S.doRemoveFromMap(e, a);
189                //System.out.println(" S = " + S);
190            } else {
191                e = e.subtract(htl[i]);
192                //logger.info("red div = " + e);
193                C c = lbc[i];
194                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
195                    a = a.divide(c);
196                    S = S.subtractMultiple(a, e, p[i]);
197                } else {
198                    mfac = mfac.multiply(c);
199                    R = R.multiply(c);
200                    //S = S.multiply(c);
201                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
202                }
203                //Q = p[i].multiply(a, e);
204                //S = S.subtract(Q);
205            }
206        }
207        if (logger.isInfoEnabled()) {
208            logger.info("multiplicative factor = " + mfac);
209        }
210        pf = new PseudoReductionEntry<C>(R, mfac);
211        return pf;
212    }
213
214
215    /**
216     * Normalform with recording. <b>Note:</b> Only meaningful if all divisions
217     * are exact. Compute first the multiplication factor <code>m</code> with
218     * <code>normalform(Pp,Ap,m)</code>, then call this method with
219     * <code>normalform(row,Pp,m*Ap)</code>.
220     * @param row recording matrix, is modified.
221     * @param Pp a polynomial list for reduction.
222     * @param Ap a polynomial.
223     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
224     */
225    @SuppressWarnings("unchecked")
226    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
227                    GenPolynomial<C> Ap) {
228        if (Pp == null || Pp.isEmpty()) {
229            return Ap;
230        }
231        if (Ap == null || Ap.isZERO()) {
232            return Ap;
233        }
234        GenPolynomial<C>[] P = new GenPolynomial[0];
235        synchronized (Pp) {
236            P = Pp.toArray(P);
237        }
238        int l = P.length;
239        ExpVector[] htl = new ExpVector[l];
240        Object[] lbc = new Object[l]; // want C 
241        GenPolynomial<C>[] p = new GenPolynomial[l];
242        Map.Entry<ExpVector, C> m;
243        int j = 0;
244        int i;
245        for (i = 0; i < l; i++) {
246            p[i] = P[i];
247            m = p[i].leadingMonomial();
248            if (m != null) {
249                p[j] = p[i];
250                htl[j] = m.getKey();
251                lbc[j] = m.getValue();
252                j++;
253            }
254        }
255        l = j;
256        ExpVector e;
257        C a;
258        boolean mt = false;
259        GenPolynomial<C> zero = Ap.ring.getZERO();
260        GenPolynomial<C> R = Ap.ring.getZERO().copy();
261        GenPolynomial<C> fac = null;
262        GenPolynomial<C> S = Ap.copy();
263        while (S.length() > 0) {
264            m = S.leadingMonomial();
265            e = m.getKey();
266            a = m.getValue();
267            for (i = 0; i < l; i++) {
268                mt = e.multipleOf(htl[i]);
269                if (mt)
270                    break;
271            }
272            if (!mt) {
273                //logger.debug("irred");
274                //R = R.sum(a, e);
275                //S = S.subtract(a, e);
276                R.doPutToMap(e, a);
277                S.doRemoveFromMap(e, a);
278                // System.out.println(" S = " + S);
279                //throw new RuntimeException("Syzygy no GB");
280            } else {
281                e = e.subtract(htl[i]);
282                //logger.info("red div = " + e);
283                C c = (C) lbc[i];
284                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
285                    a = a.divide(c);
286                    S = S.subtractMultiple(a, e, p[i]);
287                    //System.out.print("|");
288                } else {
289                    //System.out.print("*");
290                    R = R.multiply(c);
291                    //S = S.multiply(c);
292                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
293                }
294                //Q = p[i].multiply(a, e);
295                //S = S.subtract(Q);
296                fac = row.get(i);
297                if (fac == null) {
298                    fac = zero.sum(a, e);
299                } else {
300                    fac = fac.sum(a, e);
301                }
302                row.set(i, fac);
303            }
304        }
305        return R;
306    }
307
308}