001 /*
002 * $Id: PseudoReductionSeq.java 3423 2010-12-24 10:56:50Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007 import java.util.List;
008 import java.util.ArrayList;
009 import java.util.Map;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.gb.ReductionAbstract;
014 import edu.jas.poly.ExpVector;
015 import edu.jas.poly.GenPolynomial;
016
017 import edu.jas.structure.RingElem;
018
019
020 /**
021 * Polynomial pseudo reduction sequential use algorithm.
022 * Coefficients of polynomials must not be from a field,
023 * i.e. the fraction free reduction is implemented.
024 * Implements normalform.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 */
028
029 public class PseudoReductionSeq<C extends RingElem<C>>
030 extends ReductionAbstract<C>
031 implements PseudoReduction<C> {
032
033 private static final Logger logger = Logger.getLogger(PseudoReductionSeq.class);
034
035
036 /**
037 * Constructor.
038 */
039 public PseudoReductionSeq() {
040 }
041
042
043 /**
044 * Normalform.
045 * @param Ap polynomial.
046 * @param Pp polynomial list.
047 * @return nf(Ap) with respect to Pp.
048 */
049 @SuppressWarnings("unchecked")
050 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp,
051 GenPolynomial<C> Ap) {
052 if ( Pp == null || Pp.isEmpty() ) {
053 return Ap;
054 }
055 if ( Ap == null || Ap.isZERO() ) {
056 return Ap;
057 }
058 Map.Entry<ExpVector,C> m;
059 int l;
060 GenPolynomial<C>[] P;
061 synchronized (Pp) {
062 l = Pp.size();
063 P = new GenPolynomial[l];
064 //P = Pp.toArray();
065 for ( int i = 0; i < Pp.size(); i++ ) {
066 P[i] = Pp.get(i);
067 }
068 }
069 ExpVector[] htl = new ExpVector[ l ];
070 Object[] lbc = new Object[ l ]; // want C[]
071 GenPolynomial<C>[] p = new GenPolynomial[ l ];
072 int i;
073 int j = 0;
074 for ( i = 0; i < l; i++ ) {
075 if ( P[i] == null ) {
076 continue;
077 }
078 p[i] = P[i];
079 m = p[i].leadingMonomial();
080 if ( m != null ) {
081 p[j] = p[i];
082 htl[j] = m.getKey();
083 lbc[j] = m.getValue();
084 j++;
085 }
086 }
087 l = j;
088 ExpVector e;
089 C a;
090 boolean mt = false;
091 GenPolynomial<C> R = Ap.ring.getZERO();
092
093 //GenPolynomial<C> T = null;
094 GenPolynomial<C> Q = null;
095 GenPolynomial<C> S = Ap;
096 while ( S.length() > 0 ) {
097 m = S.leadingMonomial();
098 e = m.getKey();
099 a = m.getValue();
100 for ( i = 0; i < l; i++ ) {
101 mt = e.multipleOf( htl[i] );
102 if ( mt ) break;
103 }
104 if ( ! mt ) {
105 //logger.debug("irred");
106 //T = new OrderedMapPolynomial( a, e );
107 R = R.sum( a, e );
108 S = S.subtract( a, e );
109 // System.out.println(" S = " + S);
110 } else {
111 e = e.subtract( htl[i] );
112 //logger.info("red div = " + e);
113 C c = (C) lbc[i];
114 if ( a.remainder(c).isZERO() ) { //c.isUnit() ) {
115 a = a.divide( c );
116 } else {
117 S = S.multiply( c );
118 R = R.multiply( c );
119 }
120 Q = p[i].multiply( a, e );
121 S = S.subtract( Q );
122 }
123 }
124 return R;
125 }
126
127
128 /**
129 * Normalform.
130 * @param Pp polynomial list.
131 * @param Ap polynomial.
132 * @return ( nf(Ap), mf ) with respect to Pp and
133 mf as multiplication factor for Ap.
134 */
135 @SuppressWarnings("unchecked")
136 public PseudoReductionEntry<C> normalformFactor(
137 List<GenPolynomial<C>> Pp,
138 GenPolynomial<C> Ap) {
139 if ( Ap == null ) {
140 return null;
141 }
142 C mfac = Ap.ring.getONECoefficient();
143 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
144 if ( Pp == null || Pp.isEmpty() ) {
145 return pf;
146 }
147 if ( Ap.isZERO() ) {
148 return pf;
149 }
150 Map.Entry<ExpVector,C> m;
151 int l;
152 GenPolynomial<C>[] P;
153 synchronized (Pp) {
154 l = Pp.size();
155 P = new GenPolynomial[l];
156 //P = Pp.toArray();
157 for ( int i = 0; i < Pp.size(); i++ ) {
158 P[i] = Pp.get(i);
159 }
160 }
161 ExpVector[] htl = new ExpVector[ l ];
162 Object[] lbc = new Object[ l ]; // want C[]
163 GenPolynomial<C>[] p = new GenPolynomial[ l ];
164 int i;
165 int j = 0;
166 for ( i = 0; i < l; i++ ) {
167 if ( P[i] == null ) {
168 continue;
169 }
170 p[i] = P[i];
171 m = p[i].leadingMonomial();
172 if ( m != null ) {
173 p[j] = p[i];
174 htl[j] = m.getKey();
175 lbc[j] = m.getValue();
176 j++;
177 }
178 }
179 l = j;
180 ExpVector e;
181 C a;
182 boolean mt = false;
183 GenPolynomial<C> R = Ap.ring.getZERO();
184
185 //GenPolynomial<C> T = null;
186 GenPolynomial<C> Q = null;
187 GenPolynomial<C> S = Ap;
188 while ( S.length() > 0 ) {
189 m = S.leadingMonomial();
190 e = m.getKey();
191 a = m.getValue();
192 for ( i = 0; i < l; i++ ) {
193 mt = e.multipleOf( htl[i] );
194 if ( mt ) break;
195 }
196 if ( ! mt ) {
197 //logger.debug("irred");
198 //T = new OrderedMapPolynomial( a, e );
199 R = R.sum( a, e );
200 S = S.subtract( a, e );
201 // System.out.println(" S = " + S);
202 } else {
203 e = e.subtract( htl[i] );
204 //logger.info("red div = " + e);
205 C c = (C) lbc[i];
206 if ( a.remainder(c).isZERO() ) { //c.isUnit() ) {
207 a = a.divide( c );
208 } else {
209 S = S.multiply( c );
210 R = R.multiply( c );
211 mfac = mfac.multiply( c );
212 }
213 Q = p[i].multiply( a, e );
214 S = S.subtract( Q );
215 }
216 }
217 pf = new PseudoReductionEntry<C>(R, mfac);
218 return pf;
219 }
220
221
222 /**
223 * Normalform with recording.
224 * <b>Note:</b> Only meaningfull if all divisions are exact.
225 * Compute first the multiplication factor <code>m</code>
226 * with <code>normalform(Pp,Ap,m)</code>,
227 * then call this method with <code>normalform(row,Pp,m*Ap)</code>.
228 * @param row recording matrix, is modified.
229 * @param Pp a polynomial list for reduction.
230 * @param Ap a polynomial.
231 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
232 */
233 @SuppressWarnings("unchecked")
234 public GenPolynomial<C>
235 normalform(List<GenPolynomial<C>> row,
236 List<GenPolynomial<C>> Pp,
237 GenPolynomial<C> Ap) {
238 if ( Pp == null || Pp.isEmpty() ) {
239 return Ap;
240 }
241 if ( Ap == null || Ap.isZERO() ) {
242 return Ap;
243 }
244 int l = Pp.size();
245 GenPolynomial<C>[] P = new GenPolynomial[l];
246 synchronized (Pp) {
247 //P = Pp.toArray();
248 for ( int i = 0; i < Pp.size(); i++ ) {
249 P[i] = Pp.get(i);
250 }
251 }
252 ExpVector[] htl = new ExpVector[ l ];
253 Object[] lbc = new Object[ l ]; // want C
254 GenPolynomial<C>[] p = new GenPolynomial[ l ];
255 Map.Entry<ExpVector,C> m;
256 int j = 0;
257 int i;
258 for ( i = 0; i < l; i++ ) {
259 p[i] = P[i];
260 m = p[i].leadingMonomial();
261 if ( m != null ) {
262 p[j] = p[i];
263 htl[j] = m.getKey();
264 lbc[j] = m.getValue();
265 j++;
266 }
267 }
268 l = j;
269 ExpVector e;
270 C a;
271 boolean mt = false;
272 GenPolynomial<C> zero = Ap.ring.getZERO();
273 GenPolynomial<C> R = Ap.ring.getZERO();
274 GenPolynomial<C> fac = null;
275 // GenPolynomial<C> T = null;
276 GenPolynomial<C> Q = null;
277 GenPolynomial<C> S = Ap;
278 while ( S.length() > 0 ) {
279 m = S.leadingMonomial();
280 e = m.getKey();
281 a = m.getValue();
282 for ( i = 0; i < l; i++ ) {
283 mt = e.multipleOf( htl[i] );
284 if ( mt ) break;
285 }
286 if ( ! mt ) {
287 //logger.debug("irred");
288 R = R.sum( a, e );
289 S = S.subtract( a, e );
290 // System.out.println(" S = " + S);
291 //throw new RuntimeException("Syzygy no GB");
292 } else {
293 e = e.subtract( htl[i] );
294 //logger.info("red div = " + e);
295 C c = (C) lbc[i];
296 if ( a.remainder(c).isZERO() ) { //c.isUnit() ) {
297 a = a.divide( c );
298 //System.out.print("|");
299 } else {
300 //System.out.print("*");
301 S = S.multiply( c );
302 R = R.multiply( c );
303 }
304 Q = p[i].multiply( a, e );
305 S = S.subtract( Q );
306 fac = row.get(i);
307 if ( fac == null ) {
308 fac = zero.sum( a, e );
309 } else {
310 fac = fac.sum( a, e );
311 }
312 row.set(i,fac);
313 }
314 }
315 return R;
316 }
317
318 }