001/* 002 * $Id: PseudoReductionPar.java 4291 2012-11-04 18:16:27Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.List; 009import java.util.ArrayList; 010import java.util.Map; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.gb.ReductionAbstract; 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.structure.RingElem; 018 019 020/** 021 * Polynomial pseudo reduction sequential use algorithm. Coefficients of 022 * polynomials must not be from a field, i.e. the fraction free reduction is 023 * implemented. Implements normalform. 024 * @param <C> coefficient type 025 * @author Heinz Kredel 026 */ 027 028public class PseudoReductionPar<C extends RingElem<C>> extends ReductionAbstract<C> implements 029 PseudoReduction<C> { 030 031 032 private static final Logger logger = Logger.getLogger(PseudoReductionPar.class); 033 034 035 /** 036 * Constructor. 037 */ 038 public PseudoReductionPar() { 039 } 040 041 042 /** 043 * Normalform. 044 * @param Ap polynomial. 045 * @param Pp polynomial list. 046 * @return nf(Ap) with respect to Pp. 047 */ 048 @SuppressWarnings("unchecked") 049 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 050 if (Pp == null || Pp.isEmpty()) { 051 return Ap; 052 } 053 if (Ap == null || Ap.isZERO()) { 054 return Ap; 055 } 056 GenPolynomial<C>[] P = new GenPolynomial[0]; 057 List<GenPolynomial<C>> Ppp; 058 synchronized (Pp) { 059 Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic 060 } 061 P = Ppp.toArray(P); 062 int ll = Ppp.size(); 063 GenPolynomial<C> Rz = Ap.ring.getZERO(); 064 GenPolynomial<C> R = Rz.copy(); 065 066 GenPolynomial<C> S = Ap.copy(); 067 while (S.length() > 0) { 068 if (Pp.size() != ll) { 069 //System.out.println("Pp.size() = " + Pp.size() + ", ll = " + ll); 070 //long t = System.currentTimeMillis(); 071 synchronized (Pp) { 072 Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic 073 } 074 P = Ppp.toArray(P); 075 ll = Ppp.size(); 076 //ll = P.length; // wrong 077 //t = System.currentTimeMillis()-t; 078 //logger.info("Pp.toArray(): size() = " + l + ", ll = " + ll); 079 S = Ap.copy(); // S.add(R)? // restart reduction ? 080 R = Rz.copy(); 081 } 082 boolean mt = false; 083 Map.Entry<ExpVector, C> m = S.leadingMonomial(); 084 ExpVector e = m.getKey(); 085 C a = m.getValue(); 086 ExpVector f = null; 087 int i; 088 for (i = 0; i < ll; i++) { 089 f = P[i].leadingExpVector(); 090 mt = e.multipleOf(f); 091 if (mt) 092 break; 093 } 094 if (!mt) { 095 //System.out.println("m = " + m); 096 //logger.debug("irred"); 097 //R = R.sum(a, e); 098 //S = S.subtract(a, e); 099 R.doPutToMap(e, a); 100 S.doRemoveFromMap(e, a); 101 //System.out.println(" S = " + S); 102 } else { 103 e = e.subtract(f); 104 //logger.info("red div = " + e); 105 C c = P[i].leadingBaseCoefficient(); 106 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 107 a = a.divide(c); 108 S = S.subtractMultiple(a, e, P[i]); 109 } else { 110 R = R.multiply(c); 111 //S = S.multiply(c); 112 S = S.scaleSubtractMultiple(c, a, e, P[i]); 113 } 114 //Q = p[i].multiply(a, e); 115 //S = S.subtract(Q); 116 } 117 } 118 return R; 119 } 120 121 122 /** 123 * Normalform. 124 * @param Pp polynomial list. 125 * @param Ap polynomial. 126 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 127 * for Ap. 128 */ 129 @SuppressWarnings("unchecked") 130 public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 131 if (Ap == null) { 132 return null; 133 } 134 C mfac = Ap.ring.getONECoefficient(); 135 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac); 136 if (Pp == null || Pp.isEmpty()) { 137 return pf; 138 } 139 if (Ap.isZERO()) { 140 return pf; 141 } 142 GenPolynomial<C>[] P = new GenPolynomial[0]; 143 List<GenPolynomial<C>> Ppp; 144 synchronized (Pp) { 145 Ppp = new ArrayList<GenPolynomial<C>>(Pp); // sic 146 } 147 P = Ppp.toArray(P); 148 int l = Ppp.size(); 149 boolean mt = false; 150 GenPolynomial<C> Rz = Ap.ring.getZERO(); 151 GenPolynomial<C> R = Rz.copy(); 152 //GenPolynomial<C> T = null; 153 GenPolynomial<C> Q = null; 154 GenPolynomial<C> S = Ap.copy(); 155 while (S.length() > 0) { 156 if (Pp.size() != l) { 157 //long t = System.currentTimeMillis(); 158 synchronized (Pp) { 159 Ppp = new ArrayList<GenPolynomial<C>>(Pp); 160 } 161 P = Ppp.toArray(P); 162 l = Ppp.size(); 163 //t = System.currentTimeMillis()-t; 164 //logger.info("Pp.toArray() = " + t + " ms, size() = " + l); 165 S = Ap.copy(); // S.add(R)? // restart reduction ? 166 R = Rz.copy(); 167 } 168 Map.Entry<ExpVector, C> m = S.leadingMonomial(); 169 ExpVector e = m.getKey(); 170 C a = m.getValue(); 171 ExpVector f = null; 172 int i; 173 for (i = 0; i < l; i++) { 174 f = P[i].leadingExpVector(); 175 mt = e.multipleOf(f); 176 if (mt) 177 break; 178 } 179 if (!mt) { 180 //logger.debug("irred"); 181 //R = R.sum(a, e); 182 //S = S.subtract(a, e); 183 R.doPutToMap(e, a); 184 S.doRemoveFromMap(e, a); 185 //System.out.println(" S = " + S); 186 } else { 187 e = e.subtract(f); 188 //logger.info("red div = " + e); 189 C c = P[i].leadingBaseCoefficient(); 190 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 191 a = a.divide(c); 192 S = S.subtractMultiple(a, e, P[i]); 193 } else { 194 mfac = mfac.multiply(c); 195 R = R.multiply(c); 196 //S = S.multiply(c); 197 S = S.scaleSubtractMultiple(c, a, e, P[i]); 198 } 199 //Q = p[i].multiply(a, e); 200 //S = S.subtract(Q); 201 } 202 } 203 if (logger.isInfoEnabled()) { 204 logger.info("multiplicative factor = " + mfac); 205 } 206 pf = new PseudoReductionEntry<C>(R, mfac); 207 return pf; 208 } 209 210 211 /** 212 * Normalform with recording. <b>Note:</b> Only meaningful if all divisions 213 * are exact. Compute first the multiplication factor <code>m</code> with 214 * <code>normalform(Pp,Ap,m)</code>, then call this method with 215 * <code>normalform(row,Pp,m*Ap)</code>. 216 * @param row recording matrix, is modified. 217 * @param Pp a polynomial list for reduction. 218 * @param Ap a polynomial. 219 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 220 */ 221 @SuppressWarnings("unchecked") 222 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, 223 GenPolynomial<C> Ap) { 224 throw new RuntimeException("normalform with recording not implemented"); 225 } 226 227}