001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufdroot; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.logging.log4j.Logger; 012import org.apache.logging.log4j.LogManager; 013 014import edu.jas.arith.Rational; 015import edu.jas.poly.AlgebraicNumber; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.root.PolyUtilRoot; 019import edu.jas.root.RealAlgebraicNumber; 020import edu.jas.root.RealAlgebraicRing; 021import edu.jas.structure.GcdRingElem; 022import edu.jas.ufd.FactorAbstract; 023import edu.jas.ufd.FactorFactory; 024 025 026/** 027 * Real algebraic number coefficients factorization algorithms. This class 028 * implements factorization methods for polynomials over real algebraic numbers 029 * from package <code>edu.jas.root</code>. 030 * 031 * @param <C> coefficient type 032 * @author Heinz Kredel 033 */ 034 035public class FactorRealAlgebraic<C extends GcdRingElem<C> & Rational> extends 036 FactorAbstract<RealAlgebraicNumber<C>> { 037 038 039 //TODO: absolute factorization would mean factorization to linear and quadratic factors 040 //FactorAbsolute<AlgebraicNumber<C>> 041 //FactorAbstract<AlgebraicNumber<C>> 042 043 044 private static final Logger logger = LogManager.getLogger(FactorRealAlgebraic.class); 045 046 047 //private static final boolean debug = logger.isInfoEnabled(); 048 049 050 /** 051 * Factorization engine for base coefficients. 052 */ 053 public final FactorAbstract<AlgebraicNumber<C>> factorAlgebraic; 054 055 056 /** 057 * No argument constructor. <b>Note:</b> can't use this constructor. 058 */ 059 protected FactorRealAlgebraic() { 060 throw new IllegalArgumentException("don't use this constructor"); 061 } 062 063 064 /** 065 * Constructor. 066 * @param fac algebraic number factory. 067 */ 068 public FactorRealAlgebraic(RealAlgebraicRing<C> fac) { 069 this(fac, FactorFactory.<AlgebraicNumber<C>> getImplementation(fac.algebraic)); 070 } 071 072 073 /** 074 * Constructor. 075 * @param fac algebraic number factory. 076 * @param factorAlgebraic factorization engine for polynomials over base 077 * coefficients. 078 */ 079 public FactorRealAlgebraic(RealAlgebraicRing<C> fac, FactorAbstract<AlgebraicNumber<C>> factorAlgebraic) { 080 super(fac); 081 this.factorAlgebraic = factorAlgebraic; 082 } 083 084 085 /** 086 * GenPolynomial base factorization of a squarefree polynomial. 087 * @param P squarefree GenPolynomial<RealAlgebraicNumber<C>>. 088 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 089 */ 090 @Override 091 public List<GenPolynomial<RealAlgebraicNumber<C>>> baseFactorsSquarefree( 092 GenPolynomial<RealAlgebraicNumber<C>> P) { 093 if (P == null) { 094 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 095 } 096 List<GenPolynomial<RealAlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<RealAlgebraicNumber<C>>>(); 097 if (P.isZERO()) { 098 return factors; 099 } 100 if (P.isONE()) { 101 factors.add(P); 102 return factors; 103 } 104 GenPolynomialRing<RealAlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x] 105 if (pfac.nvar > 1) { 106 throw new IllegalArgumentException("only for univariate polynomials"); 107 } 108 RealAlgebraicRing<C> rfac = (RealAlgebraicRing<C>) pfac.coFac; 109 110 RealAlgebraicNumber<C> ldcf = P.leadingBaseCoefficient(); 111 if (!ldcf.isONE()) { 112 P = P.monic(); 113 factors.add(pfac.getONE().multiply(ldcf)); 114 } 115 //System.out.println("\nP = " + P); 116 GenPolynomialRing<AlgebraicNumber<C>> afac = new GenPolynomialRing<AlgebraicNumber<C>>( 117 rfac.algebraic, pfac); 118 GenPolynomial<AlgebraicNumber<C>> A = PolyUtilRoot.<C> algebraicFromRealCoefficients(afac, P); 119 // factor A: 120 List<GenPolynomial<AlgebraicNumber<C>>> afactors = factorAlgebraic.baseFactorsSquarefree(A); 121 for (GenPolynomial<AlgebraicNumber<C>> a : afactors) { 122 GenPolynomial<RealAlgebraicNumber<C>> p = PolyUtilRoot.<C> realFromAlgebraicCoefficients(pfac, a); 123 factors.add(p); 124 } 125 logger.info("real algebraic factors = {}", factors); 126 return factors; 127 } 128 129}