001 /*
002 * $Id: SquarefreeAbstract.java 3715 2011-08-03 13:48:27Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.List;
009 import java.util.ArrayList;
010 import java.util.Map;
011 import java.util.SortedMap;
012 import java.util.TreeMap;
013
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.poly.GenPolynomialRing;
016 import edu.jas.poly.PolyUtil;
017 import edu.jas.structure.GcdRingElem;
018 import edu.jas.structure.Power;
019 import edu.jas.structure.RingFactory;
020
021
022 /**
023 * Abstract squarefree decomposition class.
024 * @author Heinz Kredel
025 */
026
027 public abstract class SquarefreeAbstract<C extends GcdRingElem<C>> implements Squarefree<C> {
028
029
030 /**
031 * GCD engine for respective base coefficients.
032 */
033 protected final GreatestCommonDivisorAbstract<C> engine;
034
035
036 /**
037 * Constructor.
038 */
039 public SquarefreeAbstract(GreatestCommonDivisorAbstract<C> engine) {
040 this.engine = engine;
041 }
042
043
044 /**
045 * GenPolynomial polynomial greatest squarefree divisor.
046 * @param P GenPolynomial.
047 * @return squarefree(pp(P)).
048 */
049 public abstract GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P);
050
051
052 /**
053 * GenPolynomial polynomial squarefree factorization.
054 * @param A GenPolynomial.
055 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
056 * and p_i squarefree.
057 */
058 public abstract SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A);
059
060
061 /**
062 * GenPolynomial recursive polynomial greatest squarefree divisor.
063 * @param P recursive univariate GenPolynomial.
064 * @return squarefree(pp(P)).
065 */
066 public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(
067 GenPolynomial<GenPolynomial<C>> P);
068
069
070 /**
071 * GenPolynomial recursive univariate polynomial squarefree factorization.
072 * @param P recursive univariate GenPolynomial.
073 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
074 * and p_i squarefree.
075 */
076 public abstract SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
077 GenPolynomial<GenPolynomial<C>> P);
078
079
080 /**
081 * GenPolynomial greatest squarefree divisor.
082 * @param P GenPolynomial.
083 * @return squarefree(P) a primitive respectively monic polynomial.
084 */
085 public abstract GenPolynomial<C> squarefreePart(GenPolynomial<C> P);
086
087
088 /**
089 * GenPolynomial test if is squarefree.
090 * @param P GenPolynomial.
091 * @return true if P is squarefree, else false.
092 */
093 public boolean isSquarefree(GenPolynomial<C> P) {
094 GenPolynomial<C> S = squarefreePart(P);
095 GenPolynomial<C> Ps = P;
096 if ( P.ring.coFac.isField() ) {
097 Ps = Ps.monic();
098 } else {
099 Ps = engine.basePrimitivePart(Ps);
100 }
101 boolean f = Ps.equals(S);
102 if (!f) {
103 //System.out.println("\nisSquarefree: " + f);
104 //System.out.println("S = " + S);
105 //System.out.println("P = " + P);
106 }
107 return f;
108 }
109
110
111 /**
112 * GenPolynomial list test if squarefree.
113 * @param L list of GenPolynomial.
114 * @return true if each P in L is squarefree, else false.
115 */
116 public boolean isSquarefree(List<GenPolynomial<C>> L) {
117 if ( L == null || L.isEmpty() ) {
118 return true;
119 }
120 for ( GenPolynomial<C> P : L ) {
121 if (! isSquarefree(P) ) {
122 return false;
123 }
124 }
125 return true;
126 }
127
128
129 /**
130 * Recursive GenPolynomial test if is squarefree.
131 * @param P recursive univariate GenPolynomial.
132 * @return true if P is squarefree, else false.
133 */
134 public boolean isRecursiveSquarefree(GenPolynomial<GenPolynomial<C>> P) {
135 GenPolynomial<GenPolynomial<C>> S = recursiveUnivariateSquarefreePart(P);
136 boolean f = P.equals(S);
137 if (!f) {
138 System.out.println("\nisSquarefree: " + f);
139 System.out.println("S = " + S);
140 System.out.println("P = " + P);
141 }
142 return f;
143 }
144
145
146 /**
147 * GenPolynomial squarefree factorization.
148 * @param P GenPolynomial.
149 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
150 * and p_i squarefree.
151 */
152 public abstract SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P);
153
154
155 /**
156 * GenPolynomial squarefree and co-prime list.
157 * @param A list of GenPolynomials.
158 * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
159 * a in A there exists b in B with b|a and each b in B is
160 * squarefree. B does not contain zero or constant polynomials.
161 */
162 public List<GenPolynomial<C>> coPrimeSquarefree(List<GenPolynomial<C>> A) {
163 if (A == null || A.isEmpty()) {
164 return A;
165 }
166 List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>();
167 for (GenPolynomial<C> g : A) {
168 SortedMap<GenPolynomial<C>, Long> sm = squarefreeFactors(g);
169 S.addAll(sm.keySet());
170 }
171 List<GenPolynomial<C>> B = engine.coPrime(S);
172 return B;
173 }
174
175
176 /**
177 * GenPolynomial squarefree and co-prime list.
178 * @param a polynomial.
179 * @param P squarefree co-prime list of GenPolynomials.
180 * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
181 * there exists b in P with b|a. B does not contain zero or constant
182 * polynomials.
183 */
184 public List<GenPolynomial<C>> coPrimeSquarefree(GenPolynomial<C> a, List<GenPolynomial<C>> P) {
185 if (a == null || a.isZERO() || a.isConstant()) {
186 return P;
187 }
188 SortedMap<GenPolynomial<C>, Long> sm = squarefreeFactors(a);
189 List<GenPolynomial<C>> B = P;
190 for ( GenPolynomial<C> f : sm.keySet() ) {
191 B = engine.coPrime(f,B);
192 }
193 return B;
194 }
195
196
197 /**
198 * Test if list of GenPolynomials is squarefree and co-prime.
199 * @param B list of GenPolynomials.
200 * @return true, if for all b != c in B gcd(b,c) = 1 and
201 * each b in B is squarefree, else false.
202 */
203 public boolean isCoPrimeSquarefree(List<GenPolynomial<C>> B) {
204 if (B == null || B.isEmpty()) {
205 return true;
206 }
207 if ( !engine.isCoPrime(B) ) {
208 return false;
209 }
210 return isSquarefree(B);
211 }
212
213
214 /**
215 * GenPolynomial is (squarefree) factorization.
216 * @param P GenPolynomial.
217 * @param F = [p_1,...,p_k].
218 * @return true if P = prod_{i=1,...,r} p_i, else false.
219 */
220 public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F) {
221 if (P == null || F == null) {
222 throw new IllegalArgumentException("P and F may not be null");
223 }
224 GenPolynomial<C> t = P.ring.getONE();
225 for (GenPolynomial<C> f : F) {
226 t = t.multiply(f);
227 }
228 boolean f = P.equals(t) || P.equals(t.negate());
229 if (!f) {
230 System.out.println("\nfactorization(list): " + f);
231 System.out.println("F = " + F);
232 System.out.println("P = " + P);
233 System.out.println("t = " + t);
234 }
235 return f;
236 }
237
238
239 /**
240 * Count number of factors in a (squarefree) factorization.
241 * @param F = [p_1 -> e_1, ..., p_k -> e_k].
242 * @return sum_{i=1,...,k} e_i.
243 */
244 public long factorCount(SortedMap<GenPolynomial<C>,Long> F) {
245 if (F == null || F.isEmpty() ) {
246 return 0L;
247 }
248 long f = 0L;
249 for (Long e : F.values()) {
250 f += e;
251 }
252 return f;
253 }
254
255
256 /**
257 * GenPolynomial is (squarefree) factorization.
258 * @param P GenPolynomial.
259 * @param F = [p_1 -> e_1, ..., p_k -> e_k].
260 * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
261 */
262 public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
263 if (P == null || F == null) {
264 throw new IllegalArgumentException("P and F may not be null");
265 }
266 if (P.isZERO() && F.size() == 0) {
267 return true;
268 }
269 GenPolynomial<C> t = P.ring.getONE();
270 for (GenPolynomial<C> f : F.keySet()) {
271 Long E = F.get(f);
272 long e = E.longValue();
273 GenPolynomial<C> g = Power.<GenPolynomial<C>> positivePower(f, e);
274 t = t.multiply(g);
275 }
276 boolean f = P.equals(t) || P.equals(t.negate());
277 if (!f) {
278 //System.out.println("P = " + P);
279 //System.out.println("t = " + t);
280 P = P.monic();
281 t = t.monic();
282 f = P.equals(t) || P.equals(t.negate());
283 if (f) {
284 return f;
285 }
286 System.out.println("\nfactorization(map): " + f);
287 System.out.println("F = " + F);
288 System.out.println("P = " + P);
289 System.out.println("t = " + t);
290 //RuntimeException e = new RuntimeException("fac-map");
291 //e.printStackTrace();
292 //throw e;
293 }
294 return f;
295 }
296
297
298 /**
299 * GenPolynomial is (squarefree) factorization.
300 * @param P GenPolynomial.
301 * @param F = [p_1 -> e_1, ..., p_k -> e_k].
302 * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
303 */
304 public boolean isRecursiveFactorization(GenPolynomial<GenPolynomial<C>> P,
305 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
306 if (P == null || F == null) {
307 throw new IllegalArgumentException("P and F may not be null");
308 }
309 if (P.isZERO() && F.size() == 0) {
310 return true;
311 }
312 GenPolynomial<GenPolynomial<C>> t = P.ring.getONE();
313 for (GenPolynomial<GenPolynomial<C>> f : F.keySet()) {
314 Long E = F.get(f);
315 long e = E.longValue();
316 GenPolynomial<GenPolynomial<C>> g = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(f, e);
317 t = t.multiply(g);
318 }
319 boolean f = P.equals(t) || P.equals(t.negate());
320 if (!f) {
321 //System.out.println("P = " + P);
322 //System.out.println("t = " + t);
323 GenPolynomialRing<C> cf = (GenPolynomialRing<C>)P.ring.coFac;
324 GreatestCommonDivisorAbstract<C> engine = GCDFactory.getProxy(cf.coFac);
325 GenPolynomial<GenPolynomial<C>> Pp = engine.recursivePrimitivePart(P);
326 Pp = PolyUtil.<C>monic(Pp);
327 GenPolynomial<GenPolynomial<C>> tp = engine.recursivePrimitivePart(t);
328 tp = PolyUtil.<C>monic(tp);
329 f = Pp.equals(tp) || Pp.equals(tp.negate());
330 if (f) {
331 return f;
332 }
333 System.out.println("\nfactorization(map): " + f);
334 System.out.println("F = " + F);
335 System.out.println("P = " + P);
336 System.out.println("t = " + t);
337 System.out.println("Pp = " + Pp);
338 System.out.println("tp = " + tp);
339 //RuntimeException e = new RuntimeException("fac-map");
340 //e.printStackTrace();
341 //throw e;
342 }
343 return f;
344 }
345
346
347 /**
348 * GenPolynomial recursive polynomial greatest squarefree divisor.
349 * @param P recursive GenPolynomial.
350 * @return squarefree(pp(P)).
351 */
352 public GenPolynomial<GenPolynomial<C>> recursiveSquarefreePart(GenPolynomial<GenPolynomial<C>> P) {
353 if (P == null || P.isZERO()) {
354 return P;
355 }
356 if (P.ring.nvar <= 1) {
357 return recursiveUnivariateSquarefreePart(P);
358 }
359 // distributed polynomials squarefree part
360 GenPolynomialRing<GenPolynomial<C>> rfac = P.ring;
361 RingFactory<GenPolynomial<C>> rrfac = rfac.coFac;
362 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rrfac;
363 GenPolynomialRing<C> dfac = cfac.extend(rfac.nvar);
364 GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac, P);
365 GenPolynomial<C> Dd = squarefreePart(Pd);
366 // convert to recursive
367 GenPolynomial<GenPolynomial<C>> C = PolyUtil.<C> recursive(rfac, Dd);
368 return C;
369 }
370
371
372 /**
373 * GenPolynomial recursive polynomial squarefree factorization.
374 * @param P recursive GenPolynomial.
375 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
376 * and p_i squarefree.
377 */
378 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveSquarefreeFactors(
379 GenPolynomial<GenPolynomial<C>> P) {
380 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors;
381 factors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
382 if (P == null || P.isZERO()) {
383 return factors;
384 }
385 if (P.ring.nvar <= 1) {
386 return recursiveUnivariateSquarefreeFactors(P);
387 }
388 // distributed polynomials squarefree part
389 GenPolynomialRing<GenPolynomial<C>> rfac = P.ring;
390 RingFactory<GenPolynomial<C>> rrfac = rfac.coFac;
391 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rrfac;
392 GenPolynomialRing<C> dfac = cfac.extend(rfac.nvar);
393 GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac, P);
394 SortedMap<GenPolynomial<C>, Long> dfacs = squarefreeFactors(Pd);
395 // convert to recursive
396 for (Map.Entry<GenPolynomial<C>, Long> Dm : dfacs.entrySet()) {
397 GenPolynomial<C> Dd = Dm.getKey();
398 Long e = Dm.getValue();
399 GenPolynomial<GenPolynomial<C>> C = PolyUtil.<C> recursive(rfac, Dd);
400 factors.put(C, e);
401 }
402 return factors;
403 }
404
405
406 /**
407 * Univariate GenPolynomial partial fraction decomposition.
408 * @param A univariate GenPolynomial.
409 * @param D sorted map [d_1 -> e_1, ..., d_k -> e_k] with d_i squarefree.
410 * @return [ [Ai0, Ai1,..., Aie_i], i=0,...,k ] with A/prod(D) = A0 + sum( sum ( Aij/di^j ) ) with deg(Aij) < deg(di).
411 */
412 public List<List<GenPolynomial<C>>> basePartialFraction(GenPolynomial<C> A, SortedMap<GenPolynomial<C>,Long> D) {
413 if ( D == null || A == null ) {
414 throw new IllegalArgumentException("null A or D not allowed");
415 }
416 List<List<GenPolynomial<C>>> pf = new ArrayList<List<GenPolynomial<C>>>( D.size()+1 );
417 if ( D.size() == 0 ) {
418 return pf;
419 }
420 //List<GenPolynomial<C>> fi;
421 if ( A.isZERO() ) {
422 for ( GenPolynomial<C> d : D.keySet() ) {
423 long e = D.get(d);
424 int e1 = (int)e + 1;
425 List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(e1);
426 for ( int i = 0; i < e1; i++ ) {
427 fi.add(A);
428 }
429 pf.add(fi);
430 }
431 List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(1);
432 fi.add(A);
433 pf.add(0,fi);
434 return pf;
435 }
436 // A != 0, D != empty
437 List<GenPolynomial<C>> Dp = new ArrayList<GenPolynomial<C>>( D.size() );
438 for ( GenPolynomial<C> d : D.keySet() ) {
439 long e = D.get(d);
440 GenPolynomial<C> f = Power.<GenPolynomial<C>> positivePower(d, e);
441 Dp.add(f);
442 }
443 List<GenPolynomial<C>> F = engine.basePartialFraction(A,Dp);
444 //System.out.println("fraction list = " + F.size());
445 GenPolynomial<C> A0 = F.remove(0);
446 List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(1);
447 fi.add(A0);
448 pf.add(fi);
449 int i = 0;
450 for ( GenPolynomial<C> d : D.keySet() ) { // assume fixed sequence order
451 long e = D.get(d);
452 int ei = (int)e;
453 GenPolynomial<C> gi = F.get(i); // assume fixed sequence order
454 List<GenPolynomial<C>> Fi = engine.basePartialFraction(gi,d,ei);
455 pf.add(Fi);
456 i++;
457 }
458 return pf;
459 }
460
461
462 /**
463 * Test for Univariate GenPolynomial partial fraction decomposition.
464 * @param A univariate GenPolynomial.
465 * @param D sorted map [d_1 -> e_1, ..., d_k -> e_k] with d_i squarefree.
466 * @param F a list of lists [ [Ai0, Ai1,..., Aie_i], i=0,...,k ]
467 * @return true, if A/prod(D) = A0 + sum( sum ( Aij/di^j ) ),
468 else false.
469 */
470 public boolean isBasePartialFraction(GenPolynomial<C> A, SortedMap<GenPolynomial<C>,Long> D, List<List<GenPolynomial<C>>> F) {
471 if ( D == null || A == null || F == null ) {
472 throw new IllegalArgumentException("null A, D or F not allowed");
473 }
474 if ( D.isEmpty() && F.isEmpty() ) {
475 return true;
476 }
477 if ( D.isEmpty() || F.isEmpty() ) {
478 return false;
479 }
480 List<GenPolynomial<C>> Dp = new ArrayList<GenPolynomial<C>>( D.size() );
481 for ( GenPolynomial<C> d : D.keySet() ) {
482 long e = D.get(d);
483 GenPolynomial<C> f = Power.<GenPolynomial<C>> positivePower(d, e);
484 Dp.add(f);
485 }
486 List<GenPolynomial<C>> fi = F.get(0);
487 if ( fi.size() != 1 ) {
488 System.out.println("size(fi) != 1 " + fi);
489 return false;
490 }
491 boolean t;
492 GenPolynomial<C> A0 = fi.get(0);
493 //System.out.println("A0 = " + A0);
494 List<GenPolynomial<C>> Qp = new ArrayList<GenPolynomial<C>>(D.size()+1);
495 Qp.add(A0);
496
497 // List<GenPolynomial<C>> Fp = engine.basePartialFraction(A,Dp);
498 // System.out.println("fraction list = " + F.size());
499 // t = engine.isBasePartialFraction(A,Dp,Fp);
500 // if ( ! t ) {
501 // System.out.println("not recursion isPartFrac = " + Fp);
502 // return false;
503 // }
504 // GenPolynomial<C> A0p = Fp.remove(0);
505 // if ( ! A0.equals(A0p) ) {
506 // System.out.println("A0 != A0p " + A0p);
507 // return false;
508 // }
509
510 int i = 0;
511 for ( GenPolynomial<C> d : D.keySet() ) { // assume fixed sequence order
512 long e = D.get(d);
513 int ei = (int)e;
514 List<GenPolynomial<C>> Fi = F.get(i+1); // assume fixed sequence order
515
516 // GenPolynomial<C> pi = Fp.get(i); // assume fixed sequence order
517 // t = engine.isBasePartialFraction(pi,d,ei,Fi);
518 // if ( ! t ) {
519 // System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei);
520 // System.out.println("not isPartFrac exp = " + Fi);
521 // return false;
522 // }
523
524 GenPolynomial<C> qi = engine.basePartialFractionValue(d,ei,Fi);
525 Qp.add(qi);
526
527 // t = qi.equals(pi);
528 // if ( ! t ) {
529 // System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei + ", qi = " + qi);
530 // }
531
532 i++;
533 }
534
535 t = engine.isBasePartialFraction(A,Dp,Qp);
536 if ( ! t ) {
537 System.out.println("not final isPartFrac " + Qp);
538 }
539 return t;
540 }
541
542
543 /**
544 * Coefficients greatest squarefree divisor.
545 * @param P coefficient.
546 * @return squarefree part of P.
547 */
548 public C squarefreePart(C P) {
549 if (P == null) {
550 return null;
551 }
552 // just for the moment: TODO
553 C s = null;
554 SortedMap<C, Long> factors = squarefreeFactors(P);
555 //logger.info("sqfPart,factors = " + factors);
556 System.out.println("sqfPart,factors = " + factors);
557 for (C sp : factors.keySet()) {
558 if ( s == null ) {
559 s = sp;
560 } else {
561 s = s.multiply(sp);
562 }
563 }
564 return s;
565 }
566
567
568 /**
569 * Coefficients squarefree factorization.
570 * @param P coefficient.
571 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
572 * and p_i squarefree.
573 */
574 public abstract SortedMap<C, Long> squarefreeFactors(C P);
575 /* not possible:
576 {
577 if (P == null) {
578 return null;
579 }
580 SortedMap<C, Long> factors = new TreeMap<C, Long>();
581 SquarefreeAbstract<C> reng = SquarefreeFactory.getImplementation((RingFactory<C>) P.factory());
582 System.out.println("fcp,reng = " + reng);
583 SortedMap<C, Long> rfactors = reng.squarefreeFactors(P);
584 for (C c : rfactors.keySet()) {
585 if (!c.isONE()) {
586 C cr = (C) (Object) c;
587 Long rk = rfactors.get(c);
588 factors.put(cr, rk);
589 }
590 }
591
592 return factors;
593 }
594 */
595
596 }