001 /*
002 * $Id: GenSolvablePolynomial.java 3440 2010-12-25 14:21:08Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import java.util.Set;
008 import java.util.Map;
009 import java.util.SortedMap;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.structure.RingElem;
014 import edu.jas.structure.RingFactory;
015
016
017 /**
018 * GenSolvablePolynomial generic solvable polynomials implementing RingElem.
019 * n-variate ordered solvable polynomials over C.
020 * Objects of this class are intended to be immutable.
021 * The implementation is based on TreeMap respectively SortedMap
022 * from exponents to coefficients by extension of GenPolybomial.
023 * Only the coefficients are modeled with generic types,
024 * the exponents are fixed to ExpVector with long entries
025 * (this will eventually be changed in the future).
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030 public class GenSolvablePolynomial<C extends RingElem<C>>
031 extends GenPolynomial<C> {
032 //not possible: implements RingElem< GenSolvablePolynomial<C> > {
033
034
035 /** The factory for the solvable polynomial ring.
036 * Hides super.ring.
037 */
038 public final GenSolvablePolynomialRing< C > ring;
039
040
041 private static final Logger logger = Logger.getLogger(GenSolvablePolynomial.class);
042 private final boolean debug = false; //logger.isDebugEnabled();
043
044
045 /**
046 * Constructor for zero GenSolvablePolynomial.
047 * @param r solvable polynomial ring factory.
048 */
049 public GenSolvablePolynomial(GenSolvablePolynomialRing< C > r) {
050 super(r);
051 ring = r;
052 }
053
054
055 /**
056 * Constructor for zero GenSolvablePolynomial.
057 * @param r solvable polynomial ring factory.
058 * @param c coefficient.
059 * @param e exponent.
060 */
061 public GenSolvablePolynomial(GenSolvablePolynomialRing< C > r,
062 C c, ExpVector e) {
063 this(r);
064 if ( c != null && ! c.isZERO() ) {
065 val.put(e,c);
066 }
067 }
068
069
070 /**
071 * Constructor for zero GenSolvablePolynomial.
072 * @param r solvable polynomial ring factory.
073 * @param v the SortedMap of some other (solvable) polynomial.
074 */
075 protected GenSolvablePolynomial(GenSolvablePolynomialRing< C > r,
076 SortedMap<ExpVector,C> v) {
077 this(r);
078 val.putAll( v ); // assume no zero coefficients
079 }
080
081
082 /**
083 * Get the corresponding element factory.
084 * @return factory for this Element.
085 * @see edu.jas.structure.Element#factory()
086 */
087 public GenSolvablePolynomialRing<C> factory() {
088 return ring;
089 }
090
091
092 /**
093 * Clone this GenSolvablePolynomial.
094 * @see java.lang.Object#clone()
095 */
096 @Override
097 public GenSolvablePolynomial<C> clone() {
098 //return ring.copy(this);
099 return new GenSolvablePolynomial<C>(ring,this.val);
100 }
101
102
103 /**
104 * GenSolvablePolynomial multiplication.
105 * @param Bp GenSolvablePolynomial.
106 * @return this*Bp, where * denotes solvable multiplication.
107 */
108 public GenSolvablePolynomial<C> multiply(GenSolvablePolynomial<C> Bp) {
109 if ( Bp == null || Bp.isZERO() ) {
110 return ring.getZERO();
111 }
112 if ( this.isZERO() ) {
113 return this;
114 }
115 assert (ring.nvar == Bp.ring.nvar);
116 if ( debug ) {
117 logger.debug("ring = " + ring);
118 }
119 ExpVector Z = ring.evzero;
120 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
121 GenSolvablePolynomial<C> zero = ring.getZERO().clone();
122 C one = ring.getONECoefficient();
123
124 GenSolvablePolynomial<C> C1 = null;
125 GenSolvablePolynomial<C> C2 = null;
126 Map<ExpVector,C> A = val;
127 Map<ExpVector,C> B = Bp.val;
128 Set<Map.Entry<ExpVector,C>> Bk = B.entrySet();
129 for ( Map.Entry<ExpVector,C> y: A.entrySet() ) {
130 C a = y.getValue();
131 ExpVector e = y.getKey();
132 if ( debug ) logger.debug("e = " + e);
133 int[] ep = e.dependencyOnVariables();
134 int el1 = ring.nvar + 1;
135 if ( ep.length > 0 ) {
136 el1 = ep[0];
137 }
138 int el1s = ring.nvar + 1 - el1;
139 for ( Map.Entry<ExpVector,C> x: Bk ) {
140 C b = x.getValue();
141 ExpVector f = x.getKey();
142 if ( debug ) logger.debug("f = " + f);
143 int[] fp = f.dependencyOnVariables();
144 int fl1 = 0;
145 if ( fp.length > 0 ) {
146 fl1 = fp[fp.length-1];
147 }
148 int fl1s = ring.nvar + 1 - fl1;
149 if ( debug ) {
150 logger.debug("el1s = " + el1s + " fl1s = " + fl1s);
151 }
152 GenSolvablePolynomial<C> Cs = null;
153 if ( el1s <= fl1s ) { // symmetric
154 ExpVector g = e.sum(f);
155 //if ( debug ) logger.debug("g = " + g);
156 Cs = (GenSolvablePolynomial<C>)zero.sum( one, g ); // symmetric!
157 //Cs = new GenSolvablePolynomial<C>(ring,one,g); // symmetric!
158 } else { // unsymmetric
159 // split e = e1 * e2, f = f1 * f2
160 ExpVector e1 = e.subst(el1,0);
161 ExpVector e2 = Z.subst(el1,e.getVal(el1));
162 ExpVector e4;
163 ExpVector f1 = f.subst(fl1,0);
164 ExpVector f2 = Z.subst(fl1,f.getVal(fl1));
165 //if ( debug ) logger.debug("e1 = " + e1 + " e2 = " + e2);
166 //if ( debug ) logger.debug("f1 = " + f1 + " f2 = " + f2);
167 TableRelation<C> rel = ring.table.lookup(e2,f2);
168 //logger.info("relation = " + rel);
169 Cs = rel.p; //ring.copy( rel.p ); // do not clone()
170 if ( rel.f != null ) {
171 C2 = (GenSolvablePolynomial<C>)zero.sum( one, rel.f );
172 Cs = Cs.multiply( C2 );
173 if ( rel.e == null ) {
174 e4 = e2;
175 } else {
176 e4 = e2.subtract( rel.e );
177 }
178 ring.table.update(e4,f2,Cs);
179 }
180 if ( rel.e != null ) {
181 C1 = (GenSolvablePolynomial<C>)zero.sum( one, rel.e );
182 Cs = C1.multiply( Cs );
183 ring.table.update(e2,f2,Cs);
184 }
185 if ( !f1.isZERO() ) {
186 C2 = (GenSolvablePolynomial<C>)zero.sum( one, f1 );
187 Cs = Cs.multiply( C2 );
188 //ring.table.update(?,f1,Cs)
189 }
190 if ( !e1.isZERO() ) {
191 C1 = (GenSolvablePolynomial<C>)zero.sum( one, e1 );
192 Cs = C1.multiply( Cs );
193 //ring.table.update(e1,?,Cs)
194 }
195 }
196 C c = a.multiply(b);
197 //logger.debug("c = " + c);
198 Cs = Cs.multiply( c ); // symmetric!
199 //if ( debug ) logger.debug("Cs = " + Cs);
200 Cp = (GenSolvablePolynomial<C>)Cp.sum( Cs );
201 }
202 }
203 return Cp;
204 }
205
206
207
208 /**
209 * GenSolvablePolynomial multiplication.
210 * Product with coefficient ring element.
211 * @param b coefficient.
212 * @return this*b, where * is usual multiplication.
213 */
214 @Override
215 public GenSolvablePolynomial<C> multiply(C b) {
216 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
217 if ( b == null || b.isZERO() ) {
218 return Cp;
219 }
220 Map<ExpVector,C> Cm = Cp.val; //getMap();
221 Map<ExpVector,C> Am = val;
222 for ( Map.Entry<ExpVector,C> y: Am.entrySet() ) {
223 ExpVector e = y.getKey();
224 C a = y.getValue();
225 C c = a.multiply(b);
226 Cm.put( e, c );
227 }
228 return Cp;
229 }
230
231
232 /**
233 * GenSolvablePolynomial multiplication.
234 * Product with exponent vector.
235 * @param e exponent.
236 * @return this * x<sup>e</sup>,
237 * where * denotes solvable multiplication.
238 */
239 @Override
240 public GenSolvablePolynomial<C> multiply(ExpVector e) {
241 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
242 if ( e == null || e.isZERO() ) {
243 return this;
244 }
245 C b = ring.getONECoefficient();
246 Cp = new GenSolvablePolynomial<C>(ring,b,e);
247 return multiply(Cp);
248 }
249
250
251 /**
252 * GenSolvablePolynomial multiplication.
253 * Product with ring element and exponent vector.
254 * @param b coefficient.
255 * @param e exponent.
256 * @return this * b x<sup>e</sup>,
257 * where * denotes solvable multiplication.
258 */
259 @Override
260 public GenSolvablePolynomial<C> multiply(C b, ExpVector e) {
261 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
262 if ( b == null || b.isZERO() ) {
263 return Cp;
264 }
265 //Cp = (GenSolvablePolynomial<C>)Cp.add(b,e);
266 Cp = new GenSolvablePolynomial<C>(ring,b,e);
267 return multiply(Cp);
268 }
269
270
271 /**
272 * GenSolvablePolynomial multiplication.
273 * Left product with ring element and exponent vector.
274 * @param b coefficient.
275 * @param e exponent.
276 * @return b x<sup>e</sup> * this,
277 * where * denotes solvable multiplication.
278 */
279 public GenSolvablePolynomial<C> multiplyLeft(C b, ExpVector e) {
280 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
281 if ( b == null || b.isZERO() ) {
282 return Cp;
283 }
284 Cp = new GenSolvablePolynomial<C>(ring,b,e);
285 Cp = Cp.multiply(this);
286 return Cp;
287 }
288
289
290 /**
291 * GenSolvablePolynomial multiplication.
292 * Left product with exponent vector.
293 * @param e exponent.
294 * @return x<sup>e</sup> * this,
295 * where * denotes solvable multiplication.
296 */
297 public GenSolvablePolynomial<C> multiplyLeft(ExpVector e) {
298 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
299 if ( e == null || e.isZERO() ) {
300 return this;
301 }
302 C b = ring.getONECoefficient();
303 Cp = new GenSolvablePolynomial<C>(ring,b,e);
304 return Cp.multiply(this);
305 }
306
307
308 /**
309 * GenSolvablePolynomial multiplication.
310 * Left product with coefficient ring element.
311 * @param b coefficient.
312 * @return b*this, where * is usual multiplication.
313 */
314 public GenSolvablePolynomial<C> multiplyLeft(C b) {
315 GenSolvablePolynomial<C> Cp = ring.getZERO().clone();
316 if ( b == null || b.isZERO() ) {
317 return Cp;
318 }
319 Map<ExpVector,C> Cm = Cp.val; //getMap();
320 Map<ExpVector,C> Am = val;
321 for ( Map.Entry<ExpVector,C> y: Am.entrySet() ) {
322 ExpVector e = y.getKey();
323 C a = y.getValue();
324 C c = b.multiply(a);
325 Cm.put( e, c );
326 }
327 return Cp;
328 }
329
330
331 /**
332 * GenSolvablePolynomial multiplication.
333 * Left product with 'monimial'.
334 * @param m 'monoial'.
335 * @return m * this,
336 * where * denotes solvable multiplication.
337 */
338 public GenSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector,C> m) {
339 if ( m == null ) {
340 return ring.getZERO();
341 }
342 return multiplyLeft( m.getValue(), m.getKey() );
343 }
344
345 }