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