Source code

001/*
002 * $Id: SolvableReductionPar.java 5206 2015-04-05 10:33:56Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.List;
009import java.util.Map;
010
011// import org.apache.log4j.Logger;
012import edu.jas.poly.ExpVector;
013import edu.jas.poly.GenSolvablePolynomial;
014import edu.jas.structure.RingElem;
015
016
017/**
018 * Solvable polynomial Reduction parallel usable algorithm. Implements left
019 * normalform.
020 * @param <C> coefficient type
021 * @author Heinz Kredel
022 */
023
024public class SolvableReductionPar<C extends RingElem<C>> extends SolvableReductionAbstract<C> {
025
026
027    //private static final Logger logger = Logger.getLogger(SolvableReductionPar.class);
028
029
030    /**
031     * Constructor.
032     */
033    public SolvableReductionPar() {
034    }
035
036
037    /**
038     * Left Normalform.
039     * @param Ap solvable polynomial.
040     * @param Pp solvable polynomial list.
041     * @return left-nf(Ap) with respect to Pp.
042     */
043    @SuppressWarnings("cast")
044    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
045                    GenSolvablePolynomial<C> Ap) {
046        if (Pp == null || Pp.isEmpty()) {
047            return Ap;
048        }
049        if (Ap == null || Ap.isZERO()) {
050            return Ap;
051        }
052        int l;
053        Map.Entry<ExpVector, C> m;
054        GenSolvablePolynomial<C>[] P;
055        synchronized (Pp) {
056            l = Pp.size();
057            P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
058            //P = Pp.toArray();
059            for (int j = 0; j < Pp.size(); j++) {
060                P[j] = Pp.get(j);
061            }
062        }
063        ExpVector e;
064        ExpVector f = null;
065        C a;
066        boolean mt = false;
067        GenSolvablePolynomial<C> Rz = Ap.ring.getZERO().copy();
068        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
069
070        GenSolvablePolynomial<C> p = null;
071        GenSolvablePolynomial<C> Q = null;
072        GenSolvablePolynomial<C> S = Ap.copy();
073        while (S.length() > 0) {
074            if (Pp.size() != l) {
075                //long t = System.currentTimeMillis();
076                synchronized (Pp) { // required, bad in parallel
077                    l = Pp.size();
078                    P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
079                    //P = Pp.toArray();
080                    for (int i = 0; i < Pp.size(); i++) {
081                        P[i] = Pp.get(i);
082                    }
083                }
084                //t = System.currentTimeMillis()-t;
085                //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
086                S = Ap.copy(); // S.add(R)? // restart reduction ?
087                R = Rz.copy();
088            }
089            m = S.leadingMonomial();
090            e = m.getKey();
091            a = m.getValue();
092            for (int i = 0; i < P.length; i++) {
093                p = P[i];
094                f = p.leadingExpVector();
095                if (f != null) {
096                    mt = e.multipleOf(f);
097                    if (mt)
098                        break;
099                }
100            }
101            if (!mt) {
102                //logger.debug("irred");
103                //R = (GenSolvablePolynomial<C>) R.sum(a, e);
104                //S = (GenSolvablePolynomial<C>) S.subtract(a, e);
105                R.doPutToMap(e, a);
106                S.doRemoveFromMap(e, a);
107                // System.out.println(" S = " + S);
108            } else {
109                //logger.debug("red");
110                e = e.subtract(f);
111                Q = p.multiplyLeft(e);
112                a = a.divide(Q.leadingBaseCoefficient());
113                //Q = Q.multiplyLeft(a);
114                //S = (GenSolvablePolynomial<C>) S.subtract(Q);
115                S = S.subtractMultiple(a, Q);
116            }
117        }
118        return R;
119    }
120
121
122    /**
123     * LeftNormalform with recording.
124     * @param row recording matrix, is modified.
125     * @param Pp a polynomial list for reduction.
126     * @param Ap a polynomial.
127     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
128     */
129    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
130                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
131        throw new UnsupportedOperationException("normalform with recording not implemented");
132    }
133
134
135    /**
136     * Right Normalform.
137     * @param Ap solvable polynomial.
138     * @param Pp solvable polynomial list.
139     * @return right-nf(Ap) with respect to Pp.
140     */
141    @SuppressWarnings("cast")
142    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
143                    GenSolvablePolynomial<C> Ap) {
144        if (Pp == null || Pp.isEmpty()) {
145            return Ap;
146        }
147        if (Ap == null || Ap.isZERO()) {
148            return Ap;
149        }
150        int l;
151        Map.Entry<ExpVector, C> m;
152        GenSolvablePolynomial<C>[] P;
153        synchronized (Pp) {
154            l = Pp.size();
155            P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
156            //P = Pp.toArray();
157            for (int j = 0; j < Pp.size(); j++) {
158                P[j] = Pp.get(j);
159            }
160        }
161        ExpVector e;
162        ExpVector f = null;
163        C a;
164        boolean mt = false;
165        GenSolvablePolynomial<C> Rz = Ap.ring.getZERO().copy();
166        GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy();
167
168        GenSolvablePolynomial<C> p = null;
169        GenSolvablePolynomial<C> Q = null;
170        GenSolvablePolynomial<C> S = Ap.copy();
171        while (S.length() > 0) {
172            if (Pp.size() != l) {
173                //long t = System.currentTimeMillis();
174                synchronized (Pp) { // required, bad in parallel
175                    l = Pp.size();
176                    P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
177                    //P = Pp.toArray();
178                    for (int i = 0; i < Pp.size(); i++) {
179                        P[i] = Pp.get(i);
180                    }
181                }
182                //t = System.currentTimeMillis()-t;
183                //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
184                S = Ap.copy(); // S.add(R)? // restart reduction ?
185                R = Rz.copy();
186            }
187            m = S.leadingMonomial();
188            e = m.getKey();
189            a = m.getValue();
190            for (int i = 0; i < P.length; i++) {
191                p = P[i];
192                f = p.leadingExpVector();
193                if (f != null) {
194                    mt = e.multipleOf(f);
195                    if (mt)
196                        break;
197                }
198            }
199            if (!mt) {
200                //logger.debug("irred");
201                //R = (GenSolvablePolynomial<C>) R.sum(a, e);
202                //S = (GenSolvablePolynomial<C>) S.subtract(a, e);
203                R.doPutToMap(e, a);
204                S.doRemoveFromMap(e, a);
205                // System.out.println(" S = " + S);
206            } else {
207                //logger.debug("red");
208                e = e.subtract(f);
209                Q = p.multiply(e); // p * (a e) TODO
210                a = a.divide(Q.leadingBaseCoefficient());
211                Q = Q.multiply(a); // p * (e a) !!
212                S = (GenSolvablePolynomial<C>) S.subtract(Q);
213                //S = S.subtractMultiple(Q, a);
214            }
215        }
216        return R;
217    }
218
219
220    /**
221     * RightNormalform with recording.
222     * @param row recording matrix, is modified.
223     * @param Pp a polynomial list for reduction.
224     * @param Ap a polynomial.
225     * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp.
226     */
227    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row,
228                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
229        throw new UnsupportedOperationException("normalform with recording not implemented");
230    }
231
232}