Source code

001/*
002 * $Id: GenSolvablePolynomialRing.java 4139 2012-08-26 10:24:29Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.io.IOException;
009import java.io.Reader;
010import java.io.StringReader;
011import java.math.BigInteger;
012import java.util.ArrayList;
013import java.util.List;
014import java.util.Random;
015
016import org.apache.log4j.Logger;
017
018import edu.jas.kern.PrettyPrint;
019import edu.jas.kern.Scripting;
020import edu.jas.structure.RingElem;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * GenSolvablePolynomialRing generic solvable polynomial factory implementing
026 * RingFactory and extending GenPolynomialRing factory; Factory for n-variate
027 * ordered solvable polynomials over C. The non-commutative multiplication
028 * relations are maintained in a relation table. Almost immutable object, except
029 * variable names and relation table contents.
030 * @param <C> coefficient type.
031 * @author Heinz Kredel
032 */
033
034public class GenSolvablePolynomialRing<C extends RingElem<C>> extends GenPolynomialRing<C> {
035
036
037    //  implements RingFactory< GenSolvablePolynomial<C> > {
038
039
040    /**
041     * The solvable multiplication relations.
042     */
043    public final RelationTable<C> table;
044
045
046    /**
047     * The constant polynomial 0 for this ring. Hides super ZERO.
048     */
049    public final GenSolvablePolynomial<C> ZERO;
050
051
052    /**
053     * The constant polynomial 1 for this ring. Hides super ONE.
054     */
055    public final GenSolvablePolynomial<C> ONE;
056
057
058    private static final Logger logger = Logger.getLogger(GenSolvablePolynomialRing.class);
059
060
061    private final boolean debug = logger.isDebugEnabled();
062
063
064    /**
065     * The constructor creates a solvable polynomial factory object with the
066     * default term order and commutative relations.
067     * @param cf factory for coefficients of type C.
068     * @param n number of variables.
069     */
070    public GenSolvablePolynomialRing(RingFactory<C> cf, int n) {
071        this(cf, n, new TermOrder(), null, null);
072    }
073
074
075    /**
076     * The constructor creates a solvable polynomial factory object with the
077     * default term order.
078     * @param cf factory for coefficients of type C.
079     * @param n number of variables.
080     * @param rt solvable multiplication relations.
081     */
082    public GenSolvablePolynomialRing(RingFactory<C> cf, int n, RelationTable<C> rt) {
083        this(cf, n, new TermOrder(), null, rt);
084    }
085
086
087    /**
088     * The constructor creates a solvable polynomial factory object with the
089     * given term order and commutative relations.
090     * @param cf factory for coefficients of type C.
091     * @param n number of variables.
092     * @param t a term order.
093     */
094    public GenSolvablePolynomialRing(RingFactory<C> cf, int n, TermOrder t) {
095        this(cf, n, t, null, null);
096    }
097
098
099    /**
100     * The constructor creates a solvable polynomial factory object with the
101     * given term order.
102     * @param cf factory for coefficients of type C.
103     * @param n number of variables.
104     * @param t a term order.
105     * @param rt solvable multiplication relations.
106     */
107    public GenSolvablePolynomialRing(RingFactory<C> cf, int n, TermOrder t, RelationTable<C> rt) {
108        this(cf, n, t, null, rt);
109    }
110
111
112    /**
113     * The constructor creates a solvable polynomial factory object with the
114     * given term order and commutative relations.
115     * @param cf factory for coefficients of type C.
116     * @param n number of variables.
117     * @param t a term order.
118     * @param v names for the variables.
119     */
120    public GenSolvablePolynomialRing(RingFactory<C> cf, int n, TermOrder t, String[] v) {
121        this(cf, n, t, v, null);
122    }
123
124
125    /**
126     * The constructor creates a solvable polynomial factory object with the
127     * default term order.
128     * @param cf factory for coefficients of type C.
129     * @param v names for the variables.
130     */
131    public GenSolvablePolynomialRing(RingFactory<C> cf, String[] v) {
132        this(cf, v.length, new TermOrder(), v, null);
133    }
134
135
136    /**
137     * The constructor creates a solvable polynomial factory object with the
138     * given term order.
139     * @param cf factory for coefficients of type C.
140     * @param n number of variables.
141     * @param t a term order.
142     * @param v names for the variables.
143     * @param rt solvable multiplication relations.
144     */
145    public GenSolvablePolynomialRing(RingFactory<C> cf, int n, TermOrder t, String[] v, RelationTable<C> rt) {
146        super(cf, n, t, v);
147        if (rt == null) {
148            table = new RelationTable<C>(this);
149        } else {
150            table = rt;
151        }
152        ZERO = new GenSolvablePolynomial<C>(this);
153        C coeff = coFac.getONE();
154        //evzero = ExpVector.create(nvar); // from super
155        ONE = new GenSolvablePolynomial<C>(this, coeff, evzero);
156    }
157
158
159    /**
160     * The constructor creates a solvable polynomial factory object with the the
161     * same term order, number of variables and variable names as the given
162     * polynomial factory, only the coefficient factories differ and the
163     * solvable multiplication relations are <b>empty</b>.
164     * @param cf factory for coefficients of type C.
165     * @param o other solvable polynomial ring.
166     */
167    public GenSolvablePolynomialRing(RingFactory<C> cf, GenSolvablePolynomialRing o) {
168        this(cf, o.nvar, o.tord, o.getVars(), null);
169    }
170
171
172    /**
173     * Get the String representation.
174     * @see java.lang.Object#toString()
175     */
176    @Override
177    public String toString() {
178        String res = super.toString();
179        if (PrettyPrint.isTrue()) {
180            res += "\n" + table.toString(vars);
181        } else {
182            res += ", #rel = " + table.size();
183        }
184        return res;
185    }
186
187
188    /**
189     * Get a scripting compatible string representation.
190     * @return script compatible representation for this Element.
191     * @see edu.jas.structure.Element#toScript()
192     */
193    @Override
194    public String toScript() {
195        StringBuffer s = new StringBuffer();
196        switch (Scripting.getLang()) {
197        case Ruby:
198            s.append("SolvPolyRing.new(");
199            break;
200        case Python:
201        default:
202            s.append("SolvPolyRing(");
203        }
204        if (coFac instanceof RingElem) {
205            s.append(((RingElem<C>) coFac).toScriptFactory());
206        } else {
207            s.append(coFac.toScript().trim());
208        }
209        s.append(",\"" + varsToString() + "\",");
210        String to = tord.toString();
211        if (tord.getEvord() == TermOrder.INVLEX) {
212            to = "PolyRing.lex";
213        }
214        if (tord.getEvord() == TermOrder.IGRLEX) {
215            to = "PolyRing.grad";
216        }
217        s.append(to);
218        if (table.size() > 0) {
219            String rel = table.toScript();
220            s.append(",rel=");
221            s.append(rel);
222        }
223        s.append(")");
224        return s.toString();
225    }
226
227
228    /**
229     * Comparison with any other object.
230     * @see java.lang.Object#equals(java.lang.Object)
231     */
232    @Override
233    @SuppressWarnings("unchecked")
234    public boolean equals(Object other) {
235        if (!(other instanceof GenSolvablePolynomialRing)) {
236            return false;
237        }
238        // do a super.equals( )
239        if (!super.equals(other)) {
240            return false;
241        }
242        GenSolvablePolynomialRing<C> oring = null;
243        try {
244            oring = (GenSolvablePolynomialRing<C>) other;
245        } catch (ClassCastException ignored) {
246        }
247        if (oring == null) {
248            return false;
249        }
250        // @todo check same base relations
251        //if ( ! table.equals(oring.table) ) {
252        //    return false;
253        //}
254        return true;
255    }
256
257
258    /**
259     * Hash code for this polynomial ring.
260     * @see java.lang.Object#hashCode()
261     */
262    @Override
263    public int hashCode() {
264        int h;
265        h = super.hashCode();
266        h = 37 * h + table.hashCode();
267        return h;
268    }
269
270
271    /**
272     * Get the zero element.
273     * @return 0 as GenSolvablePolynomial<C>.
274     */
275    @Override
276    public GenSolvablePolynomial<C> getZERO() {
277        return ZERO;
278    }
279
280
281    /**
282     * Get the one element.
283     * @return 1 as GenSolvablePolynomial<C>.
284     */
285    @Override
286    public GenSolvablePolynomial<C> getONE() {
287        return ONE;
288    }
289
290
291    /**
292     * Query if this ring is commutative.
293     * @return true if this ring is commutative, else false.
294     */
295    @Override
296    public boolean isCommutative() {
297        if (table.size() == 0) {
298            return super.isCommutative();
299        }
300        // todo: check structure of relations
301        return false;
302    }
303
304
305    /**
306     * Query if this ring is associative. Test if the relations define an
307     * associative solvable ring.
308     * @return true, if this ring is associative, else false.
309     */
310    @Override
311    public boolean isAssociative() {
312        GenSolvablePolynomial<C> Xi;
313        GenSolvablePolynomial<C> Xj;
314        GenSolvablePolynomial<C> Xk;
315        GenSolvablePolynomial<C> p;
316        GenSolvablePolynomial<C> q;
317        for (int i = 0; i < nvar; i++) {
318            Xi = univariate(i);
319            for (int j = i + 1; j < nvar; j++) {
320                Xj = univariate(j);
321                for (int k = j + 1; k < nvar; k++) {
322                    Xk = univariate(k);
323                    p = Xk.multiply(Xj).multiply(Xi);
324                    q = Xk.multiply(Xj.multiply(Xi));
325                    if (!p.equals(q)) {
326                        if (debug) {
327                            logger.info("Xi = " + Xi + ", Xj = " + Xj + ", Xk = " + Xk);
328                            logger.info("p = ( Xk * Xj ) * Xi = " + p);
329                            logger.info("q = Xk * ( Xj * Xi ) = " + q);
330                        }
331                        return false;
332                    }
333                }
334            }
335        }
336        return true;
337    }
338
339
340    /**
341     * Get a (constant) GenSolvablePolynomial&lt;C&gt; element from a long
342     * value.
343     * @param a long.
344     * @return a GenSolvablePolynomial&lt;C&gt;.
345     */
346    @Override
347    public GenSolvablePolynomial<C> fromInteger(long a) {
348        return new GenSolvablePolynomial<C>(this, coFac.fromInteger(a), evzero);
349    }
350
351
352    /**
353     * Get a (constant) GenSolvablePolynomial&lt;C&gt; element from a BigInteger
354     * value.
355     * @param a BigInteger.
356     * @return a GenSolvablePolynomial&lt;C&gt;.
357     */
358    @Override
359    public GenSolvablePolynomial<C> fromInteger(BigInteger a) {
360        return new GenSolvablePolynomial<C>(this, coFac.fromInteger(a), evzero);
361    }
362
363
364    /**
365     * Random solvable polynomial. Generates a random solvable polynomial with k
366     * = 5, l = n, d = (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3.
367     * @param n number of terms.
368     * @return a random solvable polynomial.
369     */
370    @Override
371    public GenSolvablePolynomial<C> random(int n) {
372        return random(n, random);
373    }
374
375
376    /**
377     * Random solvable polynomial. Generates a random solvable polynomial with k
378     * = 5, l = n, d = (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3.
379     * @param n number of terms.
380     * @param rnd is a source for random bits.
381     * @return a random solvable polynomial.
382     */
383    @Override
384    public GenSolvablePolynomial<C> random(int n, Random rnd) {
385        if (nvar == 1) {
386            return random(5, n, n, 0.7f, rnd);
387        }
388        return random(5, n, 3, 0.3f, rnd);
389    }
390
391
392    /**
393     * Generate a random solvable polynomial.
394     * @param k bitsize of random coefficients.
395     * @param l number of terms.
396     * @param d maximal degree in each variable.
397     * @param q density of nozero exponents.
398     * @return a random solvable polynomial.
399     */
400    @Override
401    public GenSolvablePolynomial<C> random(int k, int l, int d, float q) {
402        return random(k, l, d, q, random);
403    }
404
405
406    /**
407     * Random solvable polynomial.
408     * @param k size of random coefficients.
409     * @param l number of terms.
410     * @param d maximal degree in each variable.
411     * @param q density of nozero exponents.
412     * @param rnd is a source for random bits.
413     * @return a random solvable polynomial.
414     */
415    @Override
416    public GenSolvablePolynomial<C> random(int k, int l, int d, float q, Random rnd) {
417        GenSolvablePolynomial<C> r = getZERO(); //.clone();
418        // copy( ZERO ); 
419        // new GenPolynomial<C>( this, getZERO().val );
420        ExpVector e;
421        C a;
422        // add random coeffs and exponents
423        for (int i = 0; i < l; i++) {
424            e = ExpVector.EVRAND(nvar, d, q, rnd);
425            a = coFac.random(k, rnd);
426            r = (GenSolvablePolynomial<C>) r.sum(a, e);
427            // somewhat inefficient but clean
428        }
429        return r;
430    }
431
432
433    /**
434     * Copy polynomial c.
435     * @param c
436     * @return a copy of c.
437     */
438    public GenSolvablePolynomial<C> copy(GenSolvablePolynomial<C> c) {
439        return new GenSolvablePolynomial<C>(this, c.val);
440    }
441
442
443    /**
444     * Parse a solvable polynomial with the use of GenPolynomialTokenizer
445     * @param s String.
446     * @return GenSolvablePolynomial from s.
447     */
448    @Override
449    public GenSolvablePolynomial<C> parse(String s) {
450        //return getZERO();
451        return parse(new StringReader(s));
452    }
453
454
455    /**
456     * Parse a solvable polynomial with the use of GenPolynomialTokenizer
457     * @param r Reader.
458     * @return next GenSolvablePolynomial from r.
459     */
460    @Override
461    @SuppressWarnings("unchecked")
462    public GenSolvablePolynomial<C> parse(Reader r) {
463        GenPolynomialTokenizer pt = new GenPolynomialTokenizer(this, r);
464        GenSolvablePolynomial<C> p = null;
465        try {
466            p = (GenSolvablePolynomial<C>) pt.nextSolvablePolynomial();
467        } catch (IOException e) {
468            logger.error(e.toString() + " parse " + this);
469            p = ZERO;
470        }
471        return p;
472    }
473
474
475    /**
476     * Generate univariate solvable polynomial in a given variable.
477     * @param i the index of the variable.
478     * @return X_i as solvable univariate polynomial.
479     */
480    @Override
481    public GenSolvablePolynomial<C> univariate(int i) {
482        return (GenSolvablePolynomial<C>) super.univariate(i);
483    }
484
485
486    /**
487     * Generate univariate solvable polynomial in a given variable with given
488     * exponent.
489     * @param i the index of the variable.
490     * @param e the exponent of the variable.
491     * @return X_i^e as solvable univariate polynomial.
492     */
493    @Override
494    public GenSolvablePolynomial<C> univariate(int i, long e) {
495        return (GenSolvablePolynomial<C>) super.univariate(i, e);
496    }
497
498
499    /**
500     * Generate univariate solvable polynomial in a given variable with given
501     * exponent.
502     * @param modv number of module variables.
503     * @param i the index of the variable.
504     * @param e the exponent of the variable.
505     * @return X_i^e as solvable univariate polynomial.
506     */
507    @Override
508    public GenSolvablePolynomial<C> univariate(int modv, int i, long e) {
509        return (GenSolvablePolynomial<C>) super.univariate(modv, i, e);
510    }
511
512
513    /**
514     * Generate list of univariate polynomials in all variables.
515     * @return List(X_1,...,X_n) a list of univariate polynomials.
516     */
517    @Override
518    public List<GenSolvablePolynomial<C>> univariateList() {
519        //return castToSolvableList( super.univariateList() );
520        return univariateList(0, 1L);
521    }
522
523
524    /**
525     * Generate list of univariate polynomials in all variables.
526     * @param modv number of module variables.
527     * @return List(X_1,...,X_n) a list of univariate polynomials.
528     */
529    @Override
530    public List<GenSolvablePolynomial<C>> univariateList(int modv) {
531        return univariateList(modv, 1L);
532    }
533
534
535    /**
536     * Generate list of univariate polynomials in all variables with given
537     * exponent.
538     * @param modv number of module variables.
539     * @param e the exponent of the variables.
540     * @return List(X_1^e,...,X_n^e) a list of univariate polynomials.
541     */
542    @Override
543    public List<GenSolvablePolynomial<C>> univariateList(int modv, long e) {
544        List<GenSolvablePolynomial<C>> pols = new ArrayList<GenSolvablePolynomial<C>>(nvar);
545        int nm = nvar - modv;
546        for (int i = 0; i < nm; i++) {
547            GenSolvablePolynomial<C> p = univariate(modv, nm - 1 - i, e);
548            pols.add(p);
549        }
550        return pols;
551    }
552
553
554    /*
555     * Generate list of univariate polynomials in all variables with given exponent.
556     * @param modv number of module variables.
557     * @param e the exponent of the variables.
558     * @return List(X_1^e,...,X_n^e) a list of univariate polynomials.
559     @Override
560     public List<GenSolvablePolynomial<C>> univariateList(int modv, long e) {
561     List<GenPolynomial<C>> pol = super.univariateList(modv,e);
562     UnaryFunctor<GenPolynomial<C>,GenSolvablePolynomial<C>> fc 
563     = new UnaryFunctor<GenPolynomial<C>,GenSolvablePolynomial<C>>() {
564     public GenSolvablePolynomial<C> eval(GenPolynomial<C> p) {
565     if ( ! (p instanceof GenSolvablePolynomial) ) {
566     throw new RuntimeException("no solvable polynomial "+p);
567     }
568     return (GenSolvablePolynomial<C>) p;
569     }
570     };
571     List<GenSolvablePolynomial<C>> pols 
572     = ListUtil.<GenPolynomial<C>,GenSolvablePolynomial<C>>map(this,pol,fc);
573     return pols;
574     }
575    */
576
577
578    /* include here ?
579     * Get list as List of GenSolvablePolynomials.
580     * Required because no List casts allowed. Equivalent to 
581     * cast (List&lt;GenSolvablePolynomial&lt;C&gt;&gt;) list.
582     * @return solvable polynomial list from this.
583     public List<GenSolvablePolynomial<C>> castToSolvableList(List<GenPolynomial<C>> list) {
584     List< GenSolvablePolynomial<C> > slist = null;
585     if ( list == null ) {
586     return slist;
587     }
588     slist = new ArrayList< GenSolvablePolynomial<C> >( list.size() ); 
589     GenSolvablePolynomial<C> s;
590     for ( GenPolynomial<C> p: list ) {
591     if ( ! (p instanceof GenSolvablePolynomial) ) {
592     throw new RuntimeException("no solvable polynomial "+p);
593     }
594     s = (GenSolvablePolynomial<C>) p;
595     slist.add( s );
596     }
597     return slist;
598     }
599    */
600
601
602    /**
603     * Extend variables. Used e.g. in module embedding. Extend number of
604     * variables by i.
605     * @param i number of variables to extend.
606     * @return extended solvable polynomial ring factory.
607     */
608    @Override
609    public GenSolvablePolynomialRing<C> extend(int i) {
610        GenPolynomialRing<C> pfac = super.extend(i);
611        GenSolvablePolynomialRing<C> spfac = new GenSolvablePolynomialRing<C>(pfac.coFac, pfac.nvar,
612                        pfac.tord, pfac.vars);
613        spfac.table.extend(this.table);
614        return spfac;
615    }
616
617
618    /**
619     * Contract variables. Used e.g. in module embedding. Contract number of
620     * variables by i.
621     * @param i number of variables to remove.
622     * @return contracted solvable polynomial ring factory.
623     */
624    @Override
625    public GenSolvablePolynomialRing<C> contract(int i) {
626        GenPolynomialRing<C> pfac = super.contract(i);
627        GenSolvablePolynomialRing<C> spfac = new GenSolvablePolynomialRing<C>(pfac.coFac, pfac.nvar,
628                        pfac.tord, pfac.vars);
629        spfac.table.contract(this.table);
630        return spfac;
631    }
632
633
634    /**
635     * Reverse variables. Used e.g. in opposite rings.
636     * @return solvable polynomial ring factory with reversed variables.
637     */
638    @Override
639    public GenSolvablePolynomialRing<C> reverse() {
640        return reverse(false);
641    }
642
643
644    /**
645     * Reverse variables. Used e.g. in opposite rings.
646     * @param partial true for partialy reversed term orders.
647     * @return solvable polynomial ring factory with reversed variables.
648     */
649    @Override
650    public GenSolvablePolynomialRing<C> reverse(boolean partial) {
651        GenPolynomialRing<C> pfac = super.reverse(partial);
652        GenSolvablePolynomialRing<C> spfac = new GenSolvablePolynomialRing<C>(pfac.coFac, pfac.nvar,
653                        pfac.tord, pfac.vars);
654        spfac.partial = partial;
655        spfac.table.reverse(this.table);
656        return spfac;
657    }
658
659}