Source code

001/*
002 * $Id: PseudoReductionPar.java 4973 2014-10-22 21:50:34Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.gb.ReductionAbstract;
015import edu.jas.poly.PolyUtil;
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
023 * polynomials must not be from a field, i.e. the fraction free reduction is
024 * implemented. Implements normalform.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 */
028
029public class PseudoReductionPar<C extends RingElem<C>> extends ReductionAbstract<C> implements
030                PseudoReduction<C> {
031
032
033    private static final Logger logger = Logger.getLogger(PseudoReductionPar.class);
034
035
036    private final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Constructor.
041     */
042    public PseudoReductionPar() {
043    }
044
045
046    /**
047     * Normalform.
048     * @param Ap polynomial.
049     * @param Pp polynomial list.
050     * @return nf(Ap) with respect to Pp.
051     */
052    @SuppressWarnings("unchecked")
053    public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
054        if (Pp == null || Pp.isEmpty()) {
055            return Ap;
056        }
057        if (Ap == null || Ap.isZERO()) {
058            return Ap;
059        }
060        GenPolynomial<C>[] P = new GenPolynomial[0];
061        List<GenPolynomial<C>> Ppp;
062        synchronized (Pp) {
063            Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
064        }
065        P = Ppp.toArray(P);
066        int ll = Ppp.size();
067        GenPolynomial<C> Rz = Ap.ring.getZERO();
068        GenPolynomial<C> R = Rz.copy();
069
070        GenPolynomial<C> S = Ap.copy();
071        while (S.length() > 0) {
072            if (Pp.size() != ll) {
073                //System.out.println("Pp.size() = " + Pp.size() + ", ll = " + ll);
074                //long t = System.currentTimeMillis();
075                synchronized (Pp) {
076                    Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
077                }
078                P = Ppp.toArray(P);
079                ll = Ppp.size();
080                //ll = P.length; // wrong
081                //t = System.currentTimeMillis()-t;
082                //logger.info("Pp.toArray(): size() = " + l + ", ll = " + ll);
083                S = Ap.copy(); // S.add(R)? // restart reduction ?
084                R = Rz.copy();
085            }
086            boolean mt = false;
087            Map.Entry<ExpVector, C> m = S.leadingMonomial();
088            ExpVector e = m.getKey();
089            C a = m.getValue();
090            ExpVector f = null;
091            int i;
092            for (i = 0; i < ll; i++) {
093                f = P[i].leadingExpVector();
094                mt = e.multipleOf(f);
095                if (mt)
096                    break;
097            }
098            if (!mt) {
099                //System.out.println("m = " + m);
100                //logger.debug("irred");
101                //R = R.sum(a, e);
102                //S = S.subtract(a, e);
103                R.doPutToMap(e, a);
104                S.doRemoveFromMap(e, a);
105                //System.out.println(" S = " + S);
106            } else {
107                e = e.subtract(f);
108                //logger.info("red div = " + e);
109                C c = P[i].leadingBaseCoefficient();
110                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
111                    a = a.divide(c);
112                    S = S.subtractMultiple(a, e, P[i]);
113                } else {
114                    R = R.multiply(c);
115                    //S = S.multiply(c);
116                    S = S.scaleSubtractMultiple(c, a, e, P[i]);
117                }
118                //Q = p[i].multiply(a, e);
119                //S = S.subtract(Q);
120            }
121        }
122        return R;
123    }
124
125
126    /**
127     * Normalform.
128     * @param Pp polynomial list.
129     * @param Ap polynomial.
130     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
131     *         for Ap.
132     */
133    @SuppressWarnings("unchecked")
134    public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
135        if (Ap == null) {
136            return null;
137        }
138        C mfac = Ap.ring.getONECoefficient();
139        PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
140        if (Pp == null || Pp.isEmpty()) {
141            return pf;
142        }
143        if (Ap.isZERO()) {
144            return pf;
145        }
146        GenPolynomial<C>[] P = new GenPolynomial[0];
147        List<GenPolynomial<C>> Ppp;
148        synchronized (Pp) {
149            Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic
150        }
151        P = Ppp.toArray(P);
152        int l = Ppp.size();
153        boolean mt = false;
154        GenPolynomial<C> Rz = Ap.ring.getZERO();
155        GenPolynomial<C> R = Rz.copy();
156        //GenPolynomial<C> T = null;
157        //GenPolynomial<C> Q = null;
158        GenPolynomial<C> S = Ap.copy();
159        while (S.length() > 0) {
160            if (Pp.size() != l) {
161                //long t = System.currentTimeMillis();
162                synchronized (Pp) {
163                    Ppp = new ArrayList<GenPolynomial<C>>(Pp);
164                }
165                P = Ppp.toArray(P);
166                l = Ppp.size();
167                //t = System.currentTimeMillis()-t;
168                //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
169                S = Ap.copy(); // S.add(R)? // restart reduction ?
170                R = Rz.copy();
171            }
172            Map.Entry<ExpVector, C> m = S.leadingMonomial();
173            ExpVector e = m.getKey();
174            C a = m.getValue();
175            ExpVector f = null;
176            int i;
177            for (i = 0; i < l; i++) {
178                f = P[i].leadingExpVector();
179                mt = e.multipleOf(f);
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(f);
192                //logger.info("red div = " + e);
193                C c = P[i].leadingBaseCoefficient();
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        throw new RuntimeException("normalform with recording not implemented");
229    }
230
231
232    /**
233     * Normalform recursive.
234     * @param Ap recursive polynomial.
235     * @param Pp recursive polynomial list.
236     * @return nf(Ap) with respect to Pp.
237     */
238    @SuppressWarnings("unchecked")
239    public GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp, GenPolynomial<GenPolynomial<C>> Ap) {
240        if (Pp == null || Pp.isEmpty()) {
241            return Ap;
242        }
243        if (Ap == null || Ap.isZERO()) {
244            return Ap;
245        }
246        GenPolynomial<GenPolynomial<C>>[] P = new GenPolynomial[0];
247        List<GenPolynomial<GenPolynomial<C>>> Ppp;
248        synchronized (Pp) {
249            Ppp = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Pp); // sic
250        }
251        P = Ppp.toArray(P);
252        int ll = Ppp.size();
253        GenPolynomial<GenPolynomial<C>> Rz = Ap.ring.getZERO();
254        GenPolynomial<GenPolynomial<C>> R = Rz.copy();
255
256        GenPolynomial<GenPolynomial<C>> S = Ap.copy();
257        while (S.length() > 0) {
258            if (Pp.size() != ll) {
259                //System.out.println("Pp.size() = " + Pp.size() + ", ll = " + ll);
260                //long t = System.currentTimeMillis();
261                synchronized (Pp) {
262                    Ppp = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Pp); // sic
263                }
264                P = Ppp.toArray(P);
265                ll = Ppp.size();
266                //ll = P.length; // wrong
267                //t = System.currentTimeMillis()-t;
268                //logger.info("Pp.toArray(): size() = " + l + ", ll = " + ll);
269                S = Ap.copy(); // S.add(R)? // restart reduction ?
270                R = Rz.copy();
271            }
272            boolean mt = false;
273            Map.Entry<ExpVector, GenPolynomial<C>> m = S.leadingMonomial();
274            ExpVector e = m.getKey();
275            GenPolynomial<C> a = m.getValue();
276            ExpVector f = null;
277            int i;
278            for (i = 0; i < ll; i++) {
279                f = P[i].leadingExpVector();
280                mt = e.multipleOf(f);
281                if (mt)
282                    break;
283            }
284            if (!mt) {
285                //System.out.println("m = " + m);
286                //logger.debug("irred");
287                //R = R.sum(a, e);
288                //S = S.subtract(a, e);
289                R.doPutToMap(e, a);
290                S.doRemoveFromMap(e, a);
291                //System.out.println(" S = " + S);
292            } else {
293                f = e.subtract(f);
294                if (debug) {
295                    logger.info("red div = " + e);
296                }
297                GenPolynomial<C> c = P[i].leadingBaseCoefficient();
298                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
299                if (PolyUtil.<C> baseSparsePseudoRemainder(a,c).isZERO()) { 
300                    if (debug) {
301                        logger.info("red c = " + c);
302                    }
303                    //a = a.divide(c);
304                    GenPolynomial<C> b = PolyUtil.<C> basePseudoDivide(a,c);
305                    GenPolynomial<GenPolynomial<C>> Sp = S.subtractMultiple(b, f, P[i]);
306                    if (e.equals(Sp.leadingExpVector())) { // TODO: avoid
307                        //throw new RuntimeException("degree not descending");
308                        logger.info("degree not descending: S = " + S + ", Sp = " + Sp);
309                        R = R.multiply(c);
310                        //S = S.multiply(c);
311                        Sp = S.scaleSubtractMultiple(c, a, f, P[i]);
312                    }
313                    S = Sp; 
314                } else {
315                    R = R.multiply(c);
316                    //S = S.multiply(c);
317                    S = S.scaleSubtractMultiple(c, a, f, P[i]);
318                }
319                //Q = p[i].multiply(a, f);
320                //S = S.subtract(Q);
321            }
322        }
323        return R;
324    }
325
326}