001/* 002 * $Id: WordReductionSeq.java 4152 2012-09-02 11:15:48Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007import java.util.List; 008import java.util.Map; 009 010import org.apache.log4j.Logger; 011 012import edu.jas.poly.Word; 013import edu.jas.poly.GenWordPolynomial; 014import edu.jas.structure.RingElem; 015 016 017/** 018 * Polynomial word reduction sequential use algorithm. 019 * Implements normalform. 020 * @param <C> coefficient type 021 * @author Heinz Kredel 022 */ 023 024public class WordReductionSeq<C extends RingElem<C>> // should be FieldElem<C>> 025 extends WordReductionAbstract<C> { 026 027 028 private static final Logger logger = Logger.getLogger(WordReductionSeq.class); 029 private static boolean debug = logger.isDebugEnabled(); 030 031 032 /** 033 * Constructor. 034 */ 035 public WordReductionSeq() { 036 } 037 038 039 /** 040 * Normalform. 041 * @param Ap polynomial. 042 * @param Pp polynomial list. 043 * @return nf(Ap) with respect to Pp. 044 */ 045 @SuppressWarnings("unchecked") 046 public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> Pp, 047 GenWordPolynomial<C> Ap) { 048 if ( Pp == null || Pp.isEmpty() ) { 049 return Ap; 050 } 051 if ( Ap == null || Ap.isZERO() ) { 052 return Ap; 053 } 054 if ( ! Ap.ring.coFac.isField() ) { 055 throw new IllegalArgumentException("coefficients not from a field"); 056 } 057 Map.Entry<Word,C> m; 058 int l; 059 GenWordPolynomial<C>[] P; 060 synchronized (Pp) { 061 l = Pp.size(); 062 P = new GenWordPolynomial[l]; 063 //P = Pp.toArray(); 064 for ( int i = 0; i < Pp.size(); i++ ) { 065 P[i] = Pp.get(i); 066 } 067 } 068 Word[] htl = new Word[ l ]; 069 Object[] lbc = new Object[ l ]; // want C[] 070 GenWordPolynomial<C>[] p = new GenWordPolynomial[ l ]; 071 int i; 072 int j = 0; 073 for ( i = 0; i < l; i++ ) { 074 p[i] = P[i]; 075 m = p[i].leadingMonomial(); 076 if ( m != null ) { 077 p[j] = p[i]; 078 htl[j] = m.getKey(); 079 lbc[j] = m.getValue(); 080 j++; 081 } 082 } 083 l = j; 084 Word e; 085 C a; 086 boolean mt = false; 087 GenWordPolynomial<C> R = Ap.ring.getZERO(); 088 C cone = Ap.ring.coFac.getONE(); 089 090 //GenWordPolynomial<C> T = null; 091 GenWordPolynomial<C> Q = null; 092 GenWordPolynomial<C> S = Ap; 093 while ( S.length() > 0 ) { 094 m = S.leadingMonomial(); 095 e = m.getKey(); 096 a = m.getValue(); 097 for ( i = 0; i < l; i++ ) { 098 mt = e.multipleOf( htl[i] ); 099 if ( mt ) break; 100 } 101 if ( ! mt ) { 102 //logger.debug("irred"); 103 //T = new OrderedMapPolynomial( a, e ); 104 R = R.sum( a, e ); 105 S = S.subtract( a, e ); 106 // System.out.println(" S = " + S); 107 } else { 108 Word[] elr = e.divideWord( htl[i] ); 109 e = elr[0]; 110 Word f = elr[1]; 111 if ( debug ) { 112 logger.info("red divideWord: e = " + e + ", f = " + f); 113 } 114 a = a.divide( (C)lbc[i] ); 115 Q = p[i].multiply( a, e, cone, f ); 116 S = S.subtract( Q ); 117 } 118 } 119 return R; 120 } 121 122 123 /** 124 * Normalform with left and right recording. 125 * @param lrow left recording matrix, is modified. 126 * @param rrow right recording matrix, is modified. 127 * @param Pp a polynomial list for reduction. 128 * @param Ap a polynomial. 129 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 130 */ 131 @SuppressWarnings("unchecked") 132 public GenWordPolynomial<C> 133 normalform(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow, 134 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 135 if ( Pp == null || Pp.isEmpty() ) { 136 return Ap; 137 } 138 if ( Ap == null || Ap.isZERO() ) { 139 return Ap; 140 } 141 if ( ! Ap.ring.coFac.isField() ) { 142 throw new IllegalArgumentException("coefficients not from a field"); 143 } 144 int l = Pp.size(); 145 GenWordPolynomial<C>[] P = new GenWordPolynomial[l]; 146 synchronized (Pp) { 147 //P = Pp.toArray(); 148 for ( int i = 0; i < Pp.size(); i++ ) { 149 P[i] = Pp.get(i); 150 } 151 } 152 Word[] htl = new Word[ l ]; 153 Object[] lbc = new Object[ l ]; // want C[] 154 GenWordPolynomial<C>[] p = new GenWordPolynomial[ l ]; 155 Map.Entry<Word,C> m; 156 int j = 0; 157 int i; 158 for ( i = 0; i < l; i++ ) { 159 p[i] = P[i]; 160 m = p[i].leadingMonomial(); 161 if ( m != null ) { 162 p[j] = p[i]; 163 htl[j] = m.getKey(); 164 lbc[j] = m.getValue(); 165 j++; 166 } 167 } 168 l = j; 169 Word e; 170 C a; 171 boolean mt = false; 172 GenWordPolynomial<C> zero = Ap.ring.getZERO(); 173 GenWordPolynomial<C> R = Ap.ring.getZERO(); 174 C cone = Ap.ring.coFac.getONE(); 175 176 GenWordPolynomial<C> fac = null; 177 // GenWordPolynomial<C> T = null; 178 GenWordPolynomial<C> Q = null; 179 GenWordPolynomial<C> S = Ap; 180 while ( S.length() > 0 ) { 181 m = S.leadingMonomial(); 182 e = m.getKey(); 183 a = m.getValue(); 184 for ( i = 0; i < l; i++ ) { 185 mt = e.multipleOf( htl[i] ); 186 if ( mt ) break; 187 } 188 if ( ! mt ) { 189 //logger.debug("irred"); 190 R = R.sum( a, e ); 191 S = S.subtract( a, e ); 192 // System.out.println(" S = " + S); 193 //throw new RuntimeException("Syzygy no GB"); 194 } else { 195 Word[] elr = e.divideWord( htl[i] ); 196 e = elr[0]; 197 Word f = elr[1]; 198 if ( debug ) { 199 logger.info("redRec divideWord: e = " + e + ", f = " + f); 200 } 201 C c = (C) lbc[i]; 202 a = a.divide( c ); 203 Q = p[i].multiply( a, e, cone, f ); 204 S = S.subtract( Q ); 205 // left row 206 fac = lrow.get(i); 207 if ( fac == null ) { 208 fac = zero.sum( cone, e ); 209 } else { 210 fac = fac.sum( cone, e ); 211 } 212 lrow.set(i,fac); 213 // right row 214 fac = rrow.get(i); 215 if ( fac == null ) { 216 fac = zero.sum( a, f ); 217 } else { 218 fac = fac.sum( a, f ); 219 } 220 rrow.set(i,fac); 221 } 222 } 223 return R; 224 } 225 226}