001 /*
002 * $Id: SolvableReductionPar.java 3288 2010-08-25 21:46:14Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.List;
008 import java.util.Map;
009
010 //import org.apache.log4j.Logger;
011
012 import edu.jas.poly.ExpVector;
013 import edu.jas.poly.GenSolvablePolynomial;
014 import 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
024 public 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 public GenSolvablePolynomial<C>
044 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();
068 GenSolvablePolynomial<C> R = Ap.ring.getZERO();
069
070 GenSolvablePolynomial<C> p = null;
071 GenSolvablePolynomial<C> Q = null;
072 GenSolvablePolynomial<C> S = Ap;
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; // S.add(R)? // restart reduction ?
087 R = Rz;
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 ) break;
098 }
099 }
100 if ( ! mt ) {
101 //logger.debug("irred");
102 R = (GenSolvablePolynomial<C>)R.sum( a, e );
103 S = (GenSolvablePolynomial<C>)S.subtract( a, e );
104 // System.out.println(" S = " + S);
105 } else {
106 //logger.debug("red");
107 e = e.subtract( f );
108 Q = p.multiplyLeft( e );
109 a = a.divide( Q.leadingBaseCoefficient() );
110 Q = Q.multiplyLeft( a );
111 S = (GenSolvablePolynomial<C>)S.subtract( Q );
112 }
113 }
114 return R;
115 }
116
117
118 /**
119 * LeftNormalform with recording.
120 * @param row recording matrix, is modified.
121 * @param Pp a polynomial list for reduction.
122 * @param Ap a polynomial.
123 * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
124 */
125 public GenSolvablePolynomial<C>
126 leftNormalform(List<GenSolvablePolynomial<C>> row,
127 List<GenSolvablePolynomial<C>> Pp,
128 GenSolvablePolynomial<C> Ap) {
129 throw new UnsupportedOperationException("normalform with recording not implemented");
130 }
131
132
133 /**
134 * Right Normalform.
135 * @param Ap solvable polynomial.
136 * @param Pp solvable polynomial list.
137 * @return right-nf(Ap) with respect to Pp.
138 */
139 public GenSolvablePolynomial<C>
140 rightNormalform(List<GenSolvablePolynomial<C>> Pp,
141 GenSolvablePolynomial<C> Ap) {
142 if ( Pp == null || Pp.isEmpty() ) {
143 return Ap;
144 }
145 if ( Ap == null || Ap.isZERO() ) {
146 return Ap;
147 }
148 int l;
149 Map.Entry<ExpVector,C> m;
150 GenSolvablePolynomial<C>[] P;
151 synchronized (Pp) {
152 l = Pp.size();
153 P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
154 //P = Pp.toArray();
155 for ( int j = 0; j < Pp.size(); j++ ) {
156 P[j] = Pp.get(j);
157 }
158 }
159 ExpVector e;
160 ExpVector f = null;
161 C a;
162 boolean mt = false;
163 GenSolvablePolynomial<C> Rz = Ap.ring.getZERO();
164 GenSolvablePolynomial<C> R = Ap.ring.getZERO();
165
166 GenSolvablePolynomial<C> p = null;
167 GenSolvablePolynomial<C> Q = null;
168 GenSolvablePolynomial<C> S = Ap;
169 while ( S.length() > 0 ) {
170 if ( Pp.size() != l ) {
171 //long t = System.currentTimeMillis();
172 synchronized (Pp) { // required, bad in parallel
173 l = Pp.size();
174 P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[ l ];
175 //P = Pp.toArray();
176 for ( int i = 0; i < Pp.size(); i++ ) {
177 P[i] = Pp.get(i);
178 }
179 }
180 //t = System.currentTimeMillis()-t;
181 //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
182 S = Ap; // S.add(R)? // restart reduction ?
183 R = Rz;
184 }
185 m = S.leadingMonomial();
186 e = m.getKey();
187 a = m.getValue();
188 for ( int i = 0; i < P.length ; i++ ) {
189 p = P[i];
190 f = p.leadingExpVector();
191 if ( f != null ) {
192 mt = e.multipleOf( f );
193 if ( mt ) break;
194 }
195 }
196 if ( ! mt ) {
197 //logger.debug("irred");
198 R = (GenSolvablePolynomial<C>)R.sum( a, e );
199 S = (GenSolvablePolynomial<C>)S.subtract( a, e );
200 // System.out.println(" S = " + S);
201 } else {
202 //logger.debug("red");
203 e = e.subtract( f );
204 Q = p.multiply( e );
205 a = a.divide( Q.leadingBaseCoefficient() );
206 Q = Q.multiply( a );
207 S = (GenSolvablePolynomial<C>)S.subtract( Q );
208 }
209 }
210 return R;
211 }
212
213 }