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&lt;RealAlgebraicNumber&lt;C&gt;&gt;.
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}