[Home] DMelt member access. Java source code: edu.jas.fd.FDUtil
/*
* $Id$
*/
package edu.jas.fd;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;
import java.util.Collection;
import org.apache.log4j.Logger;
import edu.jas.poly.ExpVector;
import edu.jas.poly.PolyUtil;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.poly.GenSolvablePolynomialRing;
import edu.jas.poly.RecSolvablePolynomial;
import edu.jas.poly.RecSolvablePolynomialRing;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingElem;
import edu.jas.structure.RingFactory;
import edu.jas.gbmod.SolvableQuotient;
import edu.jas.gbmod.SolvableQuotientRing;
import edu.jas.gbmod.QuotSolvablePolynomial;
import edu.jas.gbmod.QuotSolvablePolynomialRing;
/**
* Factorization domain utilities, for example recursive pseudo remainder.
* @author Heinz Kredel
*/
public class FDUtil {
private static final Logger logger = Logger.getLogger(FDUtil.class);
private static boolean debug = logger.isDebugEnabled();
/**
* GenSolvablePolynomial sparse pseudo remainder for univariate
* polynomials.
* @param coefficient type.
* @param P GenSolvablePolynomial.
* @param S nonzero GenSolvablePolynomial.
* @return remainder with ldcf(S)m' P = quotient * S + remainder.
* m' ≤ deg(P)-deg(S)
* @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial baseSparsePseudoRemainder(
GenSolvablePolynomial P, GenSolvablePolynomial S) {
if (S == null || S.isZERO()) {
throw new ArithmeticException(P.toString() + " division by zero " + S);
}
if (P.isZERO()) {
return P;
}
if (S.isConstant()) {
return P.ring.getZERO();
}
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorSimple();
ExpVector e = S.leadingExpVector();
GenSolvablePolynomial h;
GenSolvablePolynomial r = P;
while (!r.isZERO()) {
ExpVector f = r.leadingExpVector();
if (f.multipleOf(e)) {
C a = r.leadingBaseCoefficient();
f = f.subtract(e);
h = S.multiplyLeft(f); // coeff a
C c = h.leadingBaseCoefficient();
// need ga, gc: ga a = gc c
C[] oc = fd.leftOreCond(a,c);
C ga = oc[0];
C gc = oc[1];
r = r.multiplyLeft(ga); // coeff ga a, exp f
h = h.multiplyLeft(gc); // coeff gc c, exp f
r = (GenSolvablePolynomial) r.subtract(h);
} else {
break;
}
}
return r;
}
/**
* GenSolvablePolynomial sparse pseudo quotient for univariate polynomials or
* exact division.
* @param coefficient type.
* @param P GenSolvablePolynomial.
* @param S nonzero GenSolvablePolynomial.
* @return quotient with ldcf(S)m' P = quotient * S + remainder.
* m' ≤ deg(P)-deg(S)
* @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial basePseudoQuotient(
GenSolvablePolynomial P, GenSolvablePolynomial S) {
return basePseudoQuotientRemainder(P,S)[0];
}
/**
* GenSolvablePolynomial sparse pseudo quotient and remainder for
* univariate polynomials or exact division.
* @param coefficient type.
* @param P GenSolvablePolynomial.
* @param S nonzero GenSolvablePolynomial.
* @return [ quotient, remainder ] with ldcf(S)m' P = quotient *
* S + remainder. m' ≤ deg(P)-deg(S)
* @see edu.jas.poly.GenPolynomial#divide(edu.jas.poly.GenPolynomial).
*/
@SuppressWarnings("unchecked")
public static > GenSolvablePolynomial[] basePseudoQuotientRemainder(
GenSolvablePolynomial P, GenSolvablePolynomial S) {
if (S == null || S.isZERO()) {
throw new ArithmeticException(P.toString() + " division by zero " + S);
}
//if (S.ring.nvar != 1) { // ok if exact division
// throw new RuntimeException("univariate polynomials only");
//}
GenSolvablePolynomial[] ret = new GenSolvablePolynomial[2];
ret[0] = null;
ret[1] = null;
if (P.isZERO() || S.isONE()) {
ret[0] = P;
ret[1] = S.ring.getZERO();
return ret;
}
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorSimple();
ExpVector e = S.leadingExpVector();
GenSolvablePolynomial h;
GenSolvablePolynomial r = P;
GenSolvablePolynomial q = S.ring.getZERO().copy();
while (!r.isZERO()) {
ExpVector f = r.leadingExpVector();
if (f.multipleOf(e)) {
C a = r.leadingBaseCoefficient();
f = f.subtract(e);
h = S.multiplyLeft(f); // coeff a
C c = h.leadingBaseCoefficient();
C x = a.remainder(c);
if (false&&x.isZERO()) {
C y = a.divide(c);
q = (GenSolvablePolynomial) q.sum(y, f);
h = S.multiply(y, f); // coeff a
} else {
// need ga, gc: ga a = gc c
C[] oc = fd.leftOreCond(a,c);
C ga = oc[0];
C gc = oc[1];
r = r.multiplyLeft(ga); // coeff ga a, exp f
h = h.multiplyLeft(gc); // coeff gc c, exp f
q = q.multiplyLeft(ga); // c
q = (GenSolvablePolynomial) q.sum(gc, f); // a
}
r = (GenSolvablePolynomial) r.subtract(h);
} else {
break;
}
}
//GenPolynomial rhs = q.multiply(S).sum(r);
//GenPolynomial lhs = P;
ret[0] = q;
ret[1] = r;
return ret;
}
/**
* GenSolvablePolynomial sparse pseudo remainder for recursive solvable
* polynomials.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param S nonzero recursive GenSolvablePolynomial.
* @return remainder with ore(ldcf(S)m') P = quotient * S +
* remainder.
* @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial>
recursiveSparsePseudoRemainder(
GenSolvablePolynomial> P, GenSolvablePolynomial> S) {
if (S == null || S.isZERO()) {
throw new ArithmeticException(P + " division by zero " + S);
}
if (P == null || P.isZERO()) {
return P;
}
if (S.isConstant()) {
return P.ring.getZERO();
}
//SolvableSyzygyAbstract syz = new SolvableSyzygyAbstract();
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorSimple();
//GenPolynomial c = S.leadingBaseCoefficient();
ExpVector e = S.leadingExpVector();
GenSolvablePolynomial> h;
GenSolvablePolynomial> r = P;
while (!r.isZERO()) {
ExpVector f = r.leadingExpVector();
if (f.multipleOf(e)) {
GenSolvablePolynomial a = (GenSolvablePolynomial) r.leadingBaseCoefficient();
f = f.subtract(e);
h = S.multiplyLeft(f); // coeff c, exp (f-e) e
GenSolvablePolynomial d = (GenSolvablePolynomial) h.leadingBaseCoefficient();
GenSolvablePolynomial[] oc = fd.leftOreCond(a, d);
GenPolynomial ga = oc[0];
GenPolynomial gd = oc[1];
//System.out.println("OreCond: a = " + a + ", d = " + d);
//System.out.println("OreCond: ga = " + ga + ", gd = " + gd);
// ga a = gd d
r = r.multiplyLeft(ga); // coeff ga a, exp f
h = h.multiplyLeft(gd); // coeff gd d, exp f
if (!r.leadingBaseCoefficient().equals(h.leadingBaseCoefficient())) {
//System.out.println("OreCond: a = " + a + ", d = " + d);
//System.out.println("OreCond: ga = " + ga + ", gd = " + gd);
throw new RuntimeException("should not happen: lc(r) = " + r.leadingBaseCoefficient()
+ ", lc(h) = " + h.leadingBaseCoefficient());
}
r = (GenSolvablePolynomial>) r.subtract(h);
} else {
break;
}
}
return r;
}
/**
* GenSolvablePolynomial right sparse pseudo remainder for recursive solvable
* polynomials. Note: uses right multiplication of P by ldcf(S), not
* always applicable.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param S nonzero recursive GenSolvablePolynomial.
* @return remainder with P ldcf(S)m' = quotient * S + remainder.
* @see edu.jas.poly.PolyUtil#recursiveSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial> recursiveSparsePseudoRemainderRight(
GenSolvablePolynomial> P, GenSolvablePolynomial> S) {
if (S == null || S.isZERO()) {
throw new ArithmeticException(P + " division by zero " + S);
}
if (P == null || P.isZERO()) {
return P;
}
if (S.isConstant()) {
return P.ring.getZERO();
}
//GenPolynomial c = S.leadingBaseCoefficient();
ExpVector e = S.leadingExpVector();
GenSolvablePolynomial> h;
GenSolvablePolynomial> r = P;
while (!r.isZERO()) {
ExpVector f = r.leadingExpVector();
if (f.multipleOf(e)) {
f = f.subtract(e);
h = S.multiplyLeft(f); // coeff c, exp (f-e) e
GenPolynomial d = h.leadingBaseCoefficient();
GenPolynomial a = r.leadingBaseCoefficient();
r = r.multiply(d); // coeff a d, exp f
h = h.multiplyLeft(a); // coeff a d, exp f
if (!r.leadingBaseCoefficient().equals(h.leadingBaseCoefficient())) {
throw new RuntimeException("should not happen: lc(r) = " + r.leadingBaseCoefficient()
+ ", lc(h) = " + h.leadingBaseCoefficient());
//} else {
//System.out.println("lc(r) = " + r.leadingBaseCoefficient());
}
r = (GenSolvablePolynomial>) r.subtract(h);
} else {
break;
}
}
return r;
}
/**
* Is recursive GenSolvablePolynomial pseudo quotient and remainder. For recursive
* polynomials.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param S nonzero recursive GenSolvablePolynomial.
* @return true, if P ~= q * S + r, else false.
* @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
* Note: not always meaningful and working
*/
public static > boolean isRecursivePseudoQuotientRemainder(
GenSolvablePolynomial> P, GenSolvablePolynomial> S,
GenSolvablePolynomial> q, GenSolvablePolynomial> r) {
GenSolvablePolynomial> rhs = (GenSolvablePolynomial>) q.multiply(S).sum(r);
GenSolvablePolynomial> lhs = P;
GenPolynomial ldcf = S.leadingBaseCoefficient();
long d = P.degree(0) - S.degree(0) + 1;
d = (d > 0 ? d : -d + 2);
for (long i = 0; i <= d; i++) {
//System.out.println("lhs = " + lhs);
//System.out.println("rhs = " + rhs);
//System.out.println("lhs-rhs = " + lhs.subtract(rhs));
if (lhs.equals(rhs)) {
return true;
}
lhs = lhs.multiply(ldcf);
}
GenSolvablePolynomial> Pp = P;
rhs = q.multiply(S);
//System.out.println("rhs,2 = " + rhs);
for (long i = 0; i <= d; i++) {
lhs = (GenSolvablePolynomial>) Pp.subtract(r);
//System.out.println("lhs-rhs = " + lhs.subtract(rhs));
if (lhs.equals(rhs)) {
//System.out.println("lhs,2 = " + lhs);
return true;
}
Pp = Pp.multiply(ldcf);
}
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorSimple();
GenSolvablePolynomial a = (GenSolvablePolynomial) P.leadingBaseCoefficient();
rhs = (GenSolvablePolynomial>) q.multiply(S).sum(r);
GenSolvablePolynomial b = (GenSolvablePolynomial) rhs.leadingBaseCoefficient();
GenSolvablePolynomial[] oc = fd.leftOreCond(a, b);
GenPolynomial ga = oc[0];
GenPolynomial gb = oc[1];
//System.out.println("FDQR: OreCond: a = " + a + ", b = " + b);
//System.out.println("FDQR: OreCond: ga = " + ga + ", gb = " + gb);
// ga a = gd d
GenSolvablePolynomial> Pa = P.multiplyLeft(ga); // coeff ga a
GenSolvablePolynomial> Rb = rhs.multiplyLeft(gb); // coeff gb b
GenSolvablePolynomial> D = (GenSolvablePolynomial>) Pa.subtract(Rb);
if (D.isZERO()) {
return true;
}
if (debug) {
logger.info("not QR: D = " + D);
}
//System.out.println("FDQR: Pa = " + Pa);
//System.out.println("FDQR: Rb = " + Rb);
//System.out.println("FDQR: Pa-Rb = " + D);
return false;
}
/**
* GenSolvablePolynomial recursive pseudo quotient for recursive polynomials.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param S nonzero recursive GenSolvablePolynomial.
* @return quotient with ore(ldcf(S)m') P = quotient * S + remainder.
* @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial> recursivePseudoQuotient(
GenSolvablePolynomial> P, GenSolvablePolynomial> S) {
return recursivePseudoQuotientRemainder(P,S)[0];
}
/**
* GenSolvablePolynomial recursive pseudo quotient and remainder for recursive polynomials.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param S nonzero recursive GenSolvablePolynomial.
* @return [ quotient, remainder ] with ore(ldcf(S)m') P = quotient * S + remainder.
* @see edu.jas.poly.GenPolynomial#remainder(edu.jas.poly.GenPolynomial).
*/
public static > GenSolvablePolynomial>[] recursivePseudoQuotientRemainder(
GenSolvablePolynomial> P, GenSolvablePolynomial> S) {
if (S == null || S.isZERO()) {
throw new ArithmeticException(P + " division by zero " + S);
}
//if (S.ring.nvar != 1) {
// ok if exact division
// throw new RuntimeException("univariate polynomials only");
//}
GenSolvablePolynomial>[] ret = new GenSolvablePolynomial[2];
if (P == null || P.isZERO()) {
ret[0] = S.ring.getZERO();
ret[1] = S.ring.getZERO();
return ret;
}
if (S.isONE()) {
ret[0] = P;
ret[1] = S.ring.getZERO();
return ret;
}
//SolvableSyzygyAbstract syz = new SolvableSyzygyAbstract();
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorSimple();
//GenPolynomial c = S.leadingBaseCoefficient();
ExpVector e = S.leadingExpVector();
GenSolvablePolynomial> h;
GenSolvablePolynomial> r = P;
GenSolvablePolynomial> q = S.ring.getZERO().copy();
while (!r.isZERO()) {
ExpVector f = r.leadingExpVector();
if (f.multipleOf(e)) {
f = f.subtract(e);
h = S.multiplyLeft(f); // coeff c, exp (f-e) e
GenSolvablePolynomial a = (GenSolvablePolynomial) r.leadingBaseCoefficient();
GenSolvablePolynomial d = (GenSolvablePolynomial) h.leadingBaseCoefficient();
GenSolvablePolynomial[] oc = fd.leftOreCond(a, d);
GenPolynomial ga = oc[0]; // d
GenPolynomial gd = oc[1]; // a
//System.out.println("OreCond: a = " + a + ", d = " + d);
//System.out.println("OreCond: ga = " + ga + ", gd = " + gd);
// ga a = gd d
r = r.multiplyLeft(ga); // coeff ga a, exp f
h = h.multiplyLeft(gd); // coeff gd d, exp f
q = q.multiplyLeft(ga); // d
q = (GenSolvablePolynomial>) q.sum(gd, f); // a
r = (GenSolvablePolynomial>) r.subtract(h);
} else {
break;
}
}
ret[0] = q;
ret[1] = r;
return ret;
}
/**
* GenSolvablePolynomial recursive quotient for recursive
* polynomials and exact division by coefficient ring element.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param s GenSolvablePolynomial.
* @return this/s.
*/
public static > GenSolvablePolynomial> recursiveDivide(
GenSolvablePolynomial> P, GenSolvablePolynomial s) {
if (s == null || s.isZERO()) {
throw new ArithmeticException("division by zero " + P + ", " + s);
}
if (P.isZERO()) {
return P;
}
if (s.isONE()) {
return P;
}
GenSolvablePolynomial> p = P.ring.getZERO().copy();
//SortedMap> pv = p.val; //getMap();
for (Map.Entry> m1 : P.getMap().entrySet()) {
GenSolvablePolynomial c1 = (GenSolvablePolynomial) m1.getValue();
ExpVector e1 = m1.getKey();
//GenSolvablePolynomial c = FDUtil. basePseudoQuotient(c1, s);
GenSolvablePolynomial[] QR = FDUtil. basePseudoQuotientRemainder(c1, s);
GenSolvablePolynomial c = QR[0];
if ( !QR[1].isZERO() ) {
System.out.println("rDiv, P = " + P);
System.out.println("rDiv, c1 = " + c1);
System.out.println("rDiv, s = " + s);
System.out.println("rDiv, c = " + c);
throw new RuntimeException("something is wrong: rem = " + QR[1]);
}
if (!c.isZERO()) {
//pv.put(e1, c);
p.doPutToMap(e1, c);
} else {
System.out.println("rDiv, P = " + P);
System.out.println("rDiv, c1 = " + c1);
System.out.println("rDiv, s = " + s);
System.out.println("rDiv, c = " + c);
throw new RuntimeException("something is wrong: c is zero");
}
}
return p;
}
/**
* GenSolvablePolynomial recursive quotient for recursive
* polynomials and partial right exact division by coefficient
* ring element.
* @param coefficient type.
* @param P recursive GenSolvablePolynomial.
* @param s GenSolvablePolynomial.
* @return this/s.
*/
public static > GenSolvablePolynomial> recursiveRightDivide(
GenSolvablePolynomial> P, GenSolvablePolynomial s) {
if (s == null || s.isZERO()) {
throw new ArithmeticException("division by zero " + P + ", " + s);
}
if (P.isZERO()) {
return P;
}
if (s.isONE()) {
return P;
}
if ( !(P instanceof RecSolvablePolynomial)) {
return FDUtil. recursiveDivide(P,s);
}
RecSolvablePolynomialRing rfac = (RecSolvablePolynomialRing) P.ring;
if (rfac.coeffTable.isEmpty()) {
return FDUtil. recursiveDivide(P,s);
}
GenPolynomialRing cfac = (GenPolynomialRing) rfac.coFac;
GenPolynomial one = cfac.getONE();
RecSolvablePolynomial onep = rfac.getONE();
ExpVector zero = rfac.evzero;
RecSolvablePolynomial q = rfac.getZERO();
RecSolvablePolynomial r;
RecSolvablePolynomial p = (RecSolvablePolynomial) P;
System.out.println("recRightDivide: p = " + p + ", s = " + s);
while (!p.isZERO()) {
ExpVector f = p.leadingExpVector();
GenPolynomial a = p.leadingBaseCoefficient();
//GenSolvablePolynomial c = FDUtil. basePseudoQuotient(c1, s);
//GenSolvablePolynomial[] QR = FDUtil. basePseudoQuotientRemainder(c1, s);
GenSolvablePolynomial c = (GenSolvablePolynomial) a.divide(s);
// c * s = a
if (c.isZERO()) {
System.out.println("rDiv, P = " + P);
System.out.println("rDiv, a = " + a);
System.out.println("rDiv, s = " + s);
System.out.println("rDiv, c = " + c);
throw new RuntimeException("something is wrong: c is zero");
}
System.out.println("recRightDivide: a = " + a + ", c = " + c + ", f = " + f);
r = onep.multiply(c,f,s,zero); // right: (c f) * 1 * (s zero)
System.out.println("content r = " + r);
p = (RecSolvablePolynomial) p.subtract(r);
q = (RecSolvablePolynomial) q.sum(c,f);
}
return q;
}
/**
* RecSolvablePolynomial right coefficients from left
* coefficients. Note: R is represented as a polynomial
* with left coefficients, the implementation can at the moment
* not distinguish between left and right coefficients.
* @param coefficient type.
* @param P GenSolvablePolynomial.
* @return R = sum( Xi bi ), with P = sum(ai Xi )
* and eval(sum(Xi bi)) == sum(ai Xi)
*/
public static > GenSolvablePolynomial>
rightRecursivePolynomial(GenSolvablePolynomial> P) {
if (P == null || P.isZERO()) {
return P;
}
if ( !(P instanceof RecSolvablePolynomial)) {
return P;
}
RecSolvablePolynomialRing rfac = (RecSolvablePolynomialRing) P.ring;
if (rfac.coeffTable.isEmpty()) {
return P;
}
GenPolynomialRing cfac = (GenPolynomialRing) rfac.coFac;
GenPolynomial one = cfac.getONE();
RecSolvablePolynomial onep = rfac.getONE();
ExpVector zero = rfac.evzero;
RecSolvablePolynomial R = rfac.getZERO();
RecSolvablePolynomial r;
RecSolvablePolynomial p = (RecSolvablePolynomial) P;
while (!p.isZERO()) {
ExpVector f = p.leadingExpVector();
GenPolynomial a = p.leadingBaseCoefficient();
//r = h.multiply(a); // wrong method dispatch // right: f*a
r = onep.multiply(one,f,a,zero); // right: (1 f) * 1 * (a zero)
//System.out.println("a,f = " + a + ", " + f); // + ", h.ring = " + h.ring.toScript());
//System.out.println("f*a = " + r); // + ", r.ring = " + r.ring.toScript());
p = (RecSolvablePolynomial) p.subtract(r);
R = (RecSolvablePolynomial) R.sum(a,f);
}
return R;
}
/**
* Evaluate RecSolvablePolynomial as right coefficients polynomial.
* Note: R is represented as a polynomial with left
* coefficients, the implementation can at the moment not
* distinguish between left and right coefficients.
* @param coefficient type.
* @param R GenSolvablePolynomial with right coefficients.
* @return P as evaluated polynomial R.
* R = sum( Xi bi ), P = sum(ai Xi ) =
* eval(sum(Xi bi))
*/
public static > GenSolvablePolynomial>
evalAsRightRecursivePolynomial(GenSolvablePolynomial> R) {
if (R == null || R.isZERO()) {
return R;
}
if ( !(R instanceof RecSolvablePolynomial)) {
return R;
}
RecSolvablePolynomialRing rfac = (RecSolvablePolynomialRing) R.ring;
if (rfac.coeffTable.isEmpty()) {
return R;
}
GenPolynomialRing cfac = (GenPolynomialRing) rfac.coFac;
GenPolynomial one = cfac.getONE();
RecSolvablePolynomial onep = rfac.getONE();
ExpVector zero = rfac.evzero;
RecSolvablePolynomial q = rfac.getZERO();
RecSolvablePolynomial s;
RecSolvablePolynomial r = (RecSolvablePolynomial) R;
for (Map.Entry> y : r.getMap().entrySet()) {
ExpVector f = y.getKey();
GenPolynomial a = y.getValue();
// f.multiply(a); // wrong method dispatch // right: f*a
s = onep.multiply(one,f,a,zero); // right: (1 f) * 1 * (a zero)
q = (RecSolvablePolynomial) q.sum(s);
}
return q;
}
/**
* Test RecSolvablePolynomial right coefficients polynomial.
* Note: R is represented as a polynomial with left
* coefficients, the implementation can at the moment not
* distinguish between left and right coefficients.
* @param coefficient type.
* @param P GenSolvablePolynomial with left coefficients.
* @param R GenSolvablePolynomial with right coefficients.
* @return true, if R is polynomial with right coefficients of P.
* R = sum( Xi bi ), with P = sum(ai Xi )
* and eval(sum(Xi bi)) == sum(ai Xi)
*/
public static > boolean
isRightRecursivePolynomial(GenSolvablePolynomial> P,
GenSolvablePolynomial> R) {
if (P == null) {
return R == null;
}
if (P.isZERO()) {
return R.isZERO();
}
if ( !(P instanceof RecSolvablePolynomial)) {
return !(R instanceof RecSolvablePolynomial);
}
RecSolvablePolynomialRing rfac = (RecSolvablePolynomialRing) P.ring;
if (rfac.coeffTable.isEmpty()) {
RecSolvablePolynomialRing rf = (RecSolvablePolynomialRing) R.ring;
return rf.coeffTable.isEmpty();
}
RecSolvablePolynomial p = (RecSolvablePolynomial) P;
RecSolvablePolynomial q = (RecSolvablePolynomial) FDUtil. evalAsRightRecursivePolynomial(R);
p = (RecSolvablePolynomial) PolyUtil. monic(p);
q = (RecSolvablePolynomial) PolyUtil. monic(q);
return p.equals(q);
}
/**
* Integral solvable polynomial from solvable rational function coefficients. Represent as
* polynomial with integral solvable polynomial coefficients by multiplication with
* the lcm(??) of the numerators of the rational function coefficients.
* @param fac result polynomial factory.
* @param A polynomial with solvable rational function coefficients to be converted.
* @return polynomial with integral solvable polynomial coefficients.
*/
public static > GenSolvablePolynomial> integralFromQuotientCoefficients(
GenSolvablePolynomialRing> fac, GenSolvablePolynomial> A) {
GenSolvablePolynomial> B = fac.getZERO().copy();
if (A == null || A.isZERO()) {
return B;
}
GenSolvablePolynomial c = null;
GenSolvablePolynomial d;
GenSolvablePolynomial x;
GenSolvablePolynomial z;
GreatestCommonDivisorAbstract fd = new GreatestCommonDivisorPrimitive();
int s = 0;
// lcm/ore of denominators ??
for (SolvableQuotient y : A.getMap().values()) {
x = y.den;
// c = lcm(c,x)
if (c == null) {
c = x;
s = x.signum();
} else {
d = fd.gcd(c, x);
z = (GenSolvablePolynomial) x.divide(d); // ??
c = z.multiply(c); // ?? multiplyLeft
}
}
if (s < 0) {
c = (GenSolvablePolynomial) c.negate();
}
for (Map.Entry> y : A.getMap().entrySet()) {
ExpVector e = y.getKey();
SolvableQuotient a = y.getValue();
// p = n*(c/d)
GenPolynomial b = c.divide(a.den);
GenPolynomial p = a.num.multiply(b);
//B = B.sum( p, e ); // inefficient
B.doPutToMap(e, p);
}
return B;
}
/**
* Integral solvable polynomial from solvable rational function coefficients. Represent as
* polynomial with integral solvable polynomial coefficients by multiplication with
* the lcm(??) of the numerators of the solvable rational function coefficients.
* @param fac result polynomial factory.
* @param L list of polynomials with solvable rational function coefficients to be
* converted.
* @return list of polynomials with integral solvable polynomial coefficients.
*/
public static > List>>
integralFromQuotientCoefficients(
GenSolvablePolynomialRing> fac,
Collection>> L) {
if (L == null) {
return null;
}
List>> list = new ArrayList>>(L.size());
for (GenSolvablePolynomial> p : L) {
list.add(integralFromQuotientCoefficients(fac, p));
}
return list;
}
/**
* Solvable rational function from integral solvable polynomial coefficients. Represent as
* polynomial with type SolvableQuotient coefficients.
* @param fac result polynomial factory.
* @param A polynomial with integral solvable polynomial coefficients to be
* converted.
* @return polynomial with type SolvableQuotient coefficients.
*/
public static > GenSolvablePolynomial> quotientFromIntegralCoefficients(
GenSolvablePolynomialRing> fac, GenSolvablePolynomial> A) {
GenSolvablePolynomial> B = fac.getZERO().copy();
if (A == null || A.isZERO()) {
return B;
}
RingFactory> cfac = fac.coFac;
SolvableQuotientRing qfac = (SolvableQuotientRing) cfac;
for (Map.Entry> y : A.getMap().entrySet()) {
ExpVector e = y.getKey();
GenSolvablePolynomial a = (GenSolvablePolynomial) y.getValue();
SolvableQuotient p = new SolvableQuotient(qfac, a); // can not be zero
if (!p.isZERO()) {
//B = B.sum( p, e ); // inefficient
B.doPutToMap(e, p);
}
}
return B;
}
/**
* Solvable rational function from integral solvable polynomial coefficients. Represent as
* polynomial with type SolvableQuotient coefficients.
* @param fac result polynomial factory.
* @param L list of polynomials with integral solvable polynomial coefficients to be
* converted.
* @return list of polynomials with type SolvableQuotient coefficients.
*/
public static > List