Source code

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