001 /*
002 * $Id: SquarefreeRingChar0.java 3297 2010-08-26 19:09:03Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.Map;
011 import java.util.SortedMap;
012 import java.util.TreeMap;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.poly.PolyUtil;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.structure.RingFactory;
021
022
023 /**
024 * Squarefree decomposition for coefficient rings of characteristic 0.
025 * @author Heinz Kredel
026 */
027
028 public class SquarefreeRingChar0<C extends GcdRingElem<C>> extends SquarefreeAbstract<C> /*implements Squarefree<C>*/{
029
030
031 private static final Logger logger = Logger.getLogger(SquarefreeRingChar0.class);
032
033
034 private final boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Factory for ring of characteristic 0 coefficients.
039 */
040 protected final RingFactory<C> coFac;
041
042
043 /**
044 * Constructor.
045 */
046 public SquarefreeRingChar0(RingFactory<C> fac) {
047 super( GCDFactory.<C> getProxy(fac) );
048 if (fac.isField()) {
049 throw new IllegalArgumentException("fac is a field: use SquarefreeFieldChar0");
050 }
051 if (fac.characteristic().signum() != 0) {
052 throw new IllegalArgumentException("characterisic(fac) must be zero");
053 }
054 coFac = fac;
055 }
056
057
058 /**
059 * Get the String representation.
060 * @see java.lang.Object#toString()
061 */
062 @Override
063 public String toString() {
064 return getClass().getName() + " with " + engine + " over " + coFac;
065 }
066
067
068 /**
069 * GenPolynomial polynomial greatest squarefree divisor.
070 * @param P GenPolynomial.
071 * @return squarefree(pp(P)).
072 */
073 @Override
074 public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) {
075 if (P == null || P.isZERO()) {
076 return P;
077 }
078 GenPolynomialRing<C> pfac = P.ring;
079 if (pfac.nvar > 1) {
080 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
081 }
082 GenPolynomial<C> pp = engine.basePrimitivePart(P);
083 if (pp.isConstant()) {
084 return pp;
085 }
086 GenPolynomial<C> d = PolyUtil.<C> baseDeriviative(pp);
087 d = engine.basePrimitivePart(d);
088 GenPolynomial<C> g = engine.baseGcd(pp, d);
089 g = engine.basePrimitivePart(g);
090 GenPolynomial<C> q = PolyUtil.<C> basePseudoDivide(pp, g);
091 q = engine.basePrimitivePart(q);
092 return q;
093 }
094
095
096 /**
097 * GenPolynomial polynomial squarefree factorization.
098 * @param A GenPolynomial.
099 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
100 * and p_i squarefree.
101 */
102 @Override
103 public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) {
104 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
105 if (A == null || A.isZERO()) {
106 return sfactors;
107 }
108 if (A.isConstant()) {
109 sfactors.put(A, 1L);
110 return sfactors;
111 }
112 GenPolynomialRing<C> pfac = A.ring;
113 if (pfac.nvar > 1) {
114 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
115 }
116 C ldbcf = A.leadingBaseCoefficient();
117 if (!ldbcf.isONE()) {
118 C cc = engine.baseContent(A);
119 A = A.divide(cc);
120 GenPolynomial<C> f1 = pfac.getONE().multiply(cc);
121 //System.out.println("gcda sqf f1 = " + f1);
122 sfactors.put(f1, 1L);
123 }
124 GenPolynomial<C> T0 = A;
125 GenPolynomial<C> Tp;
126 GenPolynomial<C> T = null;
127 GenPolynomial<C> V = null;
128 long k = 0L;
129 boolean init = true;
130 while (true) {
131 if (init) {
132 if (T0.isConstant() || T0.isZERO()) {
133 break;
134 }
135 Tp = PolyUtil.<C> baseDeriviative(T0);
136 T = engine.baseGcd(T0, Tp);
137 T = engine.basePrimitivePart(T);
138 V = PolyUtil.<C> basePseudoDivide(T0, T);
139 //System.out.println("iT0 = " + T0);
140 //System.out.println("iTp = " + Tp);
141 //System.out.println("iT = " + T);
142 //System.out.println("iV = " + V);
143 k = 0L;
144 init = false;
145 }
146 if (V.isConstant()) {
147 break;
148 }
149 k++;
150 GenPolynomial<C> W = engine.baseGcd(T, V);
151 W = engine.basePrimitivePart(W);
152 GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W);
153 //System.out.println("W = " + W);
154 //System.out.println("z = " + z);
155 V = W;
156 T = PolyUtil.<C> basePseudoDivide(T, V);
157 //System.out.println("V = " + V);
158 //System.out.println("T = " + T);
159 if (z.degree(0) > 0) {
160 if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) {
161 z = engine.basePrimitivePart(z);
162 logger.info("z,pp = " + z);
163 }
164 sfactors.put(z, k);
165 }
166 }
167 return sfactors;
168 }
169
170
171 /**
172 * GenPolynomial recursive univariate polynomial greatest squarefree
173 * divisor.
174 * @param P recursive univariate GenPolynomial.
175 * @return squarefree(pp(P)).
176 */
177 @Override
178 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(GenPolynomial<GenPolynomial<C>> P) {
179 if (P == null || P.isZERO()) {
180 return P;
181 }
182 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
183 if (pfac.nvar > 1) {
184 throw new IllegalArgumentException(this.getClass().getName() + " only for multivariate polynomials");
185 }
186 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
187 // squarefree content
188 GenPolynomial<GenPolynomial<C>> pp = P;
189 GenPolynomial<C> Pc = engine.recursiveContent(P);
190 Pc = engine.basePrimitivePart(Pc);
191 //System.out.println("Pc,bPP = " + Pc);
192 if (!Pc.isONE()) {
193 pp = PolyUtil.<C> coefficientPseudoDivide(pp, Pc);
194 //System.out.println("pp,sqp = " + pp);
195 GenPolynomial<C> Pr = squarefreePart(Pc);
196 Pr = engine.basePrimitivePart(Pr);
197 //System.out.println("Pr,bPP = " + Pr);
198 }
199 if (pp.leadingExpVector().getVal(0) < 1) {
200 //System.out.println("pp = " + pp);
201 //System.out.println("Pc = " + Pc);
202 return pp.multiply(Pc);
203 }
204 GenPolynomial<GenPolynomial<C>> d = PolyUtil.<C> recursiveDeriviative(pp);
205 //System.out.println("d = " + d);
206 GenPolynomial<GenPolynomial<C>> g = engine.recursiveUnivariateGcd(pp, d);
207 //System.out.println("g,rec = " + g);
208 g = engine.baseRecursivePrimitivePart(g);
209 //System.out.println("g,bPP = " + g);
210 GenPolynomial<GenPolynomial<C>> q = PolyUtil.<C> recursivePseudoDivide(pp, g);
211 q = engine.baseRecursivePrimitivePart(q);
212 //System.out.println("q,bPP = " + q);
213 return q.multiply(Pc);
214 }
215
216
217 /**
218 * GenPolynomial recursive univariate polynomial squarefree factorization.
219 * @param P recursive univariate GenPolynomial.
220 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
221 * and p_i squarefree.
222 */
223 @Override
224 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
225 GenPolynomial<GenPolynomial<C>> P) {
226 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
227 if (P == null || P.isZERO()) {
228 return sfactors;
229 }
230 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
231 if (pfac.nvar > 1) {
232 // recursiveContent not possible by return type
233 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
234 }
235 // if base coefficient ring is a field, make monic
236 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
237 C bcc = engine.baseRecursiveContent(P);
238 if (!bcc.isONE()) {
239 GenPolynomial<C> lc = cfac.getONE().multiply(bcc);
240 GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc);
241 sfactors.put(pl, 1L);
242 P = PolyUtil.<C> baseRecursiveDivide(P, bcc);
243 }
244 // factors of content
245 GenPolynomial<C> Pc = engine.recursiveContent(P);
246 if (logger.isInfoEnabled()) {
247 logger.info("Pc = " + Pc);
248 }
249 Pc = engine.basePrimitivePart(Pc);
250 //System.out.println("Pc,PP = " + Pc);
251 if (!Pc.isONE()) {
252 P = PolyUtil.<C> coefficientPseudoDivide(P, Pc);
253 }
254 SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc);
255 if (logger.isInfoEnabled()) {
256 logger.info("rsf = " + rsf);
257 }
258 // add factors of content
259 for (GenPolynomial<C> c : rsf.keySet()) {
260 if (!c.isONE()) {
261 GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c);
262 Long rk = rsf.get(c);
263 sfactors.put(cr, rk);
264 }
265 }
266
267 // factors of recursive polynomial
268 GenPolynomial<GenPolynomial<C>> T0 = P;
269 GenPolynomial<GenPolynomial<C>> Tp;
270 GenPolynomial<GenPolynomial<C>> T = null;
271 GenPolynomial<GenPolynomial<C>> V = null;
272 long k = 0L;
273 boolean init = true;
274 while (true) {
275 if (init) {
276 if (T0.isConstant() || T0.isZERO()) {
277 break;
278 }
279 Tp = PolyUtil.<C> recursiveDeriviative(T0);
280 T = engine.recursiveUnivariateGcd(T0, Tp);
281 T = engine.baseRecursivePrimitivePart(T);
282 V = PolyUtil.<C> recursivePseudoDivide(T0, T);
283 //System.out.println("iT0 = " + T0);
284 //System.out.println("iTp = " + Tp);
285 //System.out.println("iT = " + T);
286 //System.out.println("iV = " + V);
287 k = 0L;
288 init = false;
289 }
290 if (V.isConstant()) {
291 break;
292 }
293 k++;
294 GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V);
295 W = engine.baseRecursivePrimitivePart(W);
296 GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W);
297 //System.out.println("W = " + W);
298 //System.out.println("z = " + z);
299 V = W;
300 T = PolyUtil.<C> recursivePseudoDivide(T, V);
301 //System.out.println("V = " + V);
302 //System.out.println("T = " + T);
303 //was: if ( z.degree(0) > 0 ) {
304 if (!z.isONE() && !z.isZERO()) {
305 z = engine.baseRecursivePrimitivePart(z);
306 sfactors.put(z, k);
307 }
308 }
309 return sfactors;
310 }
311
312
313 /**
314 * GenPolynomial greatest squarefree divisor.
315 * @param P GenPolynomial.
316 * @return squarefree(pp(P)).
317 */
318 @Override
319 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) {
320 if (P == null) {
321 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
322 }
323 if (P.isZERO()) {
324 return P;
325 }
326 GenPolynomialRing<C> pfac = P.ring;
327 if (pfac.nvar <= 1) {
328 return baseSquarefreePart(P);
329 }
330 GenPolynomialRing<C> cfac = pfac.contract(1);
331 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
332
333 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
334 GenPolynomial<C> Pc = engine.recursiveContent(Pr);
335 Pr = PolyUtil.<C> coefficientPseudoDivide(Pr, Pc);
336 GenPolynomial<C> Ps = squarefreePart(Pc);
337 GenPolynomial<GenPolynomial<C>> PP = recursiveUnivariateSquarefreePart(Pr);
338 GenPolynomial<GenPolynomial<C>> PS = PP.multiply(Ps);
339 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, PS);
340 return D;
341 }
342
343
344 /**
345 * GenPolynomial squarefree factorization.
346 * @param P GenPolynomial.
347 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
348 * and p_i squarefree.
349 */
350 @Override
351 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) {
352 if (P == null) {
353 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
354 }
355 GenPolynomialRing<C> pfac = P.ring;
356 if (pfac.nvar <= 1) {
357 return baseSquarefreeFactors(P);
358 }
359 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
360 if (P.isZERO()) {
361 return sfactors;
362 }
363 GenPolynomialRing<C> cfac = pfac.contract(1);
364 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
365
366 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
367 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);
368
369 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) {
370 Long i = m.getValue();
371 GenPolynomial<GenPolynomial<C>> Dr = m.getKey();
372 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr);
373 sfactors.put(D, i);
374 }
375 return sfactors;
376 }
377
378
379 /**
380 * Coefficients squarefree factorization.
381 * @param P coefficient.
382 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
383 * and p_i squarefree.
384 */
385 public SortedMap<C, Long> squarefreeFactors(C P) {
386 throw new UnsupportedOperationException("method not implemented");
387 }
388
389 }