Source code

001/*
002 * $Id: GenSolvablePolynomial.java 4142 2012-08-26 13:30:59Z kredel $
003 */
004
005package edu.jas.poly;
006
007import java.util.Set;
008import java.util.Map;
009import java.util.SortedMap;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.structure.RingElem;
014import 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
030public 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 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 GenSolvablePolynomial.
072     * @param r solvable polynomial ring factory.
073     * @param c coefficient.
074     */
075    public GenSolvablePolynomial(GenSolvablePolynomialRing< C > r, C c) {
076        this(r,c,r.evzero);
077    }
078
079
080    /**
081     * Constructor for GenSolvablePolynomial.
082     * @param r solvable polynomial ring factory.
083     * @param v the SortedMap of some other (solvable) polynomial.
084     */
085    protected GenSolvablePolynomial(GenSolvablePolynomialRing< C > r, 
086                                 SortedMap<ExpVector,C> v) {
087        this(r);
088        val.putAll( v ); // assume no zero coefficients
089    }
090
091
092    /**
093     * Get the corresponding element factory.
094     * @return factory for this Element.
095     * @see edu.jas.structure.Element#factory()
096     */
097    public GenSolvablePolynomialRing<C> factory() {
098        return ring;
099    }
100
101
102    /**
103     * Clone this GenSolvablePolynomial.
104     * @see java.lang.Object#clone()
105     */
106    @Override
107    public GenSolvablePolynomial<C> copy() {
108        //return ring.copy(this);
109        return new GenSolvablePolynomial<C>(ring,this.val);
110    }
111
112
113    /**
114     * Comparison with any other object.
115     * @see java.lang.Object#equals(java.lang.Object)
116     */
117    @Override
118    public boolean equals(Object B) {
119        if (!(B instanceof GenSolvablePolynomial)) {
120            return false;
121        }
122        return super.equals(B);
123    }
124
125
126    /**
127     * GenSolvablePolynomial multiplication. 
128     * @param Bp GenSolvablePolynomial.
129     * @return this*Bp, where * denotes solvable multiplication.
130     */
131    public GenSolvablePolynomial<C> multiply(GenSolvablePolynomial<C> Bp) {  
132        if ( Bp == null || Bp.isZERO() ) {
133            return ring.getZERO();
134        }
135        if ( this.isZERO() ) {
136            return this;
137        }
138        assert (ring.nvar == Bp.ring.nvar);
139        if ( debug ) {
140            logger.debug("ring = " + ring);
141        }
142        ExpVector Z = ring.evzero;
143        GenSolvablePolynomial<C> Cp = ring.getZERO().copy(); 
144        GenSolvablePolynomial<C> zero = ring.getZERO().copy();
145        C one = ring.getONECoefficient();
146
147        GenSolvablePolynomial<C> C1 = null;
148        GenSolvablePolynomial<C> C2 = null;
149        Map<ExpVector,C> A = val; 
150        Map<ExpVector,C> B = Bp.val; 
151        Set<Map.Entry<ExpVector,C>> Bk = B.entrySet();
152        for ( Map.Entry<ExpVector,C> y:  A.entrySet() ) {
153            C a = y.getValue(); 
154            ExpVector e = y.getKey(); 
155            if ( debug ) logger.debug("e = " + e);
156            int[] ep = e.dependencyOnVariables();
157            int el1 = ring.nvar + 1;
158            if ( ep.length > 0 ) {
159                el1 = ep[0];
160            }
161            int el1s = ring.nvar + 1 - el1; 
162            for ( Map.Entry<ExpVector,C> x: Bk ) {
163                C b = x.getValue(); 
164                ExpVector f = x.getKey(); 
165                if ( debug ) logger.debug("f = " + f);
166                int[] fp = f.dependencyOnVariables();
167                int fl1 = 0; 
168                if ( fp.length > 0 ) {
169                    fl1 = fp[fp.length-1];
170                }
171                int fl1s = ring.nvar + 1 - fl1; 
172                if ( debug ) {
173                    logger.debug("el1s = " + el1s + " fl1s = " + fl1s);
174                }
175                GenSolvablePolynomial<C> Cs = null;
176                if ( el1s <= fl1s ) { // symmetric
177                    ExpVector g = e.sum(f); 
178                    //if ( debug ) logger.debug("g = " + g);
179                    Cs = (GenSolvablePolynomial<C>)zero.sum( one, g ); // symmetric!
180                    //Cs = new GenSolvablePolynomial<C>(ring,one,g); // symmetric!
181                } else { // unsymmetric
182                    // split e = e1 * e2, f = f1 * f2
183                    ExpVector e1 = e.subst(el1,0);
184                    ExpVector e2 = Z.subst(el1,e.getVal(el1));
185                    ExpVector e4;
186                    ExpVector f1 = f.subst(fl1,0);
187                    ExpVector f2 = Z.subst(fl1,f.getVal(fl1));
188                    //if ( debug ) logger.debug("e1 = " + e1 + " e2 = " + e2);
189                    //if ( debug ) logger.debug("f1 = " + f1 + " f2 = " + f2);
190                    TableRelation<C> rel = ring.table.lookup(e2,f2); 
191                    //logger.info("relation = " + rel);
192                    Cs = rel.p; //ring.copy( rel.p ); // do not clone() 
193                    if ( rel.f != null ) {
194                        C2 = (GenSolvablePolynomial<C>)zero.sum( one, rel.f );
195                        Cs = Cs.multiply( C2 );
196                        if ( rel.e == null ) {
197                            e4 = e2;
198                        } else {
199                            e4 = e2.subtract( rel.e );
200                        }
201                        ring.table.update(e4,f2,Cs);
202                    }
203                    if ( rel.e != null ) {
204                        C1 = (GenSolvablePolynomial<C>)zero.sum( one, rel.e );
205                        Cs = C1.multiply( Cs );
206                        ring.table.update(e2,f2,Cs);
207                    }
208                    if ( !f1.isZERO() ) {
209                        C2 = (GenSolvablePolynomial<C>)zero.sum( one, f1 );
210                        Cs = Cs.multiply( C2 ); 
211                        //ring.table.update(?,f1,Cs)
212                    }
213                    if ( !e1.isZERO() ) {
214                        C1 = (GenSolvablePolynomial<C>)zero.sum( one, e1 );
215                        Cs = C1.multiply( Cs ); 
216                        //ring.table.update(e1,?,Cs)
217                    }
218                }
219                //C c = a.multiply(b);
220                Cs = Cs.multiply(a,b); // now non-symmetric // Cs.multiply(c); is symmetric!
221                //if ( debug ) logger.debug("Cs = " + Cs);
222                Cp = (GenSolvablePolynomial<C>)Cp.sum( Cs );
223            }
224        }
225        return Cp;
226    }
227
228
229    /**
230     * GenSolvablePolynomial left and right multiplication. Product with
231     * two polynomials.
232     * @param S GenSolvablePolynomial.
233     * @param T GenSolvablePolynomial.
234     * @return S*this*T.
235     */
236    public GenSolvablePolynomial<C> multiply(GenSolvablePolynomial<C> S, GenSolvablePolynomial<C> T) {
237        if ( S.isZERO() || T.isZERO() || this.isZERO() ) {
238            return ring.getZERO();
239        }
240        if ( S.isONE() ) {
241            return multiply(T);
242        }
243        if ( T.isONE() ) {
244            return S.multiply(this);
245        }
246        return S.multiply(this).multiply(T);
247    }
248
249
250    /**
251     * GenSolvablePolynomial multiplication. 
252     * Product with coefficient ring element.
253     * @param b coefficient.
254     * @return this*b, where * is usual multiplication.
255     */
256    @Override
257    public GenSolvablePolynomial<C> multiply(C b) {  
258        GenSolvablePolynomial<C> Cp = ring.getZERO().copy(); 
259        if ( b == null || b.isZERO() ) { 
260            return Cp;
261        }
262        Map<ExpVector,C> Cm = Cp.val; //getMap();
263        Map<ExpVector,C> Am = val; 
264        for ( Map.Entry<ExpVector,C> y: Am.entrySet() ) { 
265            ExpVector e = y.getKey(); 
266            C a = y.getValue(); 
267            C c = a.multiply(b);
268            if ( !c.isZERO() ) {
269                Cm.put( e, c );
270            }
271        }
272        return Cp;
273    }
274
275
276    /**
277     * GenSolvablePolynomial left and right multiplication. 
278     * Product with coefficient ring element.
279     * @param b coefficient.
280     * @param c coefficient.
281     * @return b*this*c, where * is coefficient multiplication.
282     */
283    public GenSolvablePolynomial<C> multiply(C b, C c) {  
284        GenSolvablePolynomial<C> Cp = ring.getZERO().copy(); 
285        if ( b == null || b.isZERO() ) { 
286            return Cp;
287        }
288        if ( c == null || c.isZERO() ) { 
289            return Cp;
290        }
291        Map<ExpVector,C> Cm = Cp.val; //getMap();
292        Map<ExpVector,C> Am = val; 
293        for ( Map.Entry<ExpVector,C> y: Am.entrySet() ) { 
294            ExpVector e = y.getKey(); 
295            C a = y.getValue(); 
296            C d = b.multiply(a).multiply(c);
297            if ( !d.isZERO() ) {
298                Cm.put( e, d );
299            }
300        }
301        return Cp;
302    }
303
304
305    /**
306     * GenSolvablePolynomial multiplication. 
307     * Product with exponent vector.
308     * @param e exponent.
309     * @return this * x<sup>e</sup>, 
310     * where * denotes solvable multiplication.
311     */
312    @Override
313    public GenSolvablePolynomial<C> multiply(ExpVector e) {  
314        if ( e == null || e.isZERO() ) { 
315            return this;
316        }
317        C b = ring.getONECoefficient();
318        return multiply(b, e);
319    }
320
321
322    /**
323     * GenSolvablePolynomial left and right multiplication. 
324     * Product with exponent vector.
325     * @param e exponent.
326     * @param f exponent.
327     * @return x<sup>e</sup> * this * x<sup>f</sup>, 
328     * where * denotes solvable multiplication.
329     */
330    public GenSolvablePolynomial<C> multiply(ExpVector e, ExpVector f) {  
331        if ( e == null || e.isZERO() ) { 
332            return this;
333        }
334        if ( f == null || f.isZERO() ) { 
335            return this;
336        }
337        C b = ring.getONECoefficient();
338        return multiply(b, e, b, f);
339    }
340
341
342    /**
343     * GenSolvablePolynomial multiplication. 
344     * Product with ring element and exponent vector.
345     * @param b coefficient.
346     * @param e exponent.
347     * @return this * b x<sup>e</sup>, 
348     * where * denotes solvable multiplication.
349     */
350    @Override
351    public GenSolvablePolynomial<C> multiply(C b, ExpVector e) {  
352        if ( b == null || b.isZERO() ) { 
353            return ring.getZERO();
354        }
355        GenSolvablePolynomial<C> Cp = new GenSolvablePolynomial<C>(ring,b,e);
356        return multiply(Cp);
357    }
358
359
360    /**
361     * GenSolvablePolynomial left and right multiplication. 
362     * Product with ring element and exponent vector.
363     * @param b coefficient.
364     * @param e exponent.
365     * @param c coefficient.
366     * @param f exponent.
367     * @return b x<sup>e</sup> * this * c x<sup>f</sup>, 
368     * where * denotes solvable multiplication.
369     */
370    public GenSolvablePolynomial<C> multiply(C b, ExpVector e, C c, ExpVector f) {   
371        if ( b == null || b.isZERO() ) { 
372            return ring.getZERO();
373        }
374        if ( c == null || c.isZERO() ) { 
375            return ring.getZERO();
376        }
377        GenSolvablePolynomial<C> Cp = new GenSolvablePolynomial<C>(ring,b,e);
378        GenSolvablePolynomial<C> Dp = new GenSolvablePolynomial<C>(ring,c,f);
379        return multiply(Cp,Dp);
380    }
381
382
383    /**
384     * GenSolvablePolynomial multiplication. 
385     * Left product with ring element and exponent vector.
386     * @param b coefficient.
387     * @param e exponent.
388     * @return b x<sup>e</sup> * this, 
389     * where * denotes solvable multiplication.
390     */
391    public GenSolvablePolynomial<C> multiplyLeft(C b, ExpVector e) {  
392        if ( b == null || b.isZERO() ) { 
393            return ring.getZERO();
394        }
395        GenSolvablePolynomial<C> Cp = new GenSolvablePolynomial<C>(ring,b,e);
396        return Cp.multiply(this);
397    }
398
399
400    /**
401     * GenSolvablePolynomial multiplication. 
402     * Left product with exponent vector.
403     * @param e exponent.
404     * @return x<sup>e</sup> * this, 
405     * where * denotes solvable multiplication.
406     */
407    public GenSolvablePolynomial<C> multiplyLeft(ExpVector e) {  
408        if ( e == null || e.isZERO() ) { 
409            return this;
410        }
411        C b = ring.getONECoefficient();
412        GenSolvablePolynomial<C> Cp = new GenSolvablePolynomial<C>(ring,b,e);
413        return Cp.multiply(this);
414    }
415
416
417    /**
418     * GenSolvablePolynomial multiplication. 
419     * Left product with coefficient ring element.
420     * @param b coefficient.
421     * @return b*this, where * is usual multiplication.
422     */
423    public GenSolvablePolynomial<C> multiplyLeft(C b) {  
424        GenSolvablePolynomial<C> Cp = ring.getZERO().copy(); 
425        if ( b == null || b.isZERO() ) { 
426            return Cp;
427        }
428        Map<ExpVector,C> Cm = Cp.val; //getMap();
429        Map<ExpVector,C> Am = val; 
430        for ( Map.Entry<ExpVector,C> y: Am.entrySet() ) { 
431            ExpVector e = y.getKey(); 
432            C a = y.getValue(); 
433            C c = b.multiply(a);
434            if ( !c.isZERO() ) {
435                Cm.put( e, c );
436            }
437        }
438        return Cp;
439    }
440
441
442    /**
443     * GenSolvablePolynomial multiplication. 
444     * Left product with 'monimial'.
445     * @param m 'monoial'.
446     * @return m * this, 
447     * where * denotes solvable multiplication.
448     */
449    public GenSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector,C> m) {  
450        if ( m == null ) {
451            return ring.getZERO();
452        }
453        return multiplyLeft( m.getValue(), m.getKey() );
454    }
455
456}