001/* 002 * $Id: WordGroebnerBaseSeq.java 4150 2012-09-01 09:18:23Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007import java.util.ArrayList; 008import java.util.List; 009import java.util.ListIterator; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.structure.RingElem; 014import edu.jas.poly.Word; 015import edu.jas.poly.GenWordPolynomial; 016import edu.jas.poly.GenWordPolynomialRing; 017 018 019/** 020 * Word Groebner Base sequential algorithm. 021 * Implements Groebner bases and GB test. 022 * @param <C> coefficient type 023 * @author Heinz Kredel 024 */ 025 026public class WordGroebnerBaseSeq<C extends RingElem<C>> 027 extends WordGroebnerBaseAbstract<C> { 028 029 private static final Logger logger = Logger.getLogger(WordGroebnerBaseSeq.class); 030 private final boolean debug = logger.isDebugEnabled(); 031 032 033 /** 034 * Constructor. 035 */ 036 public WordGroebnerBaseSeq() { 037 super(); 038 } 039 040 041 /** 042 * Constructor. 043 * @param red Reduction engine 044 */ 045 public WordGroebnerBaseSeq(WordReduction<C> red) { 046 super(red); 047 } 048 049 050 /** 051 * Constructor. 052 * @param red Reduction engine 053 * @param pl pair selection strategy 054 */ 055 public WordGroebnerBaseSeq(WordReduction<C> red, WordPairList<C> pl) { 056 super(red,pl); 057 } 058 059 060 /** 061 * Word Groebner base using word pairlist class. 062 * @param F word polynomial list. 063 * @return GB(F) a finite non-commutative Groebner base of F, if it exists. 064 */ 065 public List<GenWordPolynomial<C>> GB( List<GenWordPolynomial<C>> F ) { 066 GenWordPolynomial<C> p; 067 List<GenWordPolynomial<C>> G = new ArrayList<GenWordPolynomial<C>>(); 068 WordPairList<C> pairlist = null; 069 int l = F.size(); 070 ListIterator<GenWordPolynomial<C>> it = F.listIterator(); 071 while ( it.hasNext() ) { 072 p = it.next(); 073 if ( p.length() > 0 ) { 074 p = p.monic(); 075 if ( p.isONE() ) { 076 G.clear(); G.add( p ); 077 return G; // since no threads are activated 078 } 079 G.add( p ); 080 if ( pairlist == null ) { 081 //pairlist = new OrderedPairlist<C>(p.ring ); 082 pairlist = strategy.create( p.ring ); 083 if ( ! p.ring.coFac.isField() ) { 084 throw new IllegalArgumentException("coefficients not from a field"); 085 } 086 } 087 // putOne not required 088 pairlist.put( p ); 089 } else { 090 l--; 091 } 092 } 093 if ( l <= 1 ) { 094 return G; // since no threads are activated 095 } 096 logger.info("start " + pairlist); 097 098 WordPair<C> pair; 099 GenWordPolynomial<C> pi; 100 GenWordPolynomial<C> pj; 101 List<GenWordPolynomial<C>> S; 102 GenWordPolynomial<C> H; 103 while ( pairlist.hasNext() ) { 104 pair = pairlist.removeNext(); 105 //logger.debug("pair = " + pair); 106 if ( pair == null ) { 107 continue; 108 } 109 pi = pair.pi; 110 pj = pair.pj; 111 if ( /*false &&*/ debug ) { 112 logger.debug("pi = " + pi ); 113 logger.debug("pj = " + pj ); 114 } 115 116 S = red.SPolynomials( pi, pj ); 117 if ( S.isEmpty() ) { 118 continue; 119 } 120 for ( GenWordPolynomial<C> s : S ) { 121 if ( s.isZERO() ) { 122 //pair.setZero(); 123 continue; 124 } 125 if ( debug ) { 126 logger.debug("ht(S) = " + s.leadingWord() ); 127 } 128 129 H = red.normalform( G, s ); 130 if ( debug ) { 131 //logger.info("pair = " + pair); 132 //logger.info("ht(S) = " + S.monic()); //.leadingWord() ); 133 logger.info("ht(H) = " + H.monic()); //.leadingWord() ); 134 } 135 if ( H.isZERO() ) { 136 //pair.setZero(); 137 continue; 138 } 139 H = H.monic(); 140 if ( debug ) { 141 logger.info("ht(H) = " + H.leadingWord() ); 142 } 143 if ( H.isONE() ) { 144 G.clear(); G.add( H ); 145 return G; // since no threads are activated 146 } 147 if ( debug ) { 148 logger.info("H = " + H ); 149 } 150 if ( H.length() > 0 ) { 151 l++; 152 G.add( H ); 153 pairlist.put( H ); 154 } 155 } 156 } 157 logger.debug("#sequential list = " + G.size()); 158 G = minimalGB(G); 159 logger.info("" + pairlist); 160 return G; 161 } 162 163}