# 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` 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 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` not implemented 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` 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 Fraction-Free 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 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()` 11.4 Lazard/Rioboo/Trager Improvement, `LogarithmicPartIntegral` not implemented

Heinz Kredel