Debian Codegraph @

doc/design.html

raw
1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml">
5 <head>
6 <link rel="stylesheet" type="text/css" href="html.css" />
7 <title>JAS - API Design</title>
8 </head>
9 <body class="main">
10 <h1>API usage and design overview</h1>
11
12 <p>
13 In ths document we give an overview on the structure
14 of the interfaces, classes and packages of JAS.
15 In the first section we show how to compute Legendre polynomials
16 with the JAS API.
17 In the next three sections we focus on the structure
18 of the required types and the creation of the corresponding objects.
19 In the following three sections we focus on the functional aspects of
20 the types, i.e. their constructors and methods.
21 For a discussion of other design alternatives see
22 the <a href="problems.html">problems</a> document.
23 Further programming issues and bugs are listed in the
24 <a href="findbugs.html" target="fb">Findbugs report</a>.
25 </p>
26
27
28 <h2>1. Getting started</h2>
29
30 <p>
31 You can use whatever environment for programming in Java you like. The
32 next picture shows the usage of Eclipse, but any text editor and a
33 Java compiler will do as well.
34 </p>
35
36 <p align="center">
37 <img src="../images/eclipse-legendre.png" width="90%"
38 alt="JAS in Eclipse IDE" />
39 <br />&nbsp;
40 <br />
41 <b>JAS program to compute Legendre polynomials in the Eclipse IDE</b>
42 </p>
43
44
45 <h3>1.1. Computation of the Legendre polynomials</h3>
46
47 At first we present an example for the usage of the JAS API
48 with the computation of the Legendre polynomials.
49 The Legendre polynomials can be defined by the following recursion
50 <ul>
51 <li>P[0](x) = 1
52 </li>
53 <li>P[1](x) = x
54 </li>
55 <li>P[n](x) = 1/n ( (2n-1) x P[n-1] - (n-1) P[n-2] ).
56 </li>
57 </ul>
58 The first 10 Legendre polynomials are:
59 <pre style="background-color: #FFFFF5;">
60 P[0] = 1
61 P[1] = x
62 P[2] = 3/2 x^2 - 1/2
63 P[3] = 5/2 x^3 - 3/2 x
64 P[4] = 35/8 x^4 - 15/4 x^2 + 3/8
65 P[5] = 63/8 x^5 - 35/4 x^3 + 15/8 x
66 P[6] = 231/16 x^6 - 315/16 x^4 + 105/16 x^2 - 5/16
67 P[7] = 429/16 x^7 - 693/16 x^5 + 315/16 x^3 - 35/16 x
68 P[8] = 6435/128 x^8 - 3003/32 x^6 + 3465/64 x^4 - 315/32 x^2 + 35/128
69 P[9] = 12155/128 x^9 - 6435/32 x^7 + 9009/64 x^5 - 1155/32 x^3 + 315/128 x
70 </pre>
71
72 <p>
73 The polynomials have been computed with the following Java program.
74 First we need a polynomial ring <code>ring</code> over the rational numbers,
75 in one variable <code>"x"</code> and a list <code>P</code> to store the
76 computed polynomials.
77 The polynomial factory object itself needs at least a factory for
78 the creation of coefficients and the number of variables.
79 Additionally the term order and names for the variables can be
80 specified. With this information the polynomial ring factory
81 can be created by
82 <code>new GenPolynomialRing &lt;BigRational&gt;(fac,1,var)</code>,
83 where <code>fac</code> is the coefficient factory,
84 <code>1</code> is the number of variables, and
85 <!--<code>to</code> is the term order object and-->
86 <code>var</code> is an <code>String</code> array of names.
87 </p>
88 <pre>
89 BigRational fac = new BigRational();
90 String[] var = new String[]{ "x" };
91 GenPolynomialRing&lt;BigRational&gt; ring
92 = new GenPolynomialRing&lt;BigRational&gt;(fac,1,var);
93
94 int n = 10;
95 List&lt;GenPolynomial&lt;BigRational&gt;&gt; P
96 = new ArrayList&lt;GenPolynomial&lt;BigRational&gt;&gt;(n);
97 GenPolynomial&lt;BigRational&gt; t, one, x, xc;
98 BigRational n21, nn;
99
100 one = ring.getONE();
101 x = ring.univariate(0);
102
103 P.add( one );
104 P.add( x );
105 for ( int i = 2; i &lt; n; i++ ) {
106 n21 = new BigRational( 2*i-1 );
107 xc = x.multiply( n21 );
108 t = xc.multiply( P.get(i-1) ); // (2n-1) x P[n-1]
109 nn = new BigRational( i-1 );
110 xc = P.get(i-2).multiply( nn ); // (n-1) P[n-2]
111 t = t.subtract( xc );
112 nn = new BigRational(1,i);
113 t = t.multiply( nn ); // 1/n t
114 P.add( t );
115 }
116 for ( int i = 0; i &lt; n; i++ ) {
117 System.out.println("P["+i+"] = " + P.get(i).toString(var) );
118 System.out.println();
119 }
120 </pre>
121 <p>
122 The polynomials for the recursion base are <code>one</code> and <code>x</code>.
123 Both are generated from the polynomial ring factory
124 with method <code>ring.getONE()</code> and <code>ring.univariate(0)</code>,
125 respectively.
126 The polynomial <code>(2n-1)x</code> is produced in the for-loop by
127 <code>n21 = new BigRational( 2*i-1 );</code> and
128 <code>xc = x.multiply( n21 );</code>.
129 The polynomial <code>(n-1) P[n-2]</code> is computed by
130 <code>nn = new BigRational( i-1 );</code> and
131 <code>xc = P.get(i-2).multiply( nn )</code>.
132 Finally we have to multiply the difference of the
133 intermediate polynomials by <code>1/i</code> as
134 <code>nn = new BigRational( 1, i );</code> and
135 <code>t = t.multiply( nn )</code>.
136 Then, in the for-loop, the polynomials <code>P[i]</code> are computed
137 using the definition, and stored in the list <code>P</code> for further use.
138 In the last for-loop, the polynomials are printed, producing the
139 output shown above.
140 The string representation of the polynomial object can be created,
141 as expected, by <code>toString()</code>,
142 or by using names for the variables with <code>toString(var)</code>.
143 The imports required are
144 </p>
145 <pre>
146 import java.util.ArrayList;
147 import java.util.List;
148 import edu.jas.arith.BigRational;
149 import edu.jas.poly.GenPolynomial;
150 import edu.jas.poly.GenPolynomialRing;
151 </pre>
152 <p>
153 To use other coefficient rings, one simply changes the
154 generic type parameter, say, from <code>BigRational</code> to
155 <code>BigComplex</code> and adjusts the coefficient factory.
156 The factory would then be created as
157 <code>c = new BigComplex()</code>, followed by
158 <code>new GenPolynomialRing&lt;BigComplex&gt; (c,1,var)</code>.
159 This small example shows that this library can easily be used,
160 just as any other Java package or library.
161 </p>
162 <!--
163 The string argument of method <code>parse()</code> can be the
164 TeX-representation of the polynomial,
165 except that no subscripts may appear.
166 -->
167 <p>
168 In the following sections we describe the
169 central classes and interfaces for the polynomial API.
170 </p>
171
172 <h3>1.2. Algebraic structures overview</h3>
173
174 <p>
175 To get an idea of the scope of JAS we summarize
176 the implemented algebraic structures and
177 of the implemented algebraic algorithms.
178 </p>
179
180 <table border="1" cellpadding="3" summary="JAS AS summary" >
181 <tr>
182 <td>class</td>
183 <td>factory</td>
184 <td>structure</td>
185 <td>methods</td>
186 </tr>
187
188 <tr>
189 <td><code>BigInteger</code></td>
190 <td>self</td>
191 <td>ring of arbitrary precision integers,
192 a facade for <code>java.math.BigInteger</code>
193 </td>
194 <td>arithmetic, gcd, primality test</td>
195 </tr>
196
197 <tr>
198 <td><code>BigRational</code></td>
199 <td>self</td>
200 <td>ring of arbitrary precision rational numbers,
201 i.e. fractions of integers,
202 with Henrici optimizations for gcds
203 </td>
204 <td>arithmetic</td>
205 </tr>
206
207 <tr>
208 <td><code>ModInteger</code>, <code>ModLong</code>, <code>ModInt</code></td>
209 <td><code>ModIntegerRing</code>, <code>ModLongRing</code>, <code>ModIntRing</code></td>
210 <td>ring of integers modulo some fixed (long) integer or an arbitrary precision
211 integer <code>n</code>,
212 if <code>n</code> is a prime number, the ring is a field
213 </td>
214 <td>arithmetic, chinese remainder</td>
215 </tr>
216
217 <tr>
218 <td><code>BigDecimal</code></td>
219 <td>self</td>
220 <td>ring of arbitrary precision floating point numbers,
221 a facade for <code>java.math.BigDecimal</code>
222 </td>
223 <td>arithmetic, <code>compareTo()</code> with given precision</td>
224 </tr>
225
226 <tr>
227 <td><code>BigComplex</code></td>
228 <td>self</td>
229 <td>ring of arbitrary precision complex numbers,
230 i.e. pairs of rational numbers
231 </td>
232 <td>arithmetic</td>
233 </tr>
234
235 <tr>
236 <td><code>BigDecimalComplex</code></td>
237 <td>self</td>
238 <td>ring of arbitrary precision complex floating point numbers,
239 i.e. pairs of BigDecimal numbers
240 </td>
241 <td>arithmetic, <code>compareTo()</code> with given precision</td>
242 </tr>
243
244
245 <tr>
246 <td><code>BigQuaternion</code></td>
247 <td>self</td>
248 <td>ring of arbitrary precision quaternion numbers,
249 i.e. quadruples of rational numbers
250 </td>
251 <td>arithmetic</td>
252 </tr>
253
254 <tr>
255 <td><code>BigOctonion</code></td>
256 <td>self</td>
257 <td>ring of arbitrary precision octonion numbers,
258 i.e. implemented as pairs of quaternion numbers
259 </td>
260 <td>arithmetic</td>
261 </tr>
262
263 <tr>
264 <td><code>GenPolynomial</code></td>
265 <td><code>GenPolynomialRing</code></td>
266 <td>ring of polynomials in <code>r</code> variables
267 over any implemented coefficient ring
268 with respect to any implemented term ordering
269 </td>
270 <td>arithmetic, univariate gcd, norms,
271 chinese remainders for coefficients, evaluation</td>
272 </tr>
273
274 <tr>
275 <td><code>AlgebraicNumber</code></td>
276 <td><code>AlgebraicNumberRing</code></td>
277 <td>ring of algebraic numbers, represented as
278 univariate polynomials
279 over any implemented coefficient field
280 </td>
281 <td>arithmetic
282 </td>
283 </tr>
284
285 <tr>
286 <td><code>RealAlgebraicNumber</code></td>
287 <td><code>RealAlgebraicRing</code></td>
288 <td>ring of real algebraic numbers, represented as
289 algebraic number and an isolating interval for a real root
290 over rational numbers or real algebraic numbers
291 </td>
292 <td>arithmetic, real sign, magnitude
293 </td>
294 </tr>
295
296 <tr>
297 <td><code>ComplexAlgebraicNumber</code></td>
298 <td><code>ComplexAlgebraicRing</code></td>
299 <td>ring of complex algebraic numbers, represented as
300 algebraic number and an isolating rectangle for a complex root
301 over rational numbers as base ring
302 </td>
303 <td>arithmetic, sign invariant rectangle, magnitude
304 </td>
305 </tr>
306
307 <tr>
308 <td><code>GenSolvablePolynomial</code></td>
309 <td><code>GenSolvablePolynomialRing</code></td>
310 <td>ring of non-commutative, solvable polynomials in <code>r</code> variables
311 over any implemented coefficient ring
312 with respect to any implemented term ordering
313 (compatible with the multiplication)
314 </td>
315 <td>arithmetic</td>
316 </tr>
317
318 <tr>
319 <td><code>GenWordPolynomial</code></td>
320 <td><code>GenWordPolynomialRing</code></td>
321 <td>ring of free non-commutative polynomials in <code>r</code> letters
322 over any implemented coefficient ring
323 with respect to a graded term ordering
324 </td>
325 <td>arithmetic</td>
326 </tr>
327
328 <tr>
329 <td><code>RecSolvable</code> <code>Polynomial</code>,
330 <code>QuotSolvable</code> <code>Polynomial</code>,
331 <code>ResidueSolvable</code> <code>Polynomial</code>,
332 <code>LocalSolvable</code> <code>Polynomial</code>,
333 <code>QLRSolvablePolynomial</code>
334 </td>
335 <td><code>RecSolvable</code> <code>PolynomialRing</code>,
336 <code>QuotSolvable</code> <code>PolynomialRing</code>,
337 <code>ResidueSolvable</code> <code>PolynomialRing</code>,
338 <code>LocalSolvable</code> <code>PolynomialRing</code>,
339 <code>QLRSolvablePolynomialRing</code>
340 </td>
341 <td>ring of recursive, solvable polynomials in <code>r</code> variables
342 over a solvable polynomial coefficient ring over any implemented coefficient ring
343 with respect to any implemented term ordering
344 (compatible with the multiplication).
345 The other variants have coefficient rings <code>SolvableQuotient</code>,
346 <code>SolvableResidue</code> and <code>SolvableLocal</code> which are all based
347 on solvable polynomials.
348 The <code>QLRSolvablePolynomial</code> is a unification of the others.
349 </td>
350 <td>arithmetic</td>
351 </tr>
352
353 <tr>
354 <td><code>Quotient</code></td>
355 <td><code>QuotientRing</code></td>
356 <td>ring of rational functions,
357 i.e. fractions of multivariate polynomials
358 over any implemented commutative unique factorization coefficient domain
359 </td>
360 <td>arithmetic
361 </td>
362 </tr>
363
364 <tr>
365 <td><code>SolvableQuotient</code></td>
366 <td><code>SolvableQuotientRing</code></td>
367 <td>ring of rational functions,
368 i.e. fractions of multivariate solvable polynomials
369 (satisfying the left-, right-Ore condition)
370 over some implemented coefficient domains
371 </td>
372 <td>arithmetic
373 </td>
374 </tr>
375
376 <tr>
377 <td><code>Residue</code></td>
378 <td><code>ResidueRing</code></td>
379 <td>ring of polynomials modulo a given polynomial ideal,
380 over any implemented commutative coefficient ring
381 </td>
382 <td>arithmetic
383 </td>
384 </tr>
385
386 <tr>
387 <td><code>SolvableResidue</code></td>
388 <td><code>SolvableResidueRing</code></td>
389 <td>ring of polynomials modulo a given polynomial ideal,
390 over some implemented coefficient domains
391 </td>
392 <td>arithmetic
393 </td>
394 </tr>
395
396 <tr>
397 <td><code>Local</code></td>
398 <td><code>LocalRing</code></td>
399 <td>ring of polynomials fractions localized with respect to a given polynomial ideal,
400 over any implemented commutative coefficient ring
401 </td>
402 <td>arithmetic
403 </td>
404 </tr>
405
406 <tr>
407 <td><code>SolvableLocal</code></td>
408 <td><code>SolvableLocalRing</code></td>
409 <td>ring of solvable polynomials fractions localized with respect to a given solvable polynomial ideal,
410 over some implemented coefficient rings
411 </td>
412 <td>arithmetic
413 </td>
414 </tr>
415
416 <tr>
417 <td><code>SolvableLocalResidue</code></td>
418 <td><code>SolvableLocalResidueRing</code></td>
419 <td>ring of solvable polynomials fractions localized with respect to a given solvable polynomial ideal
420 and modulo the given polynomial ideal,
421 over some implemented coefficient rings
422 </td>
423 <td>arithmetic
424 </td>
425 </tr>
426
427 <tr>
428 <td><code>Product</code></td>
429 <td><code>ProductRing</code></td>
430 <td>(finite) direct product of fields and rings
431 over any implemented coefficient ring
432 </td>
433 <td>arithmetic, idempotent elements
434 </td>
435 </tr>
436
437 <tr>
438 <td><code>GenVector</code></td>
439 <td><code>GenVectorModule</code></td>
440 <td>tuples (vectors) of any implemented
441 ring elements
442 </td>
443 <td>arithmetic, scalar product
444 </td>
445 </tr>
446
447 <tr>
448 <td><code>GenMatrix</code></td>
449 <td><code>GenMatrixModule</code></td>
450 <td>matrices of any implemented ring elements
451 </td>
452 <td>arithmetic, scalar product
453 </td>
454 </tr>
455
456 <tr>
457 <td><code>UnivPowerSeries</code></td>
458 <td><code>UnivPowerSeriesRing</code></td>
459 <td>ring of univariate power series
460 over any implemented coefficient ring
461 </td>
462 <td>arithmetic, gcd, evaluation, integration, fixed points</td>
463 </tr>
464
465 <tr>
466 <td><code>MultiVarPowerSeries</code></td>
467 <td><code>MultiVarPowerSeriesRing</code></td>
468 <td>ring of multivatiate power series
469 over any implemented coefficient ring
470 </td>
471 <td>arithmetic, evaluation, integration, fixed points</td>
472 </tr>
473
474 <tr>
475 <td><code>Quotient</code></td>
476 <td><code>QuotientRing</code></td>
477 <td>ring of fractions
478 over any implemented (unique factorization domain) ring
479 </td>
480 <td>arithmetic
481 </td>
482 </tr>
483
484 <tr>
485 <td><code>Residue</code></td>
486 <td><code>ResidueRing</code></td>
487 <td>ring of elements modulo a given (main) ideal,
488 over any implemented ring
489 </td>
490 <td>arithmetic
491 </td>
492 </tr>
493
494 <tr>
495 <td><code>Local</code></td>
496 <td><code>LocalRing</code></td>
497 <td>ring of fractions localized with respect to a given (main) ideal,
498 over any implemented ring
499 </td>
500 <td>arithmetic
501 </td>
502 </tr>
503
504 <tr>
505 <td><code>Complex</code></td>
506 <td><code>ComplexRing</code></td>
507 <td>ring of complex numbers over any implemented ring (with gcd)
508 </td>
509 <td>arithmetic
510 </td>
511 </tr>
512
513 </table>
514
515 <p>
516 "Arithmetic" means implementation of the methods defined in the
517 interface <code>RingElem</code>. As of 2021-03 there are 36 rings
518 implemented (9 explicit, others generic). To be continued.
519 </p>
520
521
522 <h3>1.3. Algebraic algorithms overview</h3>
523
524 <p>
525 The following table contains an overview of
526 implemented algebraic algorithms.
527 </p>
528
529 <table border="1" cellpadding="3" summary="JAS AA summary" >
530 <tr>
531 <td>class / interface</td>
532 <td>algorithm&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
533 <td>methods</td>
534 </tr>
535
536 <tr>
537 <td><code>Reduction</code>,
538 <code>ReductionAbstract</code>,
539 <code>ReductionSeq</code>,
540 <code>ReductionPar</code>,
541 <code>PseudoReduction</code>
542 </td>
543 <td>Iterated subtraction of polynomials to eliminate terms from a given polynomial,
544 i.e. reduction of polynomial(s) wrt. a set of polynomials.
545 Coefficients of polynomials must be from a field and for the
546 Pseudo* version from a ring with gcd.
547 For *Par the list of polynomials can concurrently be modified.
548 </td>
549 <td>normalform,
550 S-polynomial,
551 criterions,
552 extended normalform
553 </td>
554 </tr>
555
556 <tr>
557 <td><code>DReduction</code>,
558 <code>EReduction</code>,
559 <code>DReductionSeq</code>,
560 <code>EReductionSeq</code>
561 </td>
562 <td>Reduction of polynomial(s) wrt. a set of polynomials.
563 Coefficients of polynomials must be from a
564 principial ideal domain (PID) or from an Euclidean domain.
565 </td>
566 <td>normalform,
567 S-polynomial,
568 G-polynomial,
569 criterions,
570 extended normalform
571 </td>
572 </tr>
573
574 <tr>
575 <td><code>SolvableReduction</code>,
576 <code>SolvableReductionAbstract</code>,
577 <code>SolvableReductionSeq</code>,
578 <code>SolvableReductionPar</code>,
579 <code>SolvablePseudoReduction</code>
580 </td>
581 <td>Left and right reduction of solvable polynomial(s) wrt. a
582 set of solvable polynomials.
583 Coefficients of polynomials must be from a field and for the
584 Pseudo* version from a ring with gcd.
585 </td>
586 <td>left/right normalform,
587 left/right S-polynomial,
588 criterions,
589 extended left normalform
590 </td>
591 </tr>
592
593 <tr>
594 <td><code>RReduction</code>,
595 <code>RPseudoReduction</code>,
596 <code>RReductionSeq</code>,
597 <code>RPseudoReductionSeq</code>
598 </td>
599 <td>Iterated subtraction of polynomials to eliminate terms from a given polynomial,
600 i.e. reduction of polynomial(s) wrt. a set of polynomials.
601 Coefficients of polynomials must be from a regular ring and for the
602 Pseudo* version from a regular ring with gcd.
603 Boolean closure and boolean remainder of polynomials.
604 </td>
605 <td>normalform,
606 S-polynomial,
607 <!--extended normalform,-->
608 boolean closure
609 </td>
610 </tr>
611
612 <tr>
613 <td><code>CReductionSeq</code>,
614 <code>Condition</code>,
615 <code>ColorPolynomial</code>
616 </td>
617 <td>Iterated subtraction of polynomials to eliminate terms from a given polynomial,
618 i.e. reduction of polynomial(s) wrt. a set of polynomials.
619 Coefficients of polynomials must be from a polynomial ring.
620 Case distinction and determination of polynomaials with respect to conditions
621 leading to colored polynomials.
622 </td>
623 <td>normalform,
624 S-polynomial,
625 <!--extended normalform,-->
626 color, determine
627 </td>
628 </tr>
629
630 <tr>
631 <td><code>GroebnerBase</code>,
632 <code>GroebnerBaseAbstract</code>,
633 <code>GroebnerBaseSeq</code>,
634 <code>GroebnerBaseParallel</code>,
635 <code>GroebnerBaseDistributed</code>,
636 <code>GroebnerBasePseudoSeq</code>
637 etc.
638 </td>
639 <td>Buchberger algorithm to compute Groebner bases
640 of sets of polynomials.
641 Coefficients of polynomials must be from a field.
642 <code>*Parallel</code> is a multi-threaded and
643 <code>*Distributed</code> is a message passing implementation.
644 The <code>*Pseudo</code> versions are for coefficient domains with gcd.
645 </td>
646 <td>GB, isGB, extended GB, minimal GB
647 </td>
648 </tr>
649
650 <tr>
651 <td><code>DGroebnerBaseSeq</code>,
652 <code>EGroebnerBaseSeq</code>
653 </td>
654 <td>Algorithm to compute D- and E- Groebner bases
655 of sets of polynomials.
656 Coefficients of polynomials must be from a
657 principial ideal domain (PID) or from an Euclidean domain.
658 </td>
659 <td>GB, isGB, minimal GB
660 </td>
661 </tr>
662
663 <tr>
664 <td><code>SolvableGroebnerBase</code>,
665 <code>SolvableGroebnerBaseAbstract</code>,
666 <code>SolvableGroebnerBaseSeq</code>,
667 <code>SolvableGroebnerBaseParallel</code>,
668 <code>SolvableGroebnerBasePseudoSeq</code>
669 </td>
670 <td>Algorithm to compute left, right and two-sided Groebner bases
671 of sets of solvable polynomials.
672 Coefficients of polynomials must be from a field.
673 Parallel is a multi-threaded implementation.
674 The <code>*Pseudo</code> versions are for coefficient domains with gcd.
675 </td>
676 <td>left, right, two-sided versions of GB, isGB, extended GB, minimal GB
677 </td>
678 </tr>
679
680 <tr>
681 <td><code>WordGroebnerBase</code>,
682 <code>WordGroebnerBaseAbstract</code>,
683 <code>WordGroebnerBaseSeq</code>,
684 <code>WordGroebnerBasePseudoSeq</code>
685 </td>
686 <td>Algorithm to compute two-sided Groebner bases
687 of sets of free non-commutative polynomials.
688 Coefficients of polynomials must be from a field.
689 The <code>*Pseudo</code> versions are for coefficient domains with gcd.
690 </td>
691 <td>two-sided versions of GB, isGB, minimal GB
692 </td>
693 </tr>
694
695 <tr>
696 <td><code>RGroebnerBaseSeq</code>,
697 <code>RGroebnerBasePseudoSeq</code>
698 </td>
699 <td>Algorithm to compute Groebner bases in polynomial rings over regular rings.
700 Coefficients of polynomials must be from a
701 product of fields or Euclidean domains.
702 </td>
703 <td>GB, isGB, minimal GB
704 </td>
705 </tr>
706
707 <tr>
708 <td><code>ComprehensiveGroebnerBaseSeq</code>,
709 <code>GroebnerSystem</code>,
710 <code>ColoredSystem</code>
711 </td>
712 <td>Algorithm to compute comprehensive Groebner bases in polynomial rings over
713 parameter rings.
714 Coefficients of polynomials must be from a polynomial ring.
715 Computation is done via Groebner systems (lists of colored systems).
716 </td>
717 <td>GBsys, isGBsys, GB, isGB, minimalGB
718 </td>
719 </tr>
720
721 <tr>
722 <td><code>Syzygy</code>,
723 <code>SyzygyAbstract</code>,
724 <code>ModGroebnerBase</code>,
725 <code>ModGroebnerBaseAbstract</code>
726 </td>
727 <td>Algorithm to compute syzygies of lists of polynomials
728 or Groebner Bases, free resolutions.
729 Groebner Bases for modules over polynomial rings.
730 Coefficients of polynomials must be from a field.
731 </td>
732 <td>zeroRelations, isZeroRelation,
733 resolution, zeroRelationsArbitrary,
734 GB, isGB
735 </td>
736 </tr>
737
738 <tr>
739 <td><code>SolvableSyzygy</code>,
740 <code>SolvableSyzygyAbstract</code>,
741 <code>ModSolvableGroebnerBase</code>,
742 <code>ModSolvableGroebnerBaseAbstract</code>
743 </td>
744 <td>Algorithm to compute left and right syzygies of lists
745 of solvable polynomials or Groebner Bases, free left resolutions.
746 Left, right and two-sided Groebner Bases for modules over solvable polynomial rings.
747 Coefficients of polynomials must be from a field.
748 </td>
749 <td>leftZeroRelations, rightZeroRelations,
750 isLeftZeroRelation, isRightZeroRelation,
751 (left) resolution, zeroRelationsArbitrary,
752 leftOreCond, rightOreCont(ition),
753 left, right, two-sided GB, isGB
754 </td>
755 </tr>
756
757 <tr>
758 <td><code>ReductionSeq</code>,
759 <code>StandardBaseSeq</code>,
760 etc.
761 </td>
762 <td>Mora's tangent cone reduction algorithm and computation of standard bases
763 of sets of multivariate power series.
764 Coefficients of polynomials must be from a field.
765
766 </td>
767 <td>STD, isSTD, minimalSTD, normalForm, SPolynomial
768 </td>
769 </tr>
770
771 <tr>
772 <td><code>Ideal</code>
773 </td>
774 <td>Algorithms to compute sums, products, intersections, containment
775 and (infinite) quotients of polynomial ideals.
776 Coefficients of polynomials must be from a field.
777 Prime, primary, irreducible and radical decomposition of zero dimensional ideals.
778 Prime, primary, irreducible and radical decomposition of non-zero dimensional ideals.
779 Univariate polynomials of minimal degree in ideal as well as
780 elimination, extension and contraction ideals.
781 </td>
782 <td>sum, product, intersect, contains,
783 quotient, infiniteQuotient, inverse modulo ideal,
784 zeroDimRadicalDecomposition, zeroDimPrimeDecomposition,
785 zeroDimPrimaryDecomposition, zeroDimDecomposition,
786 zeroDimRootDecomposition,
787 radicalDecomposition, primeDecomposition, decomposition,
788 primaryDecomposition
789 </td>
790 </tr>
791
792 <tr>
793 <td><code>SolvableIdeal</code>
794 </td>
795 <td>Algorithms to compute sums, products, intersections, containment
796 and (infinite) quotients of solvable polynomial ideals.
797 Coefficients of solvable polynomials must be from a field.
798 </td>
799 <td>sum, product, intersect, contains,
800 quotient, infiniteQuotient, inverse modulo ideal,
801 univariate polynomials of minimal degree in ideal
802 </td>
803 </tr>
804
805 <tr>
806 <td><code>WordIdeal</code>
807 </td>
808 <td>Algorithms to compute sums, products, and containment
809 word polynomial ideals (free algebra twosided ideals).
810 Coefficients of word polynomials must be from a field.
811 </td>
812 <td>sum, product, contains
813 </td>
814 </tr>
815
816 <tr>
817 <td><code>GreatestCommonDivisor</code>,
818 <code>GCDFactory</code>,
819 <code>GreatestCommonDivisorAbstract</code>,
820 <code>GreatestCommonDivisorSimple</code>,
821 <code>GreatestCommonDivisorPrimitive</code>,
822 <code>GreatestCommonDivisorSubres</code>,
823 <code>GreatestCommonDivisorModular</code>,
824 <code>GreatestCommonDivisorModEval</code>,
825 <code>GCDProxy</code>
826 </td>
827 <td>Algorithms to compute greatest common divisors of polynomials
828 via different polynomial remainder sequences (PRS) and modular methods.
829 Coefficients of polynomials must be from a unique factorization domain (UFD).
830 <code>GCDFactory</code> helps with the optimal selection of an algorithm
831 and <code>GCDProxy</code> uses multi-threading to compute with
832 several implementations in parallel.
833 </td>
834 <td>gcd, lcm, content, primitivePart, resultant, coPrime
835 </td>
836 </tr>
837
838 <tr>
839 <td><code>Squarefree</code>,
840 <code>SquarefreeFactory</code>,
841 <code>SquarefreeAbstract</code>,
842 <code>SquarefreeFieldChar0</code>,
843 <code>SquarefreeFieldCharP</code>,
844 <code>SquarefreeFiniteFieldCharP</code>,
845 <code>SquarefreeInfiniteFieldCharP</code>,
846 <code>Squarefree</code>-
847 <code>InfiniteAlgebraicFieldCharP</code>,
848 <code>SquarefreeRingChar0</code>
849 </td>
850 <td>Algorithms to compute squarefree decomposition of polynomials
851 over fields of characteristic zero, finite and infinite fields of characteristic p
852 and other coefficients from unique factorization domains (UFD).
853 <code>SquarefreeFactory</code> helps with the optimal selection of an algorithm.
854 </td>
855 <td>squarefreePart, squarefreeFactors,
856 isFactorization, isSquarefree, coPrimeSquarefree
857 </td>
858 </tr>
859
860 <tr>
861 <td><code>Factorization</code>,
862 <code>FactorFactory</code>,
863 <code>FactorAbstract</code>,
864 <code>FactorAbsolute</code>,
865 <code>FactorModular</code>,
866 <code>FactorInteger</code>,
867 <code>FactorRational</code>,
868 <code>FactorAlgebraic</code>
869 </td>
870 <td>Algorithms to compute factorizations of polynomials as products of irreducible polynomials
871 over different ground rings.
872 <code>FactorFactory</code> helps with the correct selection of an algorithm.
873 Reduction of the multivariate factorization to an univariate factorization is done
874 with Kronecker's algorithm in the general case and with Wang's algorithm over the integers.
875 </td>
876 <td>squarefreeFactors, factors, baseFactors,
877 isIrreducible, isReducible, isSquarefree, isFactorization,
878 isAbsoluteIrreducible, factorsAbsolute
879 </td>
880 </tr>
881
882 <tr>
883 <td><code>RealRoots</code>,
884 <code>RealRootsAbstract</code>,
885 <code>RealRootsSturm</code>
886 </td>
887 <td>Algorithms to compute isolating intervals for real roots
888 and for refinement of isolating intervals to any prescribed precision.
889 Algorithms to compute the sign of a real algebraic numer and
890 the magnitude of a real algebraic number to a given precision.
891 Coefficients of polynomials must be from a real field,
892 for example from <code>BigRational</code> or <code>RealAlgebricNumber</code>.
893 </td>
894 <td>realRoots, refineInterval, algebraicSign, algebraicMagnitude
895 </td>
896 </tr>
897
898 <tr>
899 <td><code>ComplexRoots</code>,
900 <code>ComplexRootsAbstract</code>,
901 <code>ComplexRootsSturm</code>
902 </td>
903 <td>Algorithms to compute isolating rectangles for complex roots
904 and for refinement of isolating rectangles to any prescribed precision.
905 Coefficients of polynomials must be of type <code>Complex</code> field.
906 </td>
907 <td>complexRoots, complexRootCount, complexRootRefinement
908 </td>
909 </tr>
910
911 <tr>
912 <td><code>ElementaryIntegration</code>
913 </td>
914 <td>Algorithms to compute elementary integrals of univariate rational functions.
915 </td>
916 <td>integrate, integrateHermite, integrateLogPart, isIntegral
917 </td>
918 </tr>
919
920 <tr>
921 <td><code>CharacteristicSet</code>,
922 <code>CharacteristicSetSimple</code>,
923 <code>CharacteristicSetWu</code>
924 </td>
925 <td>Algorithms to compute simple or Wu-Ritt characteristic sets.
926 </td>
927 <td>characteristicSet, isCharacteristicSet, characteristicSetReduction
928 </td>
929 </tr>
930
931 </table>
932
933 <p>
934 </p>
935
936 <h3>1.4. Packages and components overview</h3>
937
938 <p align="center">
939 <!--img src="../images/PackageOverview.png" alt="Static package structure overview" /-->
940 <img src="../images/jas-pack-over.png"
941 alt="Package and component structure overview" />
942 </p>
943
944 <p>
945 More details can be found in the <a href="http://www.clarkware.com/software/JDepend.html"
946 target="new">JDepend</a> <a href="jdepend-report.txt" target="new">report.txt</a>.
947 </p>
948
949
950 <h2>2. Recursive ring element design</h2>
951
952 <p>
953 The next figure gives an overview of the central interfaces and classes.
954 The interface <code>RingElem</code> defines a <strong>recursive type</strong>
955 which defines the functionality (see next section) of the
956 polynomial coefficients and is also implemented by the
957 polynomials itself. So polynomials can be taken as coefficients
958 for other polynomials, thus defining a recursive polynomial ring structure.
959 </p>
960
961 <p>
962 Since the construction of constant ring elements has been difficult
963 in previuos designs, we separated the creational aspects of ring elements
964 into <strong>ring factories</strong> with sufficient context information.
965 The minimal factory functionality is defined by the interface
966 <code>RingFactory</code>.
967 Constructors for polynomial rings will then require factories for
968 the coefficients so that the construction of polynomials over these
969 coefficient rings poses no problem.
970 The ring factories are additionaly required because of the
971 Java generic type design. I.e. if <code>C</code> is a generic type name
972 it is not possible to construct an new object with <code>new C()</code>.
973 Even if this would be possible, one can not specify constructor signatures
974 in Java interfaces, e.g. to construct a one or zero constant ring element.
975 Recursion is again achieved by using polynomial factories as
976 coefficient factories in recursive polynomial rings.
977 Constructors for polynomials will always require
978 a polynomial factory parameter which knows
979 all details about the polynomial ring under consideration.
980 </p>
981
982 <p class="center" >
983 <a href="../images/overview-recursive.png"
984 target="diagram"
985 ><img src="../images/overview-recursive.png" alt="JAS type overview" /></a>
986 <br />
987 UML diagram of JAS types
988 </p>
989
990
991 <h2>3. Coefficients and polynomials</h2>
992
993 <p>
994 We continue the discussion of the next layer of classes in the
995 the above figure.
996 </p>
997
998 <p>
999 Elementary <strong>coefficient classes</strong>, such as
1000 <code>BigRational</code> or <code>BigInteger</code>, implement both
1001 the <code>RingElem</code> and <code>RingFactory</code> interfaces.
1002 This is convenient, since these factories do not need further context
1003 information.
1004 In the implementation of the interfaces the type parameter
1005 <code>C extends RingElem&lt;C&gt;</code> is simultaneously bound
1006 to the respective class, e.g. <code>BigRational</code>.
1007 <strong>Coefficient objects</strong> can in most cases created directly
1008 via the respective class constructors, but also via the factory methods.
1009 E.g. the object representing the rational number 2 can be created by
1010 <code>new BigRational(2)</code> or by
1011 <code>fac = new BigRational()</code>, <code>fac.fromInteger(2)</code> and
1012 the object representing the rational number 1/2 can be created by
1013 <code>new BigRational(1,2)</code> or by
1014 <code>fac.parse("1/2")</code>.
1015 </p>
1016
1017 <p>
1018 <strong>Generic polynomials</strong> are implemented in the
1019 <code>GenPolynomial</code> class, which has a type parameter
1020 <code>C extends RingElem&lt;C&gt;</code>
1021 for the coefficient type. So all operations on coefficients required
1022 in polynomial arithmetic and manipulation are guaranteed to exist by the
1023 <code>RingElem</code> interface. The constructors of the polynomials
1024 always require a matching polynomial factory.
1025 The <strong>generic polynomial factory</strong> is implemented in the class
1026 <code>GenPolynomialRing</code>, again with type parameter
1027 <code>C extends RingElem&lt;C&gt;</code> (not <code>RingFactory</code>).
1028 The polynomial factory however implements the interface
1029 <code>RingFactory&lt;C extends RingElem&lt;C&gt;&gt;</code> so that
1030 it can also be used recursively.
1031 The constructors for <code>GenPolynomialRing</code> require at least
1032 parameters for a coefficient factory and the number of variables
1033 of the polynomial ring.
1034 </p>
1035
1036 <p>
1037 Having generic polynomial and elementary coefficient implementations
1038 one can attempt to construct <strong>polynomial objects</strong>.
1039 The type is first created by binding the type parameter
1040 <code>C extends RingElem&lt;C&gt;</code> to the desired coefficient type,
1041 e.g. <code>BigRational</code>. So we arrive at the type
1042 <code>GenPolynomial&lt;BigRational&gt;</code>.
1043 Polynomial objects are then created via the respective polynomial factory
1044 of type <code>GenPolynomialRing&lt;BigRational&gt;</code>,
1045 which is created by binding the generic coefficient type of the
1046 generic polynomial factory to the desired coefficient type,
1047 e.g. <code>BigRational</code>.
1048 A <strong>polynomial factory object</strong> is created from a
1049 coefficient factory object and the number of variables in the
1050 polynomial ring as usual with the <code>new</code> operator via one
1051 of its constructors.
1052 Given an object <code>coFac</code> of type <code>BigRational</code>,
1053 e.g. created with <code>new BigRational()</code>, a polynomial factory
1054 object <code>pfac</code> of the above described type could be created by
1055 <code>new GenPolynomialRing&lt;BigRational&gt;(coFac,5)</code>.
1056 I.e. we specified a polynomial ring with 5 variables over
1057 the rational numbers.
1058 A polynomial object <code>p</code> of the above described type can then
1059 be created by any method defined in <code>RingFactory</code>,
1060 e.g. by <code>pfac.getONE()</code>,
1061 <code>pfac.fromInteger(1)</code>, <code>pfac.random(3)</code>
1062 or <code>pfac.parse("(1)")</code>.
1063 </p>
1064
1065 <p>
1066 Since <code>GenPolynomial</code> itself implements the
1067 <code>RingElem</code> interface, they can also be used recursively
1068 as coefficients.
1069 We continue the polynomial example and are going to use polynomials over
1070 the rational numbers as coefficients of a new polynomial.
1071 The type is then
1072 <code>GenPolynomial&lt;GenPolynomial&lt;BigRational&gt;&gt;</code>
1073 and the polynomial factory has type
1074 <code>GenPolynomial<b>Ring</b>&lt;GenPolynomial&lt;BigRational&gt;&gt;</code>.
1075 Using the polynomial coefficient factory <code>pfac</code> from above
1076 a recursive polynomial factory <code>rfac</code> could be created by
1077 <code>new GenPolynomialRing&lt;GenPolynomial&lt;BigRational&gt;&gt;(pfac,3)</code>.
1078 The creation of a recursive polynomial object <code>r</code> of the
1079 above described type is then as a easy as before
1080 e.g. by <code>rfac.getONE()</code>,
1081 <code>rfac.fromInteger(1)</code> or <code>rfac.random(3)</code>.
1082 </p>
1083
1084
1085 <h2>4. Solvable polynomials</h2>
1086
1087 <p>
1088 We turn now to the last layer of classes in the the above figure.
1089 </p>
1090
1091 <p>
1092 The generic polynomials are intended as super class for further
1093 types of polynomial rings. As one example we take so called
1094 <strong>solvable polynomials</strong>, which are like normal polynomials
1095 but are equipped with a new non-commutative multiplication.
1096 They are implemented in the class <code>GenSolvablePolynomial</code>
1097 which extends <code>GenPolynomial</code> and inherits all methods
1098 except <code>clone()</code> and <code>multiply()</code>.
1099 The class also has a type parameter <code>C extends RingElem&lt;C&gt;</code>
1100 for the coefficient type.
1101 Note, that the inherited methods are in fact creating solvable polynomials
1102 since they employ the solvable polynomial factory for the creation of any
1103 new polynomial internally. Only the formal method return type is that
1104 of <code>GenPolynomial</code>, the run-time type is
1105 <code>GenSolvablePolynomial</code> to which they can be casted at any time.
1106 The <strong>factory for solvable polynomials</strong> is implemented
1107 by the class <code>GenSolvablePolynomialRing</code> which also
1108 extends the generic polynomial factory. So this factory can also be used
1109 in the constructors of <code>GenPolynomial</code> via <code>super()</code>
1110 to produce in fact solvable polynomials internally. The data structure
1111 is enhanced by a table of non-commutative relations defining the
1112 new multiplication. The constructors delegate most things to the
1113 corresponding super class constructors and additionally have a
1114 parameter for the <code>RelationTable</code> to be used.
1115 Also the methods delegate the work to the respective super class methods
1116 where possible and then handle the non-commutative multiplication relations
1117 separately.
1118 </p>
1119
1120 <p>
1121 The construction of <strong>solvable polynomial objects</strong>
1122 follows directly that of polynomial objects.
1123 The type is created by binding the type parameter
1124 <code>C extends RingElem&lt;C&gt;</code> to the desired coefficient type,
1125 e.g. <code>BigRational</code>. So we have the type
1126 <code>GenSolvablePolynomial&lt;BigRational&gt;</code>.
1127 Solvable polynomial objects are then created via the respective
1128 solvable polynomial factory of type
1129 <code>GenSolvablePolynomialRing&lt;BigRational&gt;</code>,
1130 which is created by binding the generic coefficient type of the
1131 generic polynomial factory to the desired coefficient type,
1132 e.g. <code>BigRational</code>.
1133 A <strong>solvable polynomial factory object</strong> is created from a
1134 coefficient factory object, the number of variables in the
1135 polynomial ring and a table containing the defining non-commutative relations
1136 as usual with the <code>new</code> operator via one of its constructors.
1137 Given an object <code>coFac</code> of type <code>BigRational</code>
1138 as before, a polynomial factory object <code>spfac</code>
1139 of the above described type could be created by
1140 <code>new GenSolvablePolynomialRing&lt;BigRational&gt;(coFac,5)</code>.
1141 I.e. we specified a polynomial ring with 5 variables over
1142 the rational numbers with no commutator relations.
1143 A solvable polynomial object <code>p</code> of the above described type
1144 can then be created by any method defined in <code>RingFactory</code>,
1145 e.g. by <code>spfac.getONE()</code>,
1146 <code>spfac.fromInteger(1)</code>, <code>spfac.random(3)</code>
1147 or <code>spfac.parse("(1)")</code>.
1148 Some care is needed to create <code>RelationTable</code> objects
1149 since its constructor requires the solvable polynomial ring which
1150 is under construction as parameter. It is most convenient to first
1151 create a <code>GenSolvablePolynomialRing</code> with an
1152 empty relation table and then to add the defining relations.
1153 </p>
1154
1155
1156 <h2>5. Ring element and factory functionality</h2>
1157
1158 <p>
1159 The following sections and the next figure gives an overview
1160 of the functionality of the main interfaces and polynomial classes.
1161 </p>
1162
1163 <p>
1164 The <code>RingElem</code> interface has a generic type parameter
1165 <code>C</code> which is constrained to a type with the same functionality
1166 <code>C extends RingElem&lt;C&gt;</code>.
1167 It defines the usual methods required for ring arithmetic such as
1168 <code>C sum(C S); C subtract(C S); C negate(); C abs();
1169 C multiply(C S); C divide(C S); C remainder(C S); C inverse();
1170 </code>
1171 Although the actual ring may not have inverses for every element
1172 or some division algorithm we have included these methods in the definition.
1173 In a case where there is no such function, the implementation may
1174 deliberately throw a <code>RuntimeException</code> or choose some
1175 other meaningful element to return.
1176 The method <code>isUnit()</code> can be used to check if an element
1177 is invertible.
1178 </p>
1179 <p>
1180 Besides the arithmetic method there are following testing methods
1181 <code>boolean isZERO(); boolean isONE(); boolean isUnit();
1182 int signum();
1183 boolean equals(Object b); int hashCode(); int compareTo(C b);
1184 </code>
1185 The first three test if the element is 0, 1 or a unit in the respective ring.
1186 The <code>signum()</code> method defines the sign of the element (in case
1187 of an ordered ring).
1188 <code>equals()</code>, <code>hashCode()</code> and <code>compareTo()</code>
1189 are required to keep Javas object machinery working in our sense.
1190 They are used when an element is put into a Java collection class,
1191 e.g. <code>Set</code>, <code>Map</code> or <code>SortedMap</code>.
1192 The last method <code>C clone()</code> can be used to obtain a copy of the
1193 actual element. As creational method one should better use the
1194 method <code>C copy(C a)</code> from the ring factory, but in Java
1195 it is more convenient to use the <code>clone()</code> method.
1196 </p>
1197
1198 <p>
1199 As mentioned before, the creational aspects of rings are separated
1200 into a ring factory. A ring factory is intended to store all context
1201 information known or required for a specific ring.
1202 Every ring element should also know its ring factory, so all
1203 constructors of ring element implementations require a parameter
1204 for the corresponding ring factory. Unfortunately constructors
1205 and their signature can not be specified in a Java interface.
1206 The <code>RingFactory</code> interface also has a generic type parameter
1207 <code>C</code> which is constrained to a type with the ring element
1208 functionality <code>C extends RingElem&lt;C&gt;</code>.
1209 The defined methods are
1210 <code>C getZERO(); C getONE();
1211 C fromInteger(long a); C fromInteger(java.math.BigInteger a);
1212 C random(int n); C copy(C c);
1213 C parse(String s); C parse(Reader r);
1214 </code>
1215 The first two create 0 and 1 of the ring.
1216 The second two are used to embed a natural number into the ring
1217 and create the corresponding ring element.
1218 The <code>copy()</code> method was intended as the main means to
1219 obtain a copy of a ring element, but it is now no more used in our
1220 implmentation. Instead the <code>clone()</code> method is used from
1221 the ring element interface.
1222 The <code>random(int n)</code> method creates a random element of the
1223 respective ring. The parameter <code>n</code> specifies an appropriate
1224 maximal size for the created element. In case of coefficients it
1225 usually means the maximal bit-length of the element, in case of
1226 polynomials it influences the coefficient size and the degrees.
1227 For polynomials there are <code>random()</code> methods with more
1228 parameters.
1229 The two methods
1230 <code>C parse(String s)</code> and <code>C parse(Reader r)</code>
1231 create a ring element from some external string representation.
1232 For coefficients this is mostly implemented directly and for
1233 polynomials the class <code>GenPolynomialTokenizer</code> is
1234 employed internally.
1235 In the current implementation the external representation of
1236 coefficients may never contain white space and must always start
1237 with a digit.
1238 In the future the ring factory will be enhanced by methods that
1239 test if the ring is commutative, associative or has some
1240 other important property or the value of a property,
1241 e.g. is an euclidean ring, is a field, an integal domain,
1242 a uniqe factorization domain, its characteristic or if it is noetherian.
1243 </p>
1244
1245 <p class="center" >
1246 <a href="../images/overview-methods.png"
1247 target="diagram"
1248 ><img src="../images/overview-methods.png" alt="JAS type functionality" /></a>
1249 <br />
1250 UML diagram of JAS type functionality
1251 </p>
1252
1253
1254 <h2>6. Polynomial and polynomial factory functionality</h2>
1255
1256 <p>
1257 We continue the discussion of the above figure
1258 with the generic polynomial and factory classes.
1259 </p>
1260
1261 <p>
1262 The <code>GenPolynomial</code> class has a generic type parameter
1263 <code>C</code> which is constrained to a type with the functionality
1264 of ring elements <code>C extends RingElem&lt;C&gt;</code>.
1265 Further the class implements a <code>RingElem</code> over itself
1266 <code>RingElem&lt;GenPolynomial&lt;C&gt;&gt;</code>
1267 so that it can be used for the coefficients of an other polynomial ring.
1268 The functionality of the ring element methods has already been explained
1269 in the previous section.
1270 There are two public and one protected constructors, each requires
1271 at least a ring factory parameter <code>GenPolynomialRing&lt;C&gt; r</code>.
1272 The first creates a zero polynomial
1273 <code>GenPolynomial(. r)</code>,
1274 the second creates a polynomial of one monomial with given coefficient
1275 and exponent tuple
1276 <code>GenPolynomial(. r, C c, ExpVector e)</code>,
1277 the third creates a polynomial from the internal sorted map of an
1278 other polynomial
1279 <code>GenPolynomial(. r, SortedMap&lt;ExpVector,C&gt; v)</code>.
1280 Further there are methods to access parts of the polynomial
1281 like leading term, leading coefficient
1282 (still called leading base coefficient from the Aldes/SAC-2 tradition)
1283 and leading monomial.
1284 The <code>toString()</code> method creates as usual a string representation
1285 of the polynomials consisting of exponent tuples and coefficients.
1286 One variant of it takes an array of variable names and creates a string
1287 consisting of coefficients and products of powers of variables.
1288 The method <code>extend()</code> is used to embed the polynomial into the
1289 'bigger' polynomial ring specified in the first parameter.
1290 The embeded polynomial can also be multiplied by a power of a variable.
1291 The <code>contract()</code> method returns a map of exponents and
1292 coefficients. The coefficients are polynomials belonging to the
1293 'smaller' polynomial ring specified in the first parameter.
1294 If the polynomial actually belongs to the smaller polynomial ring
1295 the map will contain only one pair, mapping the zero exponent vector
1296 to the polynomial with variables removed.
1297 A last group of methods computes (extended) greatest common divisors.
1298 They work correct for univariate polynomials over a field but not
1299 for arbitrary multivatiate polynomials. These methods will be moved
1300 to a new separate class in the future.
1301 </p>
1302
1303 <p>
1304 The <code>GenPolynomialRing</code> class has a generic type parameter
1305 <code>C</code> which is constrained to a type with the functionality
1306 of ring elements <code>C extends RingElem&lt;C&gt;</code>.
1307 Further the class implements a <code>RingFactory</code> over
1308 <code>GenPolynomial&lt;C&gt;</code> so that it can be used as
1309 coefficient factory of a different polynomial ring.
1310 The constructors require at least a factory for the coefficents as
1311 first parameter of type <code>RingFactory&lt;C&gt;</code>
1312 and the number of variables in the second parameter.
1313 A third parameter can optionally specify a <code>TermOrder</code>
1314 and a fourth parameter can specify the names for the variables
1315 of the polynomial ring.
1316 Besides the methods required by the <code>RingFactory</code>
1317 interface there are additional <code>random()</code> methods
1318 which provide more control over the creation of random polynomials.
1319 They have the following parameters:
1320 the bitsize of random coefficients to be used in the
1321 <code>random()</code> method of the coefficient factory,
1322 the number of terms (i.e. the length of the polynomial),
1323 the maximal degree in each variable
1324 and the density of nozero exponents, i.e. the ratio of nonzero to
1325 zero exponents.
1326 The <code>toString()</code> method creates a string representation
1327 of the polynomial ring consisting of the coefficient factory string
1328 representation, the tuple of variable names and the string representation
1329 of the term order.
1330 The <code>extend()</code> and <code>contract()</code> methods
1331 create 'bigger' respectively 'smaller' polynomial rings.
1332 Both methods take a parameter of how many variables are to be added
1333 or removed form the actual polynomial ring.
1334 <code>extend()</code> will setup an elimination term order consisting
1335 of two times the actual term order when ever possible.
1336 </p>
1337
1338
1339 <h2>7. Solvable polynomial and solvable polynomial factory functionality</h2>
1340
1341 <p>
1342 We continue the discussion of the above figure
1343 with the generic solvable polynomial and factory classes.
1344 </p>
1345
1346 <p>
1347 The <code>GenSolvablePolynomial</code> class has a generic type parameter
1348 <code>C</code> which is constrained to a type with the functionality
1349 of ring elements <code>C extends RingElem&lt;C&gt;</code>.
1350 The class extends the <code>GenPolynomial</code> class. It inherits
1351 all additive functionality and overwrites the multiplicative
1352 functionality with a new non-commutative multiplication method.
1353 Unfortunately it <em>cannot</em> implement a <code>RingElem</code>
1354 over itself <code>RingElem&lt;GenSolvablePolynomial&lt;C&gt;&gt;</code>
1355 but can only inherit the implementation of
1356 <code>RingElem&lt;GenPolynomial&lt;C&gt;&gt;</code> from its super class.
1357 By this limitation a solvable polynomial can still be used as
1358 coefficent in another polynomial, but only with the type of its super
1359 class. The limitation comes form the erasure of template parameters in
1360 <code>RingElem&lt;...&gt;</code> to <code>RingElem</code> for the
1361 code generated. I.e. the generic interfaces become the same after
1362 type erasure and it is not allowed to implement the same interface twice.
1363 There are two public and one protected constructors as in the super class.
1364 Each requires at least a ring factory parameter
1365 <code>GenSolvablePolynomialRing&lt;C&gt; r</code>
1366 which is stored in a variable of this type shadowing the variable
1367 with the same name of the super factory type. The rest of the
1368 initialization work is delegated to the super class constructor.
1369 </p>
1370
1371 <p>
1372 The <code>GenSolvablePolynomialRing</code> class has a generic type parameter
1373 <code>C</code> which is constrained to a type with the functionality
1374 of ring elements <code>C extends RingElem&lt;C&gt;</code>.
1375 The class extends the <code>GenPolynomialRing</code> class.
1376 It overwrites most methods to implement the new non-commutative
1377 methods.
1378 Also this class cannot implement a <code>RingFactory</code> over
1379 <code>GenSolvablePolynomial&lt;C&gt;</code>. It only implements
1380 <code>RingFactory</code> over <code>GenPolynomial&lt;C&gt;</code>
1381 by inheritance by the same reason of type erasure as above.
1382 But it can be used as coefficient factory with the type of its super class
1383 for a different polynomial ring.
1384 One part of the constructors just restate the super class constructors
1385 with the actual solvable type. A solvable polynomial ring however
1386 must know how to perform the non-commutative multiplication.
1387 To this end a data structure with the respective commutator relations
1388 is required. It is implemented in the <code>RelationTable</code> class.
1389 The other part of the constructors additionaly takes a parameter of type
1390 <code>RelationTable</code> to set the initial commutator relation table.
1391 Some care is needed to create relation tables and solvable polynomial
1392 factories since the relation table requires a solvable polynomial
1393 factory as parameter in the constructor. So it is most advisable to
1394 create a solvable polynomial factory object with empty relation table
1395 and to fill it with commutator relations after the constructor is
1396 completed but before the factory will be used.
1397 There is also a new method <code>isAssociative()</code> which tries
1398 to check if the commutator relations indeed define an associative
1399 algebra. This method should be extracted to the <code>RingFactory</code>
1400 interface together with a method <code>isCommutative()</code>,
1401 since both are of general importance and not always fulfilled
1402 in our rings. E.g. <code>BigQuaternion</code> is not commutative
1403 and so is a polynomial ring over these coefficents is not commutative.
1404 The same applies to associativity and the (not jet existing) class
1405 <code>BigOctonion</code>.
1406 </p>
1407
1408 <p>
1409 This concludes the discussion of the main interfaces and classes
1410 of the Java algebra system.
1411 </p>
1412
1413
1414 <!--
1415 <code></code>
1416 <p>
1417 </p>
1418 <p>
1419 </p>
1420 <pre>
1421 </pre>
1422 -->
1423
1424 <p><!--a href="../README" target="readme" >README</a-->
1425 </p>
1426
1427 <hr />
1428 <address><a href="mailto:kredel at rz.uni-mannheim.de">Heinz Kredel</a></address>
1429 <p>
1430 <!-- Created: Sat Mar 11 10:51:36 CET 2006 -->
1431 <!-- hhmts start -->
1432 Last modified: Wed Mar 31 22:45:31 CEST 2021
1433 <!-- hhmts end -->
1434 </p>
1435 <!--p align="right" >
1436 $Id$
1437 </p-->
1438 </body>
1439 </html>