| 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 project web-log</title> |
| 8 |
</head> |
| 9 |
<body class="main"> |
| 10 |
<h1>JAS project web-log</h1> |
| 11 |
|
| 12 |
<p>For a detailed list of the latest changes see the |
| 13 |
<a href="git_change.log" target="top">Git change log</a>. |
| 14 |
</p> |
| 15 |
|
| 16 |
<!-- |
| 17 |
<dt>2022, 1, </dt> < ! - - 2.6.60xx - - > |
| 18 |
<dd> |
| 19 |
</dd> |
| 20 |
<code></code> |
| 21 |
<code></code> |
| 22 |
--> |
| 23 |
|
| 24 |
<dl> |
| 25 |
|
| 26 |
<dt>2023, July </dt> <!-- 2.7.200 --> |
| 27 |
<dd> |
| 28 |
|
| 29 |
More tests with <code>BigQuaternion</code> polynomial coefficients. |
| 30 |
Fixed a left-right bug in solvable polynomials <code>monic()</code> |
| 31 |
method. (left and right monic must be distinguished although the |
| 32 |
inverse of the leading base coefficient is a left and right inverse.) |
| 33 |
Fix to <code>leftMonic()</code> where required. |
| 34 |
|
| 35 |
Adjust polynomial <code>reverse()</code> method with using |
| 36 |
<code>conjugate()</code> on coefficients. More tests for Ore |
| 37 |
conditions for polynomials with quaternion coefficients. |
| 38 |
|
| 39 |
Fixed default implementations in interface <code>MonoidElem</code> for |
| 40 |
left, right and two-sided operations by throwing exceptions when not |
| 41 |
correctly overriden. |
| 42 |
|
| 43 |
</dd> |
| 44 |
|
| 45 |
<dt>2023, May </dt> <!-- 2.7.190 --> |
| 46 |
<dd> |
| 47 |
This release adds exterior derivations for polynomials and rational |
| 48 |
functions. The weak or strong term order for index lists are now |
| 49 |
selectable. Explicit k-forms and improved random index lists. |
| 50 |
More non-commutative unit tests (quotient remainder, Ore conditions, |
| 51 |
common divisors) for solvable polynomials with quaternion |
| 52 |
coefficients. |
| 53 |
Exterior algebra provided within Jruby and Jython interfaces. |
| 54 |
Renamed <code>inner*Product()</code> to <code>interior*Product()</code> |
| 55 |
since this seems to be the correct translation. Remove and cleanup |
| 56 |
unsued experimental code and small bug fixes. Add file with simple |
| 57 |
NCSS report summary. |
| 58 |
</dd> |
| 59 |
|
| 60 |
<dt>2023, March </dt> <!-- 2.7.180 --> |
| 61 |
<dd> |
| 62 |
This release adds exterior algebra polynomials / vectors in classes |
| 63 |
<code>GenExteriorPolynomial</code> and |
| 64 |
<code>GenExteriorPolynomialRing</code>. With exterior multiplication |
| 65 |
and inner left / right multiplication methods. Also included are |
| 66 |
determinant and resultant methods via exterior algebra algorithms. |
| 67 |
Add new characteristic polynomial method <code>charPolynomial()</code> |
| 68 |
using Faddeev-LeVerrier algorithm in class |
| 69 |
<code>GenPolynomialRing</code>. Add <code>trace()</code>method in |
| 70 |
class <code>GenMatrix</code>. Fixed many spelling errors, small bug |
| 71 |
fixes and cleanups. |
| 72 |
</dd> |
| 73 |
|
| 74 |
<dt>2023, January </dt> <!-- 2.7.170 --> |
| 75 |
<dd> |
| 76 |
Added more unit test cases to improve code coverage of statement and |
| 77 |
expression tests together with eventual fixes, for example: exponent |
| 78 |
vector storage units, polynomial conversions, complex constants, |
| 79 |
runGB distributed cases, ideal decomposition mod prime, and right |
| 80 |
solvable multiplicaton. |
| 81 |
Ensure compatibility with JRuby version 9.4.0.0 (Ruby 3.1.0 |
| 82 |
compatible). Adjust for year 2023. Further cleanups and small bug |
| 83 |
fixes. |
| 84 |
</dd> |
| 85 |
|
| 86 |
<dt>2022, November </dt> <!-- 2.7.160/1 --> |
| 87 |
<dd> |
| 88 |
Introduce some right- and two-sided operations in |
| 89 |
<code>SolvableIdeal</code> to represent such ideals. Time-limited |
| 90 |
stop for long running or infinite word Groebner Base |
| 91 |
computations. Additionally counter stop configuration for long |
| 92 |
running Kronecker factorization algorithm cases, using <a |
| 93 |
href="https://github.com/kredel/java-algebra-system/pull/32">Pull |
| 94 |
request 32</a>. |
| 95 |
Fix bugs in <code>ExpVector</code> subclasses, in methods |
| 96 |
<code>setVal()</code>, this resolves <a |
| 97 |
href="https://github.com/kredel/java-algebra-system/issues/30">issue |
| 98 |
30</a>. Fix in <code>SquarefreeFieldCharP</code> for polynomial |
| 99 |
1. Fixes in <code>SquarefreeFieldChar0</code> and |
| 100 |
<code>SquarefreeRingChar0</code> for recursion to polynomial content. |
| 101 |
Fix in <code>PolyUfdUtilTest</code> of |
| 102 |
<code>evaluationPoints()</code> to ensure squarefree input. |
| 103 |
Added more unit test cases to improve code coverage of statement and |
| 104 |
expression tests. Further cleanups and bug fixes (see <a |
| 105 |
href="git_change.log">Git log</a>). |
| 106 |
</dd> |
| 107 |
|
| 108 |
<dt>2022, September </dt> <!-- 2.7.150 --> |
| 109 |
<dd> |
| 110 |
Tried to improve code in <code>Gen*PolynomialRing</code> constructors |
| 111 |
and method <code>getZERO()</code> with respect to Java memory model |
| 112 |
for problems appearing with Java OpenJDK version "11.0.15", |
| 113 |
2022-04-19 and still in "17.0.4", 2022-07-22. Added some unit tests |
| 114 |
to improve test coverage, for example <code>RunGB</code>, |
| 115 |
<code>RunSGB</code>, <code>IntegerProgram</code>, |
| 116 |
<code>StandardBaseSeq</code>, <code>jas.kern</code> utilities or |
| 117 |
<code>GenMatrix</code> and more. Added selectable |
| 118 |
<code>Quotient</code> normalizations, but only |
| 119 |
<code>QuoNorm.normDenLead</code> works in other parts of JAS. Other |
| 120 |
normalizations must be checked and code fixed (see <a |
| 121 |
href="https://github.com/kredel/java-algebra-system/issues/29">issue |
| 122 |
29</a>). Fix bug in <code>UnivPowerSeries</code> method |
| 123 |
<code>reductum()</code>. Fix bug in <code>ExpVector</code> |
| 124 |
constructor with respect to <code>hashCode()</code>. Verified again |
| 125 |
that JAS can be compiled and run with Java 17(.0.3) and jruby 9.2.14 |
| 126 |
and jython 2.7.2. |
| 127 |
</dd> |
| 128 |
|
| 129 |
<dt>2022, July </dt> <!-- 2.7.140 --> |
| 130 |
<dd> |
| 131 |
Fix spelling of names of <code>derivative</code> methods. Taylor |
| 132 |
series expansion for polynomial quotients. Some code moved from |
| 133 |
<code>edu.jas.ps</code> and <code>edu.jas.vector</code> to |
| 134 |
<code>edu.jas.ufd</code> to clear package dependency cycles. Pade |
| 135 |
approximation from Taylor series, in particular for polynomial |
| 136 |
quotients. |
| 137 |
</dd> |
| 138 |
|
| 139 |
<dt>2022, May </dt> <!-- 2.7.130 --> |
| 140 |
<dd> |
| 141 |
New methods <code>extGB()</code> and <code>inverse()</code> for d- |
| 142 |
and e-Groebner Bases in classes <code>DGroebnerBaseSeq</code> and via |
| 143 |
new reduction methods automatically in |
| 144 |
<code>EGroebnerBasesSeq</code>. Tests can reuse methods |
| 145 |
<code>isReductionMatrix()</code> and |
| 146 |
<code>isMinReductionMatrix()</code> from |
| 147 |
<code>GroebnerBaseAbstract</code>. Added missing methods for |
| 148 |
normalform, S-polynomial, G-Polynomial with recording in |
| 149 |
<code>DReduction</code>, <code>EReduction</code> interfaces and |
| 150 |
<code>DReductionSeq</code>, <code>EReductionSeq</code> classes. For |
| 151 |
scripting the respective methods <code>eExtGB</code>, |
| 152 |
<code>iseExtGB</code>, <code>eInverse</code> and |
| 153 |
<code>iseInverse</code> have been added to <code>Ideal</code> |
| 154 |
respectively <code>SimIdeal</code>. JAS can be compiled and run with |
| 155 |
Java 17, but no switch to Java 17 class files at the moment. The JAS |
| 156 |
debian package is build on Debian 11 bullseye with Java 17 and Jython |
| 157 |
2.7.2, so <code>jas.py</code> and <code>jas -py</code> scripts can be |
| 158 |
used again in Debian. |
| 159 |
</dd> |
| 160 |
|
| 161 |
<dt>2022, March </dt> <!-- 2.7.120 --> |
| 162 |
<dd> |
| 163 |
Fix multiplicities of complex roots in |
| 164 |
<code>ComplexRootsAbstract. complexRoots()</code>. Revisit recursive |
| 165 |
solvable polynomial algorithms and activate some missing test cases, |
| 166 |
resolve commutator table related todos, add missing right-multiply |
| 167 |
using methods from to do list |
| 168 |
(<code>SolvablePseudoReduction. rightNormalform</code>, |
| 169 |
<code>rightNormalformRecursive</code>, |
| 170 |
<code>rightNormalformFactor</code>). Related fixes and extensions in |
| 171 |
scripting frameworks. Update and revision of JAS web documentation. |
| 172 |
</dd> |
| 173 |
|
| 174 |
<dt>2022, January </dt> <!-- 2.7.110 --> |
| 175 |
<dd> |
| 176 |
Continue changes for Log4J version 2 API. Adjust year 2022. Improve |
| 177 |
maximal ideal check. Further cleanups and small fixes. |
| 178 |
</dd> |
| 179 |
|
| 180 |
<dt>2021, December </dt> <!-- 2.7.100 --> |
| 181 |
<dd> |
| 182 |
Continue changes for Log4J version 2 API. Update Log4j version |
| 183 |
because of potential CVE-2021-44228 vulnerability. |
| 184 |
</dd> |
| 185 |
|
| 186 |
<dt>2021, November, </dt> <!-- 2.7.90 --> |
| 187 |
<dd> |
| 188 |
Improved logging dependencies for JAS in Maven POM (see README or |
| 189 |
download). Started using the Log4J version 2 API. Small fixes and |
| 190 |
cleanups. |
| 191 |
</dd> |
| 192 |
|
| 193 |
<dt>2021, September </dt> <!-- 2.7.80 --> |
| 194 |
<dd> |
| 195 |
Fraction free Gauss elimination. Some matrix concatination |
| 196 |
operations. Choice of evaluation points for Hensel lifting. Some |
| 197 |
more polynomial utilities: reciprocal transformation, translation and |
| 198 |
evaluation. Missing algebraic number Jython examples. Cleanups and |
| 199 |
small bug fixes. |
| 200 |
</dd> |
| 201 |
|
| 202 |
<dt>2021, August </dt> <!-- 2.7.70 --> |
| 203 |
<dd> |
| 204 |
Factorization now provides Berlekamp, Cantor and Zassenhaus |
| 205 |
algorithms. Corresponding methods are contained in classes |
| 206 |
<code>ufd.PolyUfdUtil</code> and |
| 207 |
<code>ufd.FactorModularBerlekamp</code> and are called |
| 208 |
<code>contructQmatrix</code> and <code>baseFactorsSquarefree</code>. |
| 209 |
There are sub-methods for the small and big primes algorithm |
| 210 |
variants. Berlekamp factorization algorithm is now the default for |
| 211 |
polynomials over finite fields (algebraic extensions of prime |
| 212 |
fields), defined in <code>FactorFactory</code> for this case. |
| 213 |
<code>GenMatrix</code> is equiped with an <code>inverse</code> method |
| 214 |
with the help of <code>LinAlg.decomposeLU</code>. The extension field |
| 215 |
builder has a new method <code>matrixExtension</code> to provide |
| 216 |
matrix extension rings. A sparser form of a given row echelon matrix |
| 217 |
is computed by <code>rowEchelonFormSparse</code>. Some other small |
| 218 |
fixes and improvements. |
| 219 |
</dd> |
| 220 |
|
| 221 |
|
| 222 |
<dt>2021, July </dt> <!-- 2.7.60 --> |
| 223 |
<dd> |
| 224 |
Linear algebra package extended by LU decomposition, solution of |
| 225 |
systems of equations, matrix inversion, determinants, null space |
| 226 |
basis and row echelon form computation. Methods are called |
| 227 |
<code>decompositionLU</code>, <code>solveLU</code>, |
| 228 |
<code>determinantLU</code>, <code>inverseLU</code>, |
| 229 |
<code>nullSpaceBasis</code>, <code>rowEchelonForm</code> and |
| 230 |
<code>rankRE</code>. They are contained in class |
| 231 |
<code>vector.LinAlg</code>. Corresponding methods and examples for |
| 232 |
JRuby and Jython created. Methods <code>contFrac</code> and |
| 233 |
<code>contFracApprox</code> for continued fraction computation for |
| 234 |
JRuby and Jython. Further cleanups, improvements and small bug fixes. |
| 235 |
</dd> |
| 236 |
|
| 237 |
<dt>2021, June </dt> <!-- 2.7.50 --> |
| 238 |
<dd> |
| 239 |
New methods <code>chineseRemainderTheorem</code>, |
| 240 |
<code>isChineseRemainder</code> and <code>CRTInterpolation</code> in |
| 241 |
class <code>PolyGBUtil</code> for computing Chinese remainders for |
| 242 |
polynomials, polynomial interpolation and test. Together with |
| 243 |
corresponding methods and examples for JRuby and Jython. New class |
| 244 |
<code>SquarefreeFieldChar0Yun</code> with Yun's square-free |
| 245 |
decomposition algorithm. This is now the default algorithm in |
| 246 |
square-free factory methods since it is slightly faster. Other small |
| 247 |
fixes and improvements. Fix github deployment. |
| 248 |
</dd> |
| 249 |
|
| 250 |
<dt>2021, May </dt> <!-- 2.7.40 --> |
| 251 |
<dd> |
| 252 |
New method <code>factors</code> in class <code>PolyUfdUtil</code> for |
| 253 |
rational functions of class <code>Quotient</code>. New methods |
| 254 |
<code>subRing</code> and <code>subRingMember</code> in class |
| 255 |
<code>PolyGBUtil</code> for computing GB generators for polynomial |
| 256 |
subrings and membership tests. Together with analogous methods and |
| 257 |
examples for JRuby and Jython. More small improvements and fixes. |
| 258 |
</dd> |
| 259 |
|
| 260 |
<dt>2021, March </dt> <!-- 2.7.30 --> |
| 261 |
<dd> |
| 262 |
Methods for continued fractions of rational and real algebraic |
| 263 |
numbers. Improved heuristics for polynomial factorization. New real |
| 264 |
root methods related to Thom's lemma. Minimal root and root |
| 265 |
separation bounds. Some interval arithmetic, reimplement |
| 266 |
<code>excludeZero</code> method. Squarefree part fix in |
| 267 |
<code>edu.jas.root.</code> <code>ComplexRootsAbstract</code>. |
| 268 |
Delegate <code>compareTo</code> from <code>edu.jas.arith.</code> |
| 269 |
<code>BigDecimal</code> to <code>java.math.</code> |
| 270 |
<code>BigDecimal</code>. More unit tests for missing cases. Further |
| 271 |
code cleanup by Eclipse rules, small fixes and improvements. |
| 272 |
</dd> |
| 273 |
|
| 274 |
<dt>2021, February </dt> <!-- 2.7.20 --> |
| 275 |
<dd> |
| 276 |
In this release the source and classes are switched to Java 11, Log4j |
| 277 |
2.13.2, JRuby 9.2.14.0 and Jython 2.7.2 with some fixes. For example |
| 278 |
the deprecated JRuby <code>mathn</code> module for rational number |
| 279 |
input had to be replaced. JavaDoc is now generated in HTML5, tags and |
| 280 |
entities in method descriptions fixed. Internal calls to deprecated |
| 281 |
<code>PseudoRemainder</code> methods are replaced. Termination |
| 282 |
detection in <code>GreatestCommonDivisorModEval</code> was fixed. A |
| 283 |
new parsing method for <code>WordPolynomial</code>s was added. The |
| 284 |
<a href="https://symbolicdata.github.io/" |
| 285 |
target="new">SymbolicData</a> test are deactivated as its servers |
| 286 |
have been terminated. Further cleanups, improvements and small bug |
| 287 |
fixes. |
| 288 |
</dd> |
| 289 |
|
| 290 |
<dt>2021, January </dt> <!-- 2.7.10 --> |
| 291 |
<dd> |
| 292 |
Switch from SVN to Git, so the SVN revision number will no more be |
| 293 |
part of the JAS version. Several small fixes for some issues found |
| 294 |
by <a href="https://lgtm.com/" target="new">LGTM</a>. For example, |
| 295 |
<code>hashCode</code>, potential <code>int, long</code> overflows and |
| 296 |
parameter typos in Javadoc. |
| 297 |
<b>Note:</b> From JAS version 2.7 on, the deprecated methods and |
| 298 |
classes might be removed. |
| 299 |
</dd> |
| 300 |
|
| 301 |
<dt>2020, December, 13th </dt> <!-- 2.6.6027 --> |
| 302 |
<dd> |
| 303 |
Undo error in selection of evaluation points in factorization of |
| 304 |
polynomials with integer coeffcients. Fix in Debian package. |
| 305 |
</dd> |
| 306 |
|
| 307 |
<dt>2020, December </dt> <!-- 2.6.6025 --> |
| 308 |
<dd> |
| 309 |
In polynomial factorization check and force INVLEX term ordering. |
| 310 |
Improve special case of polynomials with positive degree of |
| 311 |
trailing term in squarefree decomposition. |
| 312 |
</dd> |
| 313 |
|
| 314 |
<dt>2020, May </dt> <!-- 2.6.6017 --> |
| 315 |
<dd> |
| 316 |
Cleanup auto generated variable names. Some new tests and examples. |
| 317 |
Reduce heap memory requirements, see issue <a |
| 318 |
href="https://github.com/kredel/java-algebra-system/issues/12" |
| 319 |
target="new">#12</a>. Fix / improve Debian <code>lintian</code> |
| 320 |
errors. Remove Javadoc reserved <code>@usage</code> tag from source |
| 321 |
and cleanup comments. Further cleanups and bug fixes. |
| 322 |
</dd> |
| 323 |
|
| 324 |
<dt>2020, March </dt> <!-- 2.6.6000 --> |
| 325 |
<dd> |
| 326 |
Fixed/improved issue <a |
| 327 |
href="https://github.com/kredel/java-algebra-system/issues/12" |
| 328 |
target="new">#12</a>. Further improvements, cleanups and small bug |
| 329 |
fixes. |
| 330 |
</dd> |
| 331 |
|
| 332 |
<dt>2019, April </dt> <!-- 2.6.5988 --> |
| 333 |
<dd> |
| 334 |
Improve factorization of multivariate polynomials with algebraic |
| 335 |
number coefficients by avoiding Kronecker reduction from multivariate |
| 336 |
polynomials to univariate polynomials. Do not use ModEval greatest |
| 337 |
common divisor computations for too small field coefficients of |
| 338 |
polynomials. |
| 339 |
New finite field constructors <code>FF(p,n)</code> in JAS scripting |
| 340 |
interfaces. |
| 341 |
Update to Jruby 9.1.7 in JRuby interface to JAS. Installation of |
| 342 |
<code>configparser</code> necessary, <code>require mathn</code> and |
| 343 |
<code>require Matrix</code> in some place. Other small improvements |
| 344 |
and bug fixes. |
| 345 |
</dd> |
| 346 |
|
| 347 |
<dt>2018, November </dt> <!-- 2.6.5961 --> |
| 348 |
<dd> |
| 349 |
New <code>mapOnStream()</code> methods implemented operating on |
| 350 |
(parallel) stream map methods of polynomial monomials. Performance |
| 351 |
seems to be worse by factors compared to non stream method variants. |
| 352 |
Provide a spliterator over monomials for polynomials via a new |
| 353 |
<code>spliterator()</code> method and class |
| 354 |
<code>PolySpliterator</code>. |
| 355 |
Polynomial absolute norm implemented and some improvements for square |
| 356 |
roots. |
| 357 |
Converted the usages of <code>edu.jas.util.ThreadPool</code> to |
| 358 |
<code>java.util.concurrent.ThreadpoolExecutor</code>. |
| 359 |
Checked that JAS compiles and runs with Java 11 (without module |
| 360 |
definition). Bug fixes and other small improvements. |
| 361 |
</dd> |
| 362 |
|
| 363 |
<dt>2018, October </dt> <!-- 2.6.5938 --> |
| 364 |
<dd> |
| 365 |
New smaller modular coefficients in <code>ModInt</code> and |
| 366 |
<code>ModIntRing</code> based on <code>int</code> integers. |
| 367 |
Performance improvements for polynomial <code>sum()</code> method for |
| 368 |
polynomials with unbalanced size. <code>sqrt()</code> |
| 369 |
approximation for <code>BigRational</code> and tests fixed for |
| 370 |
complex <code>abs()</code> methods. |
| 371 |
Further small improvements and bug fixes. |
| 372 |
</dd> |
| 373 |
|
| 374 |
<dt>2018, August </dt> <!-- 2.6.5918 --> |
| 375 |
<dd> |
| 376 |
New term order for module Gröbner bases and module |
| 377 |
reduction. Besides the (default) POT module term order there is now |
| 378 |
the TOP term order implemented for IGRLEX and INVLEX block term order |
| 379 |
combinations. (POT is "Position over Term" and TOP is "Term over |
| 380 |
Position".) Fixed issue <a |
| 381 |
href="https://github.com/kredel/java-algebra-system/issues/6" |
| 382 |
target="new">#6</a>. Further bug fixes and small improvements. |
| 383 |
</dd> |
| 384 |
|
| 385 |
<dt>2018, July </dt> <!-- 2.6.5884 --> |
| 386 |
<dd> |
| 387 |
Source refactored to use Apache Log4j version 2 API. The dependency |
| 388 |
to Log4j version 1 API can be removed. The helper logging jars |
| 389 |
<code>mylog.jar</code>, <code>nolog.jar</code> and |
| 390 |
<code>droidlog.jar</code> are no more working and obsolet. |
| 391 |
Add further missing methods for non-commutative |
| 392 |
<code>WordIdeal</code>. Small improvements and bug fixes. |
| 393 |
</dd> |
| 394 |
|
| 395 |
<dt>2018, June </dt> <!-- 2.6.5851 --> |
| 396 |
<dd> |
| 397 |
New algorithms of Lazard-Rioboo-Trager and Czichowski for the integration |
| 398 |
of rational functions developed by Youssef Elbarbary. Improved partial |
| 399 |
fraction and Bernoulli algorithm. |
| 400 |
Removed deprecated and unused package <code>edu.mas</code>. Cleanup |
| 401 |
todo comments. Improve types of return values. Checked that JAS |
| 402 |
compiles and runs with Java 10. Bug fixes and other small |
| 403 |
improvements. |
| 404 |
</dd> |
| 405 |
|
| 406 |
<dt>2018, March </dt> <!-- 2.6.5803 --> |
| 407 |
<dd> |
| 408 |
Improvements in parallel algorithms according to the Java memory |
| 409 |
model. Other bug fixes and small improvements. |
| 410 |
</dd> |
| 411 |
|
| 412 |
|
| 413 |
<dt>2017, December </dt> <!-- 2.6.5786 --> |
| 414 |
<dd> |
| 415 |
This release fixed missing factorization of polynomial content, and |
| 416 |
added generation of random irreducible polynomials. |
| 417 |
Checked that JAS compiles and runs with Java 9. Small bug fixes and |
| 418 |
improvements. |
| 419 |
</dd> |
| 420 |
|
| 421 |
<dt>2017, June </dt> <!-- 2.6.5765 --> |
| 422 |
<dd> |
| 423 |
This release improved performance of polynomial factoring methods |
| 424 |
over integers and rational numbers. The affected classes are |
| 425 |
<code>FactorRational</code>, |
| 426 |
<code>GreatestCommonDivisorModular</code> and |
| 427 |
<code>GreatestCommonDivisorModEval</code>. Thanks to Stanislav |
| 428 |
Poslavsky from the <a href="http://redberry.cc/" |
| 429 |
target="new">Redberry</a> project for pointing out these issues. |
| 430 |
Several Findbugs issues have been fixed, for example, insufficient |
| 431 |
synchronization. Other bug fixes and small improvements. |
| 432 |
</dd> |
| 433 |
|
| 434 |
<dt>2017, February </dt> <!-- 2.6.5733 --> |
| 435 |
<dd> |
| 436 |
This release adds left and right methods in <code>MonoidElem</code> |
| 437 |
with commutative default implementations. The Ore condition for |
| 438 |
<code>StarRingElem</code> classes can be computed. Quaternion classes |
| 439 |
are refactored for separate <code>Ring</code> and integral quaternion |
| 440 |
classes. Bug fixes and small improvements. |
| 441 |
There is now a Maven compatible repository with JAS at |
| 442 |
<a href="http://krum.rz.uni-mannheim.de/maven-repository/" target="new" |
| 443 |
>http://krum.rz.uni-mannheim.de/maven-repository/</a>. |
| 444 |
</dd> |
| 445 |
|
| 446 |
<dt>2017, January </dt> <!-- 2.6.5690 --> |
| 447 |
<dd> |
| 448 |
Support Java 8 lambda expressions for the generation of matrix |
| 449 |
entries and power series coefficients. Factorization for rational |
| 450 |
functions (quotients of polynomials). Factorization for BigInteger |
| 451 |
elements. |
| 452 |
Quaternion implementation extended to handle integral quaternions. |
| 453 |
Some tests and improvements for (commutative) polynomials with |
| 454 |
non-commutative coefficients. Other small improvements and bug |
| 455 |
fixes. |
| 456 |
</dd> |
| 457 |
|
| 458 |
<dt>2016, November </dt> <!-- 2.6.5652 --> |
| 459 |
<dd> |
| 460 |
New class with integer factorization, partly from previous SAC2/Aldes |
| 461 |
and MAS codes, mixed with probable prime test from |
| 462 |
<code>java.math</code>. Main method is <code>factors()</code> in |
| 463 |
class <code>PrimeInteger</code>. |
| 464 |
Cyclotomic polynomial construction and decomposition, similar to |
| 465 |
Sympy. Improvements in Gröbner walk implementation to make |
| 466 |
source and target term order selectable. Small improvements and bug |
| 467 |
fixes. |
| 468 |
</dd> |
| 469 |
|
| 470 |
<dt>2016, October </dt> <!-- 2.6.5616 --> |
| 471 |
<dd> |
| 472 |
New Gröbner walk algorithm in class |
| 473 |
<code>GroebnerBaseWalk</code>. Extensions to existing code for marked |
| 474 |
polynomials used in Gröbner walk. |
| 475 |
Bug fixes and small improvements, more use of Java 8 features. |
| 476 |
</dd> |
| 477 |
|
| 478 |
<dt>2016, August </dt> <!-- 2.6.5591 --> |
| 479 |
<dd> |
| 480 |
Improved methods to handle real and complex algebraic roots of |
| 481 |
univariate polynomials based on <code>RootFactory</code> methods. |
| 482 |
<!-- <code>realAlgebraicNumbers()</code> and |
| 483 |
<code>compelxAlgebraicNumbers()</code> --> New methods in class |
| 484 |
<code>RootFactory</code> to compute both the real and complex |
| 485 |
algebraic roots with <code>algebraicRoots()</code>, method |
| 486 |
<code>rootsOfUnity()</code> to filter roots of unity, and methods |
| 487 |
<code>rootRefine()</code> and <code>decimalRoots()</code> to compute |
| 488 |
approximations of real and complex roots. The method |
| 489 |
<code>rootReduce()</code> in <code>RootFactoryApp</code> helps to |
| 490 |
construct common field extensions via primitive element |
| 491 |
computations. The algorithms are also accessible via the scripting |
| 492 |
interfaces under the same names. |
| 493 |
Dockerfile to construct a standalone JAS scripting application. |
| 494 |
</dd> |
| 495 |
|
| 496 |
<dt>2016, July </dt> <!-- 2.6.5555 --> |
| 497 |
<dd> |
| 498 |
Mostly improvements and bug fixes in package <code>edu.jas.fd</code>. |
| 499 |
Use (Java 8) method <code>power()</code> from <code>MonoidElem</code> |
| 500 |
where possible. Further bug fixes and small improvements. |
| 501 |
</dd> |
| 502 |
|
| 503 |
<dt>2016, May </dt> <!-- 2.6.5508 --> |
| 504 |
<dd> |
| 505 |
Improvements in package <code>edu.jas.fd</code>. New class |
| 506 |
<code>SGCDFactory</code> with methods <code>getImplementation()</code> |
| 507 |
and <code>getProxy()</code> to obtian suitable common divisor |
| 508 |
implementations based on the coefficient ring of the polynomials. |
| 509 |
New class <code>SGCDParallelProxy</code> to run two common divisor |
| 510 |
implementations in parallel and take the result of the first finished |
| 511 |
one (compare to <code>GCDProxy</code>). |
| 512 |
The solvable left and right common divisor algorithms are now used in |
| 513 |
<code>SolvableLocalResidue</code>, <code>SolvableLocal</code> and |
| 514 |
<code>SolvableQuotient</code> to reduce the fractions to lower terms. |
| 515 |
Refactoring some classes to <code>edu.jas.fd</code> package. |
| 516 |
Bug fixes, small improvements and use of more Java 8 features. |
| 517 |
</dd> |
| 518 |
|
| 519 |
<dt>2016, March </dt> <!-- 2.6.5480 --> |
| 520 |
<dd> |
| 521 |
New signature-based Gröbner base algorithms, F5, GGV and Arri, |
| 522 |
after the paper <em>"Signature-based Algorithms to Compute |
| 523 |
Gröbner bases"</em> by Eder and Perry, ISSAC 2011. The classes |
| 524 |
are <code>GroebnerBaseF5SigSeqIter</code>, |
| 525 |
<code>GroebnerBaseGGVSigSeqIter</code>, |
| 526 |
<code>GroebnerBaseArriSigSeqIter</code> and are selectable via |
| 527 |
<code>GBAlgorithmBuilder</code> methods <code>F5()</code>, |
| 528 |
<code>GGV()</code> and <code>Arri()</code>. Some of the new methods |
| 529 |
use Java 8 constructions. |
| 530 |
<code>GBAlgorithmBuilder</code> expressions can be used in |
| 531 |
<code>RunGB</code> using the parameter |
| 532 |
<code>build=string</code>. Started with new methods |
| 533 |
<code>bitLength()</code> for coefficient arithmetic classes and |
| 534 |
polynomials. Some bug fixes and small improvements. Debian package |
| 535 |
improved. |
| 536 |
</dd> |
| 537 |
|
| 538 |
<dt>2016, February </dt> <!-- 2.6.5428 --> |
| 539 |
<dd> |
| 540 |
This is release 2.6 of JAS. We have switched to latest versions of |
| 541 |
used packages, for example to Apache Log4j version 2.5, JRuby version |
| 542 |
1.7.23 and Jython version 2.7.0. Junit 4.12 is already used since the |
| 543 |
last JAS version. At the moment all old versions of these packages |
| 544 |
will still work, but this may change in the next JAS versions. From |
| 545 |
then on we will eventually also make use of Java 8 features. |
| 546 |
The old version will be kept here: |
| 547 |
<a href="http://krum.rz.uni-mannheim.de/jas-2.5/" target="new">JAS 2.5</a>. |
| 548 |
<br /> |
| 549 |
We removed some long time deprecated classes <code>GBDist</code>, |
| 550 |
<code>GBDistHybrid</code>, <code>GroebnerBaseDistributed</code>, |
| 551 |
<code>GroebnerBaseDistributedHybrid</code>, the method |
| 552 |
<code>divideAndRemainder</code> of several classes and some other |
| 553 |
unused methods. Code cleanup and unified logger declaration. |
| 554 |
New class <code>IntegerProgram</code> to solve integer optimization |
| 555 |
problems via Gröbner bases. Tests and some fixes for |
| 556 |
compatibility of term orders with Sage, Singular and |
| 557 |
Mathematica. Several small bug fixes and improvements. Print JAS |
| 558 |
version in jython and jruby modules. Iterative Gröbner base |
| 559 |
algorithms selectable in <code>GBAlgorithmBuilder</code>. |
| 560 |
</dd> |
| 561 |
|
| 562 |
<dt>2016, January </dt> <!-- 2.5.5380 --> |
| 563 |
<dd> |
| 564 |
New parallel iterative Gröbner base algorithm in class |
| 565 |
<code>GreoebnerBaseParIter</code>. Names for Sage, Singular and |
| 566 |
Mathematica term orders defined in class |
| 567 |
<code>TermOrderByName</code>. Better separation of ExpVector from |
| 568 |
TermOrder. Missing polynomial methods <code>weightDegree()</code> |
| 569 |
and <code>leadingWeightPolynomial()</code> added. |
| 570 |
Switched to Junit 4.12 and use the timeout option on long running |
| 571 |
tests. Small improvements, changes and bug fixes. |
| 572 |
</dd> |
| 573 |
|
| 574 |
<dt>2015, December </dt> <!-- 2.5.5345 --> |
| 575 |
<dd> |
| 576 |
New iterative Gröbner base algorithm in class |
| 577 |
<code>GreoebnerBaseSeqIter</code>. Term orders with weight matrix are |
| 578 |
now usable from jython and jruby via the <code>PolyRing</code> |
| 579 |
constructors. More names for defined and implemented term orders in |
| 580 |
class <code>TermOrderByName</code>. |
| 581 |
Improved unit tests and further small changes and bug fixes. |
| 582 |
</dd> |
| 583 |
|
| 584 |
<dt>2015, November </dt> <!-- 2.5.5318 --> |
| 585 |
<dd> |
| 586 |
Extensions to experimental classes for solvable polynomials with |
| 587 |
non-commutative word polynomials and non-commutative residue classes |
| 588 |
as coefficients. |
| 589 |
Fixed bugs spotted by new findbugs version. Small improvements and |
| 590 |
bug fixes. The distributed byte code is now Java 8. But no Java 8 |
| 591 |
features have been used and the sources still compile with Java 7. |
| 592 |
</dd> |
| 593 |
|
| 594 |
<dt>2015, July </dt> <!-- 2.5.5281 --> |
| 595 |
<dd> |
| 596 |
Refactoring of the intefaces and classes in package |
| 597 |
<code>edu.jas.gbmod</code> to the packages <code>edu.jas.gb</code> |
| 598 |
and <code>edu.jas.gbufd</code> to cut the package dependency cycles. |
| 599 |
Changes to the organization and contents of the Web pages. |
| 600 |
<b>Note:</b> The next release will eventually use Java 8 features and |
| 601 |
drop Java 7 support, moreover many deprecated methods and classes |
| 602 |
may be removed. |
| 603 |
</dd> |
| 604 |
|
| 605 |
<dt>2015, May </dt> <!-- 2.5.5246 --> |
| 606 |
<dd> |
| 607 |
New experimental classes for solvable polynomials with |
| 608 |
non-commutative word polynomials as coefficients. Adjustments for |
| 609 |
solvable left multiplication with word polynomial coefficients and |
| 610 |
corresponding changes for Gröbner bases (might not be computable |
| 611 |
in all cases). |
| 612 |
More <code>valueOf</code> methods in polynomial ring classes to |
| 613 |
construct polynomials from coefficients and exponents or words. Check |
| 614 |
for missing Ore condition usage in solvable reduction algorithms. Use |
| 615 |
Ore condition in solvable pseudo reduction algorithms for solvable |
| 616 |
polynomial coefficients. There is a new class |
| 617 |
<code>GreatestCommonDivisorFake</code> in which <code>gcd</code> |
| 618 |
methods always return 1. |
| 619 |
Bugfix in two-sided Gröbner bases right coefficient multipliers. |
| 620 |
Fixed the polynomial parser to accept some more |
| 621 |
<code>ASCIIMath</code> expressions. Small improvements and |
| 622 |
refactoring of the HTML documentation. |
| 623 |
</dd> |
| 624 |
|
| 625 |
<dt>2015, April </dt> <!-- 2.5.5178 --> |
| 626 |
<dd> |
| 627 |
New two-sided Gröbner bases for solvable polynomial rings with |
| 628 |
parametric coefficients and commutator relations between coeficient |
| 629 |
variables and main variables. Addition of this methods also to |
| 630 |
<code>SolvableIdeal</code>. New right module Gröbner bases and |
| 631 |
right module syzygies. Syzygy methods added to scripting interfaces. |
| 632 |
Performance improvements for solvable polynomial multiplication and |
| 633 |
polynomial reduction. Small bug fixes and improvements. |
| 634 |
Moved one JAS repository from Google code to |
| 635 |
<a href="https://github.com/kredel/java-algebra-system" target="gh">GitHub</a> |
| 636 |
since Google code will be discontinued. |
| 637 |
</dd> |
| 638 |
|
| 639 |
<dt>2015, March </dt> |
| 640 |
<dd> |
| 641 |
Small modifications to comprehensive Gröbner bases |
| 642 |
implementation to allow computation of left comprehensive |
| 643 |
Gröbner bases in case of solvable polynomials with commutative |
| 644 |
parameter coefficients. Shared memory parallel versions for module |
| 645 |
Gröbner bases. Refactoring to remove package dependecy cycles. |
| 646 |
Code cleanup, small fixes and improvements. |
| 647 |
</dd> |
| 648 |
|
| 649 |
<dt>2015, February </dt> |
| 650 |
<dd> |
| 651 |
Parallel versions for module Gröbner bases. Refactor syzygy |
| 652 |
computation classes into abstract and sequential classes. Disable |
| 653 |
some correctness checks in syzygy computation depending on disabled |
| 654 |
Java assertions. Improve solvable relation table updates. Proxy and |
| 655 |
factory for solvable Gröbner bases <code>SGBProxy</code> and |
| 656 |
<code>SGBFactory</code>. |
| 657 |
Refactor term order optimization methods to naturally / better suited |
| 658 |
classes. Make use of <code>ModLong</code> classes and the improved |
| 659 |
<code>RingFactory</code> parser in the scripting interfaces. Remove |
| 660 |
the dependency on Junit from the src-tree. Some more small fixes and |
| 661 |
improvements. Ivy resolve task for log4j and junit libraries. |
| 662 |
</dd> |
| 663 |
|
| 664 |
<dt>2015, January </dt> |
| 665 |
<dd> |
| 666 |
Integer and (commutative) polynomial coefficients in solvable and |
| 667 |
word Gröbner bases. New classes <code>WordResidue</code> and |
| 668 |
<code>WordResidueRing</code> for residue classes modulo twosided |
| 669 |
ideals <code>WordIdeal</code> in word polynomial rings (free |
| 670 |
non-commutative algebas). Fix missing critical pairs to consider in |
| 671 |
word Gröbner bases. Code cleanup and small fixes and |
| 672 |
improvements. |
| 673 |
</dd> |
| 674 |
|
| 675 |
<dt>2014, December </dt> |
| 676 |
<dd> |
| 677 |
Added some jython and jruby scripts to access the |
| 678 |
<a href="http://symbolicdata.uni-leipzig.de">SymbolicData</a> |
| 679 |
data base of polynomial systems. Small improvements and corrections. |
| 680 |
The code now compiles and runs with Java 8. |
| 681 |
</dd> |
| 682 |
|
| 683 |
<dt>2014, October </dt> |
| 684 |
<dd> |
| 685 |
Improved issues spotted by <a href="https://code-spotter.com" |
| 686 |
target="new">code-spotter.com</a>. Cleanup and improvements of the |
| 687 |
<code>RingElem</code> class in the jython and Ruby script interface. |
| 688 |
Small improvements for recursive pseudo division Gröbner bases |
| 689 |
and corrections, new Junit test cases. |
| 690 |
</dd> |
| 691 |
|
| 692 |
<dt>2014, September </dt> |
| 693 |
<dd> |
| 694 |
Use of automatic variables in Jython and JRuby examples where |
| 695 |
possible. By this, the variables of a polynomial ring |
| 696 |
<code>PolyRing(QQ(),"x,y")</code> are directly available as script |
| 697 |
variables <code>x, y</code> with out calling <code>r.gens()</code>. |
| 698 |
Improved <code>jas</code> script to run also under Debian with |
| 699 |
MathLibre. Small updates, new diagrams and pictures. |
| 700 |
</dd> |
| 701 |
|
| 702 |
<dt>2014, August</dt> |
| 703 |
<dd> |
| 704 |
New class <code>BigDecimalComplex</code> for complex floating point |
| 705 |
arithmetic. Some fixes and other small improvements for floating |
| 706 |
point calculations. |
| 707 |
The Java <em>bytecode</em> of JAS is now dual licenced under the |
| 708 |
Apache 2.0 licence to allow its usage in Android projects. |
| 709 |
</dd> |
| 710 |
|
| 711 |
<dt>2014, June</dt> |
| 712 |
<dd> |
| 713 |
Small bug fixes, code optimizations, some new UML class diagrams and |
| 714 |
code cosmetic. Added Apache Commons Math3 adapter to the repository. |
| 715 |
</dd> |
| 716 |
|
| 717 |
<dt>2014, April </dt> |
| 718 |
<dd> |
| 719 |
The solvable polynomial common divisor package |
| 720 |
<code>edu.jas.fd</code> is now in a usable condition. The definition |
| 721 |
of greatest common divisor has changed slightly and left and right |
| 722 |
gcds are now distinguished. Various improvements, refactorings and |
| 723 |
bug fixes. Detection of wrong method dispatching by JRE in |
| 724 |
<code>GenSolvablePolynomial</code> and <code>GenPolynomial</code>. |
| 725 |
Cleanup of Gröbner base packages. Completion of GB class |
| 726 |
constructors with <code>PairList</code> parameters. New parallel |
| 727 |
recursive polynomial Gröbner base computation. Refactoring of |
| 728 |
<code>Quotient</code> coefficient cases. Handle more cases in |
| 729 |
<code>GBAlgorithmBuilder</code> and <code>GBFactory</code>. jython |
| 730 |
scripting GB with selectable sig-based GB algorithm. Unit tests for |
| 731 |
the new algorithms. |
| 732 |
</dd> |
| 733 |
|
| 734 |
<dt>2014, March </dt> |
| 735 |
<dd> |
| 736 |
Small improvements in solvable polynomial common divisor computation, |
| 737 |
more cases working. New method for right pseudo division. |
| 738 |
Performance improvements in <code>PrimeList</code>. Restore and keep |
| 739 |
MPJ Express compatibility and test cases. |
| 740 |
</dd> |
| 741 |
|
| 742 |
<dt>2014, January </dt> |
| 743 |
<dd> |
| 744 |
New package <code>edu.jas.fd</code> for solvable polynomial common |
| 745 |
divisor computation. It will contain algorithms for (non-unique) |
| 746 |
factorization domains. There are methods for polynomial pseudo |
| 747 |
remainder computation over Ore domains in class <code>FDUtil</code>. |
| 748 |
Further, methods for common divisors are included, but not yet |
| 749 |
finished. Converge and cleanup MPJ and MPI implementations. Added |
| 750 |
Javadocs for JLinAlg adapter. |
| 751 |
</dd> |
| 752 |
|
| 753 |
<dt>2013, November </dt> |
| 754 |
<dd> |
| 755 |
New solvable local residue ring <code>SolvableLocalResidue</code> as |
| 756 |
solvable quotient field modulo an ideal. New generic solvable |
| 757 |
polynomials <code>QLRSolvablePolynomial</code> with abstracted generic |
| 758 |
coefficients from solvable quotient, local or local-residue rings. |
| 759 |
Implemented corresponding interfaces <code>QuotPair</code> and |
| 760 |
<code>QuotPairFactory</code> in respective classes. |
| 761 |
Adjust and extend scripting examples for the new classes. |
| 762 |
Removed differences and clean-up different versions of |
| 763 |
<code>Run*GB</code> stand alone Gröbner base programs. |
| 764 |
</dd> |
| 765 |
|
| 766 |
<dt>2013, October </dt> |
| 767 |
<dd> |
| 768 |
Android version of JAS based on Ruboto (JRuby for Android) now with |
| 769 |
signed code and installable from <a href="download.html" |
| 770 |
target="main">download</a>. |
| 771 |
Least common multiple for solvable polynomials and <em>trial</em> |
| 772 |
greatest common divisor for solvable polynomials. |
| 773 |
Apel-Lassner canonical simplifier to obtain "smaller" |
| 774 |
solvable quotients in method <code>leftSimplifier()</code>. |
| 775 |
Some code refactoring to break package dependency cycles. Fixed, cleaned |
| 776 |
and worked-around some more <em>Findbugs</em> and |
| 777 |
<em>Eclipse</em> issues. Dropped Java-5 compatibility in most |
| 778 |
places. |
| 779 |
</dd> |
| 780 |
|
| 781 |
<dt>2013, September </dt> |
| 782 |
<dd> |
| 783 |
New distributed Gröbner base algorithms based on the Java |
| 784 |
bindings of <a href="http://www.open-mpi.org" target="mpi" |
| 785 |
>OpenMPI</a> similarly to the MPJ version. Both OpenMPI and MPJ are |
| 786 |
not thread-safe for all devices (in particular not for the |
| 787 |
<code>ibvdev</code> InfiniBand device), MPJ is thread-safe for |
| 788 |
<code>niodev</code> Java NewIO device. As work-around the transport |
| 789 |
layer of both versions is split to allow selection of TCP/IP sockets |
| 790 |
or MPI/MPJ channels for transport. The channels and distributed hash |
| 791 |
tables have been simplified for both MPJ and MPI. Socket based |
| 792 |
distributed hash table now implements the <code>clear()</code> |
| 793 |
method. This caused unspecific errors in iterated distributed |
| 794 |
Gröbner base computations. Simplified solvable |
| 795 |
multiplication. Fixes and improvements to Jython and JRuby scripts. |
| 796 |
</dd> |
| 797 |
|
| 798 |
<dt>2013, August </dt> |
| 799 |
<dd> |
| 800 |
New algorithms for solvable polynomial rings over solvable local |
| 801 |
rings in classes <code>LocalSolvablePolynomialRing</code> and |
| 802 |
<code>LocalSolvablePolynomial</code>. New scripting examples for |
| 803 |
solvable polynomials with solvable local coefficients. Refactoring |
| 804 |
for non-commutative relation handling of solvable polynomials with |
| 805 |
interface <code>RelationGenerator</code>. Fixed and cleanup some |
| 806 |
more <em>Findbugs</em> and <em>Eclipse</em> issues. Several fixes |
| 807 |
and improvements for jruby of Android. |
| 808 |
</dd> |
| 809 |
|
| 810 |
<dt>2013, July </dt> |
| 811 |
<dd> |
| 812 |
New algorithms for solvable polynomial rings over solvable residue |
| 813 |
rings in classes <code>ResidueSolvablePolynomialRing</code> and |
| 814 |
<code>ResidueSolvablePolynomial</code>. Methods to compute |
| 815 |
annihilators with respect to ideals and solvable ideals. New |
| 816 |
scripting examples for solvable polynomials with solvable residue |
| 817 |
coefficients. Fixed associativity of solvable multiplication by |
| 818 |
considering all Ore conditions. |
| 819 |
</dd> |
| 820 |
|
| 821 |
<dt>2013, May - June </dt> |
| 822 |
<dd> |
| 823 |
New algorithms for recursive solvable polynomial rings in classes |
| 824 |
<code>RecSolvablePolynomialRing</code> and |
| 825 |
<code>RecSolvablePolynomial</code>. New solvable polynomial rings |
| 826 |
with solvable quotient coefficients are avaliable in classes |
| 827 |
<code>QuotSolvablePolynomialRing</code> and |
| 828 |
<code>QuotSolvablePolynomial</code>. This rings feature |
| 829 |
non-commutative multiplication of variables with coefficients. |
| 830 |
New scripting examples for recursive solvable polynomial rings and |
| 831 |
solvable polynomials with solvable quotient coefficients. |
| 832 |
</dd> |
| 833 |
|
| 834 |
<dt>2013, April - May </dt> |
| 835 |
<dd> |
| 836 |
New algorithms for ideals in solvable polynomial rings in class |
| 837 |
<code>SolvableIdeal</code>, and new structures for solvable |
| 838 |
polynomial rings in classes <code>SolvableQuotient</code>, |
| 839 |
<code>SolvableResidue</code> and the corresponding factories |
| 840 |
<code>SolvableQuotientRing</code>, |
| 841 |
<code>SolvableResidueRing</code>. There is a new theme for Ruby rdoc |
| 842 |
documentation and the scripts have been adapted to a newer version of |
| 843 |
jruby (1.7.3). Further small fixes and improvements. |
| 844 |
</dd> |
| 845 |
|
| 846 |
<dt>2013, January </dt> |
| 847 |
<dd> |
| 848 |
New version number 2.5. The JAS Java API will be more stable from now |
| 849 |
on. Fixed a race condition in distributed (hybrid) Gröbner |
| 850 |
bases implementations. Improved MPJ version of GBs. Refactoring of |
| 851 |
<code>GBFactory</code> and added new option to select Gebauer & |
| 852 |
Möller critical pair handling in |
| 853 |
<code>GBAlgorithmBuilder</code>. Switch to DECIMAL128 as default in |
| 854 |
<code>BigDecimal</code>. Improved |
| 855 |
<code>GreatestCommonDivisorHensel</code> by using integer evaluation |
| 856 |
points and other optimizations. |
| 857 |
</dd> |
| 858 |
|
| 859 |
<dt>2012, December </dt> |
| 860 |
<dd> |
| 861 |
Mostly performance optimizations and small improvements and fixes. |
| 862 |
The optimizations include combined methods for polynomials like |
| 863 |
<code>scaleSubtractMultiple(b, g, a, e, S)</code> to compute the expression <em>b |
| 864 |
x<sup>g</sup> this - a x<sup>e</sup> S</em> in one rush. There is now first |
| 865 |
version of an Android App. The JAS App uses its JRuby |
| 866 |
scripting interface and runs within the Ruby IRB Android App |
| 867 |
<a href="http://www.ruboto.org">Ruboto</a>. |
| 868 |
</dd> |
| 869 |
|
| 870 |
<dt>2012, November </dt> |
| 871 |
<dd> |
| 872 |
New distributed Gröbner base algorithms based on MPI as |
| 873 |
communication middle-ware. The implementation uses the MPJ (MPI Java) |
| 874 |
API and can be run with both <a href="http://mpj-express.org/" |
| 875 |
target="mpj" >MPJ Express</a> or <a href="http://fastmpj.com/" |
| 876 |
target="mpj" >FastMPJ</a>. The implementing classes are |
| 877 |
<code>GroebnerBaseDistributedMPJ</code> for the pure distributed |
| 878 |
version and <code>GroebnerBaseDistributedHybridMPJ</code> for the |
| 879 |
distributed and multi-threaded version. |
| 880 |
</dd> |
| 881 |
|
| 882 |
<dt>2012, October </dt> |
| 883 |
<dd> |
| 884 |
New parts for free non-commutative Gröbner base computation and |
| 885 |
polynomial reduction. New interface <code>WordGroebnerBase</code> |
| 886 |
and new classes <code>WordGroebnerBaseAbstract</code> and |
| 887 |
<code>WordGroebnerBaseSeq</code>. jython and jruby access to |
| 888 |
non-commutative polynomials in <code>WordPolyRing</code> and |
| 889 |
<code>WordIdeal</code>. Improved selection of (commutative) |
| 890 |
Gröbner base algorithm implementations in class |
| 891 |
<code>GBAlgorithmBuilder</code>. For example in case of rational |
| 892 |
number coefficients a fraction free algorithm with optimization of |
| 893 |
the variable order can be requested by <code>gbab.fractionFree() |
| 894 |
.optimize() .build()</code>. |
| 895 |
</dd> |
| 896 |
|
| 897 |
<dt>2012, September </dt> |
| 898 |
<dd> |
| 899 |
Refactorings to further reduce Findbugs issues. Removed |
| 900 |
<code>Clonable</code> from <code>Element</code> and renamed |
| 901 |
<code>clone()</code> to <code>copy()</code>. New classes for free |
| 902 |
non-commutative associative rings in <code>GenWordPolynomial</code> |
| 903 |
and <code>GenWordPolynomialRing</code>. |
| 904 |
</dd> |
| 905 |
|
| 906 |
<dt>2012, August</dt> |
| 907 |
<dd> |
| 908 |
Fixed most severe and many medium Findbugs issues. Remaining |
| 909 |
programming issues and possible bugs are listed in the |
| 910 |
<a href="findbugs.html" target="fb">Findbugs report</a>. |
| 911 |
</dd> |
| 912 |
|
| 913 |
<dt>2012, July</dt> |
| 914 |
<dd> |
| 915 |
More JRuby examples. Bug fixes for right module Gröbner bases |
| 916 |
and multiple roots computation. Bug fixes for meaningful problems |
| 917 |
spotted by findbugs. |
| 918 |
</dd> |
| 919 |
|
| 920 |
<dt>2012, June</dt> |
| 921 |
<dd> |
| 922 |
Improved root bounds for real root computation. Added missing |
| 923 |
methods for real root computation. Fixed complex root selection of |
| 924 |
zero dimensional ideals. Small fixes and more missing methods. |
| 925 |
</dd> |
| 926 |
|
| 927 |
<dt>2012, May</dt> |
| 928 |
<dd> |
| 929 |
More, refactored and fixed algorithms for Wu-Ritt characteristic sets |
| 930 |
in class <code>CharacteristicSetWu</code>. Unit tests are in |
| 931 |
<code>CharSetTest</code>. jython and jruby script access to |
| 932 |
characteristic set algorithms in methods <code>CS()</code>, |
| 933 |
<code>isCS()</code>, <code>csReduction()</code>. Small fixes and |
| 934 |
improvements. |
| 935 |
</dd> |
| 936 |
|
| 937 |
<dt>2012, March</dt> |
| 938 |
<dd> |
| 939 |
The Jython and JRuby scripting classes <code>PolyRing</code> are now |
| 940 |
injecting the polynomial ring variables into the top level |
| 941 |
interpreter environment by default. New class |
| 942 |
<code>GroebnerBaseFGLM</code> to compute a Gröbner base |
| 943 |
according to the "FGLM" algorithm. It computes a Gröbner base |
| 944 |
with respect to a graded term order and then constructs the |
| 945 |
Gröbner base with respect to the requested term order via linear |
| 946 |
algebra in the residue class ring. Changes from '<code>{}</code>' to |
| 947 |
'<code>()</code>' in <code>GenPolynomial</code> to string conversion. |
| 948 |
New launcher shell script <code>jas</code>. Small fixes, improvements |
| 949 |
and a missing method implemented and in <code>PolyUtilApp</code>. |
| 950 |
</dd> |
| 951 |
|
| 952 |
<dt>2012, February</dt> |
| 953 |
<dd> |
| 954 |
Refactorings to simplify type parameters and loosen type |
| 955 |
conditions. New package <code>edu.jas.ufdroot</code> to remove cyclic |
| 956 |
package dependencies again. Improved selection of factorization |
| 957 |
implementations in <code>FactorFactory</code> classes and better |
| 958 |
suited constructors of the factorization implementations. Small |
| 959 |
fixes and improvements. |
| 960 |
</dd> |
| 961 |
|
| 962 |
<dt>2012, January</dt> |
| 963 |
<dd> |
| 964 |
Some algorithms for Wu-Ritt characteristic sets and unit tests in |
| 965 |
class <code>PolyGBUtil</code>. Small fixes and improvements. |
| 966 |
</dd> |
| 967 |
|
| 968 |
<dt>2011, Sylvester</dt> |
| 969 |
<dd> |
| 970 |
Modular variants and parallel proxy versions of resultant algorithms |
| 971 |
implemented. Cleanup and filled missing methods in |
| 972 |
<code>GreatestCommonDivisor*</code> classes in the |
| 973 |
<code>edu.jas.ufd</code> package. Fixed <code>ModLong</code> to |
| 974 |
<code>ModInteger</code> conversion. Small fixes, improvements and |
| 975 |
refactorings of methods to right classes. |
| 976 |
</dd> |
| 977 |
|
| 978 |
<dt>2011, December</dt> |
| 979 |
<dd> |
| 980 |
Switched to Java 7 for development. JAS will still compile and run on |
| 981 |
Java 6 and Java 5. A new online repositoriy for JAS on |
| 982 |
<a href="http://code.google.com/p/java-algebra-system/" target="gc">Google code</a> |
| 983 |
which contains a bug-tracker. Definition of variables for polynomial ring |
| 984 |
generators in the jython and jruby scripting interface. More JRuby examples. |
| 985 |
</dd> |
| 986 |
|
| 987 |
<dt>2011, October</dt> |
| 988 |
<dd> |
| 989 |
Separated test classes to new test source tree (trc). New <a |
| 990 |
href="../examples/basic_sigbased_gb.py" target ="py">scripting |
| 991 |
classes</a> for Gröbner base computations according to Eder and |
| 992 |
Perry (F5, Arri, GGV) and adapted <code>jas.py</code> in JAS for the |
| 993 |
required methods. More JRuby examples. Small improvements and |
| 994 |
fixes. |
| 995 |
</dd> |
| 996 |
|
| 997 |
<dt>2011, September - October</dt> |
| 998 |
<dd> |
| 999 |
Release 2.4 updates all depending packages to the latest version and |
| 1000 |
prepares for JAS 3.0. Updates for Jython 2.5.2 and JRuby 1.6.4. A |
| 1001 |
new <a href="algo-ca-book.html">index</a> of all algorithms from the book |
| 1002 |
<a href="http://www.springer.com/computer/theoretical+computer+science/book/978-0-7923-9259-0" |
| 1003 |
target="algca">Algorithms for Computer Algebra</a> by Geddes & |
| 1004 |
Czapor & Labahn to their JAS equivalents. Small improvements and |
| 1005 |
fixes again in multivariate integral polynomial factorization. |
| 1006 |
</dd> |
| 1007 |
|
| 1008 |
<dt>2011, September</dt> |
| 1009 |
<dd> |
| 1010 |
Bug fixes and missing cases for multivariate integral polynomial |
| 1011 |
factorization with multivariate Hensel lifting. Further improvements |
| 1012 |
and fixes. |
| 1013 |
</dd> |
| 1014 |
|
| 1015 |
<dt>2011, August</dt> |
| 1016 |
<dd> |
| 1017 |
Experimental multivariate integral polynomial factorization with |
| 1018 |
multivariate Hensel lifting in method |
| 1019 |
<code>factorsSquarefreeHensel()</code> in class |
| 1020 |
<code>FactorInteger</code>. Improved multivariate Hensel lifting in |
| 1021 |
class <code>HenselMultUtil</code>. Small improvements and fixes. |
| 1022 |
</dd> |
| 1023 |
|
| 1024 |
|
| 1025 |
<dt>2011, June</dt> |
| 1026 |
<dd> |
| 1027 |
Experimental ideal complex root computation in method |
| 1028 |
<code>complexAlgebraicRoots()</code> in class |
| 1029 |
<code>PolyUtilApp</code>. Simple isolating interval refinement for |
| 1030 |
real and complex roots. Alternative factoring of univariate |
| 1031 |
polynomials over algebraic number fields via prime ideal |
| 1032 |
decomposition in class <code>FactorAlgebraicPrim</code>. Improved |
| 1033 |
parsing of complex numbers. Forced term orders in some situations |
| 1034 |
and further small improvements and fixes. |
| 1035 |
</dd> |
| 1036 |
|
| 1037 |
|
| 1038 |
<dt>2011, May </dt> |
| 1039 |
<dd> |
| 1040 |
Complex roots represented by ideal real roots, uses new class |
| 1041 |
<code>RealAlgebraicNumber</code> and <code>RealAlgebraicRing</code> |
| 1042 |
in package <code>edu.jas.application</code>. New experimental |
| 1043 |
<code>RootFactory</code> with methods to compute complex roots for |
| 1044 |
polynomials with coefficients in some complex algebraic extension |
| 1045 |
field of the rational numbers. Uses the respective classes form |
| 1046 |
package <code>edu.jas.root</code> in a recursive setting. |
| 1047 |
New generic factorization classes <code>FactorRealAlgebraic</code> |
| 1048 |
and <code>FactorRealReal</code>. Small improvement for reduced / minimal |
| 1049 |
Gröbner base computation. |
| 1050 |
</dd> |
| 1051 |
|
| 1052 |
<dt>2011, April </dt> |
| 1053 |
<dd> |
| 1054 |
Multivariate algebraic ring / field extensions using class |
| 1055 |
<code>ResidueRing</code>. Jruby and Jython versions and examples of |
| 1056 |
the extension field builder. Small improvements and bug fixes for |
| 1057 |
latest Eclipse and Java 1.7 version. |
| 1058 |
</dd> |
| 1059 |
|
| 1060 |
<dt>2011, March </dt> |
| 1061 |
<dd> |
| 1062 |
Easy to use construction of towers of extension fields in class |
| 1063 |
<code>ExtensionFieldBuilder</code> with methods for algebraic and |
| 1064 |
transcendental field extensions. Improvements in real and complex |
| 1065 |
algebraic numbers. Improved polynomial parser for recursive |
| 1066 |
representations. Small bug fixes. |
| 1067 |
</dd> |
| 1068 |
|
| 1069 |
<dt>2011, February </dt> |
| 1070 |
<dd> |
| 1071 |
New class <code>HenselMultUtil</code> for multivariate Hensel lifting. |
| 1072 |
Will be used in polyomial factorization in the future. |
| 1073 |
Some parts of greatest common divisor using multivariate Hensel lifting. |
| 1074 |
The JAS source (r3408) compiles on Apache Harmony 6.0 (r991881). The |
| 1075 |
unit tests pass with the exception of test cases involving object |
| 1076 |
serialization. |
| 1077 |
</dd> |
| 1078 |
|
| 1079 |
<dt>2011, January </dt> |
| 1080 |
<dd> |
| 1081 |
New scripting interface to Ruby (JRuby). Ruby allows rational number |
| 1082 |
literals as p/q, which are better than the Python tuple form (p,q). |
| 1083 |
Some <code>toScript()</code> methods rewritten to reflect the Ruby |
| 1084 |
language requirements and to differentiate between Ruby and Python. |
| 1085 |
More precise exceptions for modular computations to return also the |
| 1086 |
discovered factors. |
| 1087 |
</dd> |
| 1088 |
|
| 1089 |
<dt>2010, December, 28</dt> |
| 1090 |
<dd> |
| 1091 |
Cleanup of package structure so that all cyclic dependencies have |
| 1092 |
been removed, see <a href="../images/PackageOverview.png">diagram</a>. |
| 1093 |
Split factory parsing parts from <code>GenPolynomialTokenizer</code> |
| 1094 |
to <code>RingFactoryTokenizer</code>. Some artificial code was |
| 1095 |
required to use solvable polynomials as ring elements since solvable |
| 1096 |
polynomials cannot implement |
| 1097 |
<code>RingElem<GenSolvablePolynomial<C>></code>. This |
| 1098 |
resulted in some cases in wrong method dispatch for the |
| 1099 |
<code>multiply()</code> method due to compiler optimizations. A work |
| 1100 |
around to detect and repair this is now implemented in class |
| 1101 |
<code>GenPolynomial</code>. |
| 1102 |
</dd> |
| 1103 |
|
| 1104 |
<dt>2010, December, 18 </dt> |
| 1105 |
<dd> |
| 1106 |
New critial pair selection for Gröbner base computation with |
| 1107 |
syzygy based algorithm after Gebauer and Möller in class |
| 1108 |
<code>OrderedSyzPairlist</code>. Refactoring of Gröbner base |
| 1109 |
classes to optionally use the new pair selection. Back port of some |
| 1110 |
JDK 1.6 constructs to be again compatible with JDK 1.5. Small |
| 1111 |
improvements in Kronecker factor combination in class |
| 1112 |
<code>FactorAbstract</code>. Fixed race condition in |
| 1113 |
<code>ThreadPool</code> and improved termination detection in |
| 1114 |
<code>Terminator</code>. Fixes in parallel reduced Gröbner base |
| 1115 |
computations. Fixed univariate polynomial construction in |
| 1116 |
<code>Ideal</code>. |
| 1117 |
<!-- New complex roots directly for rational polynomials in |
| 1118 |
<code>RootFactory</code>. --> |
| 1119 |
</dd> |
| 1120 |
|
| 1121 |
<dt>2010, October </dt> |
| 1122 |
<dd> |
| 1123 |
Multivariate Taylor series expansion interface and implementation. |
| 1124 |
Improved multivariate power series for standard base computation. |
| 1125 |
Refactored methods to better suited classes and moved classes to decouple packages, |
| 1126 |
e.g. <code>Quotient*</code> to package <code>edu.jas.ufd</code>. |
| 1127 |
Fixed small bugs and cosmetic. |
| 1128 |
</dd> |
| 1129 |
|
| 1130 |
<dt>2010, September </dt> |
| 1131 |
<dd> |
| 1132 |
Multivariate power series in classes <code>MultiVarPowerSeries</code> |
| 1133 |
and <code>MultiVarPowerSeriesRing</code>. Mora's tangent cone reduction |
| 1134 |
algorithm and standard base computation for power series in package |
| 1135 |
<code>edu.jas.ps</code>. Iterator over exponent vectors. |
| 1136 |
</dd> |
| 1137 |
|
| 1138 |
<dt>2010, August, 28 </dt> |
| 1139 |
<dd> |
| 1140 |
Iterators for finite and some infinite structures and finite and |
| 1141 |
infinite cartesian products of them. Fixed constructors to comply |
| 1142 |
with the (new) Java memory model. Small bug fixes and |
| 1143 |
improvements. More meaningful exceptions and some renamings. |
| 1144 |
</dd> |
| 1145 |
|
| 1146 |
<dt>2010, August, 8 </dt> |
| 1147 |
<dd> |
| 1148 |
Improved the polynomial parser to accept rational numbers denoted |
| 1149 |
with decimal points and to accept <code>BigDecimal</code> |
| 1150 |
coefficients. Removed the use of the underscore for algebraic number |
| 1151 |
coefficients in the polynomial parser. Now every recursive call of |
| 1152 |
<code>parse()</code> from a ring factory is triggered by braces which |
| 1153 |
can be nested to any depth. Fixed synchronization bug in solvable |
| 1154 |
polynomial relation tables and a parallelization bug in parallel |
| 1155 |
solvable polynomial Gröbner base computation. Use of unbounded |
| 1156 |
thread pools to avoid dead-locks. Added remaining parts for the |
| 1157 |
square-free decomposition in polynomial rings of characteristic p |
| 1158 |
> 0. Changed the script representation of <code>AN</code> |
| 1159 |
(<code>AlgebraicNumber</code>s). |
| 1160 |
</dd> |
| 1161 |
|
| 1162 |
<dt>2010, July </dt> |
| 1163 |
<dd> |
| 1164 |
Downgraded for Java 5 language and run-time system for use with systems relying on |
| 1165 |
older Java versions, for example MathPiper and GeoGebra. |
| 1166 |
New class <code>edu.jas.kern.TimeStatus</code> to provide user feedback for |
| 1167 |
long running tasks via method <code>checkTime()</code>. |
| 1168 |
Implemented some missing <code>extGB()</code> methods. <code>GBFactory</code> for |
| 1169 |
the selection of appropriate Gröbner base implementations. |
| 1170 |
New method <code>isFinite()</code> for all <code>ElemFactory</code>s and usage |
| 1171 |
in <code>SquarefreeFactory</code>. Added some missing parts for the factorization |
| 1172 |
in polynomial rings of characteristic p > 0 and ideal decomposition. |
| 1173 |
</dd> |
| 1174 |
|
| 1175 |
<dt>2010, June </dt> |
| 1176 |
<dd> |
| 1177 |
Factory for Gröbner base algorithm implementations in class <code>GBFactory</code>. |
| 1178 |
New <code>GBProxy</code> like <code>GCDProxy</code> to run a sequential and a parallel |
| 1179 |
Gröbner base computation concurrently. |
| 1180 |
Primitive element computation via <code>normalPositionFor()</code> in |
| 1181 |
methods <code>primitiveElement()</code> together with several |
| 1182 |
conversion methods <code>convertToPrimitiveElem()</code>. A new |
| 1183 |
<a href="gb-book.html">index</a> of all algorithms from the book |
| 1184 |
<a href="http://www.springer.com/mathematics/book/978-0-387-97971-7" |
| 1185 |
target="gbb">Gröbner bases</a> to their JAS equivalents. |
| 1186 |
</dd> |
| 1187 |
|
| 1188 |
<dt>2010, May, 28 </dt> |
| 1189 |
<dd> |
| 1190 |
Implementation of arbitrary dimensional ideal radical-, irreducible-, prime- |
| 1191 |
and primary-decomposition in class <code>Ideal</code> with methods |
| 1192 |
<code>radicalDecomposition()</code>, |
| 1193 |
<code>decomposition()</code>, |
| 1194 |
<code>primeDecomposition()</code> and |
| 1195 |
<code>primaryDecomposition()</code>. |
| 1196 |
Computation of extension and contraction ideals. |
| 1197 |
Unit tests for the decomposition methods. |
| 1198 |
Fixed a bug in multivariate polynomial factorization in Kronecker's method. |
| 1199 |
<!-- (wrong usage of <code>removeAll</code> for factors) --> |
| 1200 |
Fixed a bug in squarefree decomposition in inseparable case. |
| 1201 |
Added <code>NO_THREADS</code> flag to <code>edu.jas.kern.ComputerThreads</code> |
| 1202 |
to avoid (some) thread creation for usage in Google app engine. |
| 1203 |
</dd> |
| 1204 |
|
| 1205 |
<dt>2010, May, 8 </dt> |
| 1206 |
<dd> |
| 1207 |
Implementation of zero dimensional ideal radical-, prime-, primary- |
| 1208 |
and root-decomposition in class <code>Ideal</code> with methods |
| 1209 |
<code>zeroDimRadicalDecomposition()</code>, |
| 1210 |
<code>zeroDimDecomposition()</code>, |
| 1211 |
<code>zeroDimPrimeDecomposition()</code>, |
| 1212 |
<code>zeroDimPrimaryDecomposition()</code> and |
| 1213 |
<code>zeroDimRootDecomposition()</code>. Exact 0-dim ideal real root |
| 1214 |
computation and approximation in methods |
| 1215 |
<code>PolyUtilApp.realAlgebraicRoots()</code> and |
| 1216 |
<code>decimalApproximation()</code>. Small enhancements to Javadoc |
| 1217 |
comments. |
| 1218 |
</dd> |
| 1219 |
|
| 1220 |
<dt>2010, April </dt> |
| 1221 |
<dd> |
| 1222 |
Some more documentation for package <code>edu.jas.ufd</code>, |
| 1223 |
simplified and improved the factory classes. Refactorings of |
| 1224 |
parallel Gröbner bases computations for solvable polynomial |
| 1225 |
rings. Improved logging for distributed Gröbner bases and |
| 1226 |
distributed middle-ware. |
| 1227 |
</dd> |
| 1228 |
|
| 1229 |
<dt>2010, March </dt> |
| 1230 |
<dd> |
| 1231 |
Decimal approximations for real and complex roots based on Newton-Raphson iteration |
| 1232 |
restricted to isolating intervals or rectangles. |
| 1233 |
Small enhancements for partial Gröbner bases. Added some Mersenne primes to |
| 1234 |
<code>PrimeList</code>. |
| 1235 |
Construction of minimal univariate polynomials in zero dimensional ideals. |
| 1236 |
Supersets of complex and real roots of zero dimensional ideals. More unit tests for |
| 1237 |
real and complex roots of univariate polynomials and zero dimensional ideal roots. |
| 1238 |
Minor enhancements and fixes. |
| 1239 |
</dd> |
| 1240 |
|
| 1241 |
<dt>2010, February </dt> |
| 1242 |
<dd> |
| 1243 |
Gröbner bases for sub-sets of variables in class <code>GroebnerBasePartial</code>. |
| 1244 |
Small enhancements: polynomial recursive coefficient parser and a |
| 1245 |
matrix parser. Book-keeping of all used polynomial variable names. |
| 1246 |
New and improved unit tests. |
| 1247 |
</dd> |
| 1248 |
|
| 1249 |
<dt>2010, January </dt> |
| 1250 |
<dd> |
| 1251 |
Factorization for polynomials with <code>Complex</code> coefficients via algebraic |
| 1252 |
coefficients in Q(i). |
| 1253 |
New classes <code>ModLong</code> and <code>ModLongRing</code> for faster modular arithmetic. |
| 1254 |
New interfaces <code>Modular</code> and <code>ModularRingFactory</code> implemented also by |
| 1255 |
<code>ModInteger</code> to make both interchangable. |
| 1256 |
Improved factorization and serveral refactorings. Factorization mod p = 2 is now implemented. |
| 1257 |
</dd> |
| 1258 |
|
| 1259 |
<dt>2009, December</dt> |
| 1260 |
<dd> |
| 1261 |
Added a Git repository and a link to Ohloh code analysis of JAS. |
| 1262 |
Cosmetic, small updates and a simple Java scripting interface. |
| 1263 |
New classes for complex root isolation <code>ComplexRoots</code>, <code>ComplexRootsAbstract</code>, |
| 1264 |
<code>ComplexRootsSturm</code>. |
| 1265 |
The implementation provides an exact infallible method which follows the numeric method of Wilf. |
| 1266 |
It uses Sturm sequences following the Routh-Hurwitz Method |
| 1267 |
to count the number of complex roots within a rectangle in the complex plane. |
| 1268 |
</dd> |
| 1269 |
|
| 1270 |
<dt>2009, November</dt> |
| 1271 |
<dd> |
| 1272 |
New package for the elementary integration of rational functions |
| 1273 |
developed together with Axel Kramer during the computer algebra seminar 2009. |
| 1274 |
The implementation is based on the book <em>Bronstein: Symbolic Integration I</em>. |
| 1275 |
New adapter (<a href="commons-math_adapter.jar">commons-math_adapter.jar</a>) |
| 1276 |
for JAS to the Apache Commons Math library version 2.0 by Axel Kramer. |
| 1277 |
Cosmetic, small updates and a jython example for integration. |
| 1278 |
</dd> |
| 1279 |
|
| 1280 |
<dt>2009, September </dt> |
| 1281 |
<dd> |
| 1282 |
Improved comprehensive Gröbner bases with explicit classes for |
| 1283 |
several alternative implementations of multiplicative sets. |
| 1284 |
Base class is <code>MultiplicativeSet</code>, in sub-classes |
| 1285 |
polynomials made co-prime in <code>MultiplicativeSetCoPrime</code>, |
| 1286 |
polynomials made co-prime and squarefree in <code>MultiplicativeSetSquarefree</code> |
| 1287 |
and polynomials made irreducible in <code>MultiplicativeSetFactors</code>. |
| 1288 |
New distributed hybrid Gröbner base computation with new class |
| 1289 |
<code>TaggedMesageChannel</code> to handle multiple message types and partners over |
| 1290 |
one socket connection. Improved object serialization in distributed hash table. |
| 1291 |
Adapter updated for JLinAlg version 0.6. |
| 1292 |
</dd> |
| 1293 |
|
| 1294 |
<dt>2009, August </dt> |
| 1295 |
<dd> |
| 1296 |
New adaptor classes (<a href="jlinalg_adapter.jar">jlinalg_adapter.jar</a>) |
| 1297 |
to use the linear algebra library |
| 1298 |
<a href="http://jlinalg.sourceforge.net/" target="rela">JLinAlg</a> from JAS. |
| 1299 |
Improvements in the distributed Gröbner bases algorithms. |
| 1300 |
Minor fixes and improvements. |
| 1301 |
</dd> |
| 1302 |
|
| 1303 |
<dt>2009, July </dt> |
| 1304 |
<dd> |
| 1305 |
Code and output cosmetic, minor fixes and improvements. |
| 1306 |
New interface <code>ToRational</code> used for <code>BigRational</code> |
| 1307 |
and <code>RealAlgebraicNumber</code> to remove type case distinctions |
| 1308 |
in <code>Interval</code>. |
| 1309 |
<code>clone()</code> removed from <code>Element</code> interface because |
| 1310 |
of compiler changes. |
| 1311 |
</dd> |
| 1312 |
|
| 1313 |
<dt>2009, June and July </dt> |
| 1314 |
<dd> |
| 1315 |
Improved absolute factorization for splitting fields. Fixes and |
| 1316 |
further improvements. Implemented factorization over inseparable |
| 1317 |
field extensions. Fixed squarefree factorization and added unit |
| 1318 |
test. Refactored squarefree tests to separate classes. Refactored |
| 1319 |
squarefree algorithms to separate classes. |
| 1320 |
Interface is <code>Squarefree</code>, abstract class is |
| 1321 |
<code>SquarefreeAbstract</code>. Other main classes are |
| 1322 |
<code>SquarefreeFieldChar0</code>, <code>SquarefreeFiniteFieldCharP</code> |
| 1323 |
and <code>SquarefreeInfiniteFieldCharP</code>. |
| 1324 |
</dd> |
| 1325 |
|
| 1326 |
<dt>2009, June </dt> |
| 1327 |
<dd> |
| 1328 |
Improved algebraic and absolute factorization. |
| 1329 |
<code>FactorAlgebraic</code> can now also handle factorizations over |
| 1330 |
multiple algebraic extensions like for example Q(i)(sqrt(2)). |
| 1331 |
Class <code>FactorAbsolute</code> is now also extended |
| 1332 |
by <code>FactorAlgebraic</code>, so that absolute factorizations can |
| 1333 |
be computed over algebraic extensions of Q. Added new containers for |
| 1334 |
absolute factorization results and tests for correct absolute |
| 1335 |
factorizations. More <code>toScript()</code> methods and |
| 1336 |
improvements in Jython script interface. Minor additions and fixes. |
| 1337 |
</dd> |
| 1338 |
|
| 1339 |
<dt>2009, May </dt> |
| 1340 |
<dd> |
| 1341 |
Improved Jython script interface to handle most of the implemented rings, |
| 1342 |
developed in cooperation with Raphael Jolly. |
| 1343 |
New or improved Python functions <code>ZZ, ZM, QQ, DD, CC, Quat, Oct</code>, |
| 1344 |
<code>PolyRing, AN, RealN, RF, RC, LC, SolvPolyRing</code> |
| 1345 |
and <code>RR, PS, Vec, Mat</code> for the construction of rings and elements. |
| 1346 |
Added generic <code>Complex</code> class and <code>ComplexRing</code> factory. |
| 1347 |
Fixed a programming bug in factorization code. |
| 1348 |
</dd> |
| 1349 |
|
| 1350 |
<dt>2009, April </dt> |
| 1351 |
<dd> |
| 1352 |
Added <code>factory()</code> method to <code>Element</code> interface to have an uniform way to |
| 1353 |
obtain a corresponing ring object. |
| 1354 |
Improved <code>RealAlgebraicNumber</code> so that it can be used as polynomial coefficients, |
| 1355 |
for example <code>GenPolynomial<RealAlgebricNumber<BigRational>></code>. |
| 1356 |
Real root isolation can now also be used for polynomials with real algebraic coefficients, |
| 1357 |
for example <code>RealRootsSturm<RealAlgebraicNumber<BigRational>></code>. |
| 1358 |
</dd> |
| 1359 |
|
| 1360 |
<dt>2009, March </dt> |
| 1361 |
<dd> |
| 1362 |
Implemented univariate polynomial real root isolation algorithms |
| 1363 |
and real algebraic numbers in package <code>edu.jas.root</code> during CISIS/ECDS 2009. |
| 1364 |
Reached 100.000 lines of Java code. |
| 1365 |
</dd> |
| 1366 |
|
| 1367 |
<dt>2009, February </dt> |
| 1368 |
<dd> |
| 1369 |
Finished first version of polynomial factorization algorithms. |
| 1370 |
Refactored package names <code>edu.jas.ring</code> to <code>edu.jas.gb</code> |
| 1371 |
and <code>edu.jas.module</code> to <code>edu.jas.gbmod</code>. |
| 1372 |
</dd> |
| 1373 |
|
| 1374 |
<dt>2009, January</dt> |
| 1375 |
<dd> |
| 1376 |
Switch to version 2.3 with experimental factorization of polynomials. |
| 1377 |
<code>Factorization</code> interface with <code>FactorAbstract</code> class for common codes. |
| 1378 |
Factorization of univariate polynomials with several coefficient rings: |
| 1379 |
modulo primes in class <code>FactorModular</code>, |
| 1380 |
over integers in class <code>FactorInteger</code>, |
| 1381 |
over rational numbers in class <code>FactorRational</code> and |
| 1382 |
over algebraic numbers in class <code>FactorAlgebraic<C></code> |
| 1383 |
(where <code>C</code> can be <code>ModInteger</code> or <code>BigRational</code>). |
| 1384 |
Multivatiate polynomials are reduced to the univariate polynomials via Kronecker substitution |
| 1385 |
and are therefore not very efficient. |
| 1386 |
Refactorings and fixes. |
| 1387 |
</dd> |
| 1388 |
|
| 1389 |
<dt>2008, December </dt> |
| 1390 |
<dd> |
| 1391 |
Fixed squarefree part and factor computation for modular coefficients. |
| 1392 |
Fixed polynomial <code>compareTo</code> to be transitive as required by |
| 1393 |
Javas <code>SortedMap</code> implementations. |
| 1394 |
Implemented an adaptor package for Apache Log4j to delegate logging calls to native Java logging. |
| 1395 |
</dd> |
| 1396 |
|
| 1397 |
<dt>2008, September</dt> |
| 1398 |
<dd> |
| 1399 |
Implemented univariate power series during ADG2008 |
| 1400 |
as <code>RingElem</code> and <code>RingFactory</code> types |
| 1401 |
in package <code>edu.jas.ps</code> |
| 1402 |
in classes <code>UnivPowerSeries</code> and <code>UnivPowerSeriesRing</code>. |
| 1403 |
The implementation follows the "Infinite Streams in Java" paper of D. Gruntz |
| 1404 |
in PPPJ2006. |
| 1405 |
</dd> |
| 1406 |
|
| 1407 |
<dt>2008, August, 11</dt> |
| 1408 |
<dd> |
| 1409 |
Added jython html documentation generated by epydoc. |
| 1410 |
Added jython module to allow native polynomial expression input. |
| 1411 |
</dd> |
| 1412 |
|
| 1413 |
<dt>2008, August, 8</dt> |
| 1414 |
<dd> |
| 1415 |
New release 2.2. |
| 1416 |
Implemented interface to use JAS as an meditor engine, |
| 1417 |
see <a href="http://jscl-meditor.sourceforge.net/" target="rela">jscl-meditor</a>. |
| 1418 |
</dd> |
| 1419 |
|
| 1420 |
<dt>2008, July </dt> |
| 1421 |
<dd> |
| 1422 |
Finished implementation of comprehensive Groebner bases via Groebner systems. |
| 1423 |
Object oriented class layout uses <code>Condition</code> |
| 1424 |
and <code>ColoredSystem</code> classes. |
| 1425 |
<code>Condition</code>s consist of an ideal |
| 1426 |
(with lazy Groebner base computation) for the conditions equal to zero |
| 1427 |
and a multiplicative set for the conditions not equal to zero. |
| 1428 |
Non-zero condition polynomials are reduced modulo the ideal of |
| 1429 |
condition zero polynomials. |
| 1430 |
The squarefree part from both condition polynomials is used. |
| 1431 |
It differs from the MAS implementation by Schoenfeld, Pesch and others |
| 1432 |
by the ideal used to store the zero conditions and some more details. |
| 1433 |
</dd> |
| 1434 |
|
| 1435 |
<dt>2008, June </dt> |
| 1436 |
<dd> |
| 1437 |
Added dimension computation to Ideal. |
| 1438 |
Added term order optimization method to Ideal. |
| 1439 |
Refactored ExpVector for different storage unit implementations of the exponent arrays. |
| 1440 |
Supported storage units are <code>long</code>, |
| 1441 |
<code>int</code> (now the default, as seems to be the fastest), |
| 1442 |
<code>short</code> and <code>byte</code>. |
| 1443 |
The respective classes are <code>ExpVectorLong</code>, |
| 1444 |
<code>ExpVectorInteger</code>, |
| 1445 |
<code>ExpVectorShort</code> and <code>ExpVectorByte</code>. |
| 1446 |
</dd> |
| 1447 |
|
| 1448 |
<dt>2008, January and February</dt> |
| 1449 |
<dd> |
| 1450 |
Added Groebner bases for polynomial rings over regular rings |
| 1451 |
<code>RGroebnerBaseSeq</code> and <code>RGroebnerBasePseudoSeq</code>. |
| 1452 |
Refactorings and fixes. |
| 1453 |
</dd> |
| 1454 |
|
| 1455 |
<dt>2007, November and December</dt> |
| 1456 |
<dd> |
| 1457 |
Added von Neuman regular rings as (finite) direct products of rings, |
| 1458 |
<code>Product</code> and <code>RegularRingElem</code>. |
| 1459 |
Added fraction free pseudo reduction and Groebner bases |
| 1460 |
<code>GroebnerBasePseudoSeq</code>. |
| 1461 |
Minor refactorings and fixes. |
| 1462 |
</dd> |
| 1463 |
|
| 1464 |
<dt>2007, October</dt> |
| 1465 |
<dd> |
| 1466 |
Added Groebner bases in polynomial rings over principal ideal domains |
| 1467 |
and Euclidean domains, so called D- and E-Groebner bases, |
| 1468 |
<code>DGroebnerBaseSeq</code> and <code>EGroebnerBaseSeq</code>. |
| 1469 |
Added test methods for reducibility and refactored sequential |
| 1470 |
Groebner base implementations. |
| 1471 |
</dd> |
| 1472 |
|
| 1473 |
<dt>2007, September</dt> |
| 1474 |
<dd> |
| 1475 |
Minor refactorings and fixes. |
| 1476 |
Modular rational functions and related conversions. |
| 1477 |
</dd> |
| 1478 |
|
| 1479 |
<dt>2007, August, 19</dt> |
| 1480 |
<dd> |
| 1481 |
Added term order optimization for |
| 1482 |
polynomial and rational function coefficients. |
| 1483 |
</dd> |
| 1484 |
|
| 1485 |
<dt>2007, August, 12</dt> |
| 1486 |
<dd> |
| 1487 |
Cleanup of UFD code and subversion exports. |
| 1488 |
Term order optimization also available in jython. |
| 1489 |
</dd> |
| 1490 |
|
| 1491 |
<dt>2007, July, 28</dt> |
| 1492 |
<dd> |
| 1493 |
Added term order optimization class from old DIP/MAS system. |
| 1494 |
This introduced a dependency on JDK 1.6. |
| 1495 |
Refactored source tree to allow fully functional subversion exports. |
| 1496 |
</dd> |
| 1497 |
|
| 1498 |
<dt>2007, July, 12</dt> |
| 1499 |
<dd> |
| 1500 |
New global class edu.jas.kern.ComputerThreads to represent a thread pool. |
| 1501 |
To stop JAS, when the pool has been started, it is required |
| 1502 |
to call ComputerThreads.terminate(). |
| 1503 |
</dd> |
| 1504 |
|
| 1505 |
<dt>2007, July, 11</dt> |
| 1506 |
<dd> |
| 1507 |
New preemptive cancellation handling. |
| 1508 |
Introduced class PreemptingException as runtime exception and |
| 1509 |
a global class PreemptStatus to allow or deny preemption cancellation. |
| 1510 |
GenPolynomialRing queries PreemptStatus upon creation. |
| 1511 |
GenPolynomial checks preempt cancellation handling and thread interrupt status |
| 1512 |
on construction. If preemption is requested, it throws PreemptingException. |
| 1513 |
This allows e.g. GCDProxy to ignore the respective sub-task and get the thread free. |
| 1514 |
Removed explicit isInterrupted() checks in edu.jas.ufd package. |
| 1515 |
</dd> |
| 1516 |
|
| 1517 |
<dt>2007, July, 10</dt> |
| 1518 |
<dd> |
| 1519 |
Refactored generation of (lists of) univariate polynomials |
| 1520 |
from SolvableGroebnerBase* to GenSolvablePolynomialRing and GenPolynomialRing. |
| 1521 |
Implemented generic Power class in edu.jas.structure, |
| 1522 |
refactored power() in subresultant PRS. |
| 1523 |
</dd> |
| 1524 |
|
| 1525 |
<dt>2007, July, 9</dt> |
| 1526 |
<dd> |
| 1527 |
Added unit tests for distributive law in arith and poly packages. |
| 1528 |
Review of all documentation comments. |
| 1529 |
</dd> |
| 1530 |
|
| 1531 |
<dt>2007, July, 8</dt> |
| 1532 |
<dd> |
| 1533 |
Added assertions to check for number of polynomial variables in GenPolynomial. |
| 1534 |
In ModInteger and AlgebraicNumber inverse() now throws a NotInvertibleExecption, |
| 1535 |
which extends runtime exception. |
| 1536 |
Fixed some correctness bugs detected by Findbugs. |
| 1537 |
</dd> |
| 1538 |
|
| 1539 |
<dt>2007, July, 7</dt> |
| 1540 |
<dd> |
| 1541 |
Refactored ModInteger for ModIntegerRing factory. |
| 1542 |
Changed all depending classes. |
| 1543 |
Refactored GenPolynomial.getMap() to return unmodifiable SortedMap. |
| 1544 |
Refactored GenPolynomial.val using methods from jas.ufd package to jas.poly package. |
| 1545 |
ExpVector.getVal() renamed and made package private. |
| 1546 |
Logger variables now also final. |
| 1547 |
</dd> |
| 1548 |
|
| 1549 |
<dt>2007, June, 10</dt> |
| 1550 |
<dd> |
| 1551 |
Improved InterruptedException handling. |
| 1552 |
Refactored use of edu.ky.parallel package to use edu.jas.util and |
| 1553 |
java.util.concurrent. |
| 1554 |
Refactored project web-site. |
| 1555 |
</dd> |
| 1556 |
|
| 1557 |
<dt>2007, April and May </dt> |
| 1558 |
<dd> |
| 1559 |
Implementation of greatest common divisor algorithms. |
| 1560 |
Using recursive types. |
| 1561 |
Implemented remainder sequences: primitive, monic, subresultant. |
| 1562 |
Implemented modular methods with chinese remaindering for ModIntegers |
| 1563 |
and evaluation in finite fields to reduce the number of variables. |
| 1564 |
Implemented Hensel lifting: linear and quadratic; mod ideal is still missing. |
| 1565 |
Factory classes to select "best" implementations. |
| 1566 |
Proxy classes to run probable good implementations in parallel, |
| 1567 |
taking the result of the first terminating algorithm. |
| 1568 |
Refactored many classes to fit for the new requirements. |
| 1569 |
New method characteristic() in RingFactory and implementing classes. |
| 1570 |
Changed Quotient (rational function) to use new gcd algorithms. |
| 1571 |
Can compute GBs for polynomials with rational function coefficients. |
| 1572 |
</dd> |
| 1573 |
|
| 1574 |
<dt>2006, March </dt> |
| 1575 |
<dd> |
| 1576 |
Refactored ring package to separate application package with |
| 1577 |
more application of Groebner bases oriented classes. |
| 1578 |
The ring package could now be renamed to gb package. |
| 1579 |
Cosmetic and documentation improvements, |
| 1580 |
e.g. javadoc package descriptions and type parameter tags, |
| 1581 |
removed all tabs in all java files. |
| 1582 |
Implemented generic Quotient(Ring), Residue(Ring) and Local(Ring). |
| 1583 |
</dd> |
| 1584 |
|
| 1585 |
<dt>2006, February, 27 </dt> |
| 1586 |
<dd> |
| 1587 |
Implemented parallel solvable Groebner base algorithms and tests. |
| 1588 |
New class distributed ThreadPool. |
| 1589 |
Cosmetic and code improvements spotted by eclipse, lint4j and jdepend. |
| 1590 |
Refactored module package to separate vector package with |
| 1591 |
basic linear algebra and list handling classes. |
| 1592 |
Refactored to allow different Groebner base or reduction engines |
| 1593 |
where appropriate. |
| 1594 |
Split Syzygy etc. to an interface and a class. |
| 1595 |
Factored basic linear algebra out of Syzygy etc. |
| 1596 |
Adapted jython files to Jave code refactorings. |
| 1597 |
Reorganized jar files and documentation. |
| 1598 |
</dd> |
| 1599 |
|
| 1600 |
<dt>2006, February, 12 </dt> |
| 1601 |
<dd> |
| 1602 |
Moved old examples to MAS subdirectory and new examples |
| 1603 |
to examples directory. |
| 1604 |
Implemented some right version algorithms using opposite rings. |
| 1605 |
Switched to subversion from cvs. |
| 1606 |
Fixed bugs in new left syzygy algorithm. |
| 1607 |
</dd> |
| 1608 |
|
| 1609 |
<dt>2006, January </dt> |
| 1610 |
<dd> |
| 1611 |
More documentation and cosmetic. |
| 1612 |
Implementation of an extended Groebner Base algorithm |
| 1613 |
and arbitrary base syzygy computation. |
| 1614 |
GenPolynomialTokenizer enhanced to parse algebraic number |
| 1615 |
and Galois field coefficients. |
| 1616 |
Fixed an error in leftNormalform. |
| 1617 |
</dd> |
| 1618 |
|
| 1619 |
<dt>2005, 12, 30</dt> |
| 1620 |
<dd> |
| 1621 |
New classes CriticalPair and CriticalPairList replace OrderedPairlist. |
| 1622 |
Reworked GB parallel and distributed versions to better respect |
| 1623 |
sequential version critical pair sequences. |
| 1624 |
Fixed some race conditions in parallel and distributed algorithms. |
| 1625 |
</dd> |
| 1626 |
|
| 1627 |
<dt>2005, 12, 28</dt> |
| 1628 |
<dd> |
| 1629 |
Refactored all classes to remove static methods. |
| 1630 |
So to use any method at first an appropriate object is required. |
| 1631 |
Also class organization has changed to interfaces, abstract classes |
| 1632 |
and concrete classes, e.g. GroebnerBase, GroebnerBaseAbstract, |
| 1633 |
GroebnerBaseSeq, GroebnerBaseParallel and GroebnerBaseDistributed. |
| 1634 |
</dd> |
| 1635 |
|
| 1636 |
|
| 1637 |
<dt>2005, 12, 27</dt> |
| 1638 |
<dd> |
| 1639 |
Implemented new Ideal class with some ideal operations |
| 1640 |
like sum, product, intersection and quotient. |
| 1641 |
Added TermOrder extension and contraction. |
| 1642 |
</dd> |
| 1643 |
|
| 1644 |
|
| 1645 |
<dt>2005, 11-12 </dt> |
| 1646 |
<dd> |
| 1647 |
Updated documentation comments. |
| 1648 |
</dd> |
| 1649 |
|
| 1650 |
|
| 1651 |
<dt>2005, 7, 24</dt> |
| 1652 |
<dd> |
| 1653 |
Updated old Java JDK 1.4 branch. |
| 1654 |
Bugfixes (in twoSidedGB), minor changes and cosmetic. |
| 1655 |
<br /> |
| 1656 |
Updated documentation for new Java JDK 1.5 branch. |
| 1657 |
</dd> |
| 1658 |
|
| 1659 |
|
| 1660 |
<dt>2005, 5-7</dt> |
| 1661 |
<dd> |
| 1662 |
Working through all classes to introduce type parameters |
| 1663 |
and making all implied modifications. |
| 1664 |
</dd> |
| 1665 |
|
| 1666 |
|
| 1667 |
<dt>2005, 5, 5</dt> |
| 1668 |
<dd> |
| 1669 |
Switched to Java 1.5. |
| 1670 |
Now using covariant returns for implemented interfaces. |
| 1671 |
</dd> |
| 1672 |
|
| 1673 |
|
| 1674 |
<dt>2005, 3, 25-29</dt> |
| 1675 |
<dd> |
| 1676 |
Some module algorithms implemented. |
| 1677 |
Activated project web pages. |
| 1678 |
</dd> |
| 1679 |
|
| 1680 |
<dt>2005, 3, 12-19</dt> |
| 1681 |
<dd> |
| 1682 |
Some Syzygy algorithms implemented. |
| 1683 |
Cosmetic on comments and forked web-log. |
| 1684 |
</dd> |
| 1685 |
|
| 1686 |
|
| 1687 |
<dt>2005, 3, 5</dt> |
| 1688 |
<dd> |
| 1689 |
For the python languege and interpreter exists also a Java |
| 1690 |
version named jython. This system can directly access Java classes |
| 1691 |
and execute Java methods. |
| 1692 |
Added some jython modules Ring, Ideal, SolvRing and SolvIdeal, |
| 1693 |
to access jas GB algorithms from jython. |
| 1694 |
</dd> |
| 1695 |
|
| 1696 |
<dt>2005, 2, 25-28</dt> |
| 1697 |
<dd> |
| 1698 |
Penality of commutative GB computed as non-commutative left GB |
| 1699 |
is about 24% for (graded) Katsura 6 to 74% for (graded) Katsura 5. |
| 1700 |
Commutative GB computed as non-commutative twosided GB |
| 1701 |
is about a factor of 4 for (graded) Katsura 5 to a factor of 9 |
| 1702 |
for (graded) Katsura 5. |
| 1703 |
|
| 1704 |
Penality for weighted degree term order compated to graded Term order |
| 1705 |
is not measurable or sometimes better. |
| 1706 |
Fixed error in polynomial getONE() to correct term order. |
| 1707 |
Parser for non-commutative problems with relation tables |
| 1708 |
(but only commutative representations) and RunSGB main routine. |
| 1709 |
</dd> |
| 1710 |
|
| 1711 |
<dt>2005, 2, 14-21</dt> |
| 1712 |
<dd> |
| 1713 |
New TermOrder with direct generation of Comparators for |
| 1714 |
ExpVector comparisons. Split term orders (elimination orders) |
| 1715 |
and weighted degree orders. |
| 1716 |
</dd> |
| 1717 |
|
| 1718 |
<dt>2005, 2, 4-8</dt> |
| 1719 |
<dd> |
| 1720 |
New unit test case for TermOrder. |
| 1721 |
Fixed weak point in polynomial getONE() to correct number |
| 1722 |
of variables, e.g. correct exponent vector size. |
| 1723 |
Polynomial constant ONE still has wrong exponent vector size. |
| 1724 |
Deleted many old polynomial classes. |
| 1725 |
<p> |
| 1726 |
Implemented noncommutative product for solvable polynomials, |
| 1727 |
together with relation tables. |
| 1728 |
SolvableOrderedMapPolynomial extends OrderedMapPolynomial. |
| 1729 |
RatSolvableOrderedMapPolynomial extends SolvableOrderedMapPolynomial. |
| 1730 |
Interface SolvablePolynomial extends Ordered Polynomial. |
| 1731 |
Some more left multiplication methods, left reduction and |
| 1732 |
left Groebner Bases, twosided Groebner Base test and computation. |
| 1733 |
Pairlist class changed to avoid usage of criterion 4 if running |
| 1734 |
for SolvablePolynomials, also criterion4() method itself checks |
| 1735 |
for SolvablePolynomials. |
| 1736 |
</p> |
| 1737 |
<div align="center" > |
| 1738 |
<table border="1" cellpadding="10" |
| 1739 |
summary="relation table timings 1" > |
| 1740 |
<caption>RelationTable timings I, U(sl_3)</caption> |
| 1741 |
<tr> |
| 1742 |
<th>run / n</th> |
| 1743 |
<th>2</th> |
| 1744 |
<th>3</th> |
| 1745 |
<th>4</th> |
| 1746 |
<th>5</th> |
| 1747 |
<th>6</th> |
| 1748 |
<th>7</th> |
| 1749 |
<th>8</th> |
| 1750 |
<th>9</th> |
| 1751 |
<th>10</th> |
| 1752 |
<th>11</th> |
| 1753 |
<th>12</th> |
| 1754 |
<th>13</th> |
| 1755 |
<th>14</th> |
| 1756 |
<th>15</th> |
| 1757 |
</tr> |
| 1758 |
<tr align="right"> |
| 1759 |
<th>first</th> |
| 1760 |
<td> 3</td> |
| 1761 |
<td> 13</td> |
| 1762 |
<td> 32</td> |
| 1763 |
<td> 92</td> |
| 1764 |
<td> 128</td> |
| 1765 |
<td> 188</td> |
| 1766 |
<td> 274</td> |
| 1767 |
<td> 420</td> |
| 1768 |
<td> 683</td> |
| 1769 |
<td> 1126</td> |
| 1770 |
<td> 1795</td> |
| 1771 |
<td> 2793</td> |
| 1772 |
<td> 4380</td> |
| 1773 |
<td> 6741</td> |
| 1774 |
</tr> |
| 1775 |
<tr align="right"> |
| 1776 |
<th>second</th> |
| 1777 |
<td> 0</td> |
| 1778 |
<td> 1</td> |
| 1779 |
<td> 2</td> |
| 1780 |
<td> 3</td> |
| 1781 |
<td> 4</td> |
| 1782 |
<td> 5</td> |
| 1783 |
<td> 6</td> |
| 1784 |
<td> 8</td> |
| 1785 |
<td> 10</td> |
| 1786 |
<td> 13</td> |
| 1787 |
<td> 16</td> |
| 1788 |
<td> 21</td> |
| 1789 |
<td> 27</td> |
| 1790 |
<td> 35</td> |
| 1791 |
</tr> |
| 1792 |
</table> |
| 1793 |
</div> |
| 1794 |
<p> |
| 1795 |
Timings in ms on AMD XP 2800+. |
| 1796 |
Computation of (Y^n) * (X^n) with respect to the relation |
| 1797 |
Y * X = X Y - H. |
| 1798 |
In the first run the relation table is populated with the |
| 1799 |
products Y^i * X^i, i = 2,...,n. |
| 1800 |
In the second run the relations are reused, showing almost |
| 1801 |
no computing time anymore for the products. |
| 1802 |
</p> |
| 1803 |
<div align="center" > |
| 1804 |
<table border="1" cellpadding="10" |
| 1805 |
summary="relation table timings 2" > |
| 1806 |
<caption>RelationTable timings II, U(sl_3)</caption> |
| 1807 |
<tr> |
| 1808 |
<th>run / n</th> |
| 1809 |
<th>2</th> |
| 1810 |
<th>3</th> |
| 1811 |
<th>4</th> |
| 1812 |
<th>5</th> |
| 1813 |
<th>6</th> |
| 1814 |
<th>7</th> |
| 1815 |
</tr> |
| 1816 |
<tr align="right"> |
| 1817 |
<th>first</th> |
| 1818 |
<td> 28</td> |
| 1819 |
<td> 94</td> |
| 1820 |
<td> 303</td> |
| 1821 |
<td> 1234</td> |
| 1822 |
<td> 5185</td> |
| 1823 |
<td> 24647</td> |
| 1824 |
</tr> |
| 1825 |
<tr align="right"> |
| 1826 |
<th>second</th> |
| 1827 |
<td> 1</td> |
| 1828 |
<td> 12</td> |
| 1829 |
<td> 107</td> |
| 1830 |
<td> 782</td> |
| 1831 |
<td> 4569</td> |
| 1832 |
<td> 23897</td> |
| 1833 |
</tr> |
| 1834 |
</table> |
| 1835 |
</div> |
| 1836 |
<p> |
| 1837 |
Second example shows the computation of |
| 1838 |
( Xa + Xb + Xc + Ya + Yb + Yc + Ha + Hb )^n |
| 1839 |
in U(sl_3). |
| 1840 |
Since in the relation table only products of two variables |
| 1841 |
are stored, the improvement is minimal (for low n). |
| 1842 |
</p> |
| 1843 |
</dd> |
| 1844 |
|
| 1845 |
<dt>2005, 1, 24-31</dt> |
| 1846 |
<dd> |
| 1847 |
Removed old deprecated classes. |
| 1848 |
Todo: let DistHashTable implement Map Interface. |
| 1849 |
Reimplemented Reduction.Normalform so that asynchronous |
| 1850 |
update of the polynomial list is possible and respected. |
| 1851 |
In case a new polynomial arrives, the reduction is restarted |
| 1852 |
from the beginning. Continuing with the done work and |
| 1853 |
rereducing so far irreducible terms would be an alternative. |
| 1854 |
Todo: use JDK 1.5 java.util.concurrent with interference free Lists, |
| 1855 |
BlockingQueues. |
| 1856 |
|
| 1857 |
<div align="center" > |
| 1858 |
<table border="1" cellpadding="10" |
| 1859 |
summary="distributed timings k6g" > |
| 1860 |
<caption>Distributed computation timings, Katsura 6 (G)</caption> |
| 1861 |
<tr> |
| 1862 |
<th># Threads <br /> CPUs</th> |
| 1863 |
<th># JVMs</th> |
| 1864 |
<th>time (sec)</th> |
| 1865 |
<th>#put</th> |
| 1866 |
<th>#remove</th> |
| 1867 |
<th>% total</th> |
| 1868 |
</tr> |
| 1869 |
<tr align="right"> |
| 1870 |
<td>1, seq</td> |
| 1871 |
<td>1</td> |
| 1872 |
<td>160.2</td> |
| 1873 |
<td>70</td> |
| 1874 |
<td>327</td> |
| 1875 |
<td>13.5</td> |
| 1876 |
</tr> |
| 1877 |
<tr align="right"> |
| 1878 |
<td>1, par</td> |
| 1879 |
<td>1</td> |
| 1880 |
<td>157.0</td> |
| 1881 |
<td>70</td> |
| 1882 |
<td>327</td> |
| 1883 |
<td>13.5</td> |
| 1884 |
</tr> |
| 1885 |
<tr align="right"> |
| 1886 |
<td>2, par</td> |
| 1887 |
<td>1</td> |
| 1888 |
<td> 82.2</td> |
| 1889 |
<td>72</td> |
| 1890 |
<td>329</td> |
| 1891 |
<td>12.7</td> |
| 1892 |
</tr> |
| 1893 |
<tr align="right"> |
| 1894 |
<td>1, dist</td> |
| 1895 |
<td>1</td> |
| 1896 |
<td>177.2</td> |
| 1897 |
<td>77</td> |
| 1898 |
<td>334</td> |
| 1899 |
<td>11.4</td> |
| 1900 |
</tr> |
| 1901 |
<tr align="right"> |
| 1902 |
<td>2, dist</td> |
| 1903 |
<td>2</td> |
| 1904 |
<td> 92.2</td> |
| 1905 |
<td>90</td> |
| 1906 |
<td>347</td> |
| 1907 |
<td> 8.6</td> |
| 1908 |
</tr> |
| 1909 |
<tr align="right"> |
| 1910 |
<td>4, dist</td> |
| 1911 |
<td>2</td> |
| 1912 |
<td> 56.2</td> |
| 1913 |
<td>112</td> |
| 1914 |
<td>369</td> |
| 1915 |
<td> 5.9</td> |
| 1916 |
</tr> |
| 1917 |
<tr align="right"> |
| 1918 |
<td>8, dist</td> |
| 1919 |
<td>2</td> |
| 1920 |
<td> 58.9</td> |
| 1921 |
<td>255</td> |
| 1922 |
<td>516</td> |
| 1923 |
<td> 1.5</td> |
| 1924 |
</tr> |
| 1925 |
<tr align="right"> |
| 1926 |
<td>4, dist</td> |
| 1927 |
<td>4</td> |
| 1928 |
<td> 51.2</td> |
| 1929 |
<td>117</td> |
| 1930 |
<td>374</td> |
| 1931 |
<td> 5.5</td> |
| 1932 |
</tr> |
| 1933 |
<tr align="right"> |
| 1934 |
<td>6, dist</td> |
| 1935 |
<td>4</td> |
| 1936 |
<td> 43.7</td> |
| 1937 |
<td>129</td> |
| 1938 |
<td>386</td> |
| 1939 |
<td> 4.6</td> |
| 1940 |
</tr> |
| 1941 |
<tr align="right"> |
| 1942 |
<td>8, dist</td> |
| 1943 |
<td>4</td> |
| 1944 |
<td> 62.9</td> |
| 1945 |
<td>259</td> |
| 1946 |
<td>519</td> |
| 1947 |
<td> 1.5</td> |
| 1948 |
</tr> |
| 1949 |
<!-- |
| 1950 |
<tr align="right"> |
| 1951 |
<td></td> |
| 1952 |
<td></td> |
| 1953 |
<td></td> |
| 1954 |
</tr> |
| 1955 |
--> |
| 1956 |
</table> |
| 1957 |
</div> |
| 1958 |
<p>Timings taken on a 16 CPU Intel Xeon SMP computer running |
| 1959 |
at 2.7 GHz and with 32 GB RAM. |
| 1960 |
JVM 1.4.2 started with AggressiveHeap and UseParallelGC. |
| 1961 |
<br /> |
| 1962 |
#JVMs = number of distinct Java virtual machines. |
| 1963 |
#put = number of polynomials put to pair list. |
| 1964 |
#remove = number of pairs removed from pair list, |
| 1965 |
i.e. after application of criterions, |
| 1966 |
but including nulls up to now. |
| 1967 |
% total = per cent of removed pairs from total pairs generated, |
| 1968 |
#remove / ( #put * (#put-1) / 2 ) * 100. |
| 1969 |
</p> |
| 1970 |
<div align="center" > |
| 1971 |
<table border="1" cellpadding="10" |
| 1972 |
summary="distributed timings k7g" > |
| 1973 |
<caption>Distributed computation timings, Katsura 7 (G)</caption> |
| 1974 |
<tr> |
| 1975 |
<th># Threads <br /> CPUs</th> |
| 1976 |
<th># JVMs</th> |
| 1977 |
<th>time (sec)</th> |
| 1978 |
<th>#put</th> |
| 1979 |
<th>#remove</th> |
| 1980 |
<th>% total</th> |
| 1981 |
</tr> |
| 1982 |
<tr align="right"> |
| 1983 |
<td>1, dist</td> |
| 1984 |
<td>1</td> |
| 1985 |
<td>24726.2</td> |
| 1986 |
<td>140</td> |
| 1987 |
<td>781</td> |
| 1988 |
<td> 8.0</td> |
| 1989 |
</tr> |
| 1990 |
<tr align="right"> |
| 1991 |
<td>2, dist</td> |
| 1992 |
<td>2</td> |
| 1993 |
<td>12356.1</td> |
| 1994 |
<td>165</td> |
| 1995 |
<td>806</td> |
| 1996 |
<td> 5.9</td> |
| 1997 |
</tr> |
| 1998 |
<tr align="right"> |
| 1999 |
<td>4, dist</td> |
| 2000 |
<td>4</td> |
| 2001 |
<td>6859.3</td> |
| 2002 |
<td>218</td> |
| 2003 |
<td>859</td> |
| 2004 |
<td> 3.6</td> |
| 2005 |
</tr> |
| 2006 |
<tr align="right"> |
| 2007 |
<td>8, dist</td> |
| 2008 |
<td>4</td> |
| 2009 |
<td>7465.1</td> |
| 2010 |
<td>411</td> |
| 2011 |
<td>1054</td> |
| 2012 |
<td> 1.2</td> |
| 2013 |
</tr> |
| 2014 |
<tr align="right"> |
| 2015 |
<td>8, dist</td> |
| 2016 |
<td>8</td> |
| 2017 |
<td>6412.9</td> |
| 2018 |
<td>344</td> |
| 2019 |
<td>986</td> |
| 2020 |
<td> 1.6</td> |
| 2021 |
</tr> |
| 2022 |
<tr align="right"> |
| 2023 |
<td>8, dist</td> |
| 2024 |
<td>8</td> |
| 2025 |
<td>7173.3</td> |
| 2026 |
<td>399</td> |
| 2027 |
<td>1041</td> |
| 2028 |
<td> 1.3</td> |
| 2029 |
</tr> |
| 2030 |
</table> |
| 2031 |
</div> |
| 2032 |
<p> |
| 2033 |
Overhead for distributed variant is about 10% in Katsura 6 (G). |
| 2034 |
Distributed 1 means one distributed process is running for the |
| 2035 |
reduction of S-polynomials. There is always a master process |
| 2036 |
handling polynomial input / output, setup and management of |
| 2037 |
distributed workers and handling of the pair list. |
| 2038 |
Communication between master and workers is always via TCP/IP |
| 2039 |
with object serialization, even if running on one computer. |
| 2040 |
</p> |
| 2041 |
|
| 2042 |
</dd> |
| 2043 |
|
| 2044 |
<dt>2005, 1, 15-16</dt> |
| 2045 |
<dd> |
| 2046 |
Further things to improve in GB algorithms (from tsp): |
| 2047 |
local work queues, i.e. local Pairlists, |
| 2048 |
improve data locality in polynomials and lists, |
| 2049 |
communication using message types, |
| 2050 |
reduce object serialization in DL-broadcast |
| 2051 |
by using MarshalledObjects, |
| 2052 |
reduce communication in Pair send by not sending polynomials |
| 2053 |
but indicies (requires distributed hashtable instead of DL), |
| 2054 |
interleave communication and computation by adding a |
| 2055 |
communication thread in the distributed client. |
| 2056 |
<p> |
| 2057 |
New classes implementing a distributed hash table to hold the |
| 2058 |
polynomials in distributed GB. Index of polynomials in Pairlist |
| 2059 |
is used as hash key. |
| 2060 |
Communication is now using message types GBTransportMess. |
| 2061 |
Now polynomials are only transported once to each reducer since |
| 2062 |
only polynomial hash indexes are transported. |
| 2063 |
Distributed list is asynchronous and late updated, |
| 2064 |
so some duplicate H-polynomials (head terms) could be (are) produced. |
| 2065 |
Solution by local put to hash table with dummy index? |
| 2066 |
Timings are not dramatically better. |
| 2067 |
</p> |
| 2068 |
<p>Todo: check reduction algorithm to use later arriving polynomials. |
| 2069 |
</p> |
| 2070 |
</dd> |
| 2071 |
|
| 2072 |
<dt>2005, 1, 9-14</dt> |
| 2073 |
<dd> |
| 2074 |
Introduced all direct improvements in util classes found so far. |
| 2075 |
(ChannelFactory and others) |
| 2076 |
On parallel computers the following JVM options (1.4.2) |
| 2077 |
must be used: |
| 2078 |
<pre> |
| 2079 |
-Xms200M -Xmx400M -XX:+AggressiveHeap -XX:+UseParallelGC |
| 2080 |
</pre> |
| 2081 |
Memory must be adjusted with respect to your situation. |
| 2082 |
<p> |
| 2083 |
Seperated versions with Pair Sequence Respecting Order (PS) and |
| 2084 |
normal versions. PS versions try to keep the order of |
| 2085 |
reduced polynomials added to the ideal base the same as in |
| 2086 |
the sequential version. |
| 2087 |
Normal versions now running OK on parallel computer with the |
| 2088 |
right JVM options. |
| 2089 |
Refactoring with Eclipse (organize imports, static methods). |
| 2090 |
</p> |
| 2091 |
<div align="center" > |
| 2092 |
<table border="1" cellpadding="10" |
| 2093 |
summary="parallel timings" > |
| 2094 |
<caption>Parallel computation timings, Katsura examples</caption> |
| 2095 |
<tr> |
| 2096 |
<th># Threads<br />CPUs</th> |
| 2097 |
<th>Katsura 6 TO(G) <br />load*</th> |
| 2098 |
<th>Katsura 6 TO(G) <br />empty*</th> |
| 2099 |
<th>Katsura 7 TO(G) <br />load*</th> |
| 2100 |
<th>Katsura 7 TO(G) <br />empty*</th> |
| 2101 |
</tr> |
| 2102 |
<tr align="right"> |
| 2103 |
<td>seq</td> |
| 2104 |
<td>184.5</td> |
| 2105 |
<td>153.3</td> |
| 2106 |
<td></td> |
| 2107 |
<td></td> |
| 2108 |
</tr> |
| 2109 |
<tr align="right"> |
| 2110 |
<td>1</td> |
| 2111 |
<td>181.5</td> |
| 2112 |
<td>4% / 159.7</td> |
| 2113 |
<td></td> |
| 2114 |
<td>28418.6</td> |
| 2115 |
</tr> |
| 2116 |
<tr align="right"> |
| 2117 |
<td>2</td> |
| 2118 |
<td>118.6</td> |
| 2119 |
<td>s2.02 / p2.11 / 75.6</td> |
| 2120 |
<td></td> |
| 2121 |
<td>p2.06 / 13760.0</td> |
| 2122 |
</tr> |
| 2123 |
<tr align="right"> |
| 2124 |
<td>4</td> |
| 2125 |
<td>76.8</td> |
| 2126 |
<td>s3.79 / p3.95 / 40.4</td> |
| 2127 |
<td>6256.9</td> |
| 2128 |
<td>p4.56 / 6225.1</td> |
| 2129 |
</tr> |
| 2130 |
<tr align="right"> |
| 2131 |
<td>8</td> |
| 2132 |
<td>43.2</td> |
| 2133 |
<td>s7.19 / p7.49 / 21.3</td> |
| 2134 |
<td>3240.7</td> |
| 2135 |
<td>p8.56/ 3318.8</td> |
| 2136 |
</tr> |
| 2137 |
<tr align="right"> |
| 2138 |
<td>10</td> |
| 2139 |
<td>42.5</td> |
| 2140 |
<td></td> |
| 2141 |
<td></td> |
| 2142 |
<td></td> |
| 2143 |
</tr> |
| 2144 |
<tr align="right"> |
| 2145 |
<td>12</td> |
| 2146 |
<td>40.5</td> |
| 2147 |
<td></td> |
| 2148 |
<td>2288.1</td> |
| 2149 |
<td>p9.90 / 2868.4</td> |
| 2150 |
</tr> |
| 2151 |
<tr align="right"> |
| 2152 |
<td>14</td> |
| 2153 |
<td>31.2</td> |
| 2154 |
<td></td> |
| 2155 |
<td></td> |
| 2156 |
<td></td> |
| 2157 |
</tr> |
| 2158 |
<tr align="right"> |
| 2159 |
<td>16</td> |
| 2160 |
<td>51.9</td> |
| 2161 |
<td>s8.19 / p8.54 / 18.7</td> |
| 2162 |
<td>5376.4</td> |
| 2163 |
<td>p12.59 / 2256.1</td> |
| 2164 |
</tr> |
| 2165 |
<!-- |
| 2166 |
<tr align="right"> |
| 2167 |
<td></td> |
| 2168 |
<td></td> |
| 2169 |
<td></td> |
| 2170 |
</tr> |
| 2171 |
--> |
| 2172 |
</table> |
| 2173 |
</div> |
| 2174 |
<p>Timings taken on a 16 CPU Intel Xeon SMP computer running |
| 2175 |
at 2.7 GHz and with 32 GB RAM. |
| 2176 |
JVM 1.4.2 started with AggressiveHeap and UseParallelGC. |
| 2177 |
<br /> |
| 2178 |
*) timing taken with other load on the CPUs. |
| 2179 |
+) timing taken with no other load on the CPUs. |
| 2180 |
<br /> |
| 2181 |
Speedup: s = relative to sequential, |
| 2182 |
p = relative to parallel with one thread / CPU. |
| 2183 |
<br /> |
| 2184 |
Scaling from 8 to 16 CPUs is bad, but also observed on |
| 2185 |
non CA / GB Examples (Java and C/FORTRAN). |
| 2186 |
</p> |
| 2187 |
</dd> |
| 2188 |
|
| 2189 |
<dt>2004, 10, 3 </dt> |
| 2190 |
<dd> |
| 2191 |
Generator for Katsura examples (from POSSO / FRISCO examples). |
| 2192 |
Timings on an AMD Athlon XP 2800 (2086MHz) with log level INFO. |
| 2193 |
Log level WARN would gain 10-20 %. |
| 2194 |
<div align="center" > |
| 2195 |
<table border="1" cellpadding="10" |
| 2196 |
summary="Timings Katsura examples" > |
| 2197 |
<caption>Timings Katsura examples</caption> |
| 2198 |
<tr> |
| 2199 |
<th>N <br />vars = N+1</th> |
| 2200 |
<th>TermOrder</th> |
| 2201 |
<th>Seconds</th> |
| 2202 |
<th>TermOrder</th> |
| 2203 |
<th>Seconds</th> |
| 2204 |
</tr> |
| 2205 |
<tr align="right"> |
| 2206 |
<td> 7 </td> |
| 2207 |
<td> G </td> |
| 2208 |
<td>32044.204</td> |
| 2209 |
<td> L </td> |
| 2210 |
<td></td> |
| 2211 |
</tr> |
| 2212 |
<tr align="right"> |
| 2213 |
<td> 6 </td> |
| 2214 |
<td> G </td> |
| 2215 |
<td>112.641</td> |
| 2216 |
<td> L </td> |
| 2217 |
<td></td> |
| 2218 |
</tr> |
| 2219 |
<tr align="right"> |
| 2220 |
<td> 5 </td> |
| 2221 |
<td> G </td> |
| 2222 |
<td>4.195</td> |
| 2223 |
<td> L </td> |
| 2224 |
<td></td> |
| 2225 |
</tr> |
| 2226 |
<tr align="right"> |
| 2227 |
<td> 4 </td> |
| 2228 |
<td> G </td> |
| 2229 |
<td>0.431</td> |
| 2230 |
<td> L </td> |
| 2231 |
<td>11.650</td> |
| 2232 |
</tr> |
| 2233 |
<tr align="right"> |
| 2234 |
<td> 3 </td> |
| 2235 |
<td> G </td> |
| 2236 |
<td>0.153</td> |
| 2237 |
<td> L </td> |
| 2238 |
<td>0.310</td> |
| 2239 |
</tr> |
| 2240 |
<tr align="right"> |
| 2241 |
<td> 2 </td> |
| 2242 |
<td> G </td> |
| 2243 |
<td>0.031</td> |
| 2244 |
<td> L </td> |
| 2245 |
<td>0.032</td> |
| 2246 |
</tr> |
| 2247 |
</table> |
| 2248 |
</div> |
| 2249 |
</dd> |
| 2250 |
|
| 2251 |
<dt>2004, 9, 20-26 </dt> |
| 2252 |
<dd> |
| 2253 |
Changed OrderedPairlist to record the sequence of pairs taken from the list. |
| 2254 |
New methods <code>putParallel()</code>, <code>removeParallel()</code> and |
| 2255 |
helper methods. Sequence numbers are generated and reduced polynomials |
| 2256 |
are only put to the pair list if corresponding pair number is in |
| 2257 |
correct (sequential) sequence. |
| 2258 |
The ordered list / queue <code>pairsequence</code> (TreeMap/SortedMap) |
| 2259 |
keeps track of the polynomials not yet put to the pairlist. |
| 2260 |
<br /> |
| 2261 |
Parallelism is possible as long there are pairs to be reduced. |
| 2262 |
But non zero reduced polynomials are only put into the pairlist if |
| 2263 |
the polynomial would be put into the pairlist in the sequential |
| 2264 |
Buchberger algorithm. |
| 2265 |
GroebnerBase algorithms had to be modified to record that a polynomial |
| 2266 |
reduced to zero. |
| 2267 |
</dd> |
| 2268 |
|
| 2269 |
<dt>2004, 9, 19 </dt> |
| 2270 |
<dd> |
| 2271 |
Changed order of Pair inserts for pairs with same LCM of HTs. |
| 2272 |
Added sequence number to each Pair and indicator if Pair did not |
| 2273 |
reduce to zero. |
| 2274 |
</dd> |
| 2275 |
|
| 2276 |
<dt>2004, September </dt> |
| 2277 |
<dd> |
| 2278 |
Implemented Java server (<code>ExecutableServer</code>) for remote execution |
| 2279 |
of objects implementing the <code>RemoteExecutable</code> interface. |
| 2280 |
<p>New setup for the distributed computation of GBs: |
| 2281 |
the GB master now sends the client code to some ExecutableSevers |
| 2282 |
based on a maschine file with host and port infos about the |
| 2283 |
distributed environment. |
| 2284 |
</p> |
| 2285 |
<p>Improved the PolynomialTokenizer so that it can read almost unedited |
| 2286 |
old MAS GB input files: <code>**</code> exponents and parenthesis |
| 2287 |
around polynomials. |
| 2288 |
Lines starting with <code>#</code> are treated as comments. |
| 2289 |
Comments <code>(* *)</code> and parenthesis within polynomials are |
| 2290 |
still not supported. |
| 2291 |
</p> |
| 2292 |
<p>Implemented a common driver for GB computations <code>RunGB</code>. |
| 2293 |
Sequential, thread parallel and distributed computation can be selected |
| 2294 |
by command line parameters. The input is taken from a file. The number |
| 2295 |
of threads respectively the number of distributed clients can be specified. |
| 2296 |
For distributed execution the host and port information is taken from |
| 2297 |
a maschines file. |
| 2298 |
</p> |
| 2299 |
<pre> |
| 2300 |
Usage: RunGB [seq|par|dist|cli] <file> #procs [machinefile] |
| 2301 |
</pre> |
| 2302 |
<p>Added methods <code>putCount()</code> and <code>remCount()</code> |
| 2303 |
in <code>OrderedPairlist</code> to count the number of polynomials |
| 2304 |
put and get from the pair data structure. |
| 2305 |
</p> |
| 2306 |
<div align="center" > |
| 2307 |
<table border="1" cellpadding="10" |
| 2308 |
summary="pairlist put and remove" > |
| 2309 |
<caption>pairlist put and remove, trinks6</caption> |
| 2310 |
<tr> |
| 2311 |
<th># Threads</th> |
| 2312 |
<td>1 seq</td> |
| 2313 |
|
| 2314 |
<td>1 par</td> |
| 2315 |
<td>2 par</td> |
| 2316 |
<td>2 par</td> |
| 2317 |
<td>3 par</td> |
| 2318 |
<td>4 par</td> |
| 2319 |
<td>5 par</td> |
| 2320 |
|
| 2321 |
<td>1 dist</td> |
| 2322 |
<td>2 dist</td> |
| 2323 |
<td>3 dist</td> |
| 2324 |
<td>4 dist</td> |
| 2325 |
<td>4 dist</td> |
| 2326 |
<td>4 dist</td> |
| 2327 |
<td>5 dist</td> |
| 2328 |
</tr> |
| 2329 |
<tr> |
| 2330 |
<th># put</th> |
| 2331 |
<td>22</td> |
| 2332 |
|
| 2333 |
<td>22</td> |
| 2334 |
<td>43</td> |
| 2335 |
<td>26</td> |
| 2336 |
<td>28</td> |
| 2337 |
<td>28</td> |
| 2338 |
<td>28</td> |
| 2339 |
|
| 2340 |
<td>22</td> |
| 2341 |
<td>25</td> |
| 2342 |
<td>28</td> |
| 2343 |
<td>37</td> |
| 2344 |
<td>40</td> |
| 2345 |
<td>33</td> |
| 2346 |
<td>27</td> |
| 2347 |
</tr> |
| 2348 |
<tr> |
| 2349 |
<th># remove</th> |
| 2350 |
<td>25</td> |
| 2351 |
|
| 2352 |
<td>25</td> |
| 2353 |
<td>61</td> |
| 2354 |
<td>30</td> |
| 2355 |
<td>32</td> |
| 2356 |
<td>32</td> |
| 2357 |
<td>41</td> |
| 2358 |
|
| 2359 |
<td>26</td> |
| 2360 |
<td>33</td> |
| 2361 |
<td>42</td> |
| 2362 |
<td>47</td> |
| 2363 |
<td>61</td> |
| 2364 |
<td>54</td> |
| 2365 |
<td>69</td> |
| 2366 |
</tr> |
| 2367 |
</table> |
| 2368 |
</div> |
| 2369 |
<p>Timings @ 500 MHz on one CPU and one maschine and log4j level INFO are: <br /> |
| 2370 |
ca. 2.5 - 3.5 seconds for sequential GB,<br /> |
| 2371 |
ca. 2.5 - 6 seconds for parallel GB,<br /> |
| 2372 |
ca. 5.5 - 9 seconds plus 5 seconds sync time for distributed GB. <br /> |
| 2373 |
Network shuffling of polynomials seems to account for 3 seconds in |
| 2374 |
this example. |
| 2375 |
</p> |
| 2376 |
<p>Problem uncovered: the distributed version of GB needs an |
| 2377 |
avarage of 5 seconds to sync with all clients (on one maschine). |
| 2378 |
This is way to much for execution times in the range of 2 to 8 seconds. |
| 2379 |
</p> |
| 2380 |
<p>Redesign of DistributedList, now using TreeMap to keep the list |
| 2381 |
entries in proper sequence. As key a natural number is used, which is |
| 2382 |
assigned by the server to successive add() requests. |
| 2383 |
The server now also holds a copy of the list by itself. So the |
| 2384 |
retransmission of list elements to late arriving clients is possible. |
| 2385 |
This doubles the space required to store polynomials, but removes |
| 2386 |
initial delays to sync all clients to receive all list elements. |
| 2387 |
<br /> |
| 2388 |
By retransmission the DistributedList synchronization delay during |
| 2389 |
DistributedGB could be removed. |
| 2390 |
However the problem of about 5 seconds delay in startup |
| 2391 |
of DistributedGB still remains. It is not visible where and why this |
| 2392 |
delay occurs. |
| 2393 |
<br /> |
| 2394 |
Further improvements would be the removal of list elements or the |
| 2395 |
clearing of the list. |
| 2396 |
Next steps could be distributed HashMap or TreeMap. |
| 2397 |
<br /> |
| 2398 |
An important improvement would be to keep serialized copies of the |
| 2399 |
list elements (polynomials) at the server and to |
| 2400 |
avoid many time serialization during broadcast. |
| 2401 |
</p> |
| 2402 |
</dd> |
| 2403 |
|
| 2404 |
<dt>2004, 2, 26</dt> |
| 2405 |
<dd> |
| 2406 |
Ideas to implement: |
| 2407 |
a distributed task launcher like <code>mpirun</code>, |
| 2408 |
a daemon to run on a distributed system to work with the launcher, |
| 2409 |
solvable polynomials and non-commutative GBs. |
| 2410 |
</dd> |
| 2411 |
|
| 2412 |
<dt>2004, 2, 1</dt> |
| 2413 |
<dd> |
| 2414 |
Parallel computations with the Rose example are at ?? h with 3 threads |
| 2415 |
on 2 Pentium 4 @ 3.0 GHz hyperthreading CPUs. |
| 2416 |
<p>With one thread the time is 30.6 h. |
| 2417 |
Besides the better CPU speed, this makes a 5 % improvement on JDK 1.4 |
| 2418 |
compared to the older timings from a JDK 1.3 |
| 2419 |
and the new polynomial implementation. |
| 2420 |
</p> |
| 2421 |
</dd> |
| 2422 |
|
| 2423 |
<dt>2004, 1, 25</dt> |
| 2424 |
<dd> |
| 2425 |
<a href="https://en.wikipedia.org/wiki/SPIN_model_checker">SPIN model checker:</> |
| 2426 |
Setup a Promela description of parallel and distributed GB algorithm. Used to |
| 2427 |
verify the safety and liveness properties of the algorithms. |
| 2428 |
</dd> |
| 2429 |
|
| 2430 |
<dt>2004, 1, 17</dt> |
| 2431 |
<dd> |
| 2432 |
New (minimal) class DistributedList in preparation of a |
| 2433 |
distributed GB algorithm. |
| 2434 |
Made all mutually transported objects Serializable. |
| 2435 |
Fixed ChannelFactory and other classes in edu.unima.ky.parallel |
| 2436 |
to be interuptable. |
| 2437 |
Moved Semaphore back to edu.unima.ky.parallel. |
| 2438 |
First version of a distributed memory GB. |
| 2439 |
One problem was inner class Pair results in serialization |
| 2440 |
of outer class OrderedPairlist, which is not intented. |
| 2441 |
So Pair is now a proper class. |
| 2442 |
Distributed version mainly working. |
| 2443 |
Problem with signaling and termination if 1 in GB. |
| 2444 |
</dd> |
| 2445 |
|
| 2446 |
<dt>2004, 1, 10</dt> |
| 2447 |
<dd> |
| 2448 |
Refactored Groebner base for new OrderedPolynomials and |
| 2449 |
split sequential and parallel GB implementations. |
| 2450 |
New unit tests for sequential and parallel GBs. |
| 2451 |
GB now works for arbitrary Coefficients. |
| 2452 |
</dd> |
| 2453 |
|
| 2454 |
<dt>2004, 1, 5</dt> |
| 2455 |
<dd> |
| 2456 |
New coefficient domains BigComplex and BigQuaternion. |
| 2457 |
New test unit for all coefficients. |
| 2458 |
Based on these coefficients are new polynomials, e.g. |
| 2459 |
ComplexOrderedMapPolynomial and QuatOrderedMapPolynomial |
| 2460 |
together with unit tests. |
| 2461 |
Problem: RatPolynomial requires DEFAULT_EVORD be set correctly in ExpVector. |
| 2462 |
This is now solved for the new OrderedMapPolynomials. |
| 2463 |
</dd> |
| 2464 |
|
| 2465 |
<dt>2003, 12, 29</dt> |
| 2466 |
<dd> |
| 2467 |
New organization of polynomials: |
| 2468 |
<br /> |
| 2469 |
2 interfaces: UnorderedPolynomial and OrderedPolynomial. |
| 2470 |
Ordered polynomials have a term order and are implemented using |
| 2471 |
some SortedMap (e.g. TreeMap). |
| 2472 |
Unodered polynomials are implemented using some HashMap (e.g. LinkedHashMap). |
| 2473 |
<br /> |
| 2474 |
2 abstract classes: UnorderedMapPolynomial and OrderedMapPolynomial. |
| 2475 |
Both implement all algorithms which do not need an explicit coeficient domain, |
| 2476 |
i.e. they are formulated in terms of the Coefficient interface from jas.arith. |
| 2477 |
<br /> |
| 2478 |
2 or more classes which extend the respective abstract classes: |
| 2479 |
RatUnorderedMapPolynomial and RatOrderedMapPolynomial both need explicitly |
| 2480 |
coefficients from BigRational or others. |
| 2481 |
<p> |
| 2482 |
Multiplication with ordered polynomials is about 8-10 times faster than |
| 2483 |
the multiplication with unordered polynomials. Also the multiplication with |
| 2484 |
semi-ordered polynomials (LinkedHashMap) with orderpreserving addition is |
| 2485 |
about 7-8 times slower than multiplication with ordered polynomials. |
| 2486 |
</p> |
| 2487 |
<p> |
| 2488 |
All implementations are based on Map interface and classes. |
| 2489 |
The Map maps exponent vectors (from some monoid) to coefficients (from some domain). |
| 2490 |
This is in sync with the mathematical definition of multivariate polynomials |
| 2491 |
as mappings from some monoid to some domain. |
| 2492 |
Term orders are represented by a TermOrder class which provides the |
| 2493 |
desired Comparator classes for the SortedMap implementation. |
| 2494 |
</p> |
| 2495 |
</dd> |
| 2496 |
|
| 2497 |
<dt>2003, 12, 28</dt> |
| 2498 |
<dd>Things to do: |
| 2499 |
refactor and test HashPolynomial, check performance. |
| 2500 |
Improve the parallel GB algorithm, e.g. parallelize the reduction algorithm. |
| 2501 |
Develop a distributed memory version of the parallel GB algorithm. |
| 2502 |
</dd> |
| 2503 |
|
| 2504 |
<dt>2003, 12, 27</dt> |
| 2505 |
<dd>Using ArgoUML to produce class diagramms for jas. |
| 2506 |
Refactoring GB from edu.jas.poly to edu.jas.ring. |
| 2507 |
</dd> |
| 2508 |
|
| 2509 |
<dt>2003, 12, 21</dt> |
| 2510 |
<dd>Setup for JUnit version 3.8.1. |
| 2511 |
Added JUnit testing with Apache Ant version 1.6.0 to build.xml. |
| 2512 |
</dd> |
| 2513 |
|
| 2514 |
<dt>2003, September</dt> |
| 2515 |
<dd> |
| 2516 |
Experimented with LinkedHashMap instead of TreeMap (SortedMap) |
| 2517 |
for the representation of polynomials. |
| 2518 |
Algorithms which work also with LinkedHashMap have 1 or 2 in their names |
| 2519 |
(now in new class HashPolynomial). |
| 2520 |
LinkedHashMap has the property of using the insertion order for |
| 2521 |
the iterator order. |
| 2522 |
With LinkedHashMap the add() and subtract() can be reformulated to |
| 2523 |
use a merging algorithm as in the original DIP implementation. |
| 2524 |
Assuming the Map insertion order is the the same as the polynomial |
| 2525 |
term order. |
| 2526 |
<p> |
| 2527 |
However the merging add/subtact implementation is a factor of |
| 2528 |
2 slower than the TreeMap implementation. |
| 2529 |
Complexity for a+b is <br /> |
| 2530 |
2*(length(a)+length(b)) |
| 2531 |
for access and merging pre sorted polynomials and |
| 2532 |
<br /> |
| 2533 |
2*length(a)+length(b)+length(b)*log2(length(a+b)) |
| 2534 |
for TreeMap clone, access and insertion. |
| 2535 |
</p> |
| 2536 |
<p> |
| 2537 |
The merging multiplication implementation is by a factor of |
| 2538 |
10 slower than the TreeMap implementation. |
| 2539 |
Polynomial size was ~100 terms and the product contained ~8000 terms. |
| 2540 |
Complexity for a*b is |
| 2541 |
<br /> |
| 2542 |
lab = length(a)*length(b) coefficient multiplications for both implementations |
| 2543 |
<br /> |
| 2544 |
plus 2*length(a*b)*length(b) for merging summands, respectively |
| 2545 |
<br /> |
| 2546 |
plus length(a)*length(b)*log2(length(a*b)) for TreeMap insertion. |
| 2547 |
Since for sparse polynomials length(a*b) = lab, the TreeMap complexity |
| 2548 |
is asymptotically better in this case:<br /> |
| 2549 |
2*length(a)*length(b)*length(b) =>= length(a)*length(b)*log2(length(a*b)) |
| 2550 |
<br /> |
| 2551 |
For dense polynomials with length(a*b) ~ length(a)[+length(b)], then |
| 2552 |
the LinkedHashMap complexity is asymptotically better: |
| 2553 |
<br /> |
| 2554 |
2*length(a)*length(b) =<= length(a)*length(b)*log2(length(a*b)) |
| 2555 |
</p> |
| 2556 |
</dd> |
| 2557 |
|
| 2558 |
<dt>2003, 3, 15</dt> |
| 2559 |
<dd> |
| 2560 |
Some testing with new |
| 2561 |
AMD Athlon XP 2200+ @ 1.8 GHz, 133x2 MHz memory access.<br /> |
| 2562 |
Trinks 6: 1.013 sec with log4j level WARN, parallel 1.058 - 1.740 sec.<br /> |
| 2563 |
Trinks 7: 0.553 sec with log4j level WARN.<br /> |
| 2564 |
</dd> |
| 2565 |
|
| 2566 |
<dt>2003, 2, 2 </dt> |
| 2567 |
<dd> |
| 2568 |
Replacing all System.out.println by Log4j logging calls. |
| 2569 |
adding some Junit tests. |
| 2570 |
</dd> |
| 2571 |
|
| 2572 |
<dt>2003, 1, 28 </dt> |
| 2573 |
<dd> |
| 2574 |
Some testing with gcj (Gnu Java Compiler). this compiler gernerates |
| 2575 |
native executable binaries. the timings are not better than with |
| 2576 |
a jit, often worser. |
| 2577 |
<p>Parallel computations with the Rose example are at 18 h with 4 threads |
| 2578 |
on 2 Pentium 4 @ 2.4 GHz hyperthreading CPUs. With one thread the time |
| 2579 |
is 40 h. |
| 2580 |
</p> |
| 2581 |
</dd> |
| 2582 |
|
| 2583 |
<dt>2003, 1, 26 </dt> |
| 2584 |
<dd> |
| 2585 |
timings with JDK 1.3 (from IBM) are 30% to 40% faster |
| 2586 |
than with JDK 1.4.1 (from Sun). |
| 2587 |
timings on PowerPC 604 @ 200MHz JDK 1.3 (from IBM) |
| 2588 |
JDK 1.2 (from Sun) are a factor 3.5-4.5 slower than on Intel PIII @ 450 MHz. |
| 2589 |
on PowerPC not using jit is faster than using a jit, ca. 20% - 30%. |
| 2590 |
</dd> |
| 2591 |
|
| 2592 |
<dt>2003, 1, 12 </dt> |
| 2593 |
<dd> |
| 2594 |
General differences between sequential and parallel GB algorithms |
| 2595 |
<ul> |
| 2596 |
<li>The parallelization is achieved by doing the normal form reductions |
| 2597 |
in parallel. |
| 2598 |
</li> |
| 2599 |
<li>Since the reductions may require different times to complete |
| 2600 |
the normal forms may be entered into the list of polynomials |
| 2601 |
in different (time) order than in the sequential case. |
| 2602 |
So the pairs may be generated in different order. |
| 2603 |
However since the list of pairs is ordered wrt. the lcm of |
| 2604 |
the head terms this seems not to be a big issue. |
| 2605 |
</li> |
| 2606 |
<li>Since several reductions are scheduled in parallel |
| 2607 |
the pairs are taken from the list of pairs in different order |
| 2608 |
than in the sequential case. |
| 2609 |
One should not take more pairs from the list than can be reduced |
| 2610 |
in parallel. |
| 2611 |
</li> |
| 2612 |
</ul> |
| 2613 |
<p class="note">Does this influence the validity of criterion 3? |
| 2614 |
Access to pairlist is synchronized. |
| 2615 |
Pairs are marked as reduced as soon they are taken from the list. |
| 2616 |
But the algorithm terminates only after all reductions of pairs have |
| 2617 |
terminated. So criterion 3 holds. |
| 2618 |
</p> |
| 2619 |
<p>New implementation of parallel version of GB. |
| 2620 |
Removal of pairs is now also in parallel. |
| 2621 |
But ordering of pair insertion is no more preserved |
| 2622 |
</p> |
| 2623 |
<p>Timings are more stable |
| 2624 |
and slightly better than that of sequential GB. |
| 2625 |
</p> |
| 2626 |
<p>Todo: unit tests, comments, ... |
| 2627 |
</p> |
| 2628 |
</dd> |
| 2629 |
|
| 2630 |
<dt>2003, 1, 7-11 </dt> |
| 2631 |
<dd> |
| 2632 |
Renamed jas to mas2jas, |
| 2633 |
new cvs repository for jas, import and checkout. |
| 2634 |
<p>Improved parallel version of GB. |
| 2635 |
</p> |
| 2636 |
<ul> |
| 2637 |
<li>The sequence of polynomials added to the pair list is kept |
| 2638 |
stable. i.e. a pair scheduled for reduction at time t |
| 2639 |
will (if non zero) enter the list before any pair |
| 2640 |
scheduled at time t+x. |
| 2641 |
</li> |
| 2642 |
<li>This limits the parallelism since polynomials which reduce to zero |
| 2643 |
keep a reducer thread occupied until older polynomials are |
| 2644 |
finally reduced. One could eventualy hand over the blocking |
| 2645 |
object to the next thread. |
| 2646 |
</li> |
| 2647 |
<li>The number of pairs scheduled for reduction is now also limited |
| 2648 |
to the number of parallel reduction threads. this avoids |
| 2649 |
that to many pairs with high lcm will be scheduled before |
| 2650 |
eventually new created pairs with lower lcm. |
| 2651 |
</li> |
| 2652 |
<li>The limiting of scheduled pairs could also be implemented using |
| 2653 |
a BoundedBuffer/Queue for the ThreadPool workpile. |
| 2654 |
then addJob() would block until free Threads are avalilable. |
| 2655 |
</li> |
| 2656 |
<li>The sequencing and limiting could eventually also |
| 2657 |
achieved when the reducing threads take the pairs by |
| 2658 |
themselves instead of the master thread. |
| 2659 |
The main thread should then simply wait until all |
| 2660 |
threads are idle. |
| 2661 |
</li> |
| 2662 |
<li>The final reduction of the GB to a minimal GB is now |
| 2663 |
also parallelized. |
| 2664 |
</li> |
| 2665 |
</ul> |
| 2666 |
<p> |
| 2667 |
Todo: CVS, comments, |
| 2668 |
polynomial implementation using LinkedList, |
| 2669 |
parallel GB simplify |
| 2670 |
</p> |
| 2671 |
<p>With the improved algorithm the running time of the parallel GB |
| 2672 |
becomes more stable and not slower than the sequential GB. |
| 2673 |
However there is still no significant speedup. |
| 2674 |
</p> |
| 2675 |
<div align="center" > |
| 2676 |
<table border="1" cellpadding="10" |
| 2677 |
summary="number of reductions" > |
| 2678 |
<caption>parallel GB on one cpu</caption> |
| 2679 |
<tr> |
| 2680 |
<th># Threads</th> |
| 2681 |
<td>1</td> |
| 2682 |
<td>2</td> |
| 2683 |
<td>3</td> |
| 2684 |
<td>4</td> |
| 2685 |
<td>5</td> |
| 2686 |
<td>6</td> |
| 2687 |
<td>7</td> |
| 2688 |
<td>8</td> |
| 2689 |
<td>16</td> |
| 2690 |
</tr> |
| 2691 |
<tr> |
| 2692 |
<th># Reductions</th> |
| 2693 |
<td>25</td> |
| 2694 |
<td>25</td> |
| 2695 |
<td>27</td> |
| 2696 |
<td>25</td> |
| 2697 |
<td>25</td> |
| 2698 |
<td>25</td> |
| 2699 |
<td>25</td> |
| 2700 |
<td>25</td> |
| 2701 |
<td>25</td> |
| 2702 |
</tr> |
| 2703 |
</table> |
| 2704 |
</div> |
| 2705 |
<p></p> |
| 2706 |
<div align="center" > |
| 2707 |
<table border="1" cellpadding="10" |
| 2708 |
summary="number of reductions" > |
| 2709 |
<caption>parallel GB on 4 cpus</caption> |
| 2710 |
<tr> |
| 2711 |
<th># Threads</th> |
| 2712 |
<td>1</td> |
| 2713 |
<td>2</td> |
| 2714 |
<td>3</td> |
| 2715 |
<td>4</td> |
| 2716 |
<td>5</td> |
| 2717 |
<td>6</td> |
| 2718 |
<td>7</td> |
| 2719 |
<td>8</td> |
| 2720 |
<td>16</td> |
| 2721 |
</tr> |
| 2722 |
<tr> |
| 2723 |
<th># Reductions</th> |
| 2724 |
<td>22</td> |
| 2725 |
<td>24</td> |
| 2726 |
<td>30, 28, 24, 29</td> |
| 2727 |
<td>28</td> |
| 2728 |
<td>29</td> |
| 2729 |
<td>42</td> |
| 2730 |
<td>32</td> |
| 2731 |
<td>32</td> |
| 2732 |
<td>37</td> |
| 2733 |
</tr> |
| 2734 |
</table> |
| 2735 |
</div> |
| 2736 |
<p></p> |
| 2737 |
</dd> |
| 2738 |
|
| 2739 |
<dt>2003, 1, 6 </dt> |
| 2740 |
<dd>implemented parallel version of GB using ThreadPool from tnj |
| 2741 |
<p> |
| 2742 |
parallel results: <br /> |
| 2743 |
Trinks 7: mas 0.598 sec, jas 0.918 sec, jas par 0.955 sec <br /> |
| 2744 |
Trinks 6: mas 26.935 sec, jas 3.211 sec, jas par 3.656 sec <br /> |
| 2745 |
mas: including startup and gc time, |
| 2746 |
jas: excluding startup of jvm and including gc time, |
| 2747 |
jas par on single processor |
| 2748 |
timing on P-3@450 |
| 2749 |
</p> |
| 2750 |
this make for a penality of 12 percent, |
| 2751 |
all tests with output to files, |
| 2752 |
</dd> |
| 2753 |
|
| 2754 |
<dt>2003, 1, 5 </dt> |
| 2755 |
<dd>timing benchmarks between BigRational and Coefficient versions |
| 2756 |
of the algorithms, |
| 2757 |
the difference seems to be less than 1 percent with |
| 2758 |
no clear advantage of one side |
| 2759 |
<br /> |
| 2760 |
the sum and product algorithms have not jet optimal complexity, |
| 2761 |
sum has 2 l log(l) instead of 2 l |
| 2762 |
because of TreeMap.remove() and because of TreeMap.put(), |
| 2763 |
prod has l^2 log(l^2/2) instead of l^2 because of TreeMap.put() |
| 2764 |
<br /> |
| 2765 |
TreeMap cannot used for this, |
| 2766 |
some kind of SortedLinkedList or SortedHashMap would be required, |
| 2767 |
the last would in turn require a hashValue() of an ExpVector |
| 2768 |
<p> |
| 2769 |
implemented edu.jas.arith.BigInteger which implements Coefficient, |
| 2770 |
tested with IntPolynomial which extends Polynomial |
| 2771 |
</p> |
| 2772 |
todo: alternative Implementations, cleanup RatPolynomial, parallel GB, |
| 2773 |
conversion RatPolynomial <--> IntPolynomial |
| 2774 |
</dd> |
| 2775 |
|
| 2776 |
<dt>2003, 1, 4 </dt> |
| 2777 |
<dd>added reading of PolynomialLists and Variable Lists to |
| 2778 |
PolynomialTokenizer, |
| 2779 |
implemented PolynomialList |
| 2780 |
<br /> |
| 2781 |
refactoring RatPolynomial to extend Polynomial, |
| 2782 |
implementing IntPolynomial extends Polynomial |
| 2783 |
<br /> |
| 2784 |
to make BigInteger implement Coefficient will require |
| 2785 |
a delegation extension of BigInteger |
| 2786 |
</dd> |
| 2787 |
<!-- --> |
| 2788 |
<dt>2003, 1, 3 </dt> |
| 2789 |
<dd>implemented PolynomialTokenizer to read RatPolynomials |
| 2790 |
</dd> |
| 2791 |
|
| 2792 |
<dt>2003, 1, 2</dt> |
| 2793 |
<dd>file RatPolynomial split into RatGBase, |
| 2794 |
criterion 3 implemented with BitSet |
| 2795 |
<p> |
| 2796 |
second results (with new criterion 3 in jas): <br /> |
| 2797 |
Trinks 7: mas 0.598 sec, jas 1.159 sec <br /> |
| 2798 |
Trinks 6: mas 26.935 sec, jas 6.468 sec <br /> |
| 2799 |
mas: including startup and gc time, |
| 2800 |
jas: excluding startup of jvm and including gc time |
| 2801 |
</p> |
| 2802 |
implemented DIGBMI, H-polynomal was not monic in DIRPGB |
| 2803 |
<p> |
| 2804 |
third results (with new criterion 3 in jas and GBminimal): <br /> |
| 2805 |
Trinks 7: mas 0.598 sec, jas 0.918 sec <br /> |
| 2806 |
Trinks 6: mas 26.935 sec, jas 3.211 sec <br /> |
| 2807 |
mas: including startup and gc time, |
| 2808 |
jas: excluding startup of jvm and including gc time |
| 2809 |
timing on P-3@450 |
| 2810 |
</p> |
| 2811 |
<p> |
| 2812 |
this makes for a factor of 8-9 better, |
| 2813 |
all tests with output to files, |
| 2814 |
startup of JVM is approx. 1.0-1.2 sec, |
| 2815 |
most time is spent in BigInteger: |
| 2816 |
</p> |
| 2817 |
<pre> |
| 2818 |
java -Xrunhprof:cpu=times,format=a |
| 2819 |
|
| 2820 |
CPU TIME (ms) BEGIN (total = 136) Thu Jan 2 18:33:53 2003 |
| 2821 |
rank self accum count trace method |
| 2822 |
1 15,44% 15,44% 596610 21 java.math.MutableBigInteger.rightShift |
| 2823 |
2 13,24% 28,68% 582132 15 java.math.MutableBigInteger.difference |
| 2824 |
3 12,50% 41,18% 612760 19 java.math.MutableBigInteger.getLowestSetBit |
| 2825 |
4 9,56% 50,74% 2 9 java.lang.Object.wait |
| 2826 |
5 9,56% 60,29% 5271 22 java.math.MutableBigInteger.binaryGCD |
| 2827 |
6 6,62% 66,91% 612760 23 java.math.BigInteger.trailingZeroCnt |
| 2828 |
7 5,88% 72,79% 592152 18 java.math.BigInteger.bitLen |
| 2829 |
8 5,88% 78,68% 6018 20 java.math.MutableBigInteger.binaryGCD |
| 2830 |
9 5,15% 83,82% 578887 25 java.math.MutableBigInteger.normalize |
| 2831 |
10 4,41% 88,24% 550992 24 java.math.MutableBigInteger.primitiveRightShift |
| 2832 |
11 4,41% 92,65% 1 10 java.lang.Object.wait |
| 2833 |
12 3,68% 96,32% 582132 12 java.math.MutableBigInteger.compare |
| 2834 |
13 0,74% 97,06% 35965 13 edu.jas.poly.ExpVector.EVILCP |
| 2835 |
14 0,74% 97,79% 11612 14 java.math.BigInteger.divide |
| 2836 |
15 0,74% 98,53% 5866 11 java.math.MutableBigInteger.divide |
| 2837 |
16 0,74% 99,26% 9032 16 java.math.MutableBigInteger.divide |
| 2838 |
17 0,74% 100,00% 9032 17 java.math.BigInteger.divide |
| 2839 |
CPU TIME (ms) END |
| 2840 |
</pre> |
| 2841 |
</dd> |
| 2842 |
|
| 2843 |
<dt>2003, 1, 1</dt> |
| 2844 |
<dd>renaming packages to edu.jas, |
| 2845 |
renaming to arith, poly and ring, |
| 2846 |
new Makefile, project dokumentation in XHTML, |
| 2847 |
using JDK 1.4 with JIT |
| 2848 |
<p> |
| 2849 |
first results (without criterion 3 in jas): <br /> |
| 2850 |
Trinks 7: mas 0.598 sec, jas 1.373 sec <br /> |
| 2851 |
Trinks 6: mas 26.935 sec, jas 30.935 sec <br /> |
| 2852 |
mas: including startup and gc time, |
| 2853 |
jas: excluding startup of jvm and including gc time. |
| 2854 |
timing on P-3@450 |
| 2855 |
</p> |
| 2856 |
</dd> |
| 2857 |
|
| 2858 |
<dt>2002, 12, 31</dt> |
| 2859 |
<dd>starting with extraction of relevant files in new directory <br /> |
| 2860 |
</dd> |
| 2861 |
|
| 2862 |
<dt>2000, 7, 21</dt> |
| 2863 |
<dd>keySet/get replaced by entrySet/getval. <br /> |
| 2864 |
Implemented S-Polynomial, normal form, irreducible set. |
| 2865 |
Implemented Groebner base with criterion 4. Criterion 3 left to to. |
| 2866 |
</dd> |
| 2867 |
|
| 2868 |
<dt>2000, 7, 16</dt> |
| 2869 |
<dd>Implemented and tested BigRational based on Javas BigInteger.<br /> |
| 2870 |
With and without I/O BigRational addition, multiplication and |
| 2871 |
comparison is approx. 10 times faster than respective |
| 2872 |
SACRN functions.<br /> |
| 2873 |
<p>Implemented and testet ExpVector based on Javas int arrays. |
| 2874 |
</p> |
| 2875 |
<p>Implemented and testet RatPolynomial based on Javas TreeMap. <br /> |
| 2876 |
static methods: DIRPDF, DIRPWR via toString, DIRPON, DIRPMC, |
| 2877 |
DIRPPR, DIRPSM, DIRRAS.<br /> |
| 2878 |
Consider replacing keySet/get by entrySet/getval where appropriate. |
| 2879 |
Can there be an generic Polynomial class? |
| 2880 |
</p> |
| 2881 |
</dd> |
| 2882 |
|
| 2883 |
<dt>2000, 7, 15</dt> |
| 2884 |
<dd>Some testing with Javas builtin BigInteger class.<br /> |
| 2885 |
Without I/O builtin multiplication is approx. 15 times faster |
| 2886 |
than SAC product.<br /> |
| 2887 |
With much I/O builtin multiplication is approx. 3 times faster |
| 2888 |
than SAC product.<br /> |
| 2889 |
Builtin uses also twos-complement representation, which is |
| 2890 |
bad for decimal printing. |
| 2891 |
<p>This will be the end of list processing for Jas.</p> |
| 2892 |
<p> |
| 2893 |
DIPRNGB needs DIRPDF, DIRPWR, DIRPON, DIRPMC, DIRPPR, DIRPSM.<br /> |
| 2894 |
These need RNDIF, RNDWR, RNINT, RNSIGN, ISRNONE, RNONE, RNZERO, |
| 2895 |
RNINV (and DIRPRP), RNPROD, RNSUM. |
| 2896 |
</p> |
| 2897 |
</dd> |
| 2898 |
|
| 2899 |
<dt>2000, 7, 14</dt> |
| 2900 |
<dd>Class BigInteger based on SACI with toString().<br /> |
| 2901 |
Class List based on MASSTOR with toString(). <br /> |
| 2902 |
Problem with Modula-2 module initialization with main(args) |
| 2903 |
method: initialization of static variables. |
| 2904 |
</dd> |
| 2905 |
|
| 2906 |
<dt>2000, 7, 5</dt> |
| 2907 |
<dd>Finished testing most of masarith. |
| 2908 |
</dd> |
| 2909 |
|
| 2910 |
<dt>2000, 7, 2</dt> |
| 2911 |
<dd>Finished porting masarith. |
| 2912 |
Testing needs still to be done. MASAPF is ok. |
| 2913 |
</dd> |
| 2914 |
|
| 2915 |
<dt>2000, 6, 24</dt> |
| 2916 |
<dd>Perl script getc.pl to grab comments in Modula-2 source |
| 2917 |
and add to Java source. |
| 2918 |
Comments grabbed on most working files so far. |
| 2919 |
Generated new documentation. |
| 2920 |
</dd> |
| 2921 |
|
| 2922 |
<dt>2000, 6, 22</dt> |
| 2923 |
<dd>Future directions: |
| 2924 |
<ul> |
| 2925 |
<li>Parallel GB. |
| 2926 |
</li> |
| 2927 |
<li>Move to Java without Modula-2. |
| 2928 |
</li> |
| 2929 |
<li>Develop an applet version. |
| 2930 |
</li> |
| 2931 |
<li>Implement more of Mas. |
| 2932 |
</li> |
| 2933 |
<li>Replace SACI by Java BigInteger. |
| 2934 |
</li> |
| 2935 |
<li>Setup for real objects: <br /> |
| 2936 |
implement constructor, <br /> |
| 2937 |
implement methods: a.method(b) as STATIC_METHOD(a,b), <br /> |
| 2938 |
use real objects instead of only Cell objects <br /> |
| 2939 |
define interfaces e.g. for ring, polynomial ring, |
| 2940 |
module, group, field |
| 2941 |
</li> |
| 2942 |
<li>Small additions: <br /> |
| 2943 |
toString equivalents of xWRITEs |
| 2944 |
</li> |
| 2945 |
</ul> |
| 2946 |
Problems identified: |
| 2947 |
<ul> |
| 2948 |
<li>LISTs over Beta-Integers are diffrent to LISTs over LISTs, |
| 2949 |
when implementing LISTs as Java Types |
| 2950 |
LISTs over other types will require also special handling. |
| 2951 |
</li> |
| 2952 |
</ul> |
| 2953 |
</dd> |
| 2954 |
|
| 2955 |
<dt>2000, 6, 22</dt> |
| 2956 |
<dd>GB running on Trinks (small and big). |
| 2957 |
Jas ist about 5-8 times slower than MAS in GB computation. |
| 2958 |
Using JDK 1.1.7 without JIT on Linux, PII-300. |
| 2959 |
Using JDK 1.2.2-RC3 without JIT on Linux, PII-300 is |
| 2960 |
about 6-9 times slower. |
| 2961 |
Using JDK 1.2.2-RC4 with JIT (sunwjit) on Linux, PII-300 is |
| 2962 |
about 2-4 times slower. |
| 2963 |
Implemented Java input via BufferedReader. |
| 2964 |
</dd> |
| 2965 |
|
| 2966 |
<dt>2000, 6, 21</dt> |
| 2967 |
<dd>Got GB running. Problem was in EQUAL. |
| 2968 |
</dd> |
| 2969 |
|
| 2970 |
<dt>2000, 6, 17</dt> |
| 2971 |
<dd>Placed under control of CVS. |
| 2972 |
Begining with a clean version from Uni Passau. |
| 2973 |
Incorporated Java specific changes up to now. |
| 2974 |
</dd> |
| 2975 |
|
| 2976 |
<dt>2000, 6, 10</dt> |
| 2977 |
<dd>Transformation of DIPRNGB finished. |
| 2978 |
Important parts of maspoly finished. |
| 2979 |
</dd> |
| 2980 |
|
| 2981 |
<dt>2000, 6, 4</dt> |
| 2982 |
<dd>Transformation of SACPRIM finished. |
| 2983 |
Most of maskern finished. |
| 2984 |
Important parts of masarith finished. |
| 2985 |
</dd> |
| 2986 |
|
| 2987 |
<dt>2000, 5, 29</dt> |
| 2988 |
<dd>MASSTOR: Mapping MAS list direkt to a Java list class and using |
| 2989 |
of the garbage collector from Java. |
| 2990 |
Data types LIST and GAMMAINT are now distinct. |
| 2991 |
Buying the MHC Compiler (UK Pound 59). |
| 2992 |
</dd> |
| 2993 |
|
| 2994 |
<dt>2000, 5, 28</dt> |
| 2995 |
<dd>MASSTOR: First attempt to use list class with own garbage collection. |
| 2996 |
Using the constructor to record list pointers. |
| 2997 |
</dd> |
| 2998 |
|
| 2999 |
<dt>2000, 5, 27: </dt> |
| 3000 |
<dd>Beginning of the first tests. |
| 3001 |
Conversion of .md to .def, .mi to .mod. |
| 3002 |
</dd> |
| 3003 |
|
| 3004 |
<dt>2000, 5, 26: </dt> |
| 3005 |
<dd>Discovery of the MHC Modula-2 to Java compiler. |
| 3006 |
Mill Hill & Canterbury Corporation, Ltd, URL |
| 3007 |
<a href="http://www.mhccorp.com">http://www.mhccorp.com</a> |
| 3008 |
</dd> |
| 3009 |
|
| 3010 |
</dl> |
| 3011 |
|
| 3012 |
<!-- |
| 3013 |
<h2>To Do</h2> |
| 3014 |
|
| 3015 |
<ul> |
| 3016 |
<li>Applet front-end. |
| 3017 |
</li> |
| 3018 |
<li><del>Reimplementing MASBIOS for streams.</del> |
| 3019 |
</li> |
| 3020 |
<li>Copying the comments to java. |
| 3021 |
</li> |
| 3022 |
</ul> |
| 3023 |
--> |
| 3024 |
|
| 3025 |
<h2>Done bevore 2003</h2> |
| 3026 |
|
| 3027 |
<ul> |
| 3028 |
<li>JUnit checker for every class. |
| 3029 |
</li> |
| 3030 |
<li>Switching to Java and abandoning Modula-2. |
| 3031 |
</li> |
| 3032 |
<li>Removal of the mas prefix in directory names. |
| 3033 |
</li> |
| 3034 |
<li>Improved Makefiles. |
| 3035 |
</li> |
| 3036 |
</ul> |
| 3037 |
|
| 3038 |
|
| 3039 |
<hr /> |
| 3040 |
<address><a href="mailto:kredel@[email protected]">Heinz Kredel</a></address> |
| 3041 |
<p> |
| 3042 |
<!-- Created: Sun Jun 4 12:58:30 MEST 2000 --> |
| 3043 |
<!-- hhmts start --> |
| 3044 |
Last modified: Tue Jul 4 09:58:27 CEST 2023 |
| 3045 |
<!-- hhmts end --> |
| 3046 |
</p> |
| 3047 |
<!--p align="right" > |
| 3048 |
$Id$ |
| 3049 |
</p--> |
| 3050 |
</body> |
| 3051 |
</html> |