Source code

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