/*
* $Id$
*/
package edu.jas.gbufd;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import org.apache.log4j.Logger;
import edu.jas.gb.ReductionAbstract;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.structure.RegularRingElem;
/**
* Polynomial Regular ring Reduction sequential use algorithm. Implements
* normalform and boolean closure stuff.
* @param coefficient type
* @author Heinz Kredel
*/
public class RReductionSeq> extends ReductionAbstract implements
RReduction {
private static final Logger logger = Logger.getLogger(RReductionSeq.class);
private final boolean debug = logger.isDebugEnabled();
/**
* Constructor.
*/
public RReductionSeq() {
}
/**
* Is top reducible. Condition is a b != 0, for a=ldcf(A) and b=ldcf(B) and
* lt(B) | lt(A) for some B in F.
* @param A polynomial.
* @param P polynomial list.
* @return true if A is top reducible with respect to P.
*/
@Override
public boolean isTopReducible(List> P, GenPolynomial A) {
if (P == null || P.isEmpty()) {
return false;
}
if (A == null || A.isZERO()) {
return false;
}
boolean mt = false;
ExpVector e = A.leadingExpVector();
C a = A.leadingBaseCoefficient();
a = a.idempotent();
for (GenPolynomial p : P) {
mt = e.multipleOf(p.leadingExpVector());
if (mt) {
C b = p.leadingBaseCoefficient();
//C r = a.multiply( b );
//C r = a.multiply( b.idempotent() );
C r = a.idempotentAnd(b);
mt = !r.isZERO();
if (mt) {
return true;
}
}
}
return false;
}
/**
* Is strong top reducible. Condition is idempotent(a) == idempotent(b), for
* a=ldcf(A) and b=ldcf(B) and lt(B) | lt(A) for some B in F.
* @param A polynomial.
* @param P polynomial list.
* @return true if A is string top reducible with respect to P.
*/
public boolean isStrongTopReducible(List> P, GenPolynomial A) {
if (P == null || P.isEmpty()) {
return false;
}
if (A == null || A.isZERO()) {
return false;
}
boolean mt = false;
ExpVector e = A.leadingExpVector();
C a = A.leadingBaseCoefficient();
a = a.idempotent();
for (GenPolynomial p : P) {
mt = e.multipleOf(p.leadingExpVector());
if (mt) {
C b = p.leadingBaseCoefficient();
mt = a.equals(b.idempotent());
if (mt) {
return true;
}
}
}
return false;
}
/**
* Is in Normalform.
* @param Ap polynomial.
* @param Pp polynomial list.
* @return true if Ap is in normalform with respect to Pp.
*/
@Override
@SuppressWarnings("unchecked")
public boolean isNormalform(List> Pp, GenPolynomial Ap) {
if (Pp == null || Pp.isEmpty()) {
return true;
}
if (Ap == null || Ap.isZERO()) {
return true;
}
int l;
GenPolynomial[] P;
synchronized (Pp) {
l = Pp.size();
P = new GenPolynomial[l];
//P = Pp.toArray();
for (int i = 0; i < Pp.size(); i++) {
P[i] = Pp.get(i);
}
}
ExpVector[] htl = new ExpVector[l];
C[] lbc = (C[]) new RegularRingElem[l]; // want
GenPolynomial[] p = new GenPolynomial[l];
Map.Entry m;
int i;
int j = 0;
for (i = 0; i < l; i++) {
if (P[i] == null) {
continue;
}
p[i] = P[i];
m = p[i].leadingMonomial();
if (m != null) {
p[j] = p[i];
htl[j] = m.getKey();
lbc[j] = m.getValue();
j++;
}
}
l = j;
boolean mt = false;
Map Am = Ap.getMap();
for (Map.Entry me : Am.entrySet()) {
ExpVector e = me.getKey();
C a = me.getValue();
for (i = 0; i < l; i++) {
mt = e.multipleOf(htl[i]);
if (mt) {
//C r = a.multiply( lbc[i] );
//C r = a.idempotent().multiply( lbc[i].idempotent() );
C r = a.idempotentAnd(lbc[i]);
mt = !r.isZERO();
if (mt) {
return false;
}
}
}
}
return true;
}
/**
* Normalform using r-reduction.
* @param Ap polynomial.
* @param Pp polynomial list.
* @return r-nf(Ap) with respect to Pp.
*/
@SuppressWarnings("unchecked")
public GenPolynomial normalform(List> Pp, GenPolynomial Ap) {
if (Pp == null || Pp.isEmpty()) {
return Ap;
}
if (Ap == null || Ap.isZERO()) {
return Ap;
}
int l;
GenPolynomial[] P;
synchronized (Pp) {
l = Pp.size();
P = (GenPolynomial[]) new GenPolynomial[l];
//P = Pp.toArray();
for (int i = 0; i < Pp.size(); i++) {
P[i] = Pp.get(i);
}
}
//System.out.println("l = " + l);
Map.Entry m;
ExpVector[] htl = new ExpVector[l];
C[] lbc = (C[]) new RegularRingElem[l]; // want
GenPolynomial[] p = (GenPolynomial[]) new GenPolynomial[l];
int i;
int j = 0;
for (i = 0; i < l; i++) {
if (P[i] == null) {
continue;
}
p[i] = P[i].abs();
m = p[i].leadingMonomial();
if (m != null) {
p[j] = p[i];
htl[j] = m.getKey();
lbc[j] = m.getValue();
j++;
}
}
l = j;
ExpVector e, f;
C a, b;
C r = null;
boolean mt = false;
GenPolynomial R = Ap.ring.getZERO();
GenPolynomial Q = null;
GenPolynomial S = Ap;
while (S.length() > 0) {
m = S.leadingMonomial();
e = m.getKey();
a = m.getValue();
if (debug) {
if ( a.isZERO() ) {
throw new RuntimeException("a.isZERO(): S = " + S);
}
}
for (i = 0; i < l; i++) {
mt = e.multipleOf(htl[i]);
if (mt) {
//r = a.multiply( lbc[i] );
//r = a.idempotent().multiply( lbc[i].idempotent() );
r = a.idempotentAnd(lbc[i]);
mt = !r.isZERO(); // && mt
if (mt) {
b = a.divide(lbc[i]);
if (b.isZERO()) { // strange case in regular rings
System.out.println("b == zero: r = " + r);
continue;
}
f = e.subtract(htl[i]);
//logger.info("red div = " + f);
Q = p[i].multiply(b, f);
S = S.subtract(Q); // not ok with reductum
f = S.leadingExpVector();
if (!e.equals(f)) {
a = Ap.ring.coFac.getZERO();
break;
}
a = S.leadingBaseCoefficient();
}
}
}
if (!a.isZERO()) { //! mt ) {
//logger.debug("irred");
R = R.sum(a, e);
S = S.reductum();
}
}
return R; //.abs(); // not monic if not boolean closed
}
/**
* GB criterium 4. Use only for commutative polynomial rings. Note:
* Experimental version for r-Groebner bases.
* @param A polynomial.
* @param B polynomial.
* @param e = lcm(ht(A),ht(B))
* @return true if the S-polynomial(i,j) is required, else false.
*/
@Override
public boolean criterion4(GenPolynomial A, GenPolynomial B, ExpVector e) {
if (logger.isInfoEnabled()) {
if (!A.ring.equals(B.ring)) {
logger.error("rings equal");
}
if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
return true;
}
}
ExpVector ei = A.leadingExpVector();
ExpVector ej = B.leadingExpVector();
ExpVector g = ei.sum(ej);
// boolean t = g == e ;
ExpVector h = g.subtract(e);
int s = h.signum();
if (s == 0) { // disjoint ht
C a = A.leadingBaseCoefficient();
C b = B.leadingBaseCoefficient();
C d = a.multiply(b);
if (d.isZERO()) { // a guess
//System.out.println("d1 = " + d + ", a = " + a + ", b = " + b);
return false; // can skip pair
}
}
return true; //! ( s == 0 );
}
/**
* GB criterium 4. Use only for commutative polynomial rings. Note:
* Experimental version for r-Groebner bases.
* @param A polynomial.
* @param B polynomial.
* @return true if the S-polynomial(i,j) is required, else false.
*/
@Override
public boolean criterion4(GenPolynomial A, GenPolynomial B) {
if (logger.isInfoEnabled()) {
if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
return true;
}
}
ExpVector ei = A.leadingExpVector();
ExpVector ej = B.leadingExpVector();
ExpVector g = ei.sum(ej);
ExpVector e = ei.lcm(ej);
// boolean t = g == e ;
ExpVector h = g.subtract(e);
int s = h.signum();
if (s == 0) { // disjoint ht
C a = A.leadingBaseCoefficient();
C b = B.leadingBaseCoefficient();
C d = a.multiply(b);
if (d.isZERO()) { // a guess
return false; // can skip pair
}
}
return true; //! ( s == 0 );
}
/**
* Normalform with recording.
* @param row recording matrix, is modified.
* @param Pp a polynomial list for reduction.
* @param Ap a polynomial.
* @return Ap - row*Pp = nf(Pp,Ap) , the normal form of Ap wrt. Pp.
*/
@SuppressWarnings("unchecked")
public GenPolynomial normalform(List> row, List> Pp,
GenPolynomial Ap) {
if (Pp == null || Pp.isEmpty()) {
return Ap;
}
if (Ap == null || Ap.isZERO()) {
return Ap;
}
int l;
GenPolynomial[] P;
synchronized (Pp) {
l = Pp.size();
P = (GenPolynomial[]) new GenPolynomial[l];
//P = Pp.toArray();
for (int i = 0; i < Pp.size(); i++) {
P[i] = Pp.get(i);
}
}
//System.out.println("l = " + l);
Map.Entry m;
ExpVector[] htl = new ExpVector[l];
C[] lbc = (C[]) new RegularRingElem[l]; // want
GenPolynomial[] p = (GenPolynomial[]) new GenPolynomial[l];
int i;
int j = 0;
for (i = 0; i < l; i++) {
p[i] = P[i];
m = p[i].leadingMonomial();
if (m != null) {
p[j] = p[i];
htl[j] = m.getKey();
lbc[j] = m.getValue();
j++;
}
}
l = j;
ExpVector e, f;
C a;
C r = null;
boolean mt = false;
GenPolynomial fac = null;
GenPolynomial zero = Ap.ring.getZERO();
GenPolynomial R = Ap.ring.getZERO();
GenPolynomial Q = null;
GenPolynomial S = Ap;
while (S.length() > 0) {
m = S.leadingMonomial();
e = m.getKey();
a = m.getValue();
for (i = 0; i < l; i++) {
mt = e.multipleOf(htl[i]);
if (mt) {
//r = a.idempotent().multiply( lbc[i].idempotent() );
//r = a.multiply( lbc[i] );
r = a.idempotentAnd(lbc[i]);
//System.out.println("r = " + r);
mt = !r.isZERO(); // && mt
if (mt) {
a = a.divide(lbc[i]);
if (a.isZERO()) { // strange case in regular rings
System.out.println("b == zero: r = " + r);
continue;
}
f = e.subtract(htl[i]);
//logger.info("red div = " + f);
Q = p[i].multiply(a, f);
S = S.subtract(Q); // not ok with reductum
fac = row.get(i);
if (fac == null) {
fac = zero.sum(a, f);
} else {
fac = fac.sum(a, f);
}
row.set(i, fac);
f = S.leadingExpVector();
if (!e.equals(f)) {
a = Ap.ring.coFac.getZERO();
break;
}
a = S.leadingBaseCoefficient();
}
}
}
if (!a.isZERO()) { //! mt ) {
//logger.debug("irred");
R = R.sum(a, e);
S = S.reductum();
}
}
return R; //.abs(); not for recording
}
/**
* Irreducible set. May not be boolean closed.
* @param Pp polynomial list.
* @return a list P of polynomials which are in normalform wrt. P.
*/
@Override
public List> irreducibleSet(List> Pp) {
ArrayList> P = new ArrayList>();
if (Pp == null) {
return null;
}
for (GenPolynomial a : Pp) {
if (!a.isZERO()) {
P.add(a);
}
}
int l = P.size();
if (l <= 1)
return P;
int irr = 0;
ExpVector e;
ExpVector f;
GenPolynomial a;
logger.debug("irr = ");
while (irr != l) {
//a = P.get(0);
a = P.remove(0);
e = a.leadingExpVector();
a = normalform(P, a);
// no not make monic because of boolean closure
logger.debug(String.valueOf(irr));
if (a.isZERO()) {
l--;
if (l <= 1) {
return P;
}
} else {
f = a.leadingExpVector();
if (e.equals(f)) {
// lbcf(a) eventually shorter
// correct since longer coeffs can reduce shorter coeffs
irr++;
} else {
irr = 0;
}
P.add(a);
}
}
//System.out.println();
return P;
}
/*
* -------- boolean closure stuff -----------------------------------------
*/
/**
* Is boolean closed, test if A == idempotent(ldcf(A)) A.
* @param A polynomial.
* @return true if A is boolean closed, else false.
*/
public boolean isBooleanClosed(GenPolynomial A) {
if (A == null || A.isZERO()) {
return true;
}
C a = A.leadingBaseCoefficient();
C i = a.idempotent();
GenPolynomial B = A.multiply(i);
// better run idemAnd on coefficients
if (A.equals(B)) {
return true;
}
return false;
}
/**
* Is boolean closed, test if all A in F are boolean closed.
* @param F polynomial list.
* @return true if F is boolean closed, else false.
*/
public boolean isBooleanClosed(List> F) {
if (F == null || F.size() == 0) {
return true;
}
for (GenPolynomial a : F) {
if (a == null || a.isZERO()) {
continue;
}
//System.out.println("a = " + a);
if (!isBooleanClosed(a)) {
return false;
}
}
return true;
}
/**
* Is reduced boolean closed, test if all A in F are boolean closed or br(A)
* reduces to zero.
* @param F polynomial list.
* @return true if F is boolean closed, else false.
*/
public boolean isReducedBooleanClosed(List> F) {
if (F == null || F.size() == 0) {
return true;
}
GenPolynomial b;
GenPolynomial r;
for (GenPolynomial a : F) {
//System.out.println("a = " + a);
if (a == null) {
continue;
}
while (!a.isZERO()) {
if (!isBooleanClosed(a)) {
b = booleanClosure(a);
b = normalform(F, b);
if (!b.isZERO()) { //F.contains(r)
return false;
}
}
r = booleanRemainder(a);
r = normalform(F, r);
if (!r.isZERO()) { //F.contains(r)
return false;
}
//System.out.println("r = " + r);
a = r;
}
}
return true;
}
/**
* Boolean closure, compute idempotent(ldcf(A)) A.
* @param A polynomial.
* @return bc(A).
*/
public GenPolynomial booleanClosure(GenPolynomial A) {
if (A == null || A.isZERO()) {
return A;
}
C a = A.leadingBaseCoefficient();
C i = a.idempotent();
GenPolynomial B = A.multiply(i);
return B;
}
/**
* Boolean remainder, compute idemComplement(ldcf(A)) A.
* @param A polynomial.
* @return br(A).
*/
public GenPolynomial booleanRemainder(GenPolynomial A) {
if (A == null || A.isZERO()) {
return A;
}
C a = A.leadingBaseCoefficient();
C i = a.idemComplement();
GenPolynomial B = A.multiply(i);
return B;
}
/**
* Boolean closure, compute BC(A) for all A in F.
* @param F polynomial list.
* @return bc(F).
*/
public List> booleanClosure(List> F) {
if (F == null || F.size() == 0) {
return F;
}
List> B = new ArrayList>(F.size());
for (GenPolynomial a : F) {
if (a == null) {
continue;
}
while (!a.isZERO()) {
GenPolynomial b = booleanClosure(a);
B.add(b);
a = booleanRemainder(a);
}
}
return B;
}
/**
* Reduced boolean closure, compute BC(A) for all A in F.
* @param F polynomial list.
* @return red(bc(F)) = bc(red(F)).
*/
public List> reducedBooleanClosure(List> F) {
if (F == null || F.size() == 0) {
return F;
}
List> B = new ArrayList>(F);
GenPolynomial a;
GenPolynomial b;
GenPolynomial c;
int len = B.size();
for (int i = 0; i < len; i++) { // not B.size(), it changes
a = B.remove(0);
if (a == null) {
continue;
}
while (!a.isZERO()) {
//System.out.println("a = " + a);
b = booleanClosure(a);
//System.out.println("b = " + b);
b = booleanClosure(normalform(B, b));
if (b.isZERO()) {
break;
}
B.add(b); // adds as last
c = a.subtract(b); // = BR(a mod B)
//System.out.println("c = " + c);
c = normalform(B, c);
a = c;
}
}
return B;
}
/**
* Reduced boolean closure, compute BC(A) modulo F.
* @param A polynomial.
* @param F polynomial list.
* @return red(bc(A)).
*/
public List> reducedBooleanClosure(List> F, GenPolynomial A) {
List> B = new ArrayList>();
if (A == null || A.isZERO()) {
return B;
}
GenPolynomial a = A;
GenPolynomial b;
GenPolynomial c;
while (!a.isZERO()) {
//System.out.println("a = " + a);
b = booleanClosure(a);
//System.out.println("b = " + b);
b = booleanClosure(normalform(F, b));
if (b.isZERO()) {
break;
}
B.add(b); // adds as last
c = a.subtract(b); // = BR(a mod F)
//System.out.println("c = " + c);
c = normalform(F, c);
//System.out.println("c = " + c);
a = c;
}
return B;
}
}
Ads help maintain this website.