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