001/* 002 * $Id: SolvableReductionAbstract.java 4104 2012-08-18 10:00:59Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.Iterator; 010import java.util.List; 011import java.util.Map; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenSolvablePolynomial; 017import edu.jas.structure.RingElem; 018 019 020/** 021 * Solvable polynomial Reduction abstract class. Implements common left, right 022 * S-Polynomial, left normalform and left irreducible set. 023 * @param <C> coefficient type 024 * @author Heinz Kredel 025 */ 026 027public abstract class SolvableReductionAbstract<C extends RingElem<C>> implements SolvableReduction<C> { 028 029 030 private static final Logger logger = Logger.getLogger(SolvableReductionAbstract.class); 031 032 033 private final boolean debug = logger.isDebugEnabled(); 034 035 036 /** 037 * Constructor. 038 */ 039 public SolvableReductionAbstract() { 040 } 041 042 043 /** 044 * Left S-Polynomial. 045 * @param Ap solvable polynomial. 046 * @param Bp solvable polynomial. 047 * @return left-spol(Ap,Bp) the left S-polynomial of Ap and Bp. 048 */ 049 public GenSolvablePolynomial<C> leftSPolynomial(GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Bp) { 050 if (logger.isInfoEnabled()) { 051 if (Bp == null || Bp.isZERO()) { 052 if (Ap != null) { 053 return Ap.ring.getZERO(); 054 } 055 return null; 056 } 057 if (Ap == null || Ap.isZERO()) { 058 return Bp.ring.getZERO(); 059 } 060 if (!Ap.ring.equals(Bp.ring)) { 061 logger.error("rings not equal"); 062 } 063 } 064 Map.Entry<ExpVector, C> ma = Ap.leadingMonomial(); 065 Map.Entry<ExpVector, C> mb = Bp.leadingMonomial(); 066 067 ExpVector e = ma.getKey(); 068 ExpVector f = mb.getKey(); 069 070 ExpVector g = e.lcm(f); 071 ExpVector e1 = g.subtract(e); 072 ExpVector f1 = g.subtract(f); 073 074 C a = ma.getValue(); 075 C b = mb.getValue(); 076 077 GenSolvablePolynomial<C> App = Ap.multiplyLeft(b, e1); 078 GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft(a, f1); 079 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp); 080 return Cp; 081 } 082 083 084 /** 085 * S-Polynomial with recording. 086 * @param S recording matrix, is modified. 087 * @param i index of Ap in basis list. 088 * @param Ap a polynomial. 089 * @param j index of Bp in basis list. 090 * @param Bp a polynomial. 091 * @return leftSpol(Ap, Bp), the left S-Polynomial for Ap and Bp. 092 */ 093 public GenSolvablePolynomial<C> leftSPolynomial(List<GenSolvablePolynomial<C>> S, int i, 094 GenSolvablePolynomial<C> Ap, int j, GenSolvablePolynomial<C> Bp) { 095 if (debug /*logger.isInfoEnabled()*/) { 096 if (Bp == null || Bp.isZERO()) { 097 throw new ArithmeticException("Spol B is zero"); 098 } 099 if (Ap == null || Ap.isZERO()) { 100 throw new ArithmeticException("Spol A is zero"); 101 } 102 if (!Ap.ring.equals(Bp.ring)) { 103 logger.error("rings not equal"); 104 } 105 } 106 Map.Entry<ExpVector, C> ma = Ap.leadingMonomial(); 107 Map.Entry<ExpVector, C> mb = Bp.leadingMonomial(); 108 109 ExpVector e = ma.getKey(); 110 ExpVector f = mb.getKey(); 111 112 ExpVector g = e.lcm(f); 113 ExpVector e1 = g.subtract(e); 114 ExpVector f1 = g.subtract(f); 115 116 C a = ma.getValue(); 117 C b = mb.getValue(); 118 119 GenSolvablePolynomial<C> App = Ap.multiplyLeft(b, e1); 120 GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft(a, f1); 121 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp); 122 123 GenSolvablePolynomial<C> zero = Ap.ring.getZERO(); 124 GenSolvablePolynomial<C> As = (GenSolvablePolynomial<C>) zero.sum(b.negate(), e1); 125 GenSolvablePolynomial<C> Bs = (GenSolvablePolynomial<C>) zero.sum(a, f1); 126 S.set(i, As); 127 S.set(j, Bs); 128 return Cp; 129 } 130 131 132 /** 133 * Left Normalform Set. 134 * @param Ap solvable polynomial list. 135 * @param Pp solvable polynomial list. 136 * @return list of left-nf(a) with respect to Pp for all a in Ap. 137 */ 138 public List<GenSolvablePolynomial<C>> leftNormalform(List<GenSolvablePolynomial<C>> Pp, 139 List<GenSolvablePolynomial<C>> Ap) { 140 if (Pp == null || Pp.isEmpty()) { 141 return Ap; 142 } 143 if (Ap == null || Ap.isEmpty()) { 144 return Ap; 145 } 146 ArrayList<GenSolvablePolynomial<C>> red = new ArrayList<GenSolvablePolynomial<C>>(); 147 for (GenSolvablePolynomial<C> A : Ap) { 148 A = leftNormalform(Pp, A); 149 red.add(A); 150 } 151 return red; 152 } 153 154 155 /** 156 * Left irreducible set. 157 * @param Pp solvable polynomial list. 158 * @return a list P of solvable polynomials which are in normalform wrt. P. 159 */ 160 public List<GenSolvablePolynomial<C>> leftIrreducibleSet(List<GenSolvablePolynomial<C>> Pp) { 161 ArrayList<GenSolvablePolynomial<C>> P = new ArrayList<GenSolvablePolynomial<C>>(); 162 for (GenSolvablePolynomial<C> a : Pp) { 163 if (a.length() != 0) { 164 a = (GenSolvablePolynomial<C>) a.monic(); 165 P.add(a); 166 } 167 } 168 int l = P.size(); 169 if (l <= 1) 170 return P; 171 172 int irr = 0; 173 ExpVector e; 174 ExpVector f; 175 GenSolvablePolynomial<C> a; 176 Iterator<GenSolvablePolynomial<C>> it; 177 logger.debug("irr = "); 178 while (irr != l) { 179 it = P.listIterator(); 180 a = it.next(); 181 P.remove(0); 182 e = a.leadingExpVector(); 183 a = leftNormalform(P, a); 184 logger.debug(String.valueOf(irr)); 185 if (a.length() == 0) { 186 l--; 187 if (l <= 1) { 188 return P; 189 } 190 } else { 191 f = a.leadingExpVector(); 192 if (f.signum() == 0) { 193 P = new ArrayList<GenSolvablePolynomial<C>>(); 194 P.add((GenSolvablePolynomial<C>) a.monic()); 195 return P; 196 } 197 if (e.equals(f)) { 198 irr++; 199 } else { 200 irr = 0; 201 a = (GenSolvablePolynomial<C>) a.monic(); 202 } 203 P.add(a); 204 } 205 } 206 //System.out.println(); 207 return P; 208 } 209 210 211 /** 212 * Is reduction of normal form. 213 * @param row recording matrix. 214 * @param Pp a solvable polynomial list for reduction. 215 * @param Ap a solvable polynomial. 216 * @param Np nf(Pp,Ap), a left normal form of Ap wrt. Pp. 217 * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false. 218 */ 219 @SuppressWarnings("unchecked") 220 public boolean isLeftReductionNF(List<GenSolvablePolynomial<C>> row, List<GenSolvablePolynomial<C>> Pp, 221 GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Np) { 222 if (row == null && Pp == null) { 223 if (Ap == null) { 224 return Np == null; 225 } 226 return Ap.equals(Np); 227 } 228 if (row == null || Pp == null) { 229 return false; 230 } 231 if (row.size() != Pp.size()) { 232 return false; 233 } 234 GenSolvablePolynomial<C> t = Np; 235 GenSolvablePolynomial<C> r; 236 GenSolvablePolynomial<C> p; 237 for (int m = 0; m < Pp.size(); m++) { 238 r = row.get(m); 239 p = Pp.get(m); 240 if (r != null && p != null) { 241 if (t == null) { 242 t = r.multiply(p); 243 } else { 244 t = (GenSolvablePolynomial<C>) t.sum(r.multiply(p)); 245 } 246 } 247 //System.out.println("r = " + r ); 248 //System.out.println("p = " + p ); 249 } 250 if (debug) { 251 logger.info("t = " + t); 252 logger.info("a = " + Ap); 253 } 254 if (t == null) { 255 if (Ap == null) { 256 return true; 257 } 258 return Ap.isZERO(); 259 } 260 t = (GenSolvablePolynomial<C>) t.subtract(Ap); 261 return t.isZERO(); 262 } 263 264 265 /** 266 * Right S-Polynomial. 267 * @param Ap solvable polynomial. 268 * @param Bp solvable polynomial. 269 * @return right-spol(Ap,Bp) the right S-polynomial of Ap and Bp. 270 */ 271 @SuppressWarnings("unchecked") 272 public GenSolvablePolynomial<C> rightSPolynomial(GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Bp) { 273 if (logger.isInfoEnabled()) { 274 if (Bp == null || Bp.isZERO()) { 275 if (Ap != null) { 276 return Ap.ring.getZERO(); 277 } 278 return null; 279 } 280 if (Ap == null || Ap.isZERO()) { 281 return Bp.ring.getZERO(); 282 } 283 if (!Ap.ring.equals(Bp.ring)) { 284 logger.error("rings not equal"); 285 } 286 } 287 ExpVector e = Ap.leadingExpVector(); 288 ExpVector f = Bp.leadingExpVector(); 289 290 ExpVector g = e.lcm(f); 291 ExpVector e1 = g.subtract(e); 292 ExpVector f1 = g.subtract(f); 293 294 GenSolvablePolynomial<C> App = Ap.multiply(e1); 295 GenSolvablePolynomial<C> Bpp = Bp.multiply(f1); 296 297 C a = App.leadingBaseCoefficient(); 298 C b = Bpp.leadingBaseCoefficient(); 299 App = App.multiply(b); 300 Bpp = Bpp.multiply(a); 301 302 GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp); 303 return Cp; 304 } 305 306}