/*
* $Id$
*/
package edu.jas.gb;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import org.apache.log4j.Logger;
import edu.jas.structure.RingElem;
//import edu.jas.poly.ExpVector;
import edu.jas.gb.OrderedPairlist;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
/**
* Groebner Base sequential algorithm.
* Implements Groebner bases and GB test.
* @param coefficient type
* @author Heinz Kredel
*
* @see edu.jas.application.GBAlgorithmBuilder
* @see edu.jas.gbufd.GBFactory
*/
public class GroebnerBaseSeq>
extends GroebnerBaseAbstract {
private static final Logger logger = Logger.getLogger(GroebnerBaseSeq.class);
private final boolean debug = logger.isDebugEnabled();
/**
* Constructor.
*/
public GroebnerBaseSeq() {
super();
}
/**
* Constructor.
* @param red Reduction engine
*/
public GroebnerBaseSeq(Reduction red) {
super(red);
}
/**
* Constructor.
* @param pl pair selection strategy
*/
public GroebnerBaseSeq(PairList pl) {
super(pl);
}
/**
* Constructor.
* @param red Reduction engine
* @param pl pair selection strategy
*/
public GroebnerBaseSeq(Reduction red, PairList pl) {
super(red,pl);
}
/**
* Groebner base using pairlist class.
* @param modv module variable number.
* @param F polynomial list.
* @return GB(F) a Groebner base of F.
*/
public List>
GB( int modv,
List> F ) {
GenPolynomial p;
List> G = new ArrayList>();
PairList pairlist = null;
int l = F.size();
ListIterator> it = F.listIterator();
while ( it.hasNext() ) {
p = it.next();
if ( p.length() > 0 ) {
p = p.monic();
if ( p.isONE() ) {
G.clear(); G.add( p );
return G; // since no threads are activated
}
G.add( p );
if ( pairlist == null ) {
//pairlist = new OrderedPairlist( modv, p.ring );
pairlist = strategy.create( modv, p.ring );
if ( ! p.ring.coFac.isField() ) {
throw new IllegalArgumentException("coefficients not from a field");
}
}
// putOne not required
pairlist.put( p );
} else {
l--;
}
}
if ( l <= 1 ) {
return G; // since no threads are activated
}
logger.info("start " + pairlist);
Pair pair;
GenPolynomial pi;
GenPolynomial pj;
GenPolynomial S;
GenPolynomial H;
while ( pairlist.hasNext() ) {
pair = pairlist.removeNext();
//logger.debug("pair = " + pair);
if ( pair == null ) {
continue;
}
pi = pair.pi;
pj = pair.pj;
if ( /*false &&*/ debug ) {
logger.debug("pi = " + pi );
logger.debug("pj = " + pj );
}
S = red.SPolynomial( pi, pj );
if ( S.isZERO() ) {
pair.setZero();
continue;
}
if ( debug ) {
logger.debug("ht(S) = " + S.leadingExpVector() );
}
H = red.normalform( G, S );
if ( debug ) {
//logger.info("pair = " + pair);
//logger.info("ht(S) = " + S.monic()); //.leadingExpVector() );
logger.info("ht(H) = " + H.monic()); //.leadingExpVector() );
}
if ( H.isZERO() ) {
pair.setZero();
continue;
}
H = H.monic();
if ( debug ) {
logger.info("ht(H) = " + H.leadingExpVector() );
}
H = H.monic();
if ( H.isONE() ) {
G.clear(); G.add( H );
pairlist.putOne();
logger.info("end " + pairlist);
return G; // since no threads are activated
}
if ( debug ) {
logger.info("H = " + H );
}
if ( H.length() > 0 ) {
l++;
G.add( H );
pairlist.put( H );
}
}
logger.debug("#sequential list = " + G.size());
G = minimalGB(G);
logger.info("end " + pairlist);
return G;
}
/**
* Extended Groebner base using critical pair class.
* @param modv module variable number.
* @param F polynomial list.
* @return a container for an extended Groebner base of F.
*/
@Override
public ExtendedGB
extGB( int modv,
List> F ) {
List> G = new ArrayList>();
List>> F2G = new ArrayList>>();
List>> G2F = new ArrayList>>();
PairList pairlist = null;
boolean oneInGB = false;
int len = F.size();
List> row = null;
List> rows = null;
List> rowh = null;
GenPolynomialRing ring = null;
GenPolynomial H;
GenPolynomial p;
int nzlen = 0;
for ( GenPolynomial f : F ) {
if ( f.length() > 0 ) {
nzlen++;
}
if ( ring == null ) {
ring = f.ring;
}
}
GenPolynomial mone = ring.getONE(); //.negate();
int k = 0;
ListIterator> it = F.listIterator();
while ( it.hasNext() ) {
p = it.next();
if ( p.length() > 0 ) {
row = new ArrayList>( nzlen );
for ( int j = 0; j < nzlen; j++ ) {
row.add(null);
}
//C c = p.leadingBaseCoefficient();
//c = c.inverse();
//p = p.multiply( c );
row.set( k, mone ); //.multiply(c) );
k++;
if ( p.isUnit() ) {
G.clear(); G.add( p );
G2F.clear(); G2F.add( row );
oneInGB = true;
break;
}
G.add( p );
G2F.add( row );
if ( pairlist == null ) {
//pairlist = new OrderedPairlist( modv, p.ring );
pairlist = strategy.create( modv, p.ring );
if ( ! p.ring.coFac.isField() ) {
throw new RuntimeException("coefficients not from a field");
}
}
// putOne not required
pairlist.put( p );
} else {
len--;
}
}
ExtendedGB exgb;
if ( len <= 1 || oneInGB ) {
// adjust F2G
for ( GenPolynomial f : F ) {
row = new ArrayList>( G.size() );
for ( int j = 0; j < G.size(); j++ ) {
row.add(null);
}
H = red.normalform( row, G, f );
if ( ! H.isZERO() ) {
logger.error("nonzero H = " + H );
}
F2G.add( row );
}
exgb = new ExtendedGB(F,G,F2G,G2F);
//System.out.println("exgb 1 = " + exgb);
return exgb;
}
Pair pair;
int i, j;
GenPolynomial pi;
GenPolynomial pj;
GenPolynomial S;
GenPolynomial x;
GenPolynomial y;
//GenPolynomial z;
while ( pairlist.hasNext() && ! oneInGB ) {
pair = pairlist.removeNext();
if ( pair == null ) {
continue;
}
i = pair.i;
j = pair.j;
pi = pair.pi;
pj = pair.pj;
if ( debug ) {
logger.info("i, pi = " + i + ", " + pi );
logger.info("j, pj = " + j + ", " + pj );
}
rows = new ArrayList>( G.size() );
for ( int m = 0; m < G.size(); m++ ) {
rows.add(null);
}
S = red.SPolynomial( rows, i, pi, j, pj );
if ( debug ) {
logger.debug("is reduction S = "
+ red.isReductionNF( rows, G, ring.getZERO(), S ) );
}
if ( S.isZERO() ) {
// do not add to G2F
continue;
}
if ( debug ) {
logger.debug("ht(S) = " + S.leadingExpVector() );
}
rowh = new ArrayList>( G.size() );
for ( int m = 0; m < G.size(); m++ ) {
rowh.add(null);
}
H = red.normalform( rowh, G, S );
if ( debug ) {
logger.debug("is reduction H = "
+ red.isReductionNF( rowh, G, S, H ) );
}
if ( H.isZERO() ) {
// do not add to G2F
continue;
}
if ( debug ) {
logger.debug("ht(H) = " + H.leadingExpVector() );
}
row = new ArrayList>( G.size()+1 );
for ( int m = 0; m < G.size(); m++ ) {
x = rows.get(m);
if ( x != null ) {
//System.out.println("ms = " + m + " " + x);
x = x.negate();
}
y = rowh.get(m);
if ( y != null ) {
y = y.negate();
//System.out.println("mh = " + m + " " + y);
}
if ( x == null ) {
x = y;
} else {
x = x.sum( y );
}
//System.out.println("mx = " + m + " " + x);
row.add( x );
}
if ( debug ) {
logger.debug("is reduction 0+sum(row,G) == H : "
+ red.isReductionNF( row, G, H, ring.getZERO() ) );
}
row.add( null );
// H = H.monic();
C c = H.leadingBaseCoefficient();
c = c.inverse();
H = H.multiply( c );
row = blas.scalarProduct( mone.multiply(c), row );
row.set( G.size(), mone );
if ( H.isONE() ) {
// G.clear();
G.add( H );
G2F.add( row );
oneInGB = true;
break;
}
if ( debug ) {
logger.debug("H = " + H );
}
G.add( H );
pairlist.put( H );
G2F.add( row );
}
if ( debug ) {
exgb = new ExtendedGB(F,G,F2G,G2F);
logger.info("exgb unnorm = " + exgb);
}
G2F = normalizeMatrix( F.size(), G2F );
if ( debug ) {
exgb = new ExtendedGB(F,G,F2G,G2F);
logger.info("exgb nonmin = " + exgb);
boolean t2 = isReductionMatrix( exgb );
logger.info("exgb t2 = " + t2);
}
exgb = minimalExtendedGB(F.size(),G,G2F);
G = exgb.G;
G2F = exgb.G2F;
logger.debug("#sequential list = " + G.size());
logger.info("" + pairlist);
// setup matrices F and F2G
for ( GenPolynomial f : F ) {
row = new ArrayList>( G.size() );
for ( int m = 0; m < G.size(); m++ ) {
row.add(null);
}
H = red.normalform( row, G, f );
if ( ! H.isZERO() ) {
logger.error("nonzero H = " + H );
}
F2G.add( row );
}
exgb = new ExtendedGB(F,G,F2G,G2F);
if ( debug ) {
logger.info("exgb nonmin = " + exgb);
boolean t2 = isReductionMatrix( exgb );
logger.info("exgb t2 = " + t2);
}
return exgb;
}
}
Ads help maintain this website.