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 |
|
implemented in java.math.BigInteger.multiply
|
4.3 Polynomial Trial Division Algorithm, TrialDivision |
not implemented | see
GenPolynomial.divide
and
PolyUtil.basePseudoDivide
|
4.4 Fast Fourier Transform, FFT |
|
|
4.5 Fast Fourier Polynomial Multiplication, FFT_Multiply |
|
|
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 sub-resultant PRS | |
7.3 Extended Zassenhaus GCD Algorithm, EZ-GCD |
GreatestCommonDivisorHensel. recursiveUnivariateGcd()
|
not complete in all cases |
7.4 GCD Heuristic Algorithm, GCDHEU |
not implemented | |
8.1 Square-Free Factorization, SquareFree |
SquarefreeFieldChar0. squarefreeFactors()
|
|
8.2 Yun's Square-Free Factorization, SquareFree2 |
SquarefreeFieldChar0Yun. squarefreeFactors()
|
|
8.3 Finite Field Square-Free Factorization, SquareFreeFF |
SquarefreeFiniteFieldCharP. squarefreeFactors()
|
|
SquarefreeInfiniteFieldCharP. squarefreeFactors()
|
Algorithm for infinite fields of characteristic p, not in the book. | |
8.4 Berlekamp's Factorization Algorithm, Berlekamp |
FactorModularBerlekamp. baseFactorsSquarefree()
|
The method baseFactorsSquarefreeSmallPrime() contains the implementation.
|
8.5 Form Q Matrix, FormMatrixQ |
PolyUfdUtil.constructQmatrix()
|
|
8.6 Null Space Basis Algorithm, NullSpaceBasis |
LinAlg.nullSpaceBasis()
|
|
8.7 Big Prime Berlekamp Factoring Algorithm, BigPrimeBerlekamp |
FactorModularBerlekamp. baseFactorsSquarefree()
|
The method baseFactorsSquarefreeBigPrime() contains the implementation.
|
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 Fraction-Free Gaussian Elimination, FractionFreeElim |
LinAlg. fractionfreeGaussElimination()
|
see also
GroebnerBasePseudoSeq.GB()
|
9.2 Nonlinear Elimination Algorithm, NonlinearElim |
|
Based on iterated resultant computations.
See also the characteristic set method
CharacteristicSetSimple.characteristicSet()
|
9.3 Solution of Nonlinear System of Equations, NonlinearSolve |
|
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 |
|
|
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 bi-variate 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()
|
using resultants |
11.4 Lazard/Rioboo/Trager improvement, LogarithmicPartIntegral |
ElementaryIntegrationLazard. integrateLogPart()
|
using sub-resultants |
11.x Czichowski variant, LogarithmicPartIntegral |
ElementaryIntegrationCzichowski. integrateLogPart()
|
using Gröbner bases |
11.y Bernoulli variant, LogarithmicPartIntegral |
ElementaryIntegrationBernoulli. integrateLogPart()
|
using absolute factorization into linear factors |
Last modified: Sat Aug 7 19:41:34 CEST 2021