| 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 /> |
| 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 <BigRational>(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<BigRational> ring |
| 92 |
= new GenPolynomialRing<BigRational>(fac,1,var); |
| 93 |
|
| 94 |
int n = 10; |
| 95 |
List<GenPolynomial<BigRational>> P |
| 96 |
= new ArrayList<GenPolynomial<BigRational>>(n); |
| 97 |
GenPolynomial<BigRational> 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 < 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 < 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<BigComplex> (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 </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<C></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<C></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<C></code> (not <code>RingFactory</code>). |
| 1028 |
The polynomial factory however implements the interface |
| 1029 |
<code>RingFactory<C extends RingElem<C>></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<C></code> to the desired coefficient type, |
| 1041 |
e.g. <code>BigRational</code>. So we arrive at the type |
| 1042 |
<code>GenPolynomial<BigRational></code>. |
| 1043 |
Polynomial objects are then created via the respective polynomial factory |
| 1044 |
of type <code>GenPolynomialRing<BigRational></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<BigRational>(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<GenPolynomial<BigRational>></code> |
| 1073 |
and the polynomial factory has type |
| 1074 |
<code>GenPolynomial<b>Ring</b><GenPolynomial<BigRational>></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<GenPolynomial<BigRational>>(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<C></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<C></code> to the desired coefficient type, |
| 1125 |
e.g. <code>BigRational</code>. So we have the type |
| 1126 |
<code>GenSolvablePolynomial<BigRational></code>. |
| 1127 |
Solvable polynomial objects are then created via the respective |
| 1128 |
solvable polynomial factory of type |
| 1129 |
<code>GenSolvablePolynomialRing<BigRational></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<BigRational>(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<C></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<C></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<C></code>. |
| 1265 |
Further the class implements a <code>RingElem</code> over itself |
| 1266 |
<code>RingElem<GenPolynomial<C>></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<C> 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<ExpVector,C> 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<C></code>. |
| 1307 |
Further the class implements a <code>RingFactory</code> over |
| 1308 |
<code>GenPolynomial<C></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<C></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<C></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<GenSolvablePolynomial<C>></code> |
| 1355 |
but can only inherit the implementation of |
| 1356 |
<code>RingElem<GenPolynomial<C>></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<...></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<C> 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<C></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<C></code>. It only implements |
| 1380 |
<code>RingFactory</code> over <code>GenPolynomial<C></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> |