edu.jas.gb
Class CriticalPairList<C extends RingElem<C>>

java.lang.Object
  edu.jas.gb.OrderedPairlist<C>
      edu.jas.gb.CriticalPairList<C>

All Implemented Interfaces:

PairList<C>

public class CriticalPairList<C extends RingElem<C>>
extends OrderedPairlist<C>

Critical pair list management. Makes some effort to produce the same sequence of critical pairs as in the sequential case, when used in parallel. However already reduced pairs are not re-reduced if new polynomials appear. Implemented using GenPolynomial, SortedSet / TreeSet and BitSet.

Author:

Heinz Kredel

Field Summary

protected java.util.SortedSet<CriticalPair<C>>	pairlist
protected int	recordCount

Fields inherited from class edu.jas.gb.OrderedPairlist

moduleVars, oneInGB, P, putCount, red, reduction, remCount, ring, useCriterion4

Constructor Summary

CriticalPairList()
Constructor for CriticalPairList.

CriticalPairList(GenPolynomialRing<C> r)
Constructor for CriticalPairList.

CriticalPairList(int m, GenPolynomialRing<C> r)
Constructor for CriticalPairList.

Method Summary

PairList<C>	create(GenPolynomialRing<C> r) Create a new PairList.
PairList<C>	create(int m, GenPolynomialRing<C> r) Create a new PairList.
CriticalPair<C>	getNext() Get the next required pair from the pairlist.
boolean	hasNext() Test if there is possibly a pair in the list.
java.util.List<CriticalPair<C>>	inWork() In work pairs.
int	put(GenPolynomial<C> p) Put a polynomial to the pairlist and reduction matrix.
int	putOne() Put the ONE-Polynomial to the pairlist.
int	record(CriticalPair<C> pair, GenPolynomial<C> p) Record reduced polynomial.
Pair<C>	removeNext() Get and remove the next required pair from the pairlist.
int	update() Update pairlist.
int	update(CriticalPair<C> pair, GenPolynomial<C> p) Record reduced polynomial and update critical pair list.
int	updateMany() Update pairlist, several pairs at once.

Methods inherited from class edu.jas.gb.OrderedPairlist

criterion3, getList, putCount, putOne, remCount, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

pairlist

protected final java.util.SortedSet<CriticalPair<C extends RingElem<C>>> pairlist

recordCount

protected int recordCount

Constructor Detail

CriticalPairList

public CriticalPairList()

Constructor for CriticalPairList.

CriticalPairList

public CriticalPairList(GenPolynomialRing<C> r)

Constructor for CriticalPairList.

Parameters:

r - polynomial factory.

CriticalPairList

public CriticalPairList(int m,
                        GenPolynomialRing<C> r)

Constructor for CriticalPairList.

Parameters:

m - number of module variables.

r - polynomial factory.

Method Detail

create

public PairList<C> create(GenPolynomialRing<C> r)

Create a new PairList.

Specified by:

create in interface PairList<C extends RingElem<C>>

Overrides:

create in class OrderedPairlist<C extends RingElem<C>>

Parameters:

r - polynomial ring.

create

public PairList<C> create(int m,
                          GenPolynomialRing<C> r)

Create a new PairList.

Specified by:

create in interface PairList<C extends RingElem<C>>

Overrides:

create in class OrderedPairlist<C extends RingElem<C>>

Parameters:

m - number of module variables.

r - polynomial ring.

put

public int put(GenPolynomial<C> p)

Put a polynomial to the pairlist and reduction matrix.

Specified by:

put in interface PairList<C extends RingElem<C>>

Overrides:

put in class OrderedPairlist<C extends RingElem<C>>

Parameters:

p - polynomial.

Returns:

the index of the added polynomial.

hasNext

public boolean hasNext()

Test if there is possibly a pair in the list.

Specified by:

hasNext in interface PairList<C extends RingElem<C>>

Overrides:

hasNext in class OrderedPairlist<C extends RingElem<C>>

Returns:

true if a next pair could exist, otherwise false.

removeNext

public Pair<C> removeNext()

Get and remove the next required pair from the pairlist. Appy the criterions 3 and 4 to see if the S-polynomial is required. The pair is not removed from the pair list.

Specified by:

removeNext in interface PairList<C extends RingElem<C>>

Overrides:

removeNext in class OrderedPairlist<C extends RingElem<C>>

Returns:

the next pair if one exists, otherwise null.

getNext

public CriticalPair<C> getNext()

Get the next required pair from the pairlist. Appy the criterions 3 and 4 to see if the S-polynomial is required. The pair is not removed from the pair list.

Returns:

the next pair if one exists, otherwise null.

record

public int record(CriticalPair<C> pair,
                  GenPolynomial<C> p)

Record reduced polynomial.

Parameters:

pair - the corresponding critical pair.

p - polynomial.

Returns:

index of recorded polynomial, or -1 if not added.

update

public int update(CriticalPair<C> pair,
                  GenPolynomial<C> p)

Record reduced polynomial and update critical pair list. Note: it is better to use record and uptate separately.

Parameters:

pair - the corresponding critical pair.

p - polynomial.

Returns:

index of recorded polynomial

update

public int update()

Update pairlist. Preserve the sequential pair sequence. Remove pairs with completed reductions.

Returns:

the number of added polynomials.

inWork

public java.util.List<CriticalPair<C>> inWork()

In work pairs. List pairs which are currently reduced.

Returns:

list of critical pairs which are in reduction.

updateMany

public int updateMany()

Update pairlist, several pairs at once. This version does not preserve the sequential pair sequence. Remove pairs with completed reductions.

Returns:

the number of added polynomials.

putOne

public int putOne()

Put the ONE-Polynomial to the pairlist.

Specified by:

putOne in interface PairList<C extends RingElem<C>>

Overrides:

putOne in class OrderedPairlist<C extends RingElem<C>>

Returns:

the index of the last polynomial.