001/* 002 * $Id: FactorQuotient.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.poly.GenPolynomial; 014import edu.jas.poly.GenPolynomialRing; 015import edu.jas.structure.GcdRingElem; 016 017 018/** 019 * Rational function coefficients factorization algorithms. This class 020 * implements factorization methods for polynomials over rational functions, 021 * that is, with coefficients from class <code>application.Quotient</code>. 022 * @author Heinz Kredel 023 */ 024 025public class FactorQuotient<C extends GcdRingElem<C>> extends FactorAbstract<Quotient<C>> { 026 027 028 private static final Logger logger = Logger.getLogger(FactorQuotient.class); 029 030 031 //private final boolean debug = logger.isInfoEnabled(); 032 033 034 /** 035 * Factorization engine for normal coefficients. 036 */ 037 protected final FactorAbstract<C> nengine; 038 039 040 /** 041 * No argument constructor. 042 */ 043 protected FactorQuotient() { 044 throw new IllegalArgumentException("don't use this constructor"); 045 } 046 047 048 /** 049 * Constructor. 050 * @param fac coefficient quotient ring factory. 051 */ 052 public FactorQuotient(QuotientRing<C> fac) { 053 this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac)); 054 } 055 056 057 /** 058 * Constructor. 059 * @param fac coefficient quotient ring factory. 060 * @param nengine factorization engine for polynomials over base 061 * coefficients. 062 */ 063 public FactorQuotient(QuotientRing<C> fac, FactorAbstract<C> nengine) { 064 super(fac); 065 this.nengine = nengine; 066 } 067 068 069 /** 070 * GenPolynomial base factorization of a squarefree polynomial. 071 * @param P squarefree GenPolynomial. 072 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 073 */ 074 @Override 075 public List<GenPolynomial<Quotient<C>>> baseFactorsSquarefree(GenPolynomial<Quotient<C>> P) { 076 return factorsSquarefree(P); 077 } 078 079 080 /** 081 * GenPolynomial factorization of a squarefree polynomial. 082 * @param P squarefree GenPolynomial. 083 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 084 */ 085 @Override 086 public List<GenPolynomial<Quotient<C>>> factorsSquarefree(GenPolynomial<Quotient<C>> P) { 087 if (P == null) { 088 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 089 } 090 //System.out.println("factorsSquarefree, P = " + P); 091 List<GenPolynomial<Quotient<C>>> factors = new ArrayList<GenPolynomial<Quotient<C>>>(); 092 if (P.isZERO()) { 093 return factors; 094 } 095 if (P.isONE()) { 096 factors.add(P); 097 return factors; 098 } 099 GenPolynomialRing<Quotient<C>> pfac = P.ring; 100 GenPolynomial<Quotient<C>> Pr = P; 101 Quotient<C> ldcf = P.leadingBaseCoefficient(); 102 if (!ldcf.isONE()) { 103 //System.out.println("ldcf = " + ldcf); 104 Pr = Pr.monic(); 105 } 106 QuotientRing<C> qi = (QuotientRing<C>) pfac.coFac; 107 GenPolynomialRing<C> ci = qi.ring; 108 GenPolynomialRing<GenPolynomial<C>> ifac = new GenPolynomialRing<GenPolynomial<C>>(ci, pfac); 109 GenPolynomial<GenPolynomial<C>> Pi = PolyUfdUtil.<C> integralFromQuotientCoefficients(ifac, Pr); 110 //System.out.println("Pi = " + Pi); 111 112 // factor in C[x_1,...,x_n][y_1,...,y_m] 113 List<GenPolynomial<GenPolynomial<C>>> irfacts = nengine.recursiveFactorsSquarefree(Pi); 114 if (logger.isInfoEnabled()) { 115 logger.info("irfacts = " + irfacts); 116 } 117 if (irfacts.size() <= 1) { 118 factors.add(P); 119 return factors; 120 } 121 List<GenPolynomial<Quotient<C>>> qfacts = PolyUfdUtil.<C> quotientFromIntegralCoefficients(pfac, 122 irfacts); 123 //System.out.println("qfacts = " + qfacts); 124 //qfacts = PolyUtil.monic(qfacts); 125 //System.out.println("qfacts = " + qfacts); 126 if (!ldcf.isONE()) { 127 GenPolynomial<Quotient<C>> r = qfacts.get(0); 128 qfacts.remove(r); 129 r = r.multiply(ldcf); 130 qfacts.add(0, r); 131 } 132 if (logger.isInfoEnabled()) { 133 logger.info("qfacts = " + qfacts); 134 } 135 factors.addAll(qfacts); 136 return factors; 137 } 138 139}