001/*
002 * $Id: FactorRational.java 4067 2012-07-27 16:17:35Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.arith.BigInteger;
014import edu.jas.arith.BigRational;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.PolyUtil;
018
019
020/**
021 * Rational number coefficients factorization algorithms. This class implements
022 * factorization methods for polynomials over rational numbers.
023 * @author Heinz Kredel
024 */
025
026public class FactorRational extends FactorAbsolute<BigRational> {
027
028
029    private static final Logger logger = Logger.getLogger(FactorRational.class);
030
031
032    private final boolean debug = logger.isInfoEnabled();
033
034
035    /**
036     * Factorization engine for integer base coefficients.
037     */
038    protected final FactorAbstract<BigInteger> iengine;
039
040
041    /**
042     * No argument constructor.
043     */
044    protected FactorRational() {
045        super(BigRational.ONE);
046        iengine = FactorFactory.getImplementation(BigInteger.ONE);
047    }
048
049
050    /**
051     * GenPolynomial base factorization of a squarefree polynomial.
052     * @param P squarefree GenPolynomial.
053     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
054     */
055    @Override
056    public List<GenPolynomial<BigRational>> baseFactorsSquarefree(GenPolynomial<BigRational> P) {
057        if (P == null) {
058            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
059        }
060        List<GenPolynomial<BigRational>> factors = new ArrayList<GenPolynomial<BigRational>>();
061        if (P.isZERO()) {
062            return factors;
063        }
064        if (P.isONE()) {
065            factors.add(P);
066            return factors;
067        }
068        GenPolynomialRing<BigRational> pfac = P.ring;
069        if (pfac.nvar > 1) {
070            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
071        }
072        GenPolynomial<BigRational> Pr = P;
073        BigRational ldcf = P.leadingBaseCoefficient();
074        if (!ldcf.isONE()) {
075            //System.out.println("ldcf = " + ldcf);
076            Pr = Pr.monic();
077        }
078        BigInteger bi = BigInteger.ONE;
079        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac);
080        GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr);
081        if (debug) {
082            logger.info("Pi = " + Pi);
083        }
084        List<GenPolynomial<BigInteger>> ifacts = iengine.baseFactorsSquarefree(Pi);
085        if (logger.isInfoEnabled()) {
086            logger.info("ifacts = " + ifacts);
087        }
088        if (ifacts.size() <= 1) {
089            factors.add(P);
090            return factors;
091        }
092        List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts);
093        //System.out.println("rfacts = " + rfacts);
094        rfacts = PolyUtil.monic(rfacts);
095        //System.out.println("rfacts = " + rfacts);
096        if (!ldcf.isONE()) {
097            GenPolynomial<BigRational> r = rfacts.get(0);
098            rfacts.remove(r);
099            r = r.multiply(ldcf);
100            rfacts.set(0, r);
101        }
102        if (logger.isInfoEnabled()) {
103            logger.info("rfacts = " + rfacts);
104        }
105        factors.addAll(rfacts);
106        return factors;
107    }
108
109
110    /**
111     * GenPolynomial factorization of a squarefree polynomial.
112     * @param P squarefree GenPolynomial.
113     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
114     */
115    @Override
116    public List<GenPolynomial<BigRational>> factorsSquarefree(GenPolynomial<BigRational> P) {
117        if (P == null) {
118            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
119        }
120        List<GenPolynomial<BigRational>> factors = new ArrayList<GenPolynomial<BigRational>>();
121        if (P.isZERO()) {
122            return factors;
123        }
124        if (P.isONE()) {
125            factors.add(P);
126            return factors;
127        }
128        GenPolynomialRing<BigRational> pfac = P.ring;
129        if (pfac.nvar == 1) {
130            return baseFactorsSquarefree(P);
131        }
132        GenPolynomial<BigRational> Pr = P;
133        BigRational ldcf = P.leadingBaseCoefficient();
134        if (!ldcf.isONE()) {
135            //System.out.println("ldcf = " + ldcf);
136            Pr = Pr.monic();
137        }
138        BigInteger bi = BigInteger.ONE;
139        GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(bi, pfac);
140        GenPolynomial<BigInteger> Pi = PolyUtil.integerFromRationalCoefficients(ifac, Pr);
141        if (debug) {
142            logger.info("Pi = " + Pi);
143        }
144        List<GenPolynomial<BigInteger>> ifacts = iengine.factorsSquarefree(Pi);
145        if (logger.isInfoEnabled()) {
146            logger.info("ifacts = " + ifacts);
147        }
148        if (ifacts.size() <= 1) {
149            factors.add(P);
150            return factors;
151        }
152        List<GenPolynomial<BigRational>> rfacts = PolyUtil.fromIntegerCoefficients(pfac, ifacts);
153        //System.out.println("rfacts = " + rfacts);
154        rfacts = PolyUtil.monic(rfacts);
155        //System.out.println("rfacts = " + rfacts);
156        if (!ldcf.isONE()) {
157            GenPolynomial<BigRational> r = rfacts.get(0);
158            rfacts.remove(r);
159            r = r.multiply(ldcf);
160            rfacts.set(0, r);
161        }
162        if (logger.isInfoEnabled()) {
163            logger.info("rfacts = " + rfacts);
164        }
165        factors.addAll(rfacts);
166        return factors;
167    }
168
169}