001 /*
002 * $Id: FactorAbsolute.java 3494 2011-01-20 21:22:45Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.SortedMap;
011 import java.util.TreeMap;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.poly.AlgebraicNumber;
016 import edu.jas.poly.AlgebraicNumberRing;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019 import edu.jas.poly.PolyUtil;
020 import edu.jas.structure.GcdRingElem;
021 import edu.jas.structure.Power;
022 import edu.jas.structure.RingFactory;
023
024
025 /**
026 * Absolute factorization algorithms class. This class contains implementations
027 * of methods for factorization over algebraically closed fields. The required
028 * field extension is computed along with the factors. The methods have been
029 * tested for prime fields of characteristic zero, that is for
030 * <code>BigRational</code>. It might eventually also be used for prime
031 * fields of non-zero characteristic, that is with <code>ModInteger</code>.
032 * The field extension may yet not be minimal.
033 * @author Heinz Kredel
034 * @param <C> coefficient type
035 */
036
037 public abstract class FactorAbsolute<C extends GcdRingElem<C>> extends FactorAbstract<C> {
038
039
040 private static final Logger logger = Logger.getLogger(FactorAbsolute.class);
041
042
043 private final boolean debug = logger.isDebugEnabled();
044
045
046 /*
047 * Factorization engine for algebraic number coefficients.
048 */
049 //not possible here because of recursion AN -> Int|Mod -> AN -> ...
050 //public final FactorAbstract<AlgebraicNumber<C>> aengine;
051
052 /**
053 * No argument constructor. <b>Note:</b> can't use this constructor.
054 */
055 protected FactorAbsolute() {
056 throw new IllegalArgumentException("don't use this constructor");
057 }
058
059
060 /**
061 * Constructor.
062 * @param cfac coefficient ring factory.
063 */
064 public FactorAbsolute(RingFactory<C> cfac) {
065 super(cfac);
066 //GenPolynomialRing<C> fac = new GenPolynomialRing<C>(cfac,1);
067 //GenPolynomial<C> p = fac.univariate(0);
068 //AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(p);
069 //aengine = null; //FactorFactory.<C>getImplementation(afac); // hack
070 }
071
072
073 /**
074 * Get the String representation.
075 * @see java.lang.Object#toString()
076 */
077 @Override
078 public String toString() {
079 return getClass().getName();
080 }
081
082
083 /**
084 * GenPolynomial test if is absolute irreducible.
085 * @param P GenPolynomial.
086 * @return true if P is absolute irreducible, else false.
087 */
088 public boolean isAbsoluteIrreducible(GenPolynomial<C> P) {
089 if (!isIrreducible(P)) {
090 return false;
091 }
092 Factors<C> F = factorsAbsoluteIrreducible(P);
093 if (F.afac == null) {
094 return true;
095 } else if (F.afactors.size() > 2) {
096 return false;
097 } else { //F.size() == 2
098 boolean cnst = false;
099 for (GenPolynomial<AlgebraicNumber<C>> p : F.afactors) {
100 if (p.isConstant()) {
101 cnst = true;
102 }
103 }
104 return cnst;
105 }
106 }
107
108
109 /**
110 * GenPolynomial absolute base factorization of a polynomial.
111 * @param P univariate GenPolynomial.
112 * @return factors map container: [p_1 -> e_1, ..., p_k -> e_k] with P =
113 * prod_{i=1,...,k} p_i**e_i. <b>Note:</b> K(alpha) not yet
114 * minimal.
115 */
116 // @Override
117 public FactorsMap<C> baseFactorsAbsolute(GenPolynomial<C> P) {
118 if (P == null) {
119 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
120 }
121 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>();
122 if (P.isZERO()) {
123 return new FactorsMap<C>(P, factors);
124 }
125 //System.out.println("\nP_base = " + P);
126 GenPolynomialRing<C> pfac = P.ring; // K[x]
127 if (pfac.nvar > 1) {
128 //System.out.println("\nfacs_base: univ");
129 throw new IllegalArgumentException("only for univariate polynomials");
130 }
131 if (!pfac.coFac.isField()) {
132 //System.out.println("\nfacs_base: field");
133 throw new IllegalArgumentException("only for field coefficients");
134 }
135 if (P.degree(0) <= 1) {
136 factors.put(P, 1L);
137 return new FactorsMap<C>(P, factors);
138 }
139 // factor over K (=C)
140 SortedMap<GenPolynomial<C>, Long> facs = baseFactors(P);
141 if (debug && !isFactorization(P, facs)) {
142 System.out.println("facs = " + facs);
143 throw new ArithmeticException("isFactorization = false");
144 }
145 if (logger.isInfoEnabled()) {
146 logger.info("all K factors = " + facs); // Q[X]
147 //System.out.println("\nall K factors = " + facs); // Q[X]
148 }
149 // factor over some K(alpha)
150 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>();
151 for (GenPolynomial<C> p : facs.keySet()) {
152 Long e = facs.get(p);
153 if (p.degree(0) <= 1) {
154 factors.put(p, e);
155 } else {
156 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p);
157 //System.out.println("afacs = " + afacs);
158 afactors.put(afacs, e);
159 }
160 }
161 //System.out.println("K(alpha) factors = " + factors);
162 return new FactorsMap<C>(P, factors, afactors);
163 }
164
165
166 /**
167 * GenPolynomial absolute base factorization of a squarefree polynomial.
168 * @param P squarefree and primitive univariate GenPolynomial.
169 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k}
170 * p_i. <b>Note:</b> K(alpha) not yet minimal.
171 */
172 // @Override
173 public FactorsList<C> baseFactorsAbsoluteSquarefree(GenPolynomial<C> P) {
174 if (P == null) {
175 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
176 }
177 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>();
178 if (P.isZERO()) {
179 return new FactorsList<C>(P, factors);
180 }
181 //System.out.println("\nP_base_sqf = " + P);
182 GenPolynomialRing<C> pfac = P.ring; // K[x]
183 if (pfac.nvar > 1) {
184 //System.out.println("facs_base_sqf: univ");
185 throw new IllegalArgumentException("only for univariate polynomials");
186 }
187 if (!pfac.coFac.isField()) {
188 //System.out.println("facs_base_sqf: field");
189 throw new IllegalArgumentException("only for field coefficients");
190 }
191 if (P.degree(0) <= 1) {
192 factors.add(P);
193 return new FactorsList<C>(P, factors);
194 }
195 // factor over K (=C)
196 List<GenPolynomial<C>> facs = baseFactorsSquarefree(P);
197 //System.out.println("facs_base_irred = " + facs);
198 if (debug && !isFactorization(P, facs)) {
199 throw new ArithmeticException("isFactorization = false");
200 }
201 if (logger.isInfoEnabled()) {
202 logger.info("all K factors = " + facs); // Q[X]
203 //System.out.println("\nall K factors = " + facs); // Q[X]
204 }
205 // factor over K(alpha)
206 List<Factors<C>> afactors = new ArrayList<Factors<C>>();
207 for (GenPolynomial<C> p : facs) {
208 //System.out.println("facs_base_sqf_p = " + p);
209 if (p.degree(0) <= 1) {
210 factors.add(p);
211 } else {
212 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p);
213 //System.out.println("afacs_base_sqf = " + afacs);
214 if (logger.isInfoEnabled()) {
215 logger.info("K(alpha) factors = " + afacs); // K(alpha)[X]
216 }
217 afactors.add(afacs);
218 }
219 }
220 //System.out.println("K(alpha) factors = " + factors);
221 return new FactorsList<C>(P, factors, afactors);
222 }
223
224
225 /**
226 * GenPolynomial base absolute factorization of a irreducible polynomial.
227 * @param P irreducible! univariate GenPolynomial.
228 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i
229 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x],
230 * where K \subset K(alpha) \subset L is an algebraically closed
231 * field over K. <b>Note:</b> K(alpha) not yet minimal.
232 */
233 public Factors<C> baseFactorsAbsoluteIrreducible(GenPolynomial<C> P) {
234 if (P == null) {
235 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
236 }
237 if (P.isZERO()) {
238 return new Factors<C>(P);
239 }
240 //System.out.println("\nP_base_irred = " + P);
241 GenPolynomialRing<C> pfac = P.ring; // K[x]
242 if (pfac.nvar > 1) {
243 //System.out.println("facs_base_irred: univ");
244 throw new IllegalArgumentException("only for univariate polynomials");
245 }
246 if (!pfac.coFac.isField()) {
247 //System.out.println("facs_base_irred: field");
248 throw new IllegalArgumentException("only for field coefficients");
249 }
250 if (P.degree(0) <= 1) {
251 return new Factors<C>(P);
252 }
253 // setup field extension K(alpha) where alpha = z_xx
254 //String[] vars = new String[] { "z_" + Math.abs(P.hashCode() % 1000) };
255 String[] vars = pfac.newVars( "z_" );
256 pfac = pfac.clone();
257 vars = pfac.setVars(vars);
258 GenPolynomial<C> aP = pfac.copy(P); // hack to exchange the variables
259 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aP, true); // since irreducible
260 if (logger.isInfoEnabled()) {
261 logger.info("K(alpha) = " + afac);
262 logger.info("K(alpha) = " + afac.toScript());
263 //System.out.println("K(alpha) = " + afac);
264 }
265 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac,
266 aP.ring.nvar, aP.ring.tord, /*old*/vars);
267 // convert to K(alpha)
268 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, P);
269 if (logger.isInfoEnabled()) {
270 logger.info("P over K(alpha) = " + Pa);
271 //logger.info("P over K(alpha) = " + Pa.toScript());
272 //System.out.println("P in K(alpha) = " + Pa);
273 }
274 // factor over K(alpha)
275 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac);
276 //System.out.println("K(alpha) engine = " + engine);
277 List<GenPolynomial<AlgebraicNumber<C>>> factors = engine.baseFactorsSquarefree(Pa);
278 //System.out.println("factors = " + factors);
279 if (logger.isInfoEnabled()) {
280 logger.info("factors over K(alpha) = " + factors);
281 //System.out.println("factors over K(alpha) = " + factors);
282 }
283 List<GenPolynomial<AlgebraicNumber<C>>> faca = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(
284 factors.size());;
285 List<Factors<AlgebraicNumber<C>>> facar = new ArrayList<Factors<AlgebraicNumber<C>>>();
286 for (GenPolynomial<AlgebraicNumber<C>> fi : factors) {
287 if (fi.degree(0) <= 1) {
288 faca.add(fi);
289 } else {
290 //System.out.println("fi.deg > 1 = " + fi);
291 FactorAbsolute<AlgebraicNumber<C>> aengine = (FactorAbsolute<AlgebraicNumber<C>>) FactorFactory
292 .<C> getImplementation(afac);
293 Factors<AlgebraicNumber<C>> fif = aengine.baseFactorsAbsoluteIrreducible(fi);
294 //System.out.println("fif = " + fif);
295 facar.add(fif);
296 }
297 }
298 if (facar.size() == 0) {
299 facar = null;
300 }
301 // find minimal field extension K(beta) \subset K(alpha)
302 return new Factors<C>(P, afac, Pa, faca, facar);
303 }
304
305
306 /**
307 * Univariate GenPolynomial algebraic partial fraction decomposition,
308 * Absolute factorization or Rothstein-Trager algorithm.
309 * @param A univariate GenPolynomial, deg(A) < deg(P).
310 * @param P univariate squarefree GenPolynomial, gcd(A,P) == 1.
311 * @return partial fraction container.
312 */
313 public PartialFraction<C> baseAlgebraicPartialFraction(GenPolynomial<C> A, GenPolynomial<C> P) {
314 if (P == null || P.isZERO() ) {
315 throw new IllegalArgumentException(" P == null or P == 0");
316 }
317 if (A == null || A.isZERO() ) {
318 throw new IllegalArgumentException(" A == null or A == 0");
319 // PartialFraction(A,P,al,pl,empty,empty)
320 }
321 //System.out.println("\nP_base_algeb_part = " + P);
322 GenPolynomialRing<C> pfac = P.ring; // K[x]
323 if (pfac.nvar > 1) {
324 //System.out.println("facs_base_irred: univ");
325 throw new IllegalArgumentException("only for univariate polynomials");
326 }
327 if (!pfac.coFac.isField()) {
328 //System.out.println("facs_base_irred: field");
329 throw new IllegalArgumentException("only for field coefficients");
330 }
331 List<C> cfactors = new ArrayList<C>();
332 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>();
333 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>();
334 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
335
336 // P linear
337 if (P.degree(0) <= 1) {
338 cfactors.add(A.leadingBaseCoefficient());
339 cdenom.add(P);
340 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
341 }
342 List<GenPolynomial<C>> Pfac = baseFactorsSquarefree(P);
343 //System.out.println("\nPfac = " + Pfac);
344
345 List<GenPolynomial<C>> Afac = engine.basePartialFraction(A,Pfac);
346
347 GenPolynomial<C> A0 = Afac.remove(0);
348 if ( !A0.isZERO() ) {
349 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)");
350 }
351
352 // algebraic and linear factors
353 int i = 0;
354 for ( GenPolynomial<C> pi : Pfac ) {
355 GenPolynomial<C> ai = Afac.get(i++);
356 if ( pi.degree(0) <= 1 ) {
357 cfactors.add( ai.leadingBaseCoefficient() );
358 cdenom.add(pi);
359 continue;
360 }
361 PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducibleAbsolute(ai,pi);
362 //PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducible(ai,pi);
363 cfactors.addAll( pf.cfactors );
364 cdenom.addAll( pf.cdenom );
365 afactors.addAll( pf.afactors );
366 adenom.addAll( pf.adenom );
367 }
368 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
369 }
370
371
372 /**
373 * Univariate GenPolynomial algebraic partial fraction decomposition,
374 * Rothstein-Trager algorithm.
375 * @param A univariate GenPolynomial, deg(A) < deg(P).
376 * @param P univariate squarefree GenPolynomial, gcd(A,P) == 1.
377 * @return partial fraction container.
378 */
379 @Deprecated
380 public PartialFraction<C> baseAlgebraicPartialFractionIrreducible(GenPolynomial<C> A, GenPolynomial<C> P) {
381 if (P == null || P.isZERO() ) {
382 throw new IllegalArgumentException(" P == null or P == 0");
383 }
384 //System.out.println("\nP_base_algeb_part = " + P);
385 GenPolynomialRing<C> pfac = P.ring; // K[x]
386 if (pfac.nvar > 1) {
387 //System.out.println("facs_base_irred: univ");
388 throw new IllegalArgumentException("only for univariate polynomials");
389 }
390 if (!pfac.coFac.isField()) {
391 //System.out.println("facs_base_irred: field");
392 throw new IllegalArgumentException("only for field coefficients");
393 }
394 List<C> cfactors = new ArrayList<C>();
395 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>();
396 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>();
397 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
398
399 // P linear
400 if (P.degree(0) <= 1) {
401 cfactors.add(A.leadingBaseCoefficient());
402 cdenom.add(P);
403 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
404 }
405
406 // deriviative
407 GenPolynomial<C> Pp = PolyUtil.<C> baseDeriviative(P);
408 //no: Pp = Pp.monic();
409 //System.out.println("\nP = " + P);
410 //System.out.println("Pp = " + Pp);
411
412 // Q[t]
413 String[] vars = new String[] { "t" };
414 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(pfac.coFac, 1, pfac.tord, vars);
415 GenPolynomial<C> t = cfac.univariate(0);
416 //System.out.println("t = " + t);
417
418 // Q[x][t]
419 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(pfac, cfac); // sic
420 //System.out.println("rfac = " + rfac.toScript());
421
422 // transform polynomials to bi-variate polynomial
423 GenPolynomial<GenPolynomial<C>> Ac = PolyUfdUtil.<C> introduceLowerVariable(rfac, A);
424 //System.out.println("Ac = " + Ac);
425 GenPolynomial<GenPolynomial<C>> Pc = PolyUfdUtil.<C> introduceLowerVariable(rfac, P);
426 //System.out.println("Pc = " + Pc);
427 GenPolynomial<GenPolynomial<C>> Pcp = PolyUfdUtil.<C> introduceLowerVariable(rfac, Pp);
428 //System.out.println("Pcp = " + Pcp);
429
430 // Q[t][x]
431 GenPolynomialRing<GenPolynomial<C>> rfac1 = Pc.ring;
432 //System.out.println("rfac1 = " + rfac1.toScript());
433
434 // A - t P'
435 GenPolynomial<GenPolynomial<C>> tc = rfac1.getONE().multiply(t);
436 //System.out.println("tc = " + tc);
437 GenPolynomial<GenPolynomial<C>> At = Ac.subtract( tc.multiply(Pcp) );
438 //System.out.println("At = " + At);
439
440 GreatestCommonDivisorSubres<C> engine = new GreatestCommonDivisorSubres<C>();
441 // = GCDFactory.<C>getImplementation( cfac.coFac );
442 GreatestCommonDivisorAbstract<AlgebraicNumber<C>> aengine = null;
443
444 GenPolynomial<GenPolynomial<C>> Rc = engine.recursiveResultant(Pc, At);
445 //System.out.println("Rc = " + Rc);
446 GenPolynomial<C> res = Rc.leadingBaseCoefficient();
447 //no: res = res.monic();
448 //System.out.println("\nres = " + res);
449
450 SortedMap<GenPolynomial<C>,Long> resfac = baseFactors(res);
451 //System.out.println("resfac = " + resfac + "\n");
452
453 for ( GenPolynomial<C> r : resfac.keySet() ) {
454 //System.out.println("\nr(t) = " + r);
455 if ( r.isConstant() ) {
456 continue;
457 }
458 // if ( r.degree(0) <= 1L ) {
459 // System.out.println("warning linear factor in resultant ignored");
460 // continue;
461 // //throw new ArithmeticException("input not irreducible");
462 // }
463 //vars = new String[] { "z_" + Math.abs(r.hashCode() % 1000) };
464 vars = pfac.newVars( "z_" );
465 pfac = pfac.clone();
466 vars = pfac.setVars(vars);
467 r = pfac.copy(r); // hack to exchange the variables
468 //System.out.println("r(z_) = " + r);
469 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(r, true); // since irreducible
470 logger.debug("afac = " + afac.toScript());
471 AlgebraicNumber<C> a = afac.getGenerator();
472 //no: a = a.negate();
473 //System.out.println("a = " + a);
474
475 // K(alpha)[x]
476 GenPolynomialRing<AlgebraicNumber<C>> pafac
477 = new GenPolynomialRing<AlgebraicNumber<C>>(afac, Pc.ring);
478 //System.out.println("pafac = " + pafac.toScript());
479
480 // convert to K(alpha)[x]
481 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, P);
482 //System.out.println("Pa = " + Pa);
483 GenPolynomial<AlgebraicNumber<C>> Pap = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, Pp);
484 //System.out.println("Pap = " + Pap);
485 GenPolynomial<AlgebraicNumber<C>> Aa = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, A);
486 //System.out.println("Aa = " + Aa);
487
488 // A - a P'
489 GenPolynomial<AlgebraicNumber<C>> Ap = Aa.subtract( Pap.multiply(a) );
490 //System.out.println("Ap = " + Ap);
491
492 if ( aengine == null ) {
493 aengine = GCDFactory.<AlgebraicNumber<C>>getImplementation( afac );
494 //System.out.println("aengine = " + aengine);
495 }
496 GenPolynomial<AlgebraicNumber<C>> Ga = aengine.baseGcd(Pa,Ap);
497 //System.out.println("Ga = " + Ga);
498 if ( Ga.isConstant() ) {
499 //System.out.println("warning constant gcd ignored");
500 continue;
501 }
502 afactors.add( a );
503 adenom.add( Ga );
504 // quadratic case
505 if ( P.degree(0) == 2 && Ga.degree(0) == 1 ) {
506 GenPolynomial<AlgebraicNumber<C>>[] qra = PolyUtil.<AlgebraicNumber<C>> basePseudoQuotientRemainder(Pa,Ga);
507 GenPolynomial<AlgebraicNumber<C>> Qa = qra[0];
508 if ( !qra[1].isZERO() ) {
509 throw new ArithmeticException("remainder not zero");
510 }
511 //System.out.println("Qa = " + Qa);
512 afactors.add( a.negate() );
513 adenom.add( Qa );
514 }
515 if ( false && P.degree(0) == 3 && Ga.degree(0) == 1 ) {
516 GenPolynomial<AlgebraicNumber<C>>[] qra = PolyUtil.<AlgebraicNumber<C>> basePseudoQuotientRemainder(Pa,Ga);
517 GenPolynomial<AlgebraicNumber<C>> Qa = qra[0];
518 if ( !qra[1].isZERO() ) {
519 throw new ArithmeticException("remainder not zero");
520 }
521 System.out.println("Qa3 = " + Qa);
522 //afactors.add( a.negate() );
523 //adenom.add( Qa );
524 }
525 }
526 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
527 }
528
529
530 /**
531 * Univariate GenPolynomial algebraic partial fraction decomposition,
532 * via absolute factorization to linear factors.
533 * @param A univariate GenPolynomial, deg(A) < deg(P).
534 * @param P univariate squarefree GenPolynomial, gcd(A,P) == 1.
535 * @return partial fraction container.
536 */
537 public PartialFraction<C> baseAlgebraicPartialFractionIrreducibleAbsolute(GenPolynomial<C> A, GenPolynomial<C> P) {
538 if (P == null || P.isZERO() ) {
539 throw new IllegalArgumentException(" P == null or P == 0");
540 }
541 //System.out.println("\nP_base_algeb_part = " + P);
542 GenPolynomialRing<C> pfac = P.ring; // K[x]
543 if (pfac.nvar > 1) {
544 //System.out.println("facs_base_irred: univ");
545 throw new IllegalArgumentException("only for univariate polynomials");
546 }
547 if (!pfac.coFac.isField()) {
548 //System.out.println("facs_base_irred: field");
549 throw new IllegalArgumentException("only for field coefficients");
550 }
551 List<C> cfactors = new ArrayList<C>();
552 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>();
553 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>();
554 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
555
556 // P linear
557 if (P.degree(0) <= 1) {
558 cfactors.add(A.leadingBaseCoefficient());
559 cdenom.add(P);
560 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
561 }
562
563 // non linear case
564 Factors<C> afacs = factorsAbsoluteIrreducible(P);
565 //System.out.println("linear algebraic factors = " + afacs);
566
567 //System.out.println("afactors = " + afacs.afactors);
568 //System.out.println("arfactors = " + afacs.arfactors);
569 //System.out.println("arfactors pol = " + afacs.arfactors.get(0).poly);
570 //System.out.println("arfactors2 = " + afacs.arfactors.get(0).afactors);
571
572 List<GenPolynomial<AlgebraicNumber<C>>> fact = afacs.getFactors();
573 //System.out.println("factors = " + fact);
574 GenPolynomial<AlgebraicNumber<C>> Pa = afacs.apoly;
575
576 GenPolynomial<AlgebraicNumber<C>> Aa = PolyUtil
577 .<C> convertToRecAlgebraicCoefficients(1, Pa.ring, A);
578
579
580 GreatestCommonDivisorAbstract<AlgebraicNumber<C>> aengine = GCDFactory.getProxy(afacs.afac);
581
582 //System.out.println("denom = " + Pa);
583 //System.out.println("numer = " + Aa);
584
585 List<GenPolynomial<AlgebraicNumber<C>>> numers = aengine.basePartialFraction(Aa,fact);
586 //System.out.println("part frac = " + numers);
587 GenPolynomial<AlgebraicNumber<C>> A0 = numers.remove(0);
588 if ( ! A0.isZERO() ) {
589 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)");
590 }
591 int i = 0;
592 for ( GenPolynomial<AlgebraicNumber<C>> fa : fact ) {
593 GenPolynomial<AlgebraicNumber<C>> an = numers.get(i++);
594 if ( fa.degree(0) <= 1 ) {
595 afactors.add(an.leadingBaseCoefficient());
596 adenom.add( fa );
597 continue;
598 }
599 System.out.println("fa = " + fa);
600 Factors<AlgebraicNumber<C>> faf = afacs.getFactor(fa);
601 System.out.println("faf = " + faf);
602 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> fafact = faf.getFactors();
603 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> Aaa = PolyUtil
604 .<AlgebraicNumber<C>> convertToRecAlgebraicCoefficients(1, faf.apoly.ring, an);
605
606 GreatestCommonDivisorAbstract<AlgebraicNumber<AlgebraicNumber<C>>> aaengine = GCDFactory.getImplementation(faf.afac);
607
608 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> anumers = aaengine.basePartialFraction(Aaa,fafact);
609 System.out.println("algeb part frac = " + anumers);
610 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> A0a = anumers.remove(0);
611 if ( ! A0a.isZERO() ) {
612 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)");
613 }
614 int k = 0;
615 for ( GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> faa : fafact ) {
616 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> ana = anumers.get(k++);
617 System.out.println("faa = " + faa);
618 System.out.println("ana = " + ana);
619 if ( faa.degree(0) > 1 ) {
620 throw new ArithmeticException(" faa not linear");
621 }
622 GenPolynomial<AlgebraicNumber<C>> ana1 = (GenPolynomial<AlgebraicNumber<C>>)(GenPolynomial)ana;
623 GenPolynomial<AlgebraicNumber<C>> faa1 = (GenPolynomial<AlgebraicNumber<C>>)(GenPolynomial)faa;
624
625
626 afactors.add(ana1.leadingBaseCoefficient());
627 adenom.add( faa1 );
628 }
629 }
630 return new PartialFraction<C>(A,P,cfactors,cdenom,afactors,adenom);
631 }
632
633
634 /**
635 * GenPolynomial absolute factorization of a polynomial.
636 * @param P GenPolynomial.
637 * @return factors map container: [p_1 -> e_1, ..., p_k -> e_k] with P =
638 * prod_{i=1,...,k} p_i**e_i. <b>Note:</b> K(alpha) not yet
639 * minimal.
640 */
641 public FactorsMap<C> factorsAbsolute(GenPolynomial<C> P) {
642 if (P == null) {
643 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
644 }
645 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>();
646 if (P.isZERO()) {
647 return new FactorsMap<C>(P, factors);
648 }
649 //System.out.println("\nP_mult = " + P);
650 GenPolynomialRing<C> pfac = P.ring; // K[x]
651 if (pfac.nvar <= 1) {
652 return baseFactorsAbsolute(P);
653 }
654 if (!pfac.coFac.isField()) {
655 throw new IllegalArgumentException("only for field coefficients");
656 }
657 if (P.degree() <= 1) {
658 factors.put(P, 1L);
659 return new FactorsMap<C>(P, factors);
660 }
661 // factor over K (=C)
662 SortedMap<GenPolynomial<C>, Long> facs = factors(P);
663 if (debug && !isFactorization(P, facs)) {
664 throw new ArithmeticException("isFactorization = false");
665 }
666 if (logger.isInfoEnabled()) {
667 logger.info("all K factors = " + facs); // Q[X]
668 //System.out.println("\nall K factors = " + facs); // Q[X]
669 }
670 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>();
671 // factor over K(alpha)
672 for (GenPolynomial<C> p : facs.keySet()) {
673 Long e = facs.get(p);
674 if (p.degree() <= 1) {
675 factors.put(p, e);
676 } else {
677 Factors<C> afacs = factorsAbsoluteIrreducible(p);
678 if (afacs.afac == null) { // absolute irreducible
679 factors.put(p, e);
680 } else {
681 afactors.put(afacs, e);
682 }
683 }
684 }
685 //System.out.println("K(alpha) factors multi = " + factors);
686 return new FactorsMap<C>(P, factors, afactors);
687 }
688
689
690 /**
691 * GenPolynomial absolute factorization of a squarefree polynomial.
692 * @param P squarefree and primitive GenPolynomial.
693 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k}
694 * p_i. <b>Note:</b> K(alpha) not yet minimal.
695 */
696 // @Override
697 public FactorsList<C> factorsAbsoluteSquarefree(GenPolynomial<C> P) {
698 if (P == null) {
699 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
700 }
701 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>();
702 if (P.isZERO()) {
703 return new FactorsList<C>(P, factors);
704 }
705 //System.out.println("\nP = " + P);
706 GenPolynomialRing<C> pfac = P.ring; // K[x]
707 if (pfac.nvar <= 1) {
708 return baseFactorsAbsoluteSquarefree(P);
709 }
710 if (!pfac.coFac.isField()) {
711 throw new IllegalArgumentException("only for field coefficients");
712 }
713 if (P.degree() <= 1) {
714 factors.add(P);
715 return new FactorsList<C>(P, factors);
716 }
717 // factor over K (=C)
718 List<GenPolynomial<C>> facs = factorsSquarefree(P);
719 if (debug && !isFactorization(P, facs)) {
720 throw new ArithmeticException("isFactorization = false");
721 }
722 if (logger.isInfoEnabled()) {
723 logger.info("all K factors = " + facs); // Q[X]
724 //System.out.println("\nall K factors = " + facs); // Q[X]
725 }
726 List<Factors<C>> afactors = new ArrayList<Factors<C>>();
727 // factor over K(alpha)
728 for (GenPolynomial<C> p : facs) {
729 if (p.degree() <= 1) {
730 factors.add(p);
731 } else {
732 Factors<C> afacs = factorsAbsoluteIrreducible(p);
733 if (debug) {
734 logger.info("K(alpha) factors = " + afacs); // K(alpha)[X]
735 }
736 if (afacs.afac == null) { // absolute irreducible
737 factors.add(p);
738 } else {
739 afactors.add(afacs);
740 }
741 }
742 }
743 //System.out.println("K(alpha) factors = " + factors);
744 return new FactorsList<C>(P, factors, afactors);
745 }
746
747
748 /**
749 * GenPolynomial absolute factorization of a irreducible polynomial.
750 * @param P irreducible! GenPolynomial.
751 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i
752 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x],
753 * where K \subset K(alpha) \subset L is an algebraically closed
754 * field over K. <b>Note:</b> K(alpha) not yet minimal.
755 */
756 public Factors<C> factorsAbsoluteIrreducible(GenPolynomial<C> P) {
757 if (P == null) {
758 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
759 }
760 if (P.isZERO()) {
761 return new Factors<C>(P);
762 }
763 GenPolynomialRing<C> pfac = P.ring; // K[x]
764 if (pfac.nvar <= 1) {
765 return baseFactorsAbsoluteIrreducible(P);
766 }
767 if (!pfac.coFac.isField()) {
768 throw new IllegalArgumentException("only for field coefficients");
769 }
770 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>();
771 if (P.degree() <= 1) {
772 return new Factors<C>(P);
773 }
774 // find field extension K(alpha)
775 GenPolynomial<C> up = P;
776 RingFactory<C> cf = pfac.coFac;
777 long cr = cf.characteristic().longValue(); // char might be larger
778 if (cr == 0L) {
779 cr = Long.MAX_VALUE;
780 }
781 long rp = 0L;
782 for (int i = 0; i < (pfac.nvar - 1); i++) {
783 rp = 0L;
784 GenPolynomialRing<C> nfac = pfac.contract(1);
785 String[] vn = new String[] { pfac.getVars()[pfac.nvar - 1] };
786 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(nfac, 1,
787 pfac.tord, vn);
788 GenPolynomial<GenPolynomial<C>> upr = PolyUtil.<C> recursive(rfac, up);
789 //System.out.println("upr = " + upr);
790 GenPolynomial<C> ep;
791 do {
792 if (rp >= cr) {
793 throw new ArithmeticException("elements of prime field exhausted: " + cr);
794 }
795 C r = cf.fromInteger(rp); //cf.random(rp);
796 //System.out.println("r = " + r);
797 ep = PolyUtil.<C> evaluateMainRecursive(nfac, upr, r);
798 //System.out.println("ep = " + ep);
799 rp++;
800 } while (!isSquarefree(ep) /*todo: || ep.degree() <= 1*/); // max deg
801 up = ep;
802 pfac = nfac;
803 }
804 up = up.monic();
805 if (debug) {
806 logger.info("P(" + rp + ") = " + up);
807 //System.out.println("up = " + up);
808 }
809 if (debug && !isSquarefree(up)) {
810 throw new ArithmeticException("not irreducible up = " + up);
811 }
812 if (up.degree(0) <= 1) {
813 return new Factors<C>(P);
814 }
815 // find irreducible factor of up
816 List<GenPolynomial<C>> UF = baseFactorsSquarefree(up);
817 //System.out.println("UF = " + UF);
818 FactorsList<C> aUF = baseFactorsAbsoluteSquarefree(up);
819 //System.out.println("aUF = " + aUF);
820 AlgebraicNumberRing<C> arfac = aUF.findExtensionField();
821 //System.out.println("arfac = " + arfac);
822
823 long e = up.degree(0);
824 // search factor polynomial with smallest degree
825 for (int i = 0; i < UF.size(); i++) {
826 GenPolynomial<C> upi = UF.get(i);
827 long d = upi.degree(0);
828 if (1 <= d && d <= e) {
829 up = upi;
830 e = up.degree(0);
831 }
832 }
833 if (up.degree(0) <= 1) {
834 return new Factors<C>(P);
835 }
836 if (debug) {
837 logger.info("field extension by " + up);
838 }
839
840 List<GenPolynomial<AlgebraicNumber<C>>> afactors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
841
842 // setup field extension K(alpha)
843 //String[] vars = new String[] { "z_" + Math.abs(up.hashCode() % 1000) };
844 String[] vars = pfac.newVars( "z_" );
845 pfac = pfac.clone();
846 String[] ovars = pfac.setVars(vars); // side effects!
847 GenPolynomial<C> aup = pfac.copy(up); // hack to exchange the variables
848
849 //AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aup,true); // since irreducible
850 AlgebraicNumberRing<C> afac = arfac;
851 int depth = afac.depth();
852 //System.out.println("afac = " + afac);
853 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac,
854 P.ring.nvar, P.ring.tord, P.ring.getVars());
855 //System.out.println("pafac = " + pafac);
856 // convert to K(alpha)
857 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil
858 .<C> convertToRecAlgebraicCoefficients(depth, pafac, P);
859 //System.out.println("Pa = " + Pa);
860 // factor over K(alpha)
861 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac);
862 afactors = engine.factorsSquarefree(Pa);
863 if (debug) {
864 logger.info("K(alpha) factors multi = " + afactors);
865 //System.out.println("K(alpha) factors = " + afactors);
866 }
867 if (afactors.size() <= 1) {
868 return new Factors<C>(P);
869 }
870 // normalize first factor to monic
871 GenPolynomial<AlgebraicNumber<C>> p1 = afactors.get(0);
872 AlgebraicNumber<C> p1c = p1.leadingBaseCoefficient();
873 if (!p1c.isONE()) {
874 GenPolynomial<AlgebraicNumber<C>> p2 = afactors.get(1);
875 afactors.remove(p1);
876 afactors.remove(p2);
877 p1 = p1.divide(p1c);
878 p2 = p2.multiply(p1c);
879 afactors.add(p1);
880 afactors.add(p2);
881 }
882 // recursion for splitting field
883 // find minimal field extension K(beta) \subset K(alpha)
884 return new Factors<C>(P, afac, Pa, afactors);
885 }
886
887
888 /**
889 * GenPolynomial is absolute factorization.
890 * @param facs factors container.
891 * @return true if P = prod_{i=1,...,r} p_i, else false.
892 */
893 public boolean isAbsoluteFactorization(Factors<C> facs) {
894 if (facs == null) {
895 throw new IllegalArgumentException("facs may not be null");
896 }
897 if (facs.afac == null) {
898 return true;
899 }
900 GenPolynomial<AlgebraicNumber<C>> fa = facs.apoly;
901 GenPolynomialRing<AlgebraicNumber<C>> pafac = fa.ring;
902 GenPolynomial<AlgebraicNumber<C>> t = pafac.getONE();
903 for (GenPolynomial<AlgebraicNumber<C>> f : facs.afactors) {
904 t = t.multiply(f);
905 }
906 //return fa.equals(t) || fa.equals(t.negate());
907 boolean b = fa.equals(t) || fa.equals(t.negate());
908 if ( b ) {
909 return b;
910 }
911 if ( facs.arfactors == null ) {
912 return false;
913 }
914 for (Factors<AlgebraicNumber<C>> arp : facs.arfactors) {
915 t = t.multiply(arp.poly);
916 }
917 b = fa.equals(t) || fa.equals(t.negate());
918 if (!b) {
919 System.out.println("\nFactors: " + facs);
920 System.out.println("fa = " + fa);
921 System.out.println("t = " + t);
922 }
923 return b;
924 }
925
926
927 /**
928 * GenPolynomial is absolute factorization.
929 * @param facs factors list container.
930 * @return true if P = prod_{i=1,...,r} p_i, else false.
931 */
932 public boolean isAbsoluteFactorization(FactorsList<C> facs) {
933 if (facs == null) {
934 throw new IllegalArgumentException("facs may not be null");
935 }
936 GenPolynomial<C> P = facs.poly;
937 GenPolynomial<C> t = P.ring.getONE();
938 for (GenPolynomial<C> f : facs.factors) {
939 t = t.multiply(f);
940 }
941 if (P.equals(t) || P.equals(t.negate())) {
942 return true;
943 }
944 if (facs.afactors == null) {
945 return false;
946 }
947 for (Factors<C> fs : facs.afactors) {
948 if (!isAbsoluteFactorization(fs)) {
949 return false;
950 }
951 t = t.multiply(facs.poly);
952 }
953 //return P.equals(t) || P.equals(t.negate());
954 boolean b = P.equals(t) || P.equals(t.negate());
955 if (!b) {
956 System.out.println("\nFactorsList: " + facs);
957 System.out.println("P = " + P);
958 System.out.println("t = " + t);
959 }
960 return b;
961 }
962
963
964 /**
965 * GenPolynomial is absolute factorization.
966 * @param facs factors map container.
967 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false.
968 */
969 public boolean isAbsoluteFactorization(FactorsMap<C> facs) {
970 if (facs == null) {
971 throw new IllegalArgumentException("facs may not be null");
972 }
973 GenPolynomial<C> P = facs.poly;
974 GenPolynomial<C> t = P.ring.getONE();
975 for (GenPolynomial<C> f : facs.factors.keySet()) {
976 long e = facs.factors.get(f);
977 GenPolynomial<C> g = Power.<GenPolynomial<C>> positivePower(f, e);
978 t = t.multiply(g);
979 }
980 if (P.equals(t) || P.equals(t.negate())) {
981 return true;
982 }
983 if (facs.afactors == null) {
984 return false;
985 }
986 for (Factors<C> fs : facs.afactors.keySet()) {
987 if (!isAbsoluteFactorization(fs)) {
988 return false;
989 }
990 long e = facs.afactors.get(fs);
991 GenPolynomial<C> g = Power.<GenPolynomial<C>> positivePower(fs.poly, e);
992 t = t.multiply(g);
993 }
994 boolean b = P.equals(t) || P.equals(t.negate());
995 if (!b) {
996 System.out.println("\nFactorsMap: " + facs);
997 System.out.println("P = " + P);
998 System.out.println("t = " + t);
999 }
1000 return b;
1001 }
1002
1003 }