Source code

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