001/*
002 * $Id: SolvableReductionPar.java 4104 2012-08-18 10:00:59Z kredel $
003 */
004
005package edu.jas.gb;
006
007import java.util.List;
008import java.util.Map;
009
010//import org.apache.log4j.Logger;
011
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.
019 * Implements left normalform.
020 * @param <C> coefficient type
021 * @author Heinz Kredel
022 */
023
024public class SolvableReductionPar<C extends RingElem<C>>
025             extends SolvableReductionAbstract<C> {
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("unchecked")
044    public GenSolvablePolynomial<C> 
045           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();
069        GenSolvablePolynomial<C> R = Ap.ring.getZERO();
070
071        GenSolvablePolynomial<C> p = null;
072        GenSolvablePolynomial<C> Q = null;
073        GenSolvablePolynomial<C> S = Ap;
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() = " + t + " ms, size() = " + l);
087                 S = Ap; // S.add(R)? // restart reduction ?
088                 R = Rz; 
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 ) 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                 // System.out.println(" S = " + S);
106              } else { 
107                 //logger.debug("red");
108                 e =  e.subtract( f );
109                 Q = p.multiplyLeft( e );
110                 a = a.divide( Q.leadingBaseCoefficient() );
111                 Q = Q.multiplyLeft( a );
112                 S = (GenSolvablePolynomial<C>)S.subtract( Q );
113              }
114        }
115        return R;
116    }
117
118
119    /**
120     * LeftNormalform with recording.
121     * @param row recording matrix, is modified.
122     * @param Pp a polynomial list for reduction.
123     * @param Ap a polynomial.
124     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
125     */
126    public GenSolvablePolynomial<C> 
127           leftNormalform(List<GenSolvablePolynomial<C>> row,
128                          List<GenSolvablePolynomial<C>> Pp, 
129                          GenSolvablePolynomial<C> Ap) {  
130        throw new UnsupportedOperationException("normalform with recording not implemented");
131    }
132
133
134    /**
135     * Right Normalform.
136     * @param Ap solvable polynomial.
137     * @param Pp solvable polynomial list.
138     * @return right-nf(Ap) with respect to Pp.
139     */
140    @SuppressWarnings("unchecked")
141    public GenSolvablePolynomial<C> 
142           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();
166        GenSolvablePolynomial<C> R = Ap.ring.getZERO();
167
168        GenSolvablePolynomial<C> p = null;
169        GenSolvablePolynomial<C> Q = null;
170        GenSolvablePolynomial<C> S = Ap;
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; // S.add(R)? // restart reduction ?
185                 R = Rz; 
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 ) break; 
196                  }
197              }
198              if ( ! mt ) { 
199                 //logger.debug("irred");
200                 R = (GenSolvablePolynomial<C>)R.sum( a, e );
201                 S = (GenSolvablePolynomial<C>)S.subtract( a, e ); 
202                 // System.out.println(" S = " + S);
203              } else { 
204                 //logger.debug("red");
205                 e =  e.subtract( f );
206                 Q = p.multiply( e );
207                 a = a.divide( Q.leadingBaseCoefficient() );
208                 Q = Q.multiply( a );
209                 S = (GenSolvablePolynomial<C>)S.subtract( Q );
210              }
211        }
212        return R;
213    }
214
215}