Summary of algorithms from the Algorithms for Computer Algebra book and corresponding JAS classes and methods.
The JAS base package edu.jas
name is omitted in the
following table.
JAS also contains improved versions of the algorithms which may be located through the links.
A short explanation of code organization with interfaces and several implementing classes
can be found in the API guide.
Algorithms for Computer Algebra  JAS interfaces, classes and methods  remarks 
2.1 Euclidean Algorithm, Euclid 
structure.RingElem.gcd

all classes which implement this interface 
2.2 Extended Euclidean Algorithm, EEA 
structure.RingElem.egcd

all classes which implement this interface 
2.3 Primitive Euclidean Algorithm, PrimitiveEuclidean 
ufd.GreatestCommonDivisorPrimitive


4.1 Multiprecision Integer Multiplication, BigIntegerMultiply 
BigInteger.multiply

adapter for native Java implementation in java.math.BigInteger.multiply

4.2 Karatsuba's Multiplication Algorithm, Karatsuba 

not visible 
4.3 Polynomial Trial Division Algorithm, TrialDivision 
not implemented  see
GenPolynomial.divide
and
PolyUtil.basePseudoDivide

4.4 Fast Fourier Transform, FFT 
not implemented


4.5 Fast Fourier Polynomial Multiplication, FFT_Multiply 
not implemented


4.6 Newtons's Method for Power Series Inversion, FastNewtonInversion 
not implemented  see
UnivPowerSeries.inverse()
and
MultiVarPowerSeries.inverse()

4.7 Newtons's Method for Solving P(y) = 0, NewtonSolve 
not implemented  see
UnivPowerSeriesRing.solveODE()

5.1 Garner's Chinese Remainder Algorithm, IntegerCRA 
ModIntegerRing.chineseRemainder()

only for two moduli 
5.2 Newtons Interpolation Algorithm, NewtonInterp 
not implemented  see
PolyUtil.chineseRemainder()
and
PolyUtil.interpolate()

6.1 Univariate Hensel Lifting Algorithm, UnivariateHensel 
HenselUtil.liftHensel()


6.2 Multivariate Polynomial Diophantine Equantions, MultivariateDiophant 
HenselMultUtil.liftDiophant()


6.3 Univariate Polynomial Diophantine Equantions, UnivariateDiophant 
HenselUtil.liftDiophant()


6.4 Multivariate Hensel Lifting Algorithm, MultivariateHensel 
HenselMultUtil.liftHensel()
 
7.1 Modular GCD Algorithm, MGCD 
GreatestCommonDivisorModular.baseGcd()


7.2 Multivariate GCD Reduction Algorithm, PGCD 
GreatestCommonDivisorModEval.gcd()


GreatestCommonDivisorSubres.gcd()

many more algorithms, for example using polynomial remainder sequences (PRS), in particular a subresultant PRS  
7.3 Extended Zassenhaus GCD Algorithm, EZGCD 
GreatestCommonDivisorHensel. recursiveUnivariateGcd()

not complete in all cases 
7.4 GCD Heuristic Algorithm, GCDHEU 
not implemented  
8.1 SquareFree Factorization, SquareFree 
SquarefreeFieldChar0.squarefreeFactors()


8.2 Yun's SquareFree Factorization, SquareFree2 
not implemented


8.3 Finite Field SquareFree Factorization, SquareFreeFF 
SquarefreeFiniteFieldCharP .squarefreeFactors()


SquarefreeInfiniteFieldCharP .squarefreeFactors()

Algorithm for infinite fields of characteristic p, not in the book.  
8.4 Berlekamp's Factorization Algorithm, Berlekamp 
not implemented


8.5 Form Q Matrix, FormMatrixQ 
not implemented


8.6 Null Space Basis Algorithm, NullSpaceBasis 
not implemented


8.7 Big Prime Berlekamp Factoring Algorithm, BigPrimeBerlekamp 
not implemented


8.8 Distinct Degree Factorization I, PartialFactorDD 
FactorModular.baseDistinctDegreeFactors()


8.9 Distinct Degree Factorization II, SplitDD 
FactorModular.baseEqualDegreeFactors()
 
FactorInteger.factorsSquarefree()
 Algorithm of P. Wang, not presented in the book.  
8.10 Factorization over Algebraic Number Fields, AlgebraicFactorization 
FactorAlgebraic.baseFactorsSquarefree()


9.1 FractionFree Gaussian Elimination, FractionFreeElim 
not implemented

but see
GroebnerBasePseudoSeq.GB()

9.2 Nonlinear Elimination Algorithm, NonlinearElim 
not implemented

Based on iterated resultant computations.
See also the characteristic set method
CharacteristicSetSimple.characteristicSet()

9.3 Solution of Nonlinear System of Equations, NonlinearSolve 
not implemented

Based on resultant computations and algebraic root substitution.
See also the ideal complex and real root computation and decomposition methods
PolyUtilApp.complexAlgebraicRoots()

10.1 Full Reduction Algorithm, Reduce 
Reduction.normalform()

all classes which implement this interface 
10.2 Buchbergers's Algorithm for Gröbner Bases, Gbasis 
not implemented


10.3 Construction of a Reduced Ideal Basis, ReduceSet 
GroebnerBase.minimalGB()

all classes which implement this interface 
10.4 Improved Construction of a Reduced Gröbner Basis, Gbasis 
GroebnerBaseSeq.GB()

can be parametrized also with different strategies, e.g. Gebauer & Möller 
10.5 Solution of System P in Variable x, Solve1 
Ideal.constructUnivariate()

univariate polynomials of minimal degree in the ideal 
10.6 Complete Solution of System P, GröbnerSolve 
Ideal.zeroDimDecomposition() ,

univariate polynomials in the ideal are irreducible 
10.7 Solution of P using Lexicographic Gröbner Basis, LexSolve 
Ideal.zeroDimRootDecomposition()

additionally to 10.6, the ideal basis consists of maximally bivariate polynomials 
11.1 Hermite's Method for Rational Functions, HermiteReduction 
ElementaryIntegration.integrateHermite()


11.2 Horowitz's Reduction for Rational Functions, HorowitzReduction 
ElementaryIntegration.integrate()


11.3 Rothstein/Trager Method, LogarithmicPartIntegral 
ElementaryIntegration.integrateLogPart()


11.4 Lazard/Rioboo/Trager Improvement, LogarithmicPartIntegral 
not implemented

Last modified: Sun Apr 19 12:47:06 CEST 2015