JAS project web-log

For a detailed list of the latest changes see the Subversion change log.

2017, June
This release improved performance of polynomial factoring methods, over integers and rational numbers. The affected classes are FactorRational, GreatestCommonDivisorModular and GreatestCommonDivisorModEval. Thanks to Stanislav Poslavsky from the Redberry project for pointing out these issues. Several Findbugs issues have been fixed, for example, insufficient synchronization. Other bug fixes and small improvements.
2017, February
This release adds left and right methods in MonoidElem with commutative default implementations. The Ore condition for StarRingElem classes can be computed. Quaternion classes are refactored for separate Ring and integral quaternion classes. Bug fixes and small improvements. There is now a Maven compatible repository with JAS at http://krum.rz.uni-mannheim.de/maven-repository/.
2017, January
Support Java 8 lambda expressions for the generation of matrix entries and power series coefficients. Factorization for rational functions (quotients of polynomials). Factorization for BigInteger elements. Quaternion implementation extended to handle integral quaternions. Some tests and improvements for (commutative) polynomials with non-commutative coefficients. Other small improvements and bug fixes.
2016, November
New class with integer factorization, partly from previous SAC2/Aldes and MAS codes, mixed with probable prime test from java.math. Main method is factors() in class PrimeInteger. Cyclotomic polynomial construction and decomposition, similar to Sympy. Improvements in Gröbner walk implementation to make source and target term order selectable. Small improvements and bug fixes.
2016, October
New Gröbner walk algorithm in class GroebnerBaseWalk. Extensions to existing code for marked polynomials used in Gröbner walk. Bug fixes and small improvements, more use of Java 8 features.
2016, August
Improved methods to handle real and complex algebraic roots of univariate polynomials based on RootFactory methods. New methods in class RootFactory to compute both the real and complex algebraic roots with algebraicRoots(), method rootsOfUnity() to filter roots of unity, and methods rootRefine() and decimalRoots() to compute approximations of real and complex roots. The method rootReduce() in RootFactoryApp helps to construct common field extensions via primitive element computations. The algorithms are also accessible via the scripting interfaces under the same names. Dockerfile to construct a standalone JAS scripting application.
2016, July
Mostly improvements and bug fixes in package edu.jas.fd. Use (Java 8) method power() from MonoidElem where possible. Further bug fixes and small improvements.
2016, May
Improvements in package edu.jas.fd. New class SGCDFactory with methods getImplementation() and getProxy() to obtian suitable common divisor implementations based on the coefficient ring of the polynomials. New class SGCDParallelProxy to run two common divisor implementations in parallel and take the result of the first finished one (compare to GCDProxy). The solvable left and right common divisor algorithms are now used in SolvableLocalResidue, SolvableLocal and SolvableQuotient to reduce the fractions to lower terms. Refactoring some classes to edu.jas.fd package. Bug fixes, small improvements and use of more Java 8 features.
2016, March
New signature-based Gröbner base algorithms, F5, GGV and Arri, after the paper "Signature-based Algorithms to Compute Gröbner bases" by Eder and Perry, ISSAC 2011. The classes are GroebnerBaseF5SigSeqIter, GroebnerBaseGGVSigSeqIter, GroebnerBaseArriSigSeqIter and are selectable via GBAlgorithmBuilder methods F5(), GGV() and Arri(). Some of the new methods use Java 8 constructions. GBAlgorithmBuilder expressions can be used in RunGB using the parameter build=string. Started with new methods bitLength() for coefficient arithmetic classes and polynomials. Some bug fixes and small improvements. Debian package improved.
2016, February
This is release 2.6 of JAS. We have switched to latest versions of used packages, for example to Apache Log4j version 2.5, JRuby version 1.7.23 and Jython version 2.7.0. Junit 4.12 is already used since the last JAS version. At the moment all old versions of these packages will still work, but this may change in the next JAS versions. From then on we will eventually also make use of Java 8 features. The old version will be kept here: JAS 2.5.
We removed some long time deprecated classes GBDist, GBDistHybrid, GroebnerBaseDistributed, GroebnerBaseDistributedHybrid, the method divideAndRemainder of several classes and some other unused methods. Code cleanup and unified logger declaration. New class IntegerProgram to solve integer optimization problems via Gröbner bases. Tests and some fixes for compatibility of term orders with Sage, Singular and Mathematica. Several small bug fixes and improvements. Print JAS version in jython and jruby modules. Iterative Gröbner base algorithms selectable in GBAlgorithmBuilder.
2016, January
New parallel iterative Gröbner base algorithm in class GreoebnerBaseParIter. Names for Sage, Singular and Mathematica term orders defined in class TermOrderByName. Better separation of ExpVector from TermOrder. Missing polynomial methods weightDegree() and leadingWeightPolynomial() added. Switched to Junit 4.12 and use the timeout option on long running tests. Small improvements, changes and bug fixes.
2015, December
New iterative Gröbner base algorithm in class GreoebnerBaseSeqIter. Term orders with weight matrix are now usable from jython and jruby via the PolyRing constructors. More names for defined and implemented term orders in class TermOrderByName. Improved unit tests and further small changes and bug fixes.
2015, November
Extensions to experimental classes for solvable polynomials with non-commutative word polynomials and non-commutative residue classes as coefficients. Fixed bugs spotted by new findbugs version. Small improvements and bug fixes. The distributed byte code is now Java 8. But no Java 8 features have been used and the sources still compile with Java 7.
2015, July
Refactoring of the intefaces and classes in package edu.jas.gbmod to the packages edu.jas.gb and edu.jas.gbufd to cut the package dependency cycles. Changes to the organization and contents of the Web pages. Note: The next release will eventually use Java 8 features and drop Java 7 support, moreover many deprecated methods and classes may be removed.
2015, May
New experimental classes for solvable polynomials with non-commutative word polynomials as coefficients. Adjustments for solvable left multiplication with word polynomial coefficients and corresponding changes for Gröbner bases (might not be computable in all cases). More valueOf methods in polynomial ring classes to construct polynomials from coefficients and exponents or words. Check for missing Ore condition usage in solvable reduction algorithms. Use Ore condition in solvable pseudo reduction algorithms for solvable polynomial coefficients. There is a new class GreatestCommonDivisorFake in which gcd methods always return 1. Bugfix in two-sided Gröbner bases right coefficient multipliers. Fixed the polynomial parser to accept some more ASCIIMath expressions. Small improvements and refactoring of the HTML documentation.
2015, April
New two-sided Gröbner bases for solvable polynomial rings with parametric coefficients and commutator relations between coeficient variables and main variables. Addition of this methods also to SolvableIdeal. New right module Gröbner bases and right module syzygies. Syzygy methods added to scripting interfaces. Performance improvements for solvable polynomial multiplication and polynomial reduction. Small bug fixes and improvements. Moved one JAS repository from Google code to GitHub since Google code will be discontinued.
2015, March
Small modifications to comprehensive Gröbner bases implementation to allow computation of left comprehensive Gröbner bases in case of solvable polynomials with commutative parameter coefficients. Shared memory parallel versions for module Gröbner bases. Refactoring to remove package dependecy cycles. Code cleanup, small fixes and improvements.
2015, February
Parallel versions for module Gröbner bases. Refactor syzygy computation classes into abstract and sequential classes. Disable some correctness checks in syzygy computation depending on disabled Java assertions. Improve solvable relation table updates. Proxy and factory for solvable Gröbner bases SGBProxy and SGBFactory. Refactor term order optimization methods to naturally / better suited classes. Make use of ModLong classes and the improved RingFactory parser in the scripting interfaces. Remove the dependency on Junit from the src-tree. Some more small fixes and improvements. Ivy resolve task for log4j and junit libraries.
2015, January
Integer and (commutative) polynomial coefficients in solvable and word Gröbner bases. New classes WordResidue and WordResidueRing for residue classes modulo twosided ideals WordIdeal in word polynomial rings (free non-commutative algebas). Fix missing critical pairs to consider in word Gröbner bases. Code cleanup and small fixes and improvements.
2014, December
Added some jython and jruby scripts to access the SymbolicData data base of polynomial systems. Small improvements and corrections. The code now compiles and runs with Java 8.
2014, October
Improved issues spotted by code-spotter.com. Cleanup and improvements of the RingElem class in the jython and Ruby script interface. Small improvements for recursive pseudo division Gröbner bases and corrections, new Junit test cases.
2014, September
Use of automatic variables in Jython and JRuby examples where possible. By this, the variables of a polynomial ring PolyRing(QQ(),"x,y") are directly available as script variables x, y with out calling r.gens(). Improved jas script to run also under Debian with MathLibre. Small updates, new diagrams and pictures.
2014, August
New class BigDecimalComplex for complex floating point arithmetic. Some fixes and other small improvements for floating point calculations. The Java bytecode of JAS is now dual licenced under the Apache 2.0 licence to allow its usage in Android projects.
2014, June
Small bug fixes, code optimizations, some new UML class diagrams and code cosmetic. Added Apache Commons Math3 adapter to the repository.
2014, April
The solvable polynomial common divisor package edu.jas.fd is now in a usable condition. The definition of greatest common divisor has changed slightly and left and right gcds are now distinguished. Various improvements, refactorings and bug fixes. Detection of wrong method dispatching by JRE in GenSolvablePolynomial and GenPolynomial. Cleanup of Gröbner base packages. Completion of GB class constructors with PairList parameters. New parallel recursive polynomial Gröbner base computation. Refactoring of Quotient coefficient cases. Handle more cases in GBAlgorithmBuilder and GBFactory. jython scripting GB with selectable sig-based GB algorithm. Unit tests for the new algorithms.
2014, March
Small improvements in solvable polynomial common divisor computation, more cases working. New method for right pseudo division. Performance improvements in PrimeList. Restore and keep MPJ Express compatibility and test cases.
2014, January
New package edu.jas.fd for solvable polynomial common divisor computation. It will contain algorithms for (non-unique) factorization domains. There are methods for polynomial pseudo remainder computation over Ore domains in class FDUtil. Further, methods for common divisors are included, but not yet finished. Converge and cleanup MPJ and MPI implementations. Added Javadocs for JLinAlg adapter.
2013, November
New solvable local residue ring SolvableLocalResidue as solvable quotient field modulo an ideal. New generic solvable polynomials QLRSolvablePolynomial with abstracted generic coefficients from solvable quotient, local or local-residue rings. Implemented corresponding interfaces QuotPair and QuotPairFactory in respective classes. Adjust and extend scripting examples for the new classes. Removed differences and clean-up different versions of Run*GB stand alone Gröbner base programs.
2013, October
Android version of JAS based on Ruboto (JRuby for Android) now with signed code and installable from download. Least common multiple for solvable polynomials and trial greatest common divisor for solvable polynomials. Apel-Lassner canonical simplifier to obtain "smaller" solvable quotients in method leftSimplifier(). Some code refactoring to break package dependency cycles. Fixed, cleaned and worked-around some more Findbugs and Eclipse issues. Dropped Java-5 compatibility in most places.
2013, September
New distributed Gröbner base algorithms based on the Java bindings of OpenMPI similarly to the MPJ version. Both OpenMPI and MPJ are not thread-safe for all devices (in particular not for the ibvdev InfiniBand device), MPJ is thread-safe for niodev Java NewIO device. As work-around the transport layer of both versions is split to allow selection of TCP/IP sockets or MPI/MPJ channels for transport. The channels and distributed hash tables have been simplified for both MPJ and MPI. Socket based distributed hash table now implements the clear() method. This caused unspecific errors in iterated distributed Gröbner base computations. Simplified solvable multiplication. Fixes and improvements to Jython and JRuby scripts.
2013, August
New algorithms for solvable polynomial rings over solvable local rings in classes LocalSolvablePolynomialRing and LocalSolvablePolynomial. New scripting examples for solvable polynomials with solvable local coefficients. Refactoring for non-commutative relation handling of solvable polynomials with interface RelationGenerator. Fixed and cleanup some more Findbugs and Eclipse issues. Several fixes and improvements for jruby of Android.
2013, July
New algorithms for solvable polynomial rings over solvable residue rings in classes ResidueSolvablePolynomialRing and ResidueSolvablePolynomial. Methods to compute annihilators with respect to ideals and solvable ideals. New scripting examples for solvable polynomials with solvable residue coefficients. Fixed associativity of solvable multiplication by considering all Ore conditions.
2013, May - June
New algorithms for recursive solvable polynomial rings in classes RecSolvablePolynomialRing and RecSolvablePolynomial. New solvable polynomial rings with solvable quotient coefficients are avaliable in classes QuotSolvablePolynomialRing and QuotSolvablePolynomial. This rings feature non-commutative multiplication of variables with coefficients. New scripting examples for recursive solvable polynomial rings and solvable polynomials with solvable quotient coefficients.
2013, April - May
New algorithms for ideals in solvable polynomial rings in class SolvableIdeal, and new structures for solvable polynomial rings in classes SolvableQuotient, SolvableResidue and the corresponding factories SolvableQuotientRing, SolvableResidueRing. There is a new theme for Ruby rdoc documentation and the scripts have been adapted to a newer version of jruby (1.7.3). Further small fixes and improvements.
2013, January
New version number 2.5. The JAS Java API will be more stable from now on. Fixed a race condition in distributed (hybrid) Gröbner bases implementations. Improved MPJ version of GBs. Refactoring of GBFactory and added new option to select Gebauer & Möller critical pair handling in GBAlgorithmBuilder. Switch to DECIMAL128 as default in BigDecimal. Improved GreatestCommonDivisorHensel by using integer evaluation points and other optimizations.
2012, December
Mostly performance optimizations and small improvements and fixes. The optimizations include combined methods for polynomials like scaleSubtractMultiple(b, g, a, e, S) to compute the expression b xg this - a xe S in one rush. There is now first version of an Android App. The JAS App uses its JRuby scripting interface and runs within the Ruby IRB Android App Ruboto.
2012, November
New distributed Gröbner base algorithms based on MPI as communication middle-ware. The implementation uses the MPJ (MPI Java) API and can be run with both MPJ Express or FastMPJ. The implementing classes are GroebnerBaseDistributedMPJ for the pure distributed version and GroebnerBaseDistributedHybridMPJ for the distributed and multi-threaded version.
2012, October
New parts for free non-commutative Gröbner base computation and polynomial reduction. New interface WordGroebnerBase and new classes WordGroebnerBaseAbstract and WordGroebnerBaseSeq. jython and jruby access to non-commutative polynomials in WordPolyRing and WordIdeal. Improved selection of (commutative) Gröbner base algorithm implementations in class GBAlgorithmBuilder. For example in case of rational number coefficients a fraction free algorithm with optimization of the variable order can be requested by gbab.fractionFree() .optimize() .build().
2012, September
Refactorings to further reduce Findbugs issues. Removed Clonable from Element and renamed clone() to copy(). New classes for free non-commutative associative rings in GenWordPolynomial and GenWordPolynomialRing.
2012, August
Fixed most severe and many medium Findbugs issues. Remaining programming issues and possible bugs are listed in the Findbugs report.
2012, July
More JRuby examples. Bug fixes for right module Gröbner bases and multiple roots computation. Bug fixes for meaningful problems spotted by findbugs.
2012, June
Improved root bounds for real root computation. Added missing methods for real root computation. Fixed complex root selection of zero dimensional ideals. Small fixes and more missing methods.
2012, May
More, refactored and fixed algorithms for Wu-Ritt characteristic sets in class CharacteristicSetWu. Unit tests are in CharSetTest. jython and jruby script access to characteristic set algorithms in methods CS(), isCS(), csReduction(). Small fixes and improvements.
2012, March
The Jython and JRuby scripting classes PolyRing are now injecting the polynomial ring variables into the top level interpreter environment by default. New class GroebnerBaseFGLM to compute a Gröbner base according to the "FGLM" algorithm. It computes a Gröbner base with respect to a graded term order and then constructs the Gröbner base with respect to the requested term order via linear algebra in the residue class ring. Changes from '{}' to '()' in GenPolynomial to string conversion. New launcher shell script jas. Small fixes, improvements and a missing method implemented and in PolyUtilApp.
2012, February
Refactorings to simplify type parameters and loosen type conditions. New package edu.jas.ufdroot to remove cyclic package dependencies again. Improved selection of factorization implementations in FactorFactory classes and better suited constructors of the factorization implementations. Small fixes and improvements.
2012, January
Some algorithms for Wu-Ritt characteristic sets and unit tests in class PolyGBUtil. Small fixes and improvements.
2011, Sylvester
Modular variants and parallel proxy versions of resultant algorithms implemented. Cleanup and filled missing methods in GreatestCommonDivisor* classes in the edu.jas.ufd package. Fixed ModLong to ModInteger conversion. Small fixes, improvements and refactorings of methods to right classes.
2011, December
Switched to Java 7 for development. JAS will still compile and run on Java 6 and Java 5. A new online repositoriy for JAS on Google code which contains a bug-tracker. Definition of variables for polynomial ring generators in the jython and jruby scripting interface. More JRuby examples.
2011, October
Separated test classes to new test source tree (trc). New scripting classes for Gröbner base computations according to Eder and Perry (F5, Arri, GGV) and adapted jas.py in JAS for the required methods. More JRuby examples. Small improvements and fixes.
2011, September - October
Release 2.4 updates all depending packages to the latest version and prepares for JAS 3.0. Updates for Jython 2.5.2 and JRuby 1.6.4. A new index of all algorithms from the book Algorithms for Computer Algebra by Geddes & Czapor & Labahn to their JAS equivalents. Small improvements and fixes again in multivariate integral polynomial factorization.
2011, September
Bug fixes and missing cases for multivariate integral polynomial factorization with multivariate Hensel lifting. Further improvements and fixes.
2011, August
Experimental multivariate integral polynomial factorization with multivariate Hensel lifting in method factorsSquarefreeHensel() in class FactorInteger. Improved multivariate Hensel lifting in class HenselMultUtil. Small improvements and fixes.
2011, June
Experimental ideal complex root computation in method complexAlgebraicRoots() in class PolyUtilApp. Simple isolating interval refinement for real and complex roots. Alternative factoring of univariate polynomials over algebraic number fields via prime ideal decomposition in class FactorAlgebraicPrim. Improved parsing of complex numbers. Forced term orders in some situations and further small improvements and fixes.
2011, May
Complex roots represented by ideal real roots, uses new class RealAlgebraicNumber and RealAlgebraicRing in package edu.jas.application. New experimental RootFactory with methods to compute complex roots for polynomials with coefficients in some complex algebraic extension field of the rational numbers. Uses the respective classes form package edu.jas.root in a recursive setting. New generic factorization classes FactorRealAlgebraic and FactorRealReal. Small improvement for reduced / minimal Gröbner base computation.
2011, April
Multivariate algebraic ring / field extensions using class ResidueRing. Jruby and Jython versions and examples of the extension field builder. Small improvements and bug fixes for latest Eclipse and Java 1.7 version.
2011, March
Easy to use construction of towers of extension fields in class ExtensionFieldBuilder with methods for algebraic and transcendental field extensions. Improvements in real and complex algebraic numbers. Improved polynomial parser for recursive representations. Small bug fixes.
2011, February
New class HenselMultUtil for multivariate Hensel lifting. Will be used in polyomial factorization in the future. Some parts of greatest common divisor using multivariate Hensel lifting. The JAS source (r3408) compiles on Apache Harmony 6.0 (r991881). The unit tests pass with the exception of test cases involving object serialization.
2011, January
New scripting interface to Ruby (JRuby). Ruby allows rational number literals as p/q, which are better than the Python tuple form (p,q). Some toScript() methods rewritten to reflect the Ruby language requirements and to differentiate between Ruby and Python. More precise exceptions for modular computations to return also the discovered factors.
2010, December, 28
Cleanup of package structure so that all cyclic dependencies have been removed, see diagram. Split factory parsing parts from GenPolynomialTokenizer to RingFactoryTokenizer. Some artificial code was required to use solvable polynomials as ring elements since solvable polynomials cannot implement RingElem<GenSolvablePolynomial<C>>. This resulted in some cases in wrong method dispatch for the multiply() method due to compiler optimizations. A work around to detect and repair this is now implemented in class GenPolynomial.
2010, December, 18
New critial pair selection for Gröbner base computation with syzygy based algorithm after Gebauer and Möller in class OrderedSyzPairlist. Refactoring of Gröbner base classes to optionally use the new pair selection. Back port of some JDK 1.6 constructs to be again compatible with JDK 1.5. Small improvements in Kronecker factor combination in class FactorAbstract. Fixed race condition in ThreadPool and improved termination detection in Terminator. Fixes in parallel reduced Gröbner base computations. Fixed univariate polynomial construction in Ideal.
2010, October
Multivariate Taylor series expansion interface and implementation. Improved multivariate power series for standard base computation. Refactored methods to better suited classes and moved classes to decouple packages, e.g. Quotient* to package edu.jas.ufd. Fixed small bugs and cosmetic.
2010, September
Multivariate power series in classes MultiVarPowerSeries and MultiVarPowerSeriesRing. Mora's tangent cone reduction algorithm and standard base computation for power series in package edu.jas.ps. Iterator over exponent vectors.
2010, August, 28
Iterators for finite and some infinite structures and finite and infinite cartesian products of them. Fixed constructors to comply with the (new) Java memory model. Small bug fixes and improvements. More meaningful exceptions and some renamings.
2010, August, 8
Improved the polynomial parser to accept rational numbers denoted with decimal points and to accept BigDecimal coefficients. Removed the use of the underscore for algebraic number coefficients in the polynomial parser. Now every recursive call of parse() from a ring factory is triggered by braces which can be nested to any depth. Fixed synchronization bug in solvable polynomial relation tables and a parallelization bug in parallel solvable polynomial Gröbner base computation. Use of unbounded thread pools to avoid dead-locks. Added remaining parts for the square-free decomposition in polynomial rings of characteristic p > 0. Changed the script representation of AN (AlgebraicNumbers).
2010, July
Downgraded for Java 5 language and run-time system for use with systems relying on older Java versions, for example MathPiper and GeoGebra. New class edu.jas.kern.TimeStatus to provide user feedback for long running tasks via method checkTime(). Implemented some missing extGB() methods. GBFactory for the selection of appropriate Gröbner base implementations. New method isFinite() for all ElemFactorys and usage in SquarefreeFactory. Added some missing parts for the factorization in polynomial rings of characteristic p > 0 and ideal decomposition.
2010, June
Factory for Gröbner base algorithm implementations in class GBFactory. New GBProxy like GCDProxy to run a sequential and a parallel Gröbner base computation concurrently. Primitive element computation via normalPositionFor() in methods primitiveElement() together with several conversion methods convertToPrimitiveElem(). A new index of all algorithms from the book Gröbner bases to their JAS equivalents.
2010, May, 28
Implementation of arbitrary dimensional ideal radical-, irreducible-, prime- and primary-decomposition in class Ideal with methods radicalDecomposition(), decomposition(), primeDecomposition() and primaryDecomposition(). Computation of extension and contraction ideals. Unit tests for the decomposition methods. Fixed a bug in multivariate polynomial factorization in Kronecker's method. Fixed a bug in squarefree decomposition in inseparable case. Added NO_THREADS flag to edu.jas.kern.ComputerThreads to avoid (some) thread creation for usage in Google app engine.
2010, May, 8
Implementation of zero dimensional ideal radical-, prime-, primary- and root-decomposition in class Ideal with methods zeroDimRadicalDecomposition(), zeroDimDecomposition(), zeroDimPrimeDecomposition(), zeroDimPrimaryDecomposition() and zeroDimRootDecomposition(). Exact 0-dim ideal real root computation and approximation in methods PolyUtilApp.realAlgebraicRoots() and decimalApproximation(). Small enhancements to Javadoc comments.
2010, April
Some more documentation for package edu.jas.ufd, simplified and improved the factory classes. Refactorings of parallel Gröbner bases computations for solvable polynomial rings. Improved logging for distributed Gröbner bases and distributed middle-ware.
2010, March
Decimal approximations for real and complex roots based on Newton-Raphson iteration restricted to isolating intervals or rectangles. Small enhancements for partial Gröbner bases. Added some Mersenne primes to PrimeList. Construction of minimal univariate polynomials in zero dimensional ideals. Supersets of complex and real roots of zero dimensional ideals. More unit tests for real and complex roots of univariate polynomials and zero dimensional ideal roots. Minor enhancements and fixes.
2010, February
Gröbner bases for sub-sets of variables in class GroebnerBasePartial. Small enhancements: polynomial recursive coefficient parser and a matrix parser. Book-keeping of all used polynomial variable names. New and improved unit tests.
2010, January
Factorization for polynomials with Complex coefficients via algebraic coefficients in Q(i). New classes ModLong and ModLongRing for faster modular arithmetic. New interfaces Modular and ModularRingFactory implemented also by ModInteger to make both interchangable. Improved factorization and serveral refactorings. Factorization mod p = 2 is now implemented.
2009, December
Added a Git repository and a link to Ohloh code analysis of JAS. Cosmetic, small updates and a simple Java scripting interface. New classes for complex root isolation ComplexRoots, ComplexRootsAbstract, ComplexRootsSturm. The implementation provides an exact infallible method which follows the numeric method of Wilf. It uses Sturm sequences following the Routh-Hurwitz Method to count the number of complex roots within a rectangle in the complex plane.
2009, November
New package for the elementary integration of rational functions developed together with Axel Kramer during the computer algebra seminar 2009. The implementation is based on the book Bronstein: Symbolic Integration I. New adapter (commons-math_adapter.jar) for JAS to the Apache Commons Math library version 2.0 by Axel Kramer. Cosmetic, small updates and a jython example for integration.
2009, September
Improved comprehensive Gröbner bases with explicit classes for several alternative implementations of multiplicative sets. Base class is MultiplicativeSet, in sub-classes polynomials made co-prime in MultiplicativeSetCoPrime, polynomials made co-prime and squarefree in MultiplicativeSetSquarefree and polynomials made irreducible in MultiplicativeSetFactors. New distributed hybrid Gröbner base computation with new class TaggedMesageChannel to handle multiple message types and partners over one socket connection. Improved object serialization in distributed hash table. Adapter updated for JLinAlg version 0.6.
2009, August
New adaptor classes (jlinalg_adapter.jar) to use the linear algebra library JLinAlg from JAS. Improvements in the distributed Gröbner bases algorithms. Minor fixes and improvements.
2009, July
Code and output cosmetic, minor fixes and improvements. New interface ToRational used for BigRational and RealAlgebraicNumber to remove type case distinctions in Interval. clone() removed from Element interface because of compiler changes.
2009, June and July
Improved absolute factorization for splitting fields. Fixes and further improvements. Implemented factorization over inseparable field extensions. Fixed squarefree factorization and added unit test. Refactored squarefree tests to separate classes. Refactored squarefree algorithms to separate classes. Interface is Squarefree, abstract class is SquarefreeAbstract. Other main classes are SquarefreeFieldChar0, SquarefreeFiniteFieldCharP and SquarefreeInfiniteFieldCharP.
2009, June
Improved algebraic and absolute factorization. FactorAlgebraic can now also handle factorizations over multiple algebraic extensions like for example Q(i)(sqrt(2)). Class FactorAbsolute is now also extended by FactorAlgebraic, so that absolute factorizations can be computed over algebraic extensions of Q. Added new containers for absolute factorization results and tests for correct absolute factorizations. More toScript() methods and improvements in Jython script interface. Minor additions and fixes.
2009, May
Improved Jython script interface to handle most of the implemented rings, developed in cooperation with Raphael Jolly. New or improved Python functions ZZ, ZM, QQ, DD, CC, Quat, Oct, PolyRing, AN, RealN, RF, RC, LC, SolvPolyRing and RR, PS, Vec, Mat for the construction of rings and elements. Added generic Complex class and ComplexRing factory. Fixed a programming bug in factorization code.
2009, April
Added factory() method to Element interface to have an uniform way to obtain a corresponing ring object. Improved RealAlgebraicNumber so that it can be used as polynomial coefficients, for example GenPolynomial<RealAlgebricNumber<BigRational>>. Real root isolation can now also be used for polynomials with real algebraic coefficients, for example RealRootsSturm<RealAlgebraicNumber<BigRational>>.
2009, March
Implemented univariate polynomial real root isolation algorithms and real algebraic numbers in package edu.jas.root during CISIS/ECDS 2009. Reached 100.000 lines of Java code.
2009, February
Finished first version of polynomial factorization algorithms. Refactored package names edu.jas.ring to edu.jas.gb and edu.jas.module to edu.jas.gbmod.
2009, January
Switch to version 2.3 with experimental factorization of polynomials. Factorization interface with FactorAbstract class for common codes. Factorization of univariate polynomials with several coefficient rings: modulo primes in class FactorModular, over integers in class FactorInteger, over rational numbers in class FactorRational and over algebraic numbers in class FactorAlgebraic<C> (where C can be ModInteger or BigRational). Multivatiate polynomials are reduced to the univariate polynomials via Kronecker substitution and are therefore not very efficient. Refactorings and fixes.
2008, December
Fixed squarefree part and factor computation for modular coefficients. Fixed polynomial compareTo to be transitive as required by Javas SortedMap implementations. Implemented an adaptor package for Apache Log4j to delegate logging calls to native Java logging.
2008, September
Implemented univariate power series during ADG2008 as RingElem and RingFactory types in package edu.jas.ps in classes UnivPowerSeries and UnivPowerSeriesRing. The implementation follows the "Infinite Streams in Java" paper of D. Gruntz in PPPJ2006.
2008, August, 11
Added jython html documentation generated by epydoc. Added jython module to allow native polynomial expression input.
2008, August, 8
New release 2.2. Implemented interface to use JAS as an meditor engine, see jscl-meditor.
2008, July
Finished implementation of comprehensive Groebner bases via Groebner systems. Object oriented class layout uses Condition and ColoredSystem classes. Conditions consist of an ideal (with lazy Groebner base computation) for the conditions equal to zero and a multiplicative set for the conditions not equal to zero. Non-zero condition polynomials are reduced modulo the ideal of condition zero polynomials. The squarefree part from both condition polynomials is used. It differs from the MAS implementation by Schoenfeld, Pesch and others by the ideal used to store the zero conditions and some more details.
2008, June
Added dimension computation to Ideal. Added term order optimization method to Ideal. Refactored ExpVector for different storage unit implementations of the exponent arrays. Supported storage units are long, int (now the default, as seems to be the fastest), short and byte. The respective classes are ExpVectorLong, ExpVectorInteger, ExpVectorShort and ExpVectorByte.
2008, January and February
Added Groebner bases for polynomial rings over regular rings RGroebnerBaseSeq and RGroebnerBasePseudoSeq. Refactorings and fixes.
2007, November and December
Added von Neuman regular rings as (finite) direct products of rings, Product and RegularRingElem. Added fraction free pseudo reduction and Groebner bases GroebnerBasePseudoSeq. Minor refactorings and fixes.
2007, October
Added Groebner bases in polynomial rings over principal ideal domains and Euclidean domains, so called D- and E-Groebner bases, DGroebnerBaseSeq and EGroebnerBaseSeq. Added test methods for reducibility and refactored sequential Groebner base implementations.
2007, September
Minor refactorings and fixes. Modular rational functions and related conversions.
2007, August, 19
Added term order optimization for polynomial and rational function coefficients.
2007, August, 12
Cleanup of UFD code and subversion exports. Term order optimization also available in jython.
2007, July, 28
Added term order optimization class from old DIP/MAS system. This introduced a dependency on JDK 1.6. Refactored source tree to allow fully functional subversion exports.
2007, July, 12
New global class edu.jas.kern.ComputerThreads to represent a thread pool. To stop JAS, when the pool has been started, it is required to call ComputerThreads.terminate().
2007, July, 11
New preemptive cancellation handling. Introduced class PreemptingException as runtime exception and a global class PreemptStatus to allow or deny preemption cancellation. GenPolynomialRing queries PreemptStatus upon creation. GenPolynomial checks preempt cancellation handling and thread interrupt status on construction. If preemption is requested, it throws PreemptingException. This allows e.g. GCDProxy to ignore the respective sub-task and get the thread free. Removed explicit isInterrupted() checks in edu.jas.ufd package.
2007, July, 10
Refactored generation of (lists of) univariate polynomials from SolvableGroebnerBase* to GenSolvablePolynomialRing and GenPolynomialRing. Implemented generic Power class in edu.jas.structure, refactored power() in subresultant PRS.
2007, July, 9
Added unit tests for distributive law in arith and poly packages. Review of all documentation comments.
2007, July, 8
Added assertions to check for number of polynomial variables in GenPolynomial. In ModInteger and AlgebraicNumber inverse() now throws a NotInvertibleExecption, which extends runtime exception. Fixed some correctness bugs detected by Findbugs.
2007, July, 7
Refactored ModInteger for ModIntegerRing factory. Changed all depending classes. Refactored GenPolynomial.getMap() to return unmodifiable SortedMap. Refactored GenPolynomial.val using methods from jas.ufd package to jas.poly package. ExpVector.getVal() renamed and made package private. Logger variables now also final.
2007, June, 10
Improved InterruptedException handling. Refactored use of edu.ky.parallel package to use edu.jas.util and java.util.concurrent. Refactored project web-site.
2007, April and May
Implementation of greatest common divisor algorithms. Using recursive types. Implemented remainder sequences: primitive, monic, subresultant. Implemented modular methods with chinese remaindering for ModIntegers and evaluation in finite fields to reduce the number of variables. Implemented Hensel lifting: linear and quadratic; mod ideal is still missing. Factory classes to select "best" implementations. Proxy classes to run probable good implementations in parallel, taking the result of the first terminating algorithm. Refactored many classes to fit for the new requirements. New method characteristic() in RingFactory and implementing classes. Changed Quotient (rational function) to use new gcd algorithms. Can compute GBs for polynomials with rational function coefficients.
2006, March
Refactored ring package to separate application package with more application of Groebner bases oriented classes. The ring package could now be renamed to gb package. Cosmetic and documentation improvements, e.g. javadoc package descriptions and type parameter tags, removed all tabs in all java files. Implemented generic Quotient(Ring), Residue(Ring) and Local(Ring).
2006, February, 27
Implemented parallel solvable Groebner base algorithms and tests. New class distributed ThreadPool. Cosmetic and code improvements spotted by eclipse, lint4j and jdepend. Refactored module package to separate vector package with basic linear algebra and list handling classes. Refactored to allow different Groebner base or reduction engines where appropriate. Split Syzygy etc. to an interface and a class. Factored basic linear algebra out of Syzygy etc. Adapted jython files to Jave code refactorings. Reorganized jar files and documentation.
2006, February, 12
Moved old examples to MAS subdirectory and new examples to examples directory. Implemented some right version algorithms using opposite rings. Switched to subversion from cvs. Fixed bugs in new left syzygy algorithm.
2006, January
More documentation and cosmetic. Implementation of an extended Groebner Base algorithm and arbitrary base syzygy computation. GenPolynomialTokenizer enhanced to parse algebraic number and Galois field coefficients. Fixed an error in leftNormalform.
2005, 12, 30
New classes CriticalPair and CriticalPairList replace OrderedPairlist. Reworked GB parallel and distributed versions to better respect sequential version critical pair sequences. Fixed some race conditions in parallel and distributed algorithms.
2005, 12, 28
Refactored all classes to remove static methods. So to use any method at first an appropriate object is required. Also class organization has changed to interfaces, abstract classes and concrete classes, e.g. GroebnerBase, GroebnerBaseAbstract, GroebnerBaseSeq, GroebnerBaseParallel and GroebnerBaseDistributed.
2005, 12, 27
Implemented new Ideal class with some ideal operations like sum, product, intersection and quotient. Added TermOrder extension and contraction.
2005, 11-12
Updated documentation comments.
2005, 7, 24
Updated old Java JDK 1.4 branch. Bugfixes (in twoSidedGB), minor changes and cosmetic.
Updated documentation for new Java JDK 1.5 branch.
2005, 5-7
Working through all classes to introduce type parameters and making all implied modifications.
2005, 5, 5
Switched to Java 1.5. Now using covariant returns for implemented interfaces.
2005, 3, 25-29
Some module algorithms implemented. Activated project web pages.
2005, 3, 12-19
Some Syzygy algorithms implemented. Cosmetic on comments and forked web-log.
2005, 3, 5
For the python languege and interpreter exists also a Java version named jython. This system can directly access Java classes and execute Java methods. Added some jython modules Ring, Ideal, SolvRing and SolvIdeal, to access jas GB algorithms from jython.
2005, 2, 25-28
Penality of commutative GB computed as non-commutative left GB is about 24% for (graded) Katsura 6 to 74% for (graded) Katsura 5. Commutative GB computed as non-commutative twosided GB is about a factor of 4 for (graded) Katsura 5 to a factor of 9 for (graded) Katsura 5. Penality for weighted degree term order compated to graded Term order is not measurable or sometimes better. Fixed error in polynomial getONE() to correct term order. Parser for non-commutative problems with relation tables (but only commutative representations) and RunSGB main routine.
2005, 2, 14-21
New TermOrder with direct generation of Comparators for ExpVector comparisons. Split term orders (elimination orders) and weighted degree orders.
2005, 2, 4-8
New unit test case for TermOrder. Fixed weak point in polynomial getONE() to correct number of variables, e.g. correct exponent vector size. Polynomial constant ONE still has wrong exponent vector size. Deleted many old polynomial classes.

Implemented noncommutative product for solvable polynomials, together with relation tables. SolvableOrderedMapPolynomial extends OrderedMapPolynomial. RatSolvableOrderedMapPolynomial extends SolvableOrderedMapPolynomial. Interface SolvablePolynomial extends Ordered Polynomial. Some more left multiplication methods, left reduction and left Groebner Bases, twosided Groebner Base test and computation. Pairlist class changed to avoid usage of criterion 4 if running for SolvablePolynomials, also criterion4() method itself checks for SolvablePolynomials.

RelationTable timings I, U(sl_3)
run / n 2 3 4 5 6 7 8 9 10 11 12 13 14 15
first 3 13 32 92 128 188 274 420 683 1126 1795 2793 4380 6741
second 0 1 2 3 4 5 6 8 10 13 16 21 27 35

Timings in ms on AMD XP 2800+. Computation of (Y^n) * (X^n) with respect to the relation Y * X = X Y - H. In the first run the relation table is populated with the products Y^i * X^i, i = 2,...,n. In the second run the relations are reused, showing almost no computing time anymore for the products.

RelationTable timings II, U(sl_3)
run / n 2 3 4 5 6 7
first 28 94 303 1234 5185 24647
second 1 12 107 782 4569 23897

Second example shows the computation of ( Xa + Xb + Xc + Ya + Yb + Yc + Ha + Hb )^n in U(sl_3). Since in the relation table only products of two variables are stored, the improvement is minimal (for low n).

2005, 1, 24-31
Removed old deprecated classes. Todo: let DistHashTable implement Map Interface. Reimplemented Reduction.Normalform so that asynchronous update of the polynomial list is possible and respected. In case a new polynomial arrives, the reduction is restarted from the beginning. Continuing with the done work and rereducing so far irreducible terms would be an alternative. Todo: use JDK 1.5 java.util.concurrent with interference free Lists, BlockingQueues.
Distributed computation timings, Katsura 6 (G)
# Threads
CPUs
# JVMs time (sec) #put #remove % total
1, seq 1 160.2 70 327 13.5
1, par 1 157.0 70 327 13.5
2, par 1 82.2 72 329 12.7
1, dist 1 177.2 77 334 11.4
2, dist 2 92.2 90 347 8.6
4, dist 2 56.2 112 369 5.9
8, dist 2 58.9 255 516 1.5
4, dist 4 51.2 117 374 5.5
6, dist 4 43.7 129 386 4.6
8, dist 4 62.9 259 519 1.5

Timings taken on a 16 CPU Intel Xeon SMP computer running at 2.7 GHz and with 32 GB RAM. JVM 1.4.2 started with AggressiveHeap and UseParallelGC.
#JVMs = number of distinct Java virtual machines. #put = number of polynomials put to pair list. #remove = number of pairs removed from pair list, i.e. after application of criterions, but including nulls up to now. % total = per cent of removed pairs from total pairs generated, #remove / ( #put * (#put-1) / 2 ) * 100.

Distributed computation timings, Katsura 7 (G)
# Threads
CPUs
# JVMs time (sec) #put #remove % total
1, dist 1 24726.2 140 781 8.0
2, dist 2 12356.1 165 806 5.9
4, dist 4 6859.3 218 859 3.6
8, dist 4 7465.1 411 1054 1.2
8, dist 8 6412.9 344 986 1.6
8, dist 8 7173.3 399 1041 1.3

Overhead for distributed variant is about 10% in Katsura 6 (G). Distributed 1 means one distributed process is running for the reduction of S-polynomials. There is always a master process handling polynomial input / output, setup and management of distributed workers and handling of the pair list. Communication between master and workers is always via TCP/IP with object serialization, even if running on one computer.

2005, 1, 15-16
Further things to improve in GB algorithms (from tsp): local work queues, i.e. local Pairlists, improve data locality in polynomials and lists, communication using message types, reduce object serialization in DL-broadcast by using MarshalledObjects, reduce communication in Pair send by not sending polynomials but indicies (requires distributed hashtable instead of DL), interleave communication and computation by adding a communication thread in the distributed client.

New classes implementing a distributed hash table to hold the polynomials in distributed GB. Index of polynomials in Pairlist is used as hash key. Communication is now using message types GBTransportMess. Now polynomials are only transported once to each reducer since only polynomial hash indexes are transported. Distributed list is asynchronous and late updated, so some duplicate H-polynomials (head terms) could be (are) produced. Solution by local put to hash table with dummy index? Timings are not dramatically better.

Todo: check reduction algorithm to use later arriving polynomials.

2005, 1, 9-14
Introduced all direct improvements in util classes found so far. (ChannelFactory and others) On parallel computers the following JVM options (1.4.2) must be used:
  -Xms200M -Xmx400M -XX:+AggressiveHeap -XX:+UseParallelGC
Memory must be adjusted with respect to your situation.

Seperated versions with Pair Sequence Respecting Order (PS) and normal versions. PS versions try to keep the order of reduced polynomials added to the ideal base the same as in the sequential version. Normal versions now running OK on parallel computer with the right JVM options. Refactoring with Eclipse (organize imports, static methods).

Parallel computation timings, Katsura examples
# Threads
CPUs
Katsura 6 TO(G)
load*
Katsura 6 TO(G)
empty*
Katsura 7 TO(G)
load*
Katsura 7 TO(G)
empty*
seq 184.5 153.3
1 181.5 4% / 159.7 28418.6
2 118.6 s2.02 / p2.11 / 75.6 p2.06 / 13760.0
4 76.8 s3.79 / p3.95 / 40.4 6256.9 p4.56 / 6225.1
8 43.2 s7.19 / p7.49 / 21.3 3240.7 p8.56/ 3318.8
10 42.5
12 40.5 2288.1 p9.90 / 2868.4
14 31.2
16 51.9 s8.19 / p8.54 / 18.7 5376.4 p12.59 / 2256.1

Timings taken on a 16 CPU Intel Xeon SMP computer running at 2.7 GHz and with 32 GB RAM. JVM 1.4.2 started with AggressiveHeap and UseParallelGC.
*) timing taken with other load on the CPUs. +) timing taken with no other load on the CPUs.
Speedup: s = relative to sequential, p = relative to parallel with one thread / CPU.
Scaling from 8 to 16 CPUs is bad, but also observed on non CA / GB Examples (Java and C/FORTRAN).

2004, 10, 3
Generator for Katsura examples (from POSSO / FRISCO examples). Timings on an AMD Athlon XP 2800 (2086MHz) with log level INFO. Log level WARN would gain 10-20 %.
Timings Katsura examples
N
vars = N+1
TermOrder Seconds TermOrder Seconds
7 G 32044.204 L
6 G 112.641 L
5 G 4.195 L
4 G 0.431 L 11.650
3 G 0.153 L 0.310
2 G 0.031 L 0.032
2004, 9, 20-26
Changed OrderedPairlist to record the sequence of pairs taken from the list. New methods putParallel(), removeParallel() and helper methods. Sequence numbers are generated and reduced polynomials are only put to the pair list if corresponding pair number is in correct (sequential) sequence. The ordered list / queue pairsequence (TreeMap/SortedMap) keeps track of the polynomials not yet put to the pairlist.
Parallelism is possible as long there are pairs to be reduced. But non zero reduced polynomials are only put into the pairlist if the polynomial would be put into the pairlist in the sequential Buchberger algorithm. GroebnerBase algorithms had to be modified to record that a polynomial reduced to zero.
2004, 9, 19
Changed order of Pair inserts for pairs with same LCM of HTs. Added sequence number to each Pair and indicator if Pair did not reduce to zero.
2004, September
Implemented Java server (ExecutableServer) for remote execution of objects implementing the RemoteExecutable interface.

New setup for the distributed computation of GBs: the GB master now sends the client code to some ExecutableSevers based on a maschine file with host and port infos about the distributed environment.

Improved the PolynomialTokenizer so that it can read almost unedited old MAS GB input files: ** exponents and parenthesis around polynomials. Lines starting with # are treated as comments. Comments (* *) and parenthesis within polynomials are still not supported.

Implemented a common driver for GB computations RunGB. Sequential, thread parallel and distributed computation can be selected by command line parameters. The input is taken from a file. The number of threads respectively the number of distributed clients can be specified. For distributed execution the host and port information is taken from a maschines file.

Usage: RunGB [seq|par|dist|cli] <file> #procs [machinefile]

Added methods putCount() and remCount() in OrderedPairlist to count the number of polynomials put and get from the pair data structure.

pairlist put and remove, trinks6
# Threads 1 seq 1 par 2 par 2 par 3 par 4 par 5 par 1 dist 2 dist 3 dist 4 dist 4 dist 4 dist 5 dist
# put 22 22 43 26 28 28 28 22 25 28 37 40 33 27
# remove 25 25 61 30 32 32 41 26 33 42 47 61 54 69

Timings @ 500 MHz on one CPU and one maschine and log4j level INFO are:
ca. 2.5 - 3.5 seconds for sequential GB,
ca. 2.5 - 6 seconds for parallel GB,
ca. 5.5 - 9 seconds plus 5 seconds sync time for distributed GB.
Network shuffling of polynomials seems to account for 3 seconds in this example.

Problem uncovered: the distributed version of GB needs an avarage of 5 seconds to sync with all clients (on one maschine). This is way to much for execution times in the range of 2 to 8 seconds.

Redesign of DistributedList, now using TreeMap to keep the list entries in proper sequence. As key a natural number is used, which is assigned by the server to successive add() requests. The server now also holds a copy of the list by itself. So the retransmission of list elements to late arriving clients is possible. This doubles the space required to store polynomials, but removes initial delays to sync all clients to receive all list elements.
By retransmission the DistributedList synchronization delay during DistributedGB could be removed. However the problem of about 5 seconds delay in startup of DistributedGB still remains. It is not visible where and why this delay occurs.
Further improvements would be the removal of list elements or the clearing of the list. Next steps could be distributed HashMap or TreeMap.
An important improvement would be to keep serialized copies of the list elements (polynomials) at the server and to avoid many time serialization during broadcast.

2004, 2, 26
Ideas to implement: a distributed task launcher like mpirun, a daemon to run on a distributed system to work with the launcher, solvable polynomials and non-commutative GBs.
2004, 2, 1
Parallel computations with the Rose example are at ?? h with 3 threads on 2 Pentium 4 @ 3.0 GHz hyperthreading CPUs.

With one thread the time is 30.6 h. Besides the better CPU speed, this makes a 5 % improvement on JDK 1.4 compared to the older timings from a JDK 1.3 and the new polynomial implementation.

2004, 1, 25
Spin model checker: Setup Promella description of parallel and distributed GB algorithm. Used to verify the safety and liveness properties of the algorithms.
2004, 1, 17
New (minimal) class DistributedList in preparation of a distributed GB algorithm. Made all mutually transported objects Serializable. Fixed ChannelFactory and other classes in edu.unima.ky.parallel to be interuptable. Moved Semaphore back to edu.unima.ky.parallel. First version of a distributed memory GB. One problem was inner class Pair results in serialization of outer class OrderedPairlist, which is not intented. So Pair is now a proper class. Distributed version mainly working. Problem with signaling and termination if 1 in GB.
2004, 1, 10
Refactored Groebner base for new OrderedPolynomials and split sequential and parallel GB implementations. New unit tests for sequential and parallel GBs. GB now works for arbitrary Coefficients.
2004, 1, 5
New coefficient domains BigComplex and BigQuaternion. New test unit for all coefficients. Based on these coefficients are new polynomials, e.g. ComplexOrderedMapPolynomial and QuatOrderedMapPolynomial together with unit tests. Problem: RatPolynomial requires DEFAULT_EVORD be set correctly in ExpVector. This is now solved for the new OrderedMapPolynomials.
2003, 12, 29
New organization of polynomials:
2 interfaces: UnorderedPolynomial and OrderedPolynomial. Ordered polynomials have a term order and are implemented using some SortedMap (e.g. TreeMap). Unodered polynomials are implemented using some HashMap (e.g. LinkedHashMap).
2 abstract classes: UnorderedMapPolynomial and OrderedMapPolynomial. Both implement all algorithms which do not need an explicit coeficient domain, i.e. they are formulated in terms of the Coefficient interface from jas.arith.
2 or more classes which extend the respective abstract classes: RatUnorderedMapPolynomial and RatOrderedMapPolynomial both need explicitly coefficients from BigRational or others.

Multiplication with ordered polynomials is about 8-10 times faster than the multiplication with unordered polynomials. Also the multiplication with semi-ordered polynomials (LinkedHashMap) with orderpreserving addition is about 7-8 times slower than multiplication with ordered polynomials.

All implementations are based on Map interface and classes. The Map maps exponent vectors (from some monoid) to coefficients (from some domain). This is in sync with the mathematical definition of multivariate polynomials as mappings from some monoid to some domain. Term orders are represented by a TermOrder class which provides the desired Comparator classes for the SortedMap implementation.

2003, 12, 28
Things to do: refactor and test HashPolynomial, check performance. Improve the parallel GB algorithm, e.g. parallelize the reduction algorithm. Develop a distributed memory version of the parallel GB algorithm.
2003, 12, 27
Using ArgoUML to produce class diagramms for jas. Refactoring GB from edu.jas.poly to edu.jas.ring.
2003, 12, 21
Setup for JUnit version 3.8.1. Added JUnit testing with Apache Ant version 1.6.0 to build.xml.
2003, September
Experimented with LinkedHashMap instead of TreeMap (SortedMap) for the representation of polynomials. Algorithms which work also with LinkedHashMap have 1 or 2 in their names (now in new class HashPolynomial). LinkedHashMap has the property of using the insertion order for the iterator order. With LinkedHashMap the add() and subtract() can be reformulated to use a merging algorithm as in the original DIP implementation. Assuming the Map insertion order is the the same as the polynomial term order.

However the merging add/subtact implementation is a factor of 2 slower than the TreeMap implementation. Complexity for a+b is
2*(length(a)+length(b)) for access and merging pre sorted polynomials and
2*length(a)+length(b)+length(b)*log2(length(a+b)) for TreeMap clone, access and insertion.

The merging multiplication implementation is by a factor of 10 slower than the TreeMap implementation. Polynomial size was ~100 terms and the product contained ~8000 terms. Complexity for a*b is
lab = length(a)*length(b) coefficient multiplications for both implementations
plus 2*length(a*b)*length(b) for merging summands, respectively
plus length(a)*length(b)*log2(length(a*b)) for TreeMap insertion. Since for sparse polynomials length(a*b) = lab, the TreeMap complexity is asymptotically better in this case:
2*length(a)*length(b)*length(b) =>= length(a)*length(b)*log2(length(a*b))
For dense polynomials with length(a*b) ~ length(a)[+length(b)], then the LinkedHashMap complexity is asymptotically better:
2*length(a)*length(b) =<= length(a)*length(b)*log2(length(a*b))

2003, 3, 15
Some testing with new AMD Athlon XP 2200+ @ 1.8 GHz, 133x2 MHz memory access.
Trinks 6: 1.013 sec with log4j level WARN, parallel 1.058 - 1.740 sec.
Trinks 7: 0.553 sec with log4j level WARN.
2003, 2, 2
Replacing all System.out.println by Log4j logging calls. adding some Junit tests.
2003, 1, 28
Some testing with gcj (Gnu Java Compiler). this compiler gernerates native executable binaries. the timings are not better than with a jit, often worser.

Parallel computations with the Rose example are at 18 h with 4 threads on 2 Pentium 4 @ 2.4 GHz hyperthreading CPUs. With one thread the time is 40 h.

2003, 1, 26
timings with JDK 1.3 (from IBM) are 30% to 40% faster than with JDK 1.4.1 (from Sun). timings on PowerPC 604 @ 200MHz JDK 1.3 (from IBM) JDK 1.2 (from Sun) are a factor 3.5-4.5 slower than on Intel PIII @ 450 MHz. on PowerPC not using jit is faster than using a jit, ca. 20% - 30%.
2003, 1, 12
General differences between sequential and parallel GB algorithms

Does this influence the validity of criterion 3? Access to pairlist is synchronized. Pairs are marked as reduced as soon they are taken from the list. But the algorithm terminates only after all reductions of pairs have terminated. So criterion 3 holds.

New implementation of parallel version of GB. Removal of pairs is now also in parallel. But ordering of pair insertion is no more preserved

Timings are more stable and slightly better than that of sequential GB.

Todo: unit tests, comments, ...

2003, 1, 7-11
Renamed jas to mas2jas, new cvs repository for jas, import and checkout.

Improved parallel version of GB.

Todo: CVS, comments, polynomial implementation using LinkedList, parallel GB simplify

With the improved algorithm the running time of the parallel GB becomes more stable and not slower than the sequential GB. However there is still no significant speedup.

parallel GB on one cpu
# Threads 1 2 3 4 5 6 7 8 16
# Reductions 25 25 27 25 25 25 25 25 25

parallel GB on 4 cpus
# Threads 1 2 3 4 5 6 7 8 16
# Reductions 22 24 30, 28, 24, 29 28 29 42 32 32 37

2003, 1, 6
implemented parallel version of GB using ThreadPool from tnj

parallel results:
Trinks 7: mas 0.598 sec, jas 0.918 sec, jas par 0.955 sec
Trinks 6: mas 26.935 sec, jas 3.211 sec, jas par 3.656 sec
mas: including startup and gc time, jas: excluding startup of jvm and including gc time, jas par on single processor timing on P-3@450

this make for a penality of 12 percent, all tests with output to files,
2003, 1, 5
timing benchmarks between BigRational and Coefficient versions of the algorithms, the difference seems to be less than 1 percent with no clear advantage of one side
the sum and product algorithms have not jet optimal complexity, sum has 2 l log(l) instead of 2 l because of TreeMap.remove() and because of TreeMap.put(), prod has l^2 log(l^2/2) instead of l^2 because of TreeMap.put()
TreeMap cannot used for this, some kind of SortedLinkedList or SortedHashMap would be required, the last would in turn require a hashValue() of an ExpVector

implemented edu.jas.arith.BigInteger which implements Coefficient, tested with IntPolynomial which extends Polynomial

todo: alternative Implementations, cleanup RatPolynomial, parallel GB, conversion RatPolynomial <--> IntPolynomial
2003, 1, 4
added reading of PolynomialLists and Variable Lists to PolynomialTokenizer, implemented PolynomialList
refactoring RatPolynomial to extend Polynomial, implementing IntPolynomial extends Polynomial
to make BigInteger implement Coefficient will require a delegation extension of BigInteger
2003, 1, 3
implemented PolynomialTokenizer to read RatPolynomials
2003, 1, 2
file RatPolynomial split into RatGBase, criterion 3 implemented with BitSet

second results (with new criterion 3 in jas):
Trinks 7: mas 0.598 sec, jas 1.159 sec
Trinks 6: mas 26.935 sec, jas 6.468 sec
mas: including startup and gc time, jas: excluding startup of jvm and including gc time

implemented DIGBMI, H-polynomal was not monic in DIRPGB

third results (with new criterion 3 in jas and GBminimal):
Trinks 7: mas 0.598 sec, jas 0.918 sec
Trinks 6: mas 26.935 sec, jas 3.211 sec
mas: including startup and gc time, jas: excluding startup of jvm and including gc time timing on P-3@450

this makes for a factor of 8-9 better, all tests with output to files, startup of JVM is approx. 1.0-1.2 sec, most time is spent in BigInteger:

java -Xrunhprof:cpu=times,format=a

CPU TIME (ms) BEGIN (total = 136) Thu Jan  2 18:33:53 2003
rank   self  accum   count trace method
   1 15,44% 15,44%  596610    21 java.math.MutableBigInteger.rightShift
   2 13,24% 28,68%  582132    15 java.math.MutableBigInteger.difference
   3 12,50% 41,18%  612760    19 java.math.MutableBigInteger.getLowestSetBit
   4  9,56% 50,74%       2     9 java.lang.Object.wait
   5  9,56% 60,29%    5271    22 java.math.MutableBigInteger.binaryGCD
   6  6,62% 66,91%  612760    23 java.math.BigInteger.trailingZeroCnt
   7  5,88% 72,79%  592152    18 java.math.BigInteger.bitLen
   8  5,88% 78,68%    6018    20 java.math.MutableBigInteger.binaryGCD
   9  5,15% 83,82%  578887    25 java.math.MutableBigInteger.normalize
  10  4,41% 88,24%  550992    24 java.math.MutableBigInteger.primitiveRightShift
  11  4,41% 92,65%       1    10 java.lang.Object.wait
  12  3,68% 96,32%  582132    12 java.math.MutableBigInteger.compare
  13  0,74% 97,06%   35965    13 edu.jas.poly.ExpVector.EVILCP
  14  0,74% 97,79%   11612    14 java.math.BigInteger.divide
  15  0,74% 98,53%    5866    11 java.math.MutableBigInteger.divide
  16  0,74% 99,26%    9032    16 java.math.MutableBigInteger.divide
  17  0,74% 100,00%   9032    17 java.math.BigInteger.divide
CPU TIME (ms) END
2003, 1, 1
renaming packages to edu.jas, renaming to arith, poly and ring, new Makefile, project dokumentation in XHTML, using JDK 1.4 with JIT

first results (without criterion 3 in jas):
Trinks 7: mas 0.598 sec, jas 1.373 sec
Trinks 6: mas 26.935 sec, jas 30.935 sec
mas: including startup and gc time, jas: excluding startup of jvm and including gc time. timing on P-3@450

2002, 12, 31
starting with extraction of relevant files in new directory
2000, 7, 21
keySet/get replaced by entrySet/getval.
Implemented S-Polynomial, normal form, irreducible set. Implemented Groebner base with criterion 4. Criterion 3 left to to.
2000, 7, 16
Implemented and tested BigRational based on Javas BigInteger.
With and without I/O BigRational addition, multiplication and comparison is approx. 10 times faster than respective SACRN functions.

Implemented and testet ExpVector based on Javas int arrays.

Implemented and testet RatPolynomial based on Javas TreeMap.
static methods: DIRPDF, DIRPWR via toString, DIRPON, DIRPMC, DIRPPR, DIRPSM, DIRRAS.
Consider replacing keySet/get by entrySet/getval where appropriate. Can there be an generic Polynomial class?

2000, 7, 15
Some testing with Javas builtin BigInteger class.
Without I/O builtin multiplication is approx. 15 times faster than SAC product.
With much I/O builtin multiplication is approx. 3 times faster than SAC product.
Builtin uses also twos-complement representation, which is bad for decimal printing.

This will be the end of list processing for Jas.

DIPRNGB needs DIRPDF, DIRPWR, DIRPON, DIRPMC, DIRPPR, DIRPSM.
These need RNDIF, RNDWR, RNINT, RNSIGN, ISRNONE, RNONE, RNZERO, RNINV (and DIRPRP), RNPROD, RNSUM.

2000, 7, 14
Class BigInteger based on SACI with toString().
Class List based on MASSTOR with toString().
Problem with Modula-2 module initialization with main(args) method: initialization of static variables.
2000, 7, 5
Finished testing most of masarith.
2000, 7, 2
Finished porting masarith. Testing needs still to be done. MASAPF is ok.
2000, 6, 24
Perl script getc.pl to grab comments in Modula-2 source and add to Java source. Comments grabbed on most working files so far. Generated new documentation.
2000, 6, 22
Future directions: Problems identified:
2000, 6, 22
GB running on Trinks (small and big). Jas ist about 5-8 times slower than MAS in GB computation. Using JDK 1.1.7 without JIT on Linux, PII-300. Using JDK 1.2.2-RC3 without JIT on Linux, PII-300 is about 6-9 times slower. Using JDK 1.2.2-RC4 with JIT (sunwjit) on Linux, PII-300 is about 2-4 times slower. Implemented Java input via BufferedReader.
2000, 6, 21
Got GB running. Problem was in EQUAL.
2000, 6, 17
Placed under control of CVS. Begining with a clean version from Uni Passau. Incorporated Java specific changes up to now.
2000, 6, 10
Transformation of DIPRNGB finished. Important parts of maspoly finished.
2000, 6, 4
Transformation of SACPRIM finished. Most of maskern finished. Important parts of masarith finished.
2000, 5, 29
MASSTOR: Mapping MAS list direkt to a Java list class and using of the garbage collector from Java. Data types LIST and GAMMAINT are now distinct. Buying the MHC Compiler (UK Pound 59).
2000, 5, 28
MASSTOR: First attempt to use list class with own garbage collection. Using the constructor to record list pointers.
2000, 5, 27:
Beginning of the first tests. Conversion of .md to .def, .mi to .mod.
2000, 5, 26:
Discovery of the MHC Modula-2 to Java compiler. Mill Hill & Canterbury Corporation, Ltd, URL http://www.mhccorp.com

Done bevore 2003


Heinz Kredel

Last modified: Sun Jun 11 23:50:44 CEST 2017