| 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 |
<title>JAS - Designs, Problems and Solutions</title> |
| 7 |
<style type="text/css"> |
| 8 |
body { background-color: #FFFFF5; } |
| 9 |
pre { background-color: silver; |
| 10 |
margin-left: 1em; |
| 11 |
margin-right: 1em; |
| 12 |
padding: 1em; |
| 13 |
} |
| 14 |
dt { font-weight: bolder; |
| 15 |
margin-top: 1em; |
| 16 |
} |
| 17 |
.note { color: maroon; } |
| 18 |
</style> |
| 19 |
</head> |
| 20 |
<body> |
| 21 |
<h1>JAS - Designs, Problems and Solutions</h1> |
| 22 |
|
| 23 |
<p>In ths document we discus some design alternatives, |
| 24 |
some problems and present our implemented solutions. |
| 25 |
</p> |
| 26 |
|
| 27 |
|
| 28 |
<h2>1. Designs</h2> |
| 29 |
|
| 30 |
<p><strong>Note:</strong> |
| 31 |
In this section 'base ring' |
| 32 |
and 'extension ring' mean object oriented concepts not |
| 33 |
the mathematical concepts. I.e. 'base ring' is the super class |
| 34 |
of all considered ring classes and 'extension ring' is some |
| 35 |
subclass of the 'base ring' class. |
| 36 |
</p> |
| 37 |
|
| 38 |
<p>The first question is which classes or which objects |
| 39 |
implement the arithmetic of polynomials. Are polynomials |
| 40 |
only passive containers which are transformed by ring methods? |
| 41 |
Or are polynomials active objects with methods. |
| 42 |
</p> |
| 43 |
|
| 44 |
|
| 45 |
<h3>1.1. Ring is object with methods</h3> |
| 46 |
|
| 47 |
<p> |
| 48 |
One design was proposed e.g. by M. Conrad in 2002 |
| 49 |
(see <a href="http://ring.perisic.com/">ring.perisic.com</a>). |
| 50 |
It starts with an abstract <code>Ring</code> with abstract |
| 51 |
methods for the ring operations and some real implementations, |
| 52 |
e.g. for powers. The method parameters are <code>RingElt</code>s, |
| 53 |
which serve mostly as containers for the different ring |
| 54 |
implementations. The concrete rings, e.g. rational numbers |
| 55 |
or polynomials, extend <code>Ring</code> and implement the |
| 56 |
algortihms for the respective (extended) <code>RingElt</code> |
| 57 |
data structures. <code>RingElt</code> structures are moreover |
| 58 |
mostly private classes within their corresponding <code>Ring</code> |
| 59 |
extension. |
| 60 |
</p> |
| 61 |
<p> |
| 62 |
Type resolution of the parameters of the methods is completely dynamic |
| 63 |
during runtime. There is no compile time type checking. |
| 64 |
The type resolution, by means of a <code>RingX.map(RingElt)</code> |
| 65 |
method, is moreover able to coerce elements from one ring to |
| 66 |
some other ring, e.g. form rational to polynomial over rationals, |
| 67 |
similar to Scratchpad. |
| 68 |
The base <code>Ring</code> knows about all extension rings, like in |
| 69 |
a closed world. |
| 70 |
</p> |
| 71 |
<p> |
| 72 |
Creation of extension rings is mainly at initialization time of the |
| 73 |
base ring (since it knows all extensions) into ring properties. |
| 74 |
Creation of ring elements is mostly dynamic using direct constructors |
| 75 |
in the various <code>map()</code> methods. |
| 76 |
</p> |
| 77 |
|
| 78 |
|
| 79 |
|
| 80 |
<h3>1.2. Polynomial is object with methods</h3> |
| 81 |
|
| 82 |
<p> |
| 83 |
An other design, e.g. used in our approach, takes polynomials as |
| 84 |
the primary players. A <code>Polynomial</code> is implemented as |
| 85 |
a class with the usual algebraic operations as methods. |
| 86 |
Each polynomial has a reference to a corresponding <code>Ring</code> |
| 87 |
object, which is a container for the ring characteristics. E.g. |
| 88 |
for polynomial rings these are the number of variables, the |
| 89 |
type information of the coefficent ring, the term order, |
| 90 |
the names of the variables and eventualy the commutator relations. |
| 91 |
There is one proposal by V. Niculescu, from 2003, |
| 92 |
[ref: |
| 93 |
<a href="http://www.cs.ubbcluj.ro/~vniculescu/Niculescu-03i1.zip" |
| 94 |
>A design proposal for an object oriented algebraic library</a>] |
| 95 |
to view and implement the <code>Ring</code> as a factory class |
| 96 |
for polynomials and to make the polynomial constructors unavailable. |
| 97 |
</p> |
| 98 |
<p> |
| 99 |
Creation of ring elements was in our first design by employing the |
| 100 |
prototype creational pattern (via <code>clone()</code>) |
| 101 |
and directly using element constructors. In the new design it |
| 102 |
will use the factory pattern (via <code>getZERO()</code>, |
| 103 |
<code>getONE()</code> etc.) of the <code>RingFactory</code> |
| 104 |
</p> |
| 105 |
<p> |
| 106 |
Type resolution of the coefficient or polynomial method parameters are |
| 107 |
to the respective interface during compile time with a dynamic upcast |
| 108 |
to the actual polynomial or coefficient during runtime. |
| 109 |
There is currently no mapping of elements from one ring to |
| 110 |
another. However there are conversions / constructor / parser methods |
| 111 |
from <code>long</code>, <code>java.math.BigInteger</code>, |
| 112 |
<code>String</code> and <code>java.io.Reader</code> in the new design. |
| 113 |
</p> |
| 114 |
|
| 115 |
|
| 116 |
<h3>1.3. Template, generics and type parameter approaches</h3> |
| 117 |
|
| 118 |
<p> |
| 119 |
These approaches may not be completely covered by Java, C++ or C#. |
| 120 |
For polynomials they mean the usage of a type parameter (eventually |
| 121 |
restricted to some unterface) for the coefficient ring. |
| 122 |
</p> |
| 123 |
<p> |
| 124 |
The creation problem is difficult to solve in Java, since |
| 125 |
type parameters can not be used in <code>new</code> |
| 126 |
or <code>class.newInstance()</code>. I.e. new objects can not be |
| 127 |
generated only from a type parameter but only from an object or class. |
| 128 |
</p> |
| 129 |
|
| 130 |
|
| 131 |
|
| 132 |
<h2>2. Problems</h2> |
| 133 |
|
| 134 |
<p>During the development and refactorings |
| 135 |
<!--no to use type parmeters (generics, templates) --> |
| 136 |
some problems have been detected. |
| 137 |
Consider the following interface and class definitions. |
| 138 |
</p> |
| 139 |
|
| 140 |
<pre> |
| 141 |
interface ModulElem { |
| 142 |
ModulElem sum(ModulElem other); |
| 143 |
... |
| 144 |
} |
| 145 |
|
| 146 |
interface RingElem extends ModulElem { |
| 147 |
// RingElem sum(RingElem other); no override |
| 148 |
RingElem multiply(RingElem other); |
| 149 |
... |
| 150 |
} |
| 151 |
|
| 152 |
class Rational implements RingElem { // jdk 1.5 |
| 153 |
|
| 154 |
/*ModulElem*/ Rational sum(ModulElem other) { |
| 155 |
... |
| 156 |
} |
| 157 |
|
| 158 |
/*RingElem*/ Rational multiply(RingElem other) { |
| 159 |
if ( other instanceof Rational ) { |
| 160 |
return multiply( (Rational)other ); |
| 161 |
} else { |
| 162 |
return // coerce to suitable ring extension |
| 163 |
} |
| 164 |
} |
| 165 |
|
| 166 |
Rational multiply(Rational other) { |
| 167 |
... |
| 168 |
} |
| 169 |
|
| 170 |
} |
| 171 |
|
| 172 |
class Complex implements RingElem { |
| 173 |
... |
| 174 |
} |
| 175 |
|
| 176 |
void usageOK() { |
| 177 |
Rational a = new Rational(); |
| 178 |
Rational b = new Rational(); |
| 179 |
Rational c; |
| 180 |
c = a.sum(b); // jdk 1.5 |
| 181 |
c = a.multiply(b); // jdk 1.5 |
| 182 |
} |
| 183 |
|
| 184 |
void usageProblem1() { |
| 185 |
RingElem a = new Rational(); |
| 186 |
RingElem b = new Rational(); |
| 187 |
RingElem c; |
| 188 |
c = (RingElem) a.sum(b); // must cast |
| 189 |
c = a.multiply(b); // no cast |
| 190 |
} |
| 191 |
|
| 192 |
void usageProblem2() { |
| 193 |
RingElem a = new Rational(); |
| 194 |
RingElem b = new Complex(); |
| 195 |
RingElem c; |
| 196 |
c = a.multiply(b); // runtime failiure |
| 197 |
} |
| 198 |
</pre> |
| 199 |
|
| 200 |
<p> |
| 201 |
One problem is the cast in |
| 202 |
<code>c = (RingElem)a.sum(b)</code> |
| 203 |
which is not expected since a and b are <code>RingElem</code>s. |
| 204 |
One sulution would be to redefine <code>sum()</code> for |
| 205 |
<code>RingElem</code>, but then <code>sum()</code> in |
| 206 |
<code>ModulElem</code> is not overriden. |
| 207 |
Then <code>RingElem</code> is no longer an extension of |
| 208 |
<code>ModulElem</code> and the relation between the |
| 209 |
interfaces is broken. |
| 210 |
</p> |
| 211 |
|
| 212 |
<p> |
| 213 |
The other problem is 'up cast' in |
| 214 |
<code>return multiply( (Rational)other )</code> |
| 215 |
which defeates compile time type safety. |
| 216 |
<code>multiply( )</code> is at first not meaningful defined |
| 217 |
between <code>Rational</code> and <code>Complex</code>. |
| 218 |
One could as in Scratchpad coerce <code>Rational</code> |
| 219 |
to <code>Complex</code> (here extend) and multiply to |
| 220 |
<code>Complex</code> objects, but this may not be expected |
| 221 |
by the application. |
| 222 |
</p> |
| 223 |
|
| 224 |
<p> |
| 225 |
This problems exist also if abstract classes are used |
| 226 |
instead of interfaces. |
| 227 |
</p> |
| 228 |
|
| 229 |
|
| 230 |
<h2>3. Solutions</h2> |
| 231 |
|
| 232 |
<p>Reflecting on the mentioned designs and problems our |
| 233 |
design proposal is as follows. |
| 234 |
</p> |
| 235 |
<ol> |
| 236 |
<li><p>We do not distinguish between interfaces for |
| 237 |
modules, rings or fields. There is only one interface |
| 238 |
for rings, wich also defines <code>inverse()</code> |
| 239 |
and <code>quotient()</code> together with |
| 240 |
a method <code>isUnit()</code> to see if a certain element is |
| 241 |
invertible or can be used as divisor. |
| 242 |
</p> |
| 243 |
</li> |
| 244 |
<li><p>To separate the creation process of ring elements |
| 245 |
from the implementation of the ring element |
| 246 |
abstract data type we distinguish two interfaces: |
| 247 |
<code>RingElem<C extends RingElem></code> |
| 248 |
and |
| 249 |
<code>RingFactory<C extends RingElem></code>. |
| 250 |
</p> |
| 251 |
</li> |
| 252 |
<li><p><code>RingElem</code> uses a type parameter |
| 253 |
<code>C</code> which is itself recursively reqired |
| 254 |
to extend <code>RingElem</code>: <code>C extends RingElem</code>. |
| 255 |
Also the interface <code>RingFactory</code> depends on the |
| 256 |
same type parameter. |
| 257 |
</p> |
| 258 |
</li> |
| 259 |
<li><p>Basic data types, such as rational numbers, can directly |
| 260 |
implement both interfaces but more complex data types, such |
| 261 |
as polynomials will implement the interfaces in two different |
| 262 |
classes. e.g. |
| 263 |
</p> |
| 264 |
<pre> |
| 265 |
BigRational implements RingElem<BigRational>, RingFactory<BigRational> |
| 266 |
</pre> |
| 267 |
<p>or for generic polynomials |
| 268 |
</p> |
| 269 |
<pre> |
| 270 |
GenPolynomial<C extends RingElem<C> > implements RingElem< GenPolynomial<C> > |
| 271 |
|
| 272 |
GenPolynomialRing<C extends RingElem<C> > implements RingFactory< GenPolynomial<C> > |
| 273 |
</pre> |
| 274 |
</li> |
| 275 |
<li><p>Constructors for basic data types can be implemented in any |
| 276 |
appropriate way. |
| 277 |
Constructors for more complex data types should always require one |
| 278 |
parameter to be of the respective factory type. This is to |
| 279 |
avoid the creation of elements with no knowledge of is corresponding |
| 280 |
ring factory. |
| 281 |
Constructors which require more preconditions, which are only |
| 282 |
provided by type (internal) methods should not be declared public. |
| 283 |
It seems best to declare them as protected. |
| 284 |
</p> |
| 285 |
</li> |
| 286 |
<li><p>Basic arithmetic is implemented using the |
| 287 |
<code>java.math.BigInteger</code> class, which |
| 288 |
is itself implemented like GnuMP. |
| 289 |
At the moment the following classes are implemented |
| 290 |
<code>BigInteger</code>, |
| 291 |
<code>BigRational</code>, |
| 292 |
<code>ModInteger</code>, |
| 293 |
<code>BigComplex</code>, |
| 294 |
<code>BigQuaternion</code> |
| 295 |
and <code>AlgebraicNumber</code>. |
| 296 |
</p> |
| 297 |
</li> |
| 298 |
<li><p>Generic polynomials are implemented as sorted maps from |
| 299 |
exponent vectors to coefficients. |
| 300 |
For sorted map the Java class <code>java.util.TreeMap</code> |
| 301 |
is used. |
| 302 |
The older alternative implementation using <code>Map</code>, |
| 303 |
implemented with <code>java.util.LinkedHashMap</code>, has |
| 304 |
been abandoned. |
| 305 |
There is only one implementation of exponent vectors |
| 306 |
<code>ExpVector</code> as dense Java array of <code>long</code>s. |
| 307 |
Other implementations, e.g. sparse representation or |
| 308 |
bigger numbers or <code>int</code>s are not considered |
| 309 |
at the moment. |
| 310 |
The comparators for <code>SortedMap<ExpVector,C></code> |
| 311 |
are created from a <code>TermOrder</code> class which |
| 312 |
implements most used term orders in practice. |
| 313 |
</p> |
| 314 |
</li> |
| 315 |
<li><p>Non commutative polynomials with respect to certain |
| 316 |
commutator relations, so called solvable polynomials, |
| 317 |
are extended from |
| 318 |
<code>GenPolynomial</code> respectively |
| 319 |
<code>GenPolynomialRing</code>. |
| 320 |
The relations are stored in <code>RelationTable</code> objects, |
| 321 |
which are inteded to be internal to the |
| 322 |
<code>GenSolvablePolynomialRing</code>. |
| 323 |
The class |
| 324 |
<code>GenSolvablePolynomial</code> implements the |
| 325 |
non commutative multiplication and uses the commutative |
| 326 |
methods from its super class <code>GenPolynomial</code>. |
| 327 |
As mentioned before, some casts are eventualy required, e.g. |
| 328 |
<code>GenSolvablePolynomial<C> p.sum(q)</code>. |
| 329 |
The respective objects are however correctly buildt |
| 330 |
using the methods from the solvable ring factory. |
| 331 |
<br /> |
| 332 |
The class design allows solvable polynomial objects to be |
| 333 |
used in all algorithms where <code>GenPolynomial</code>s |
| 334 |
can be used as parameters as long as no distinction between |
| 335 |
left and right multiplication is required. |
| 336 |
</p> |
| 337 |
</li> |
| 338 |
<!-- |
| 339 |
<li><p> |
| 340 |
</p> |
| 341 |
</li> |
| 342 |
--> |
| 343 |
</ol> |
| 344 |
|
| 345 |
|
| 346 |
<h3>3.1. Interfaces</h3> |
| 347 |
|
| 348 |
<p>The interface definition for ring elements with the usual |
| 349 |
arithmetic operations and some status, comparison methods |
| 350 |
and a clone method is as follows. |
| 351 |
</p> |
| 352 |
<pre> |
| 353 |
public interface RingElem<C extends RingElem> |
| 354 |
extends Cloneable, |
| 355 |
Comparable<C>, |
| 356 |
Serializable { |
| 357 |
public C clone(); |
| 358 |
|
| 359 |
public boolean isZERO(); |
| 360 |
public boolean isONE(); |
| 361 |
public boolean isUnit(); |
| 362 |
public boolean equals(Object b); |
| 363 |
public int hashCode(); |
| 364 |
public int compareTo(C b); |
| 365 |
public int signum(); |
| 366 |
|
| 367 |
public C sum(C S); |
| 368 |
public C subtract(C S); |
| 369 |
public C negate(); |
| 370 |
public C abs(); |
| 371 |
public C multiply(C S); |
| 372 |
public C divide(C S); |
| 373 |
public C remainder(C S); |
| 374 |
public C inverse(); |
| 375 |
} |
| 376 |
</pre> |
| 377 |
|
| 378 |
<p>The interface definition for a ring factory for the creation |
| 379 |
respectively the reference to the ring constants 0 and 1 is given |
| 380 |
in the following code. Moreover there are often used casts / |
| 381 |
conversions from the basic Java types long and BigInteger, |
| 382 |
as well as a method to create a random element of the ring, |
| 383 |
a counter part to clone and some parsing methods to obtain |
| 384 |
a ring element from some external String or Reader. |
| 385 |
</p> |
| 386 |
<pre> |
| 387 |
public interface RingFactory<C extends RingElem> |
| 388 |
extends Serializable { |
| 389 |
public C getZERO(); |
| 390 |
public C getONE(); |
| 391 |
|
| 392 |
public C fromInteger(long a); |
| 393 |
public C fromInteger(BigInteger a); |
| 394 |
|
| 395 |
public C random(int n); |
| 396 |
public C copy(C c); |
| 397 |
|
| 398 |
public C parse(String s); |
| 399 |
public C parse(Reader r); |
| 400 |
} |
| 401 |
</pre> |
| 402 |
|
| 403 |
|
| 404 |
<h3>3.2. Some constructors</h3> |
| 405 |
|
| 406 |
<p>Constructors for BigRational: |
| 407 |
</p> |
| 408 |
<pre> |
| 409 |
protected BigRational(BigInteger n, BigInteger d) |
| 410 |
// assert gcd(n,d) == 1 |
| 411 |
public BigRational(BigInteger n) |
| 412 |
public BigRational(long n, long d) |
| 413 |
public BigRational(long n) |
| 414 |
public BigRational() |
| 415 |
public BigRational(String s) throws NumberFormatException |
| 416 |
</pre> |
| 417 |
|
| 418 |
<p>Constructors for GenPolynomial |
| 419 |
</p> |
| 420 |
<pre> |
| 421 |
public GenPolynomial(GenPolynomialRing< C > r) |
| 422 |
public GenPolynomial(GenPolynomialRing< C > r, SortedMap<ExpVector,C> v) |
| 423 |
public GenPolynomial(GenPolynomialRing< C > r, C c, ExpVector e) |
| 424 |
</pre> |
| 425 |
|
| 426 |
<p>Constructors for GenPolynomialRing |
| 427 |
</p> |
| 428 |
<pre> |
| 429 |
public GenPolynomialRing(RingFactory< C > cf, int n) |
| 430 |
public GenPolynomialRing(RingFactory< C > cf, int n, TermOrder t) { |
| 431 |
public GenPolynomialRing(RingFactory< C > cf, int n, TermOrder t, String[] v) |
| 432 |
</pre> |
| 433 |
|
| 434 |
|
| 435 |
<h3>3.3. Polynomial examples</h3> |
| 436 |
|
| 437 |
<p>Example of a |
| 438 |
random polynomial in 7 variables over the rational numbers |
| 439 |
with default term order and with 10 non zero coefficients: |
| 440 |
</p> |
| 441 |
<pre> |
| 442 |
BigRational cfac = new BigRational(); |
| 443 |
GenPolynomialRing<BigRational> fac; |
| 444 |
fac = new GenPolynomialRing<BigRational>(cfac,7); |
| 445 |
|
| 446 |
GenPolynomial<BigRational> a = fac.random(10); |
| 447 |
|
| 448 |
a = GenPolynomial[ 31/5 (0,0,0,1,2,1,2), 19/15 (2,0,0,0,0,0,2), |
| 449 |
13/5 (0,2,1,1,0,0,0), 2/3 (0,0,2,0,0,0,0), 217/18 (0,0,0,2,0,0,0), |
| 450 |
18/5 (0,0,0,0,2,0,0), 11/32 (1,0,0,0,0,0,0), 63/4 (0,0,0,0,0,0,0) ] |
| 451 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] |
| 452 |
</pre> |
| 453 |
|
| 454 |
<p>Example of a |
| 455 |
random polynomial in 3 variables over a polynomial ring in 7 variables |
| 456 |
over the rational numbers, both with default term order and |
| 457 |
with 10 non zero coefficients: |
| 458 |
</p> |
| 459 |
<pre> |
| 460 |
BigRational cfac = new BigRational(); |
| 461 |
GenPolynomialRing<BigRational> fac; |
| 462 |
fac = new GenPolynomialRing<BigRational>(cfac,7); |
| 463 |
|
| 464 |
GenPolynomialRing<GenPolynomial<BigRational>> gfac; |
| 465 |
gfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac,3); |
| 466 |
|
| 467 |
GenPolynomial<GenPolynomial<BigRational>> a = gfac.random(10); |
| 468 |
|
| 469 |
a = GenPolynomial[ |
| 470 |
GenPolynomial[ 10/3 (2,0,1,1,0,0,2), 8/7 (1,0,2,0,0,0,0), |
| 471 |
9/5 (0,1,0,0,0,0,0), 1/4 (0,0,1,0,0,0,0), 3/14 (0,0,0,0,0,0,0) ] |
| 472 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (2,1,0), |
| 473 |
GenPolynomial[ 26/23 (0,2,2,0,1,0,2), 9/4 (1,0,0,0,0,1,1), |
| 474 |
29/17 (0,0,2,0,1,0,0), 24/19 (2,0,0,0,0,0,0), 28/13 (1,0,0,1,0,0,0), |
| 475 |
11/32 (0,0,1,0,1,0,0), 18/11 (1,0,0,0,0,0,0), 5/11 (0,0,0,0,1,0,0), |
| 476 |
475/32 (0,0,0,0,0,0,0) ] |
| 477 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (2,0,0), |
| 478 |
GenPolynomial[ 14/15 (2,0,0,1,1,0,2), 19/5 (1,1,0,0,0,0,0), |
| 479 |
4/29 (0,0,2,0,0,0,0), 23/27 (0,0,0,2,0,0,0), 20/13 (0,0,0,0,0,0,0) ] |
| 480 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (0,0,2), |
| 481 |
GenPolynomial[ 13/8 (2,0,0,1,1,0,0), 8/7 (2,0,0,0,0,0,2), |
| 482 |
21/2 (0,0,1,0,0,0,2), 23/22 (0,1,0,0,0,1,0), 9/11 (0,0,0,2,0,0,0), |
| 483 |
21/2 (0,0,0,0,2,0,0), 23/13 (0,0,0,0,0,2,0), 5/2 (0,1,0,0,0,0,0), |
| 484 |
367/62 (0,0,0,0,0,0,0) ] |
| 485 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (1,0,0), |
| 486 |
GenPolynomial[ 4/3 (0,1,0,1,2,1,1), 17/2 (2,1,0,0,2,0,0), |
| 487 |
10/29 (1,0,0,0,0,2,2), 3/2 (0,0,2,2,0,0,1), 11/8 (2,0,0,0,0,0,2), |
| 488 |
26/31 (0,2,1,0,0,0,0), 10/9 (0,0,1,2,0,0,0), 4/5 (0,0,1,0,0,2,0), |
| 489 |
1/8 (2,0,0,0,0,0,0), 1161/406 (0,2,0,0,0,0,0), 31/6 (0,0,0,2,0,0,0), |
| 490 |
19 (0,0,1,0,0,0,0), 2 (0,0,0,0,0,1,0), 7/19 (0,0,0,0,0,0,1), |
| 491 |
20227/2520 (0,0,0,0,0,0,0) ] |
| 492 |
:: GenPolynomialRing[ BigRational, 7, IGRLEX(4), ] (0,0,0) ] |
| 493 |
:: GenPolynomialRing[ GenPolynomialRing, 3, IGRLEX(4), ] |
| 494 |
</pre> |
| 495 |
|
| 496 |
|
| 497 |
<h3>3.4. Algebraic number examples</h3> |
| 498 |
|
| 499 |
<p>Example of algebraic numbers |
| 500 |
</p> |
| 501 |
<pre> |
| 502 |
AlgebraicNumber<C extends RingElem<C> > |
| 503 |
implements RingElem< AlgebraicNumber<C> >, |
| 504 |
RingFactory< AlgebraicNumber<C> > |
| 505 |
</pre> |
| 506 |
|
| 507 |
<p>over rational numbers (so defining an algebraic extension Q(alpha)) |
| 508 |
</p> |
| 509 |
<pre> |
| 510 |
BigRational cfac = new BigRational(); |
| 511 |
|
| 512 |
GenPolynomialRing<BigRational> mfac; |
| 513 |
mfac = new GenPolynomialRing<BigRational>( cfac, 1 ); |
| 514 |
|
| 515 |
GenPolynomial<BigRational> modul = mfac.random(8).monic(); |
| 516 |
// assume !modul.isUnit() |
| 517 |
|
| 518 |
AlgebraicNumber<BigRational> fac; |
| 519 |
fac = new AlgebraicNumber<BigRational>( modul ); |
| 520 |
|
| 521 |
AlgebraicNumber< BigRational > a = fac.random(15); |
| 522 |
|
| 523 |
modul = GenPolynomial[ 1 (2), 13/12 (1), 55/21 (0) ] |
| 524 |
:: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] |
| 525 |
|
| 526 |
a = AlgebraicNumber[ |
| 527 |
GenPolynomial[ 1 (1), -175698982/14106209 (0) ] |
| 528 |
:: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] |
| 529 |
mod |
| 530 |
GenPolynomial[ 1 (2), 13/12 (1), 55/21 (0) ] |
| 531 |
:: GenPolynomialRing[ BigRational, 1, IGRLEX(4), ] ] |
| 532 |
</pre> |
| 533 |
|
| 534 |
<p>or modular integers (so defining a Galois field GF(p,n)). |
| 535 |
</p> |
| 536 |
<pre> |
| 537 |
long prime = getPrime(); // 2^60-93 |
| 538 |
ModInteger cfac = new ModInteger(prime,1); |
| 539 |
|
| 540 |
GenPolynomialRing<ModInteger> mfac; |
| 541 |
mfac = new GenPolynomialRing<ModInteger>( cfac, 1 ); |
| 542 |
|
| 543 |
GenPolynomial<ModInteger> modul = mfac.random(8).monic(); |
| 544 |
// assume !modul.isUnit() |
| 545 |
|
| 546 |
AlgebraicNumber<ModInteger> fac; |
| 547 |
fac = new AlgebraicNumber<ModInteger>( modul ); |
| 548 |
|
| 549 |
AlgebraicNumber< ModInteger > a = fac.random(12); |
| 550 |
|
| 551 |
modul = GenPolynomial[ 1 mod(1152921504606846883) (2), |
| 552 |
123527304065019309 mod(1152921504606846883) (1), |
| 553 |
452933448238404135 mod(1152921504606846883) (0) ] |
| 554 |
:: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] |
| 555 |
|
| 556 |
a = AlgebraicNumber[ |
| 557 |
GenPolynomial[ 1 mod(1152921504606846883) (1), |
| 558 |
384307168202282226 mod(1152921504606846883) (0) ] |
| 559 |
:: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] |
| 560 |
mod |
| 561 |
GenPolynomial[ 1 mod(1152921504606846883) (2), |
| 562 |
123527304065019309 mod(1152921504606846883) (1), |
| 563 |
452933448238404135 mod(1152921504606846883) (0) ] |
| 564 |
:: GenPolynomialRing[ ModInteger, 1, IGRLEX(4), ] ] |
| 565 |
</pre> |
| 566 |
|
| 567 |
|
| 568 |
<h3>3.5. Solvable polynomial examples</h3> |
| 569 |
|
| 570 |
<p>Example for the creation of a solvable polynomial ring factory. |
| 571 |
The relation table is created internally. |
| 572 |
</p> |
| 573 |
<pre> |
| 574 |
BigRational fac = new BigRational(0); |
| 575 |
TermOrder tord = new TermOrder(TermOrder.INVLEX); |
| 576 |
String[] vars = new String[]{ "x", "y", "z" }; |
| 577 |
int nvar = vars.length; |
| 578 |
spfac = new GenSolvablePolynomialRing<BigRational>(fac,nvar,tord,vars); |
| 579 |
|
| 580 |
spfac = GenSolvablePolynomialRing[ BigRational, 3, |
| 581 |
INVLEX(2), x y z , |
| 582 |
#rel = 0 ] |
| 583 |
spfac.table = RelationTable[] |
| 584 |
</pre> |
| 585 |
|
| 586 |
<p>A non empty relation table looks as follows. |
| 587 |
</p> |
| 588 |
<pre> |
| 589 |
f = GenSolvablePolynomialRing[ BigRational, 3, INVLEX(2), x y z , #rel = 1 ] |
| 590 |
|
| 591 |
f.ring.table = RelationTable[ |
| 592 |
[0, 1]=[ExpVectorPair[(1,0,0),(0,1,0)], |
| 593 |
GenSolvablePolynomial[ 1 (1,1,0), -1 (0,0,0) ] |
| 594 |
:: GenSolvablePolynomialRing[ BigRational, 3, |
| 595 |
INVLEX(2), x y z , |
| 596 |
#rel = 1 ] |
| 597 |
] |
| 598 |
] |
| 599 |
</pre> |
| 600 |
|
| 601 |
<p>Example of a solvable polynomial over Z_19. |
| 602 |
</p> |
| 603 |
<pre> |
| 604 |
d = GenSolvablePolynomial[ 3 mod(19) (1,1,0), 1 mod(19) (0,0,1) ] |
| 605 |
:: GenSolvablePolynomialRing[ ModInteger, 3, INVLEX(2), x y z , #rel = 1 ] |
| 606 |
</pre> |
| 607 |
|
| 608 |
|
| 609 |
<!-- |
| 610 |
<p> |
| 611 |
</p> |
| 612 |
<pre> |
| 613 |
</pre> |
| 614 |
--> |
| 615 |
|
| 616 |
<p><!--a href="README" target="readme" >README</a--> |
| 617 |
</p> |
| 618 |
|
| 619 |
<hr /> |
| 620 |
<address><a href="mailto:kredel at rz.uni-mannheim.de">Heinz Kredel</a></address> |
| 621 |
<p> |
| 622 |
<!-- Created: Thu May 26 10:38:37 CEST 2005 --> |
| 623 |
<!-- hhmts start --> |
| 624 |
Last modified: Sun Mar 12 14:29:09 CET 2006 |
| 625 |
<!-- hhmts end --> |
| 626 |
</p> |
| 627 |
<p align="right" > |
| 628 |
$Id$ |
| 629 |
</p> |
| 630 |
</body> |
| 631 |
</html> |