001 /*
002 * $Id: FactorRational.java 3733 2011-08-13 20:08:25Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.arith.BigInteger;
014 import edu.jas.arith.BigRational;
015 import edu.jas.poly.GenPolynomial;
016 import edu.jas.poly.GenPolynomialRing;
017 import edu.jas.poly.PolyUtil;
018
019
020 /**
021 * Rational number coefficients factorization algorithms.
022 * This class implements factorization methods for polynomials over rational numbers.
023 * @author Heinz Kredel
024 */
025
026 public class FactorRational extends FactorAbsolute<BigRational> {
027
028
029 private static final Logger logger = Logger.getLogger(FactorRational.class);
030
031
032 private final boolean debug = true || 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 }