/*
* $Id$
*/
package edu.jas.gbufd;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.apache.log4j.Logger;
import edu.jas.gb.GroebnerBaseAbstract;
import edu.jas.gb.Pair;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.structure.RegularRingElem;
/**
* Regular ring Groebner Base sequential algorithm. Implements R-Groebner bases
* and GB test.
* @param coefficient type
* @author Heinz Kredel
*/
public class RGroebnerBaseSeq> extends GroebnerBaseAbstract {
private static final Logger logger = Logger.getLogger(RGroebnerBaseSeq.class);
private final boolean debug = logger.isDebugEnabled();
/**
* Reduction engine.
*/
protected RReduction rred; // shadow super.red ??
/**
* Constructor.
*/
public RGroebnerBaseSeq() {
this(new RReductionSeq());
}
/**
* Constructor.
* @param rred R-Reduction engine
*/
public RGroebnerBaseSeq(RReduction rred) {
super(rred);
this.rred = rred;
assert super.red == this.rred;
}
/**
* R-Groebner base test.
* @param modv module variable number.
* @param F polynomial list.
* @return true, if F is a R-Groebner base, else false.
*/
@Override
public boolean isGB(int modv, List> F) {
if (F == null) {
return true;
}
if (!rred.isBooleanClosed(F)) {
if (debug) {
logger.debug("not boolean closed");
}
return false;
}
GenPolynomial pi, pj, s;
for (int i = 0; i < F.size(); i++) {
pi = F.get(i);
for (int j = i + 1; j < F.size(); j++) {
pj = F.get(j);
if (!red.moduleCriterion(modv, pi, pj)) {
continue;
}
// red.criterion4 not applicable
s = red.SPolynomial(pi, pj);
if (s.isZERO()) {
continue;
}
s = red.normalform(F, s);
if (!s.isZERO()) {
if (debug) {
logger.debug("p" + i + " = " + pi);
logger.debug("p" + j + " = " + pj);
logger.debug("s-pol = " + red.SPolynomial(pi, pj));
logger.debug("s-pol(" + i + "," + j + ") != 0: " + s);
}
return false;
}
}
}
return true;
}
/**
* R-Groebner base using pairlist class.
* @param modv module variable number.
* @param F polynomial list.
* @return GB(F) a R-Groebner base of F.
*/
public List> GB(int modv, List> F) {
/* boolean closure */
List> bcF = rred.reducedBooleanClosure(F);
logger.info("#bcF-#F = " + (bcF.size() - F.size()));
F = bcF;
/* normalize input */
List> G = new ArrayList>();
OrderedRPairlist pairlist = null;
for (GenPolynomial p : F) {
if (!p.isZERO()) {
p = p.monic(); //p.abs(); // not monic, monic if boolean closed
if (p.isONE()) {
G.clear();
G.add(p);
return G; // since boolean closed and no threads are activated
}
G.add(p); //G.add( 0, p ); //reverse list
if (pairlist == null) {
pairlist = new OrderedRPairlist(modv, p.ring);
}
// putOne not required
pairlist.put(p);
}
}
if (G.size() <= 1) {
return G; // since boolean closed and no threads are activated
}
/* loop on critical pairs */
Pair pair;
GenPolynomial pi;
GenPolynomial pj;
GenPolynomial S;
//GenPolynomial D;
GenPolynomial H;
List> bcH;
//int len = G.size();
//System.out.println("len = " + len);
while (pairlist.hasNext()) {
pair = pairlist.removeNext();
//System.out.println("pair = " + pair);
if (pair == null)
continue;
pi = pair.pi;
pj = pair.pj;
if (logger.isDebugEnabled()) {
logger.debug("pi = " + pi);
logger.debug("pj = " + pj);
}
if (!red.moduleCriterion(modv, pi, pj)) {
continue;
}
// S-polynomial -----------------------
// Criterion3() Criterion4() not applicable
S = red.SPolynomial(pi, pj);
if (S.isZERO()) {
pair.setZero();
continue;
}
if (logger.isDebugEnabled()) {
logger.debug("ht(S) = " + S.leadingExpVector());
}
H = red.normalform(G, S);
if (H.isZERO()) {
pair.setZero();
continue;
}
//H = H.monic(); // only for boolean closed H
if (logger.isDebugEnabled()) {
logger.debug("ht(H) = " + H.leadingExpVector());
}
if (H.isONE()) { // mostly useless
G.clear();
G.add(H);
return G; // not boolean closed ok, since no threads are activated
}
if (logger.isDebugEnabled()) {
logger.debug("H = " + H);
}
if (!H.isZERO()) {
logger.info("Sred = " + H);
//len = G.size();
bcH = rred.reducedBooleanClosure(G, H);
logger.info("#bcH = " + bcH.size());
for (GenPolynomial h : bcH) {
h = h.monic(); // monic() ok, since boolean closed
G.add(h);
pairlist.put(h);
}
if (debug) {
if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
logger.info("H != 0 but: " + pair);
}
}
}
}
logger.debug("#sequential list = " + G.size());
G = minimalGB(G);
//G = red.irreducibleSet(G);
logger.info("" + pairlist);
return G;
}
/**
* Minimal ordered Groebner basis.
* @param Gp a Groebner base.
* @return a reduced Groebner base of Gp.
*/
@Override
public List> minimalGB(List> Gp) {
if (Gp == null || Gp.size() <= 1) {
return Gp;
}
// remove zero polynomials
List> G = new ArrayList>(Gp.size());
for (GenPolynomial a : Gp) {
if (a != null && !a.isZERO()) { // always true in GB()
// already positive a = a.abs();
G.add(a);
}
}
//if (G.size() <= 1) {
//wg monic do not return G;
//}
// remove top reducible polynomials
GenPolynomial a, b;
List> F;
List> bcH;
F = new ArrayList>(G.size());
while (G.size() > 0) {
a = G.remove(0);
b = a;
if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
// drop polynomial
if (logger.isInfoEnabled()) {
List> ff;
ff = new ArrayList>(G);
ff.addAll(F);
a = red.normalform(ff, a);
if (!a.isZERO()) { // happens
logger.info("minGB not zero " + a);
bcH = rred.reducedBooleanClosure(G, a);
if (bcH.size() > 1) { // never happend so far
System.out.println("minGB not bc: bcH size = " + bcH.size());
F.add(b); // do not replace, stay with b
} else {
//System.out.println("minGB add bc(a): a = " + a + ", bc(a) = " + bcH.get(0));
F.addAll(bcH);
}
} else {
//System.out.println("minGB dropped " + b);
}
}
} else {
F.add(a);
}
}
G = F;
//if (G.size() <= 1) {
// wg monic return G;
//}
Collections.reverse(G); // important for lex GB
// reduce remaining polynomials
int len = G.size();
int el = 0;
while (el < len) {
a = G.remove(0);
b = a;
//System.out.println("doing " + a.length());
a = red.normalform(G, a);
bcH = rred.reducedBooleanClosure(G, a);
if (bcH.size() > 1) {
System.out.println("minGB not bc: bcH size = " + bcH.size());
G.add(b); // do not reduce
} else {
G.addAll(bcH);
}
el++;
}
// make monic if possible
F = new ArrayList>(G.size());
for (GenPolynomial p : G) {
a = p.monic().abs();
if (p.length() != a.length()) {
System.out.println("minGB not bc: #p != #a: a = " + a + ", p = " + p);
a = p; // dont make monic for now
}
F.add(a);
}
G = F;
/* stratify: collect polynomials with equal leading terms */
ExpVector e, f;
F = new ArrayList>(G.size());
for (int i = 0; i < G.size(); i++) {
a = G.get(i);
if (a == null || a.isZERO()) {
continue;
}
e = a.leadingExpVector();
for (int j = i + 1; j < G.size(); j++) {
b = G.get(j);
if (b == null || b.isZERO()) {
continue;
}
f = b.leadingExpVector();
if (e.equals(f)) {
//System.out.println("minGB e == f: " + a + ", " + b);
a = a.sum(b);
G.set(j, null);
}
}
F.add(a);
}
G = F;
/* info on boolean algebra element blocks
Map>> bd = new TreeMap>>();
for ( GenPolynomial p : G ) {
C cf = p.leadingBaseCoefficient();
cf = cf.idempotent();
List> block = bd.get( cf );
if ( block == null ) {
block = new ArrayList>();
}
block.add( p );
bd.put( cf, block );
}
System.out.println("\nminGB bd:");
for( C k: bd.keySet() ) {
System.out.println("\nkey = " + k + ":");
System.out.println("val = " + bd.get(k));
}
System.out.println();
*/
return G;
}
}
Ads help maintain this website.