Source code

001/*
002 * $Id: PseudoReductionPar.java 5870 2018-07-20 15:56:23Z 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.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() = " + l + ", ll = " + 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() = " + t + " ms, size() = " + 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        if (logger.isInfoEnabled()) {
209            logger.info("multiplicative factor = " + mfac);
210        }
211        pf = new PseudoReductionEntry<C>(R, mfac);
212        return pf;
213    }
214
215
216    /**
217     * Normalform with recording. <b>Note:</b> Only meaningful if all divisions
218     * are exact. Compute first the multiplication factor <code>m</code> with
219     * <code>normalform(Pp,Ap,m)</code>, then call this method with
220     * <code>normalform(row,Pp,m*Ap)</code>.
221     * @param row recording matrix, is modified.
222     * @param Pp a polynomial list for reduction.
223     * @param Ap a polynomial.
224     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
225     */
226    @SuppressWarnings("unchecked")
227    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
228                    GenPolynomial<C> Ap) {
229        throw new RuntimeException("normalform with recording not implemented");
230    }
231
232
233    /**
234     * Normalform recursive.
235     * @param Ap recursive polynomial.
236     * @param Pp recursive polynomial list.
237     * @return nf(Ap) with respect to Pp.
238     */
239    @SuppressWarnings("unchecked")
240    public GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp, GenPolynomial<GenPolynomial<C>> Ap) {
241        if (Pp == null || Pp.isEmpty()) {
242            return Ap;
243        }
244        if (Ap == null || Ap.isZERO()) {
245            return Ap;
246        }
247        GenPolynomial<GenPolynomial<C>>[] P = new GenPolynomial[0];
248        List<GenPolynomial<GenPolynomial<C>>> Ppp;
249        synchronized (Pp) {
250            Ppp = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Pp); // sic
251        }
252        P = Ppp.toArray(P);
253        int ll = Ppp.size();
254        GenPolynomial<GenPolynomial<C>> Rz = Ap.ring.getZERO();
255        GenPolynomial<GenPolynomial<C>> R = Rz.copy();
256
257        GenPolynomial<GenPolynomial<C>> S = Ap.copy();
258        while (S.length() > 0) {
259            if (Pp.size() != ll) {
260                //System.out.println("Pp.size() = " + Pp.size() + ", ll = " + ll);
261                //long t = System.currentTimeMillis();
262                synchronized (Pp) {
263                    Ppp = new ArrayList<GenPolynomial<GenPolynomial<C>>>(Pp); // sic
264                }
265                P = Ppp.toArray(P);
266                ll = Ppp.size();
267                //ll = P.length; // wrong
268                //t = System.currentTimeMillis()-t;
269                //logger.info("Pp.toArray(): size() = " + l + ", ll = " + ll);
270                S = Ap.copy(); // S.add(R)? // restart reduction ?
271                R = Rz.copy();
272            }
273            boolean mt = false;
274            Map.Entry<ExpVector, GenPolynomial<C>> m = S.leadingMonomial();
275            ExpVector e = m.getKey();
276            GenPolynomial<C> a = m.getValue();
277            ExpVector f = null;
278            int i;
279            for (i = 0; i < ll; i++) {
280                f = P[i].leadingExpVector();
281                mt = e.multipleOf(f);
282                if (mt)
283                    break;
284            }
285            if (!mt) {
286                //System.out.println("m = " + m);
287                //logger.debug("irred");
288                //R = R.sum(a, e);
289                //S = S.subtract(a, e);
290                R.doPutToMap(e, a);
291                S.doRemoveFromMap(e, a);
292                //System.out.println(" S = " + S);
293            } else {
294                f = e.subtract(f);
295                if (debug) {
296                    logger.info("red div = " + e);
297                }
298                GenPolynomial<C> c = P[i].leadingBaseCoefficient();
299                //if (a.remainder(c).isZERO()) { //c.isUnit() ) {
300                if (PolyUtil.<C> baseSparsePseudoRemainder(a,c).isZERO()) { 
301                    if (debug) {
302                        logger.info("red c = " + c);
303                    }
304                    //a = a.divide(c);
305                    GenPolynomial<C> b = PolyUtil.<C> basePseudoDivide(a,c);
306                    GenPolynomial<GenPolynomial<C>> Sp = S.subtractMultiple(b, f, P[i]);
307                    if (e.equals(Sp.leadingExpVector())) { // TODO: avoid if possible
308                        //throw new RuntimeException("degree not descending");
309                        logger.info("degree not descending: S = " + S + ", Sp = " + Sp);
310                        R = R.multiply(c);
311                        //S = S.multiply(c);
312                        Sp = S.scaleSubtractMultiple(c, a, f, P[i]);
313                    }
314                    S = Sp; 
315                } else {
316                    R = R.multiply(c);
317                    //S = S.multiply(c);
318                    S = S.scaleSubtractMultiple(c, a, f, P[i]);
319                }
320                //Q = p[i].multiply(a, f);
321                //S = S.subtract(Q);
322            }
323        }
324        return R;
325    }
326
327}