Algorithms for Computer Algebra book and JAS methods

Summary of algorithms from the Algorithms for Computer Algebra book and corresponding JAS classes and methods.

Algorithms for Computer Algebra book

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 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 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 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 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


Heinz Kredel

Last modified: Sat Aug 7 19:41:34 CEST 2021