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