Source code

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