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