001 /*
002 * $Id: Examples.java 1976 2008-08-03 09:56:01Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import java.util.ArrayList;
008 //import java.util.Arrays;
009 import java.util.List;
010
011 import edu.jas.arith.BigRational;
012 import edu.jas.arith.BigInteger;
013 import edu.jas.arith.ModInteger;
014 import edu.jas.arith.ModIntegerRing;
015
016 /**
017 * Examples for polynomials usage.
018 * @author Heinz Kredel.
019 */
020
021 public class Examples {
022
023 /**
024 * main.
025 */
026 public static void main (String[] args) {
027 //example0();
028 /*
029 example1();
030 example2();
031 example3();
032 example4();
033 example5();
034 */
035 //example6();
036 example7();
037 example7();
038 //example8();
039 //example9();
040 //example10();
041 //example11();
042 //example12();
043 }
044
045
046 /**
047 * example0.
048 * for PPPJ 2006.
049 */
050 public static void example0() {
051 BigInteger z = new BigInteger();
052
053 TermOrder to = new TermOrder();
054 String[] vars = new String[] { "x1", "x2", "x3" };
055 GenPolynomialRing<BigInteger> ring;
056 ring = new GenPolynomialRing<BigInteger>(z,3,to,vars);
057 System.out.println("ring = " + ring);
058
059 GenPolynomial<BigInteger> pol;
060 pol = ring.parse( "3 x1^2 x3^4 + 7 x2^5 - 61" );
061 System.out.println("pol = " + pol);
062 System.out.println("pol = " + pol.toString(ring.getVars()));
063
064 GenPolynomial<BigInteger> one;
065 one = ring.parse( "1" );
066 System.out.println("one = " + one);
067 System.out.println("one = " + one.toString(ring.getVars()));
068
069 GenPolynomial<BigInteger> p;
070 p = pol.subtract(pol);
071 System.out.println("p = " + p);
072 System.out.println("p = " + p.toString(ring.getVars()));
073
074 p = pol.multiply(pol);
075 System.out.println("p = " + p);
076 System.out.println("p = " + p.toString(ring.getVars()));
077 }
078
079
080 /**
081 * example1.
082 * random polynomial with rational coefficients.
083 * Q[x_1,...x_7]
084 */
085 public static void example1() {
086 System.out.println("\n\n example 1");
087
088 BigRational cfac = new BigRational();
089 System.out.println("cfac = " + cfac);
090 GenPolynomialRing<BigRational> fac;
091 fac = new GenPolynomialRing<BigRational>(cfac,7);
092 //System.out.println("fac = " + fac);
093 System.out.println("fac = " + fac);
094
095 GenPolynomial<BigRational> a = fac.random(10);
096 System.out.println("a = " + a);
097 }
098
099
100 /**
101 * example2.
102 * random polynomial with coefficients of rational polynomials.
103 * Q[x_1,...x_7][y_1,...,y_3]
104 */
105 public static void example2() {
106 System.out.println("\n\n example 2");
107
108 BigRational cfac = new BigRational();
109 System.out.println("cfac = " + cfac);
110 GenPolynomialRing<BigRational> fac;
111 fac = new GenPolynomialRing<BigRational>(cfac,7);
112 System.out.println("fac = " + fac);
113
114 GenPolynomialRing<GenPolynomial<BigRational>> gfac;
115 gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac,3);
116 System.out.println("gfac = " + gfac);
117
118 GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10);
119 System.out.println("a = " + a);
120 }
121
122
123 /**
124 * example3.
125 * random rational algebraic number.
126 * Q(alpha)
127 */
128 public static void example3() {
129 System.out.println("\n\n example 3");
130
131 BigRational cfac = new BigRational();
132 System.out.println("cfac = " + cfac);
133
134 GenPolynomialRing<BigRational> mfac;
135 mfac = new GenPolynomialRing<BigRational>( cfac, 1 );
136 System.out.println("mfac = " + mfac);
137
138 GenPolynomial<BigRational> modul = mfac.random(8).monic();
139 // assume !mo.isUnit()
140 System.out.println("modul = " + modul);
141
142 AlgebraicNumberRing<BigRational> fac;
143 fac = new AlgebraicNumberRing<BigRational>( modul );
144 System.out.println("fac = " + fac);
145
146 AlgebraicNumber< BigRational > a = fac.random(15);
147 System.out.println("a = " + a);
148 }
149
150 protected static long getPrime() {
151 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
152 for ( int i = 1; i < 60; i++ ) {
153 prime *= 2;
154 }
155 prime -= 93;
156 //System.out.println("prime = " + prime);
157 return prime;
158 }
159
160
161 /**
162 * example4.
163 * random modular algebraic number.
164 * Z_p(alpha)
165 */
166 public static void example4() {
167 System.out.println("\n\n example 4");
168
169 long prime = getPrime();
170 ModIntegerRing cfac = new ModIntegerRing(prime);
171 System.out.println("cfac = " + cfac);
172
173 GenPolynomialRing<ModInteger> mfac;
174 mfac = new GenPolynomialRing<ModInteger>( cfac, 1 );
175 System.out.println("mfac = " + mfac);
176
177 GenPolynomial<ModInteger> modul = mfac.random(8).monic();
178 // assume !modul.isUnit()
179 System.out.println("modul = " + modul);
180
181 AlgebraicNumberRing<ModInteger> fac;
182 fac = new AlgebraicNumberRing<ModInteger>( modul );
183 System.out.println("fac = " + fac);
184
185 AlgebraicNumber< ModInteger > a = fac.random(12);
186 System.out.println("a = " + a);
187 }
188
189
190 /**
191 * example5.
192 * random solvable polynomial with rational coefficients.
193 * Q{x_1,...x_6, {x_2 * x_1 = x_1 x_2 +1, ...} }
194 */
195 public static void example5() {
196 System.out.println("\n\n example 5");
197
198 BigRational cfac = new BigRational();
199 System.out.println("cfac = " + cfac);
200 GenSolvablePolynomialRing<BigRational> sfac;
201 sfac = new GenSolvablePolynomialRing<BigRational>(cfac,6);
202 //System.out.println("sfac = " + sfac);
203
204 WeylRelations<BigRational> wl = new WeylRelations<BigRational>(sfac);
205 wl.generate();
206 System.out.println("sfac = " + sfac);
207
208 GenSolvablePolynomial<BigRational> a = sfac.random(5);
209 System.out.println("a = " + a);
210 System.out.println("a = " + a.toString( sfac.vars ) );
211
212 GenSolvablePolynomial<BigRational> b = a.multiply(a);
213 System.out.println("b = " + b);
214 System.out.println("b = " + b.toString( sfac.vars ) );
215
216 System.out.println("sfac = " + sfac);
217 }
218
219
220 /**
221 * example6.
222 * Fateman benchmark: p = (x+y+z)^20; q = p * (p+1)
223 * Z[z,y,x]
224 */
225 public static void example6() {
226 System.out.println("\n\n example 6");
227
228 BigInteger cfac = new BigInteger();
229 System.out.println("cfac = " + cfac);
230
231 TermOrder to = new TermOrder( TermOrder.INVLEX );
232 System.out.println("to = " + to);
233
234 GenPolynomialRing<BigInteger> fac;
235 fac = new GenPolynomialRing<BigInteger>(cfac,3,to);
236 System.out.println("fac = " + fac);
237 fac.setVars( new String[]{ "z", "y", "x" } );
238 System.out.println("fac = " + fac);
239
240 GenPolynomial<BigInteger> x = fac.univariate(0);
241 GenPolynomial<BigInteger> y = fac.univariate(1);
242 GenPolynomial<BigInteger> z = fac.univariate(2);
243
244 System.out.println("x = " + x);
245 System.out.println("x = " + x.toString( fac.vars ) );
246 System.out.println("y = " + y);
247 System.out.println("y = " + y.toString( fac.vars ) );
248 System.out.println("z = " + z);
249 System.out.println("z = " + z.toString( fac.vars ) );
250
251 GenPolynomial<BigInteger> p = x.sum(y).sum(z).sum( fac.getONE());
252 BigInteger f = cfac.fromInteger(10000000001L);
253 // p = p.multiply( f );
254 System.out.println("p = " + p);
255 System.out.println("p = " + p.toString( fac.vars ) );
256
257 GenPolynomial<BigInteger> q = p;
258 for ( int i = 1; i < 20; i++ ) {
259 q = q.multiply(p);
260 }
261 //System.out.println("q = " + q.toString( fac.vars ) );
262 System.out.println("q = " + q.length());
263
264 GenPolynomial<BigInteger> q1 = q.sum( fac.getONE() );
265
266 GenPolynomial<BigInteger> q2;
267 long t = System.currentTimeMillis();
268 q2 = q.multiply(q1);
269 t = System.currentTimeMillis() - t;
270
271 System.out.println("q2 = " + q2.length());
272 System.out.println("time = " + t + " ms");
273 }
274
275
276 /**
277 * example7.
278 * Fateman benchmark: p = (x+y+z)^20; q = p * (p+1)
279 * Q[z,y,x]
280 */
281 public static void example7() {
282 System.out.println("\n\n example 7");
283
284 BigRational cfac = new BigRational();
285 System.out.println("cfac = " + cfac);
286
287 TermOrder to = new TermOrder( TermOrder.INVLEX );
288 System.out.println("to = " + to);
289
290 GenPolynomialRing<BigRational> fac;
291 fac = new GenPolynomialRing<BigRational>(cfac,3,to);
292 System.out.println("fac = " + fac);
293 fac.setVars( new String[]{ "z", "y", "x" } );
294 System.out.println("fac = " + fac);
295
296 long mi = 1L;
297 //long mi = Integer.MAX_VALUE;
298 GenPolynomial<BigRational> x = fac.univariate(0,mi);
299 GenPolynomial<BigRational> y = fac.univariate(1,mi);
300 GenPolynomial<BigRational> z = fac.univariate(2,mi);
301
302 // System.out.println("x = " + x);
303 System.out.println("x = " + x.toString( fac.vars ) );
304 // System.out.println("y = " + y);
305 System.out.println("y = " + y.toString( fac.vars ) );
306 // System.out.println("z = " + z);
307 System.out.println("z = " + z.toString( fac.vars ) );
308
309 GenPolynomial<BigRational> p = x.sum(y).sum(z).sum( fac.getONE());
310 BigRational f = cfac.fromInteger(10000000001L);
311 //f = f.multiply( f );
312 //p = p.multiply( f );
313 // System.out.println("p = " + p);
314 System.out.println("p = " + p.toString( fac.vars ) );
315
316 int mpow = 20;
317 System.out.println("mpow = " + mpow);
318 GenPolynomial<BigRational> q = p;
319 for ( int i = 1; i < mpow; i++ ) {
320 q = q.multiply(p);
321 }
322 //System.out.println("q = " + q.toString( fac.vars ) );
323 System.out.println("len(q) = " + q.length());
324 System.out.println("deg(q) = " + q.degree());
325
326 GenPolynomial<BigRational> q1 = q.sum( fac.getONE() );
327
328 GenPolynomial<BigRational> q2;
329 long t = System.currentTimeMillis();
330 q2 = q.multiply(q1);
331 t = System.currentTimeMillis() - t;
332
333 System.out.println("len(q2) = " + q2.length());
334 System.out.println("deg(q2) = " + q2.degree());
335 System.out.println("LeadEV(q2) = " + q2.leadingExpVector());
336 System.out.println("time = " + t + " ms");
337 }
338
339
340 /**
341 * example8.
342 * Chebyshev polynomials
343 *
344 * T(0) = 1
345 * T(1) = x
346 * T(n) = 2x * T(n-1) - T(n-2)
347 */
348 public static void example8() {
349 int m = 10;
350 BigInteger fac = new BigInteger();
351 String[] var = new String[]{ "x" };
352
353 GenPolynomialRing<BigInteger> ring
354 = new GenPolynomialRing<BigInteger>(fac,1,var);
355
356 List<GenPolynomial<BigInteger>> T
357 = new ArrayList<GenPolynomial<BigInteger>>(m);
358
359 GenPolynomial<BigInteger> t, one, x, x2, x2a, x2b;
360
361 one = ring.getONE();
362 x = ring.univariate(0);
363 x2 = ring.parse("2 x");
364 x2a = x.multiply( fac.fromInteger(2) );
365 x2b = x.multiply( new BigInteger(2) );
366 x2 = x2b;
367
368 T.add( one );
369 T.add( x );
370 for ( int n = 2; n < m; n++ ) {
371 t = x2.multiply( T.get(n-1) ).subtract( T.get(n-2) );
372 T.add( t );
373 }
374 for ( int n = 0 /*m-2*/; n < m; n++ ) {
375 System.out.println("T["+n+"] = " + T.get(n) ); //.toString(var) );
376 }
377 }
378
379
380 /**
381 * example9.
382 * Legendre polynomials
383 *
384 * P(0) = 1
385 * P(1) = x
386 * P(n) = 1/n [ (2n-1) * x * P(n-1) - (n-1) * P(n-2) ]
387 */
388 // P(n+1) = 1/(n+1) [ (2n+1) * x * P(n) - n * P(n-1) ]
389 public static void example9() {
390 int n = 10;
391
392 BigRational fac = new BigRational();
393 String[] var = new String[]{ "x" };
394
395 GenPolynomialRing<BigRational> ring
396 = new GenPolynomialRing<BigRational>(fac,1,var);
397
398 List<GenPolynomial<BigRational>> P
399 = new ArrayList<GenPolynomial<BigRational>>(n);
400
401 GenPolynomial<BigRational> t, one, x, xc, xn;
402 BigRational n21, nn;
403
404 one = ring.getONE();
405 x = ring.univariate(0);
406
407 P.add( one );
408 P.add( x );
409 for ( int i = 2; i < n; i++ ) {
410 n21 = new BigRational( 2*i-1 );
411 xc = x.multiply( n21 );
412 t = xc.multiply( P.get(i-1) );
413 nn = new BigRational( i-1 );
414 xc = P.get(i-2).multiply( nn );
415 t = t.subtract( xc );
416 nn = new BigRational(1,i);
417 t = t.multiply( nn );
418 P.add( t );
419 }
420 for ( int i = 0; i < n; i++ ) {
421 System.out.println("P["+i+"] = " + P.get(i).toString(var) );
422 System.out.println();
423 }
424 }
425
426
427 /**
428 * example10.
429 * Hermite polynomials
430 *
431 * H(0) = 1
432 * H(1) = 2 x
433 * H(n) = 2 * x * H(n-1) - 2 * (n-1) * H(n-2)
434 */
435 // H(n+1) = 2 * x * H(n) - 2 * n * H(n-1)
436 public static void example10() {
437 int n = 100;
438
439 BigInteger fac = new BigInteger();
440 String[] var = new String[]{ "x" };
441
442 GenPolynomialRing<BigInteger> ring
443 = new GenPolynomialRing<BigInteger>(fac,1,var);
444
445 List<GenPolynomial<BigInteger>> H
446 = new ArrayList<GenPolynomial<BigInteger>>(n);
447
448 GenPolynomial<BigInteger> t, one, x2, xc, x;
449 BigInteger n2, nn;
450
451 one = ring.getONE();
452 x = ring.univariate(0);
453 n2 = new BigInteger(2);
454 x2 = x.multiply( n2 );
455 H.add( one );
456 H.add( x2 );
457 for ( int i = 2; i < n; i++ ) {
458 t = x2.multiply( H.get(i-1) );
459 nn = new BigInteger( 2*(i-1) );
460 xc = H.get(i-2).multiply( nn );
461 t = t.subtract( xc );
462 H.add( t );
463 }
464 for ( int i = n-1; i < n; i++ ) {
465 System.out.println("H["+i+"] = " + H.get(i).toString(var) );
466 System.out.println();
467 }
468 }
469
470
471 /**
472 * example11.
473 * degree matrix;
474 *
475 */
476 public static void example11() {
477 int n = 50;
478 BigRational fac = new BigRational();
479 GenPolynomialRing<BigRational> ring
480 = new GenPolynomialRing<BigRational>(fac,n);
481 System.out.println("ring = " + ring + "\n");
482
483 GenPolynomial<BigRational> p = ring.random(5,3,6,0.5f);
484 System.out.println("p = " + p + "\n");
485
486 List<GenPolynomial<BigInteger>> dem
487 = TermOrderOptimization.<BigRational>degreeMatrix( p );
488
489 System.out.println("dem = " + dem + "\n");
490
491 List<GenPolynomial<BigRational>> polys
492 = new ArrayList<GenPolynomial<BigRational>>();
493 polys.add( p );
494 for ( int i = 0; i < 5; i++ ) {
495 polys.add( ring.random(5,3,6,0.1f) );
496 }
497 System.out.println("polys = " + polys + "\n");
498
499 dem = TermOrderOptimization.<BigRational>degreeMatrix( polys );
500 System.out.println("dem = " + dem + "\n");
501
502 List<Integer> perm;
503 perm = TermOrderOptimization.optimalPermutation( dem );
504 System.out.println("perm = " + perm + "\n");
505
506 List<GenPolynomial<BigInteger>> pdem;
507 pdem = TermOrderOptimization.<GenPolynomial<BigInteger>>listPermutation( perm, dem );
508 System.out.println("pdem = " + pdem + "\n");
509
510 GenPolynomialRing<BigRational> pring;
511 pring = TermOrderOptimization.<BigRational>permutation( perm, ring );
512 System.out.println("ring = " + ring);
513 System.out.println("pring = " + pring + "\n");
514
515 List<GenPolynomial<BigRational>> ppolys;
516 ppolys = TermOrderOptimization.<BigRational>permutation( perm, pring, polys );
517 System.out.println("ppolys = " + ppolys + "\n");
518
519 dem = TermOrderOptimization.<BigRational>degreeMatrix( ppolys );
520 //System.out.println("pdem = " + dem + "\n");
521
522 perm = TermOrderOptimization.optimalPermutation( dem );
523 //System.out.println("pperm = " + perm + "\n");
524 int i = 0;
525 for ( Integer j : perm ) {
526 if ( i != (int)j ) {
527 System.out.println("error = " + i + " != " + j + "\n");
528 }
529 i++;
530 }
531
532 OptimizedPolynomialList<BigRational> op;
533 op = TermOrderOptimization.<BigRational>optimizeTermOrder( ring, polys );
534 System.out.println("op:\n" + op);
535 if ( ! op.equals( new PolynomialList<BigRational>(pring,ppolys) ) ) {
536 System.out.println("error = " + "\n" + op);
537 }
538 }
539
540
541 /**
542 * example12.
543 * type games.
544 */
545 public static void example12() {
546 System.out.println("\n\n example 12");
547
548 BigRational t1 = new BigRational();
549 System.out.println("t1 = " + t1);
550
551 BigInteger t2 = new BigInteger();
552 System.out.println("t2 = " + t2);
553
554 System.out.println("t1.isAssignableFrom(t2) = "
555 + t1.getClass().isAssignableFrom(t2.getClass()));
556 System.out.println("t2.isAssignableFrom(t1) = "
557 + t2.getClass().isAssignableFrom(t1.getClass()));
558
559 GenPolynomialRing<BigInteger> t3
560 = new GenPolynomialRing<BigInteger>(t2,3);
561 System.out.println("t3 = " + t3);
562
563 GenSolvablePolynomialRing<BigInteger> t4
564 = new GenSolvablePolynomialRing<BigInteger>(t2,3);
565 System.out.println("t4 = " + t4);
566
567 System.out.println("t3.isAssignableFrom(t4) = "
568 + t3.getClass().isAssignableFrom(t4.getClass()));
569 System.out.println("t4.isAssignableFrom(t3) = "
570 + t4.getClass().isAssignableFrom(t3.getClass()));
571
572
573 GenPolynomialRing<BigRational> t5
574 = new GenPolynomialRing<BigRational>(t1,3);
575 System.out.println("t5 = " + t5);
576
577 System.out.println("t3.isAssignableFrom(t5) = "
578 + t3.getClass().isAssignableFrom(t5.getClass()));
579 System.out.println("t5.isAssignableFrom(t3) = "
580 + t5.getClass().isAssignableFrom(t3.getClass()));
581 }
582
583 }