001 /*
002 * $Id: SolvableReductionSeq.java 3296 2010-08-26 17:30:55Z kredel $
003 */
004
005 package edu.jas.gb;
006
007
008 import java.util.List;
009 import java.util.Map;
010
011 import edu.jas.poly.ExpVector;
012 import edu.jas.poly.GenSolvablePolynomial;
013 import edu.jas.structure.RingElem;
014
015
016 /**
017 * Solvable polynomial Reduction algorithm. Implements left, right normalform.
018 * @param <C> coefficient type
019 * @author Heinz Kredel
020 */
021
022 public class SolvableReductionSeq<C extends RingElem<C>> extends SolvableReductionAbstract<C> {
023
024
025 //private static final Logger logger = Logger.getLogger(SolvableReductionSeq.class);
026
027
028 /**
029 * Constructor.
030 */
031 public SolvableReductionSeq() {
032 }
033
034
035 /**
036 * Left Normalform.
037 * @param Ap solvable polynomial.
038 * @param Pp solvable polynomial list.
039 * @return left-nf(Ap) with respect to Pp.
040 */
041 public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
042 GenSolvablePolynomial<C> Ap) {
043 if (Pp == null || Pp.isEmpty()) {
044 return Ap;
045 }
046 if (Ap == null || Ap.isZERO()) {
047 return Ap;
048 }
049 int l;
050 Map.Entry<ExpVector, C> m;
051 GenSolvablePolynomial<C>[] P;
052 synchronized (Pp) {
053 l = Pp.size();
054 P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
055 //P = Pp.toArray();
056 for (int j = 0; j < Pp.size(); j++) {
057 P[j] = Pp.get(j);
058 }
059 }
060 int i;
061 ExpVector[] htl = new ExpVector[l];
062 Object[] lbc = new Object[l]; // want <C>
063 GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
064 int j = 0;
065 for (i = 0; i < l; i++) {
066 p[i] = P[i];
067 m = p[i].leadingMonomial();
068 if (m != null) {
069 p[j] = p[i];
070 htl[j] = m.getKey();
071 lbc[j] = m.getValue();
072 j++;
073 }
074 }
075 l = j;
076 ExpVector e;
077 C a;
078 boolean mt = false;
079 GenSolvablePolynomial<C> R = Ap.ring.getZERO();
080
081 //GenSolvablePolynomial<C> T = null;
082 GenSolvablePolynomial<C> Q = null;
083 GenSolvablePolynomial<C> S = Ap;
084 while (S.length() > 0) {
085 m = S.leadingMonomial();
086 e = m.getKey();
087 //logger.info("red = " + e);
088 a = m.getValue();
089 for (i = 0; i < l; i++) {
090 mt = e.multipleOf(htl[i]);
091 if (mt)
092 break;
093 }
094 if (!mt) {
095 //logger.debug("irred");
096 //T = new OrderedMapPolynomial( a, e );
097 R = (GenSolvablePolynomial<C>) R.sum(a, e);
098 S = (GenSolvablePolynomial<C>) S.subtract(a, e);
099 // System.out.println(" S = " + S);
100 } else {
101 //logger.debug("red");
102 e = e.subtract(htl[i]);
103 //a = a.divide( (C)lbc[i] );
104 Q = p[i].multiplyLeft(e);
105 a = a.divide(Q.leadingBaseCoefficient());
106 Q = Q.multiplyLeft(a);
107 S = (GenSolvablePolynomial<C>) S.subtract(Q);
108 }
109 }
110 return R;
111 }
112
113
114 /**
115 * LeftNormalform with recording.
116 * @param row recording matrix, is modified.
117 * @param Pp a polynomial list for reduction.
118 * @param Ap a polynomial.
119 * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
120 */
121 public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
122 List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
123 if (Pp == null || Pp.isEmpty()) {
124 return Ap;
125 }
126 if (Ap == null || Ap.isZERO()) {
127 return Ap;
128 }
129 int l = Pp.size();
130 GenSolvablePolynomial<C>[] P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
131 synchronized (Pp) {
132 //P = Pp.toArray();
133 for (int i = 0; i < Pp.size(); i++) {
134 P[i] = Pp.get(i);
135 }
136 }
137 ExpVector[] htl = new ExpVector[l];
138 Object[] lbc = new Object[l]; // want <C>
139 GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
140 Map.Entry<ExpVector, C> m;
141 int j = 0;
142 int i;
143 for (i = 0; i < l; i++) {
144 p[i] = P[i];
145 m = p[i].leadingMonomial();
146 if (m != null) {
147 p[j] = p[i];
148 htl[j] = m.getKey();
149 lbc[j] = m.getValue();
150 j++;
151 }
152 }
153 l = j;
154 ExpVector e;
155 C a;
156 boolean mt = false;
157 GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
158 GenSolvablePolynomial<C> R = Ap.ring.getZERO();
159
160 GenSolvablePolynomial<C> fac = null;
161 // GenSolvablePolynomial<C> T = null;
162 GenSolvablePolynomial<C> Q = null;
163 GenSolvablePolynomial<C> S = Ap;
164 while (S.length() > 0) {
165 m = S.leadingMonomial();
166 e = m.getKey();
167 a = m.getValue();
168 for (i = 0; i < l; i++) {
169 mt = e.multipleOf(htl[i]);
170 if (mt)
171 break;
172 }
173 if (!mt) {
174 //logger.debug("irred");
175 R = (GenSolvablePolynomial<C>) R.sum(a, e);
176 S = (GenSolvablePolynomial<C>) S.subtract(a, e);
177 // System.out.println(" S = " + S);
178 // throw new RuntimeException("Syzygy no leftGB");
179 } else {
180 e = e.subtract(htl[i]);
181 //logger.info("red div = " + e);
182 //a = a.divide( (C)lbc[i] );
183 //Q = p[i].multiplyLeft( a, e );
184 Q = p[i].multiplyLeft(e);
185 a = a.divide(Q.leadingBaseCoefficient());
186 Q = Q.multiply(a);
187 S = (GenSolvablePolynomial<C>) S.subtract(Q);
188 fac = row.get(i);
189 if (fac == null) {
190 fac = (GenSolvablePolynomial<C>) zero.sum(a, e);
191 } else {
192 fac = (GenSolvablePolynomial<C>) fac.sum(a, e);
193 }
194 row.set(i, fac);
195 }
196 }
197 return R;
198 }
199
200
201 /**
202 * Right Normalform.
203 * @param Ap solvable polynomial.
204 * @param Pp solvable polynomial list.
205 * @return right-nf(Ap) with respect to Pp.
206 */
207 public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
208 GenSolvablePolynomial<C> Ap) {
209 if (Pp == null || Pp.isEmpty()) {
210 return Ap;
211 }
212 if (Ap == null || Ap.isZERO()) {
213 return Ap;
214 }
215 int l;
216 Map.Entry<ExpVector, C> m;
217 GenSolvablePolynomial<C>[] P;
218 synchronized (Pp) {
219 l = Pp.size();
220 P = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
221 //P = Pp.toArray();
222 for (int j = 0; j < Pp.size(); j++) {
223 P[j] = Pp.get(j);
224 }
225 }
226 int i;
227 ExpVector[] htl = new ExpVector[l];
228 Object[] lbc = new Object[l]; // want <C>
229 GenSolvablePolynomial<C>[] p = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[l];
230 int j = 0;
231 for (i = 0; i < l; i++) {
232 p[i] = P[i];
233 m = p[i].leadingMonomial();
234 if (m != null) {
235 p[j] = p[i];
236 htl[j] = m.getKey();
237 lbc[j] = m.getValue();
238 j++;
239 }
240 }
241 l = j;
242 ExpVector e;
243 C a;
244 boolean mt = false;
245 GenSolvablePolynomial<C> R = Ap.ring.getZERO();
246
247 //GenSolvablePolynomial<C> T = null;
248 GenSolvablePolynomial<C> Q = null;
249 GenSolvablePolynomial<C> S = Ap;
250 while (S.length() > 0) {
251 m = S.leadingMonomial();
252 e = m.getKey();
253 //logger.info("red = " + e);
254 a = m.getValue();
255 for (i = 0; i < l; i++) {
256 mt = e.multipleOf(htl[i]);
257 if (mt)
258 break;
259 }
260 if (!mt) {
261 //logger.debug("irred");
262 //T = new OrderedMapPolynomial( a, e );
263 R = (GenSolvablePolynomial<C>) R.sum(a, e);
264 S = (GenSolvablePolynomial<C>) S.subtract(a, e);
265 // System.out.println(" S = " + S);
266 } else {
267 //logger.debug("red");
268 e = e.subtract(htl[i]);
269 //a = a.divide( (C)lbc[i] );
270 Q = p[i].multiply(e);
271 a = a.divide(Q.leadingBaseCoefficient());
272 Q = Q.multiply(a);
273 S = (GenSolvablePolynomial<C>) S.subtract(Q);
274 }
275 }
276 return R;
277 }
278
279 }