# Gröbner bases book algorithms and JAS methods

Summary of algorithms from the Gröbner bases book and corresponding JAS classes and methods.

## Gröbner bases book algorithms

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.

 GB book algorithm JAS interfaces, classes and methods remarks 0.1 `DIVINT` `arith.BigInteger.divideAndRemainder` adapter for `java.math.BigInteger.divideAndRemainder` 2.1 `DIV` `structure.MonoidElem.divide` and `structure.MonoidElem.remainder` all classes which implement this interface 2.2 `DIVPOL` `poly.GenPolynomial.` `divideAndRemainder` for univariate polynomials over fields 2.3 `EXTEUC` `poly.GenPolynomial.egcd` for univariate polynomials over fields 3.1 `LINDEP` not implemented But see `vector.LinAlg.` `rowEchelonForm` and other classes in the `vector` package. 3.2 `EXCHANGE` not implemented 4.1 `EQUIV` `structure.Residue.equals` or `application.Residue.equals` arbitrary residue class rings and residue class rings modulo polynomial ideals 5.1 `REDPOL` `gb.Reduction.normalform`, `gb.ReductionAbstract.normalform`, `gb.ReductionSeq.normalform` interface and sequential computation class, the method exists also for polynomial lists and with a reduction recording matrix (this is exactly `REDPOL`) 5.2 `REDUCTION` `gb.Reduction.irreducibleSet` 5.3 `GRÖBNERTEST` `gb.GroebnerBase.isGB` provided by all classes which implement this interface 5.4 `GRÖBNER` not implemented 5.5 `REDGRÖBNER` `gb.GroebnerBase.GB` with `gb.OrderedMinPairlist` provided by all classes which implement the interface and allow the selection of the pair-list in a constructor 5.6 `GRÖBNERNEW1` `gb.GroebnerBase.GB` with `gb.OrderedPairlist` provided by all classes which implement the interface and allow the selection of the pair-list in a constructor 5.7 `UPDATE`, 5.8 `GRÖBNERNEW2` `gb.GroebnerBase.GB` with `gb.OrderedSyzPairlist` provided by all classes which implement the interface and allow the selection of the pair-list in a constructor 5.9 `EXTGRÖBNER` `gb.GroebnerBase.extGB` provided by some classes which implement the interface 6.1 `ELIMINATION` `application.Ideal.eliminate` the version with the `String[]` parameter computes a Gröbner base wrt. the corresponding elimination order 6.2 `PROPER` `application.Ideal.isONE` proper ideal test is `! id.isONE()` 6.3 `INTERSECTION` `application.Ideal.intersect` for lists of ideals a simple iterative algorithm is used and for a pair of ideals it is the same algorithm 6.4 `CRT` `gbufd.PolyGBUtil.chineseRemainderTheorem` 6.5 `IDEALDIV1` `application.Ideal.quotient` for an ideal a simple iterative algorithm is used and for one polynomial it is an algorithm without computing syzygies 6.6 `IDEALDIV2` `application.Ideal.` `infiniteQuotientRab` and `application.Ideal.` `infiniteQuotientExponent` the exponent is computed in a separate step at the moment 6.7 `RADICALMEMTEST` `application.Ideal.isRadicalMember` the exponent is not computed 6.8 `SUBRINGMEMTEST` `gbufd.PolyGBUtil.subRingAndMember` 8.1 `PREDEC` `application.Ideal.` `zeroDimDecomposition` univariate polynomials of minimal degree in the ideal are irreducible and not a power of an irreducible polynomial as specified in `PREDEC` 8.2 `ZRADICALTEST` `application.Ideal.isZeroDimRadical` will also work in characteritsic p > 0 8.3 `ZRADICAL` `application.Ideal.radical` `ZRADICAL` is containted as special case, see also `application.Ideal.` `zeroDimRadicalDecomposition` 8.4 `NORMPRIMDEC` `application.Ideal.` `zeroDimPrimaryDecomposition` contains all preprocessing steps, see `ZPRIMDEC` 8.5 `NORMPOS` `application.Ideal.normalPositionFor` one step of `NORMPOS` as explained for the modified algorithm on page 383ff 8.6 `ZPRIMDEC` `application.Ideal.` `zeroDimPrimaryDecomposition` returns a list of `PrimaryComponent` containers 8.7 `CONT` `application.Ideal.contraction` more complicated since the permutation of variables must be considered also, see `application.Ideal.permContraction`, the polynomial `f` is returned in the `IdealWithUniv` container 8.8 `EXTCONT` `application.Ideal.extension` only `EXT`, the combination `EXTCONT` is not implemented explicitly, the polynomial `f` is returned in the `IdealWithUniv` container 8.9 `RADICAL` `application.Ideal.radical` for ideals with arbitrary dimension 8.10 `PRIMDEC` `application.Ideal.` `primaryDecomposition` for ideals with arbitrary dimension 8.11 `VARSIGN` `root.RootUtil.signVar` 8.12 `STURMSEQ` `root.RealRootsSturm.sturmSequence` 8.13 `ISOLATE` `root.RealRoots.realRoots` could also be used for real root isolations not using Sturm sequences 8.14 `ISOREC` `root.RealRootsSturm.realRoots` interval bi-section until a root is isolated 8.15 `ISOREFINE` `root.RealRoots.refineInterval` also for real root isolations not using Sturm sequences 8.16 `SQUEEZE` `root.RealRoots.` `invariantMagnitudeInterval` see also `root.RealRoots.` `realMagnitude` 8.17 `REALZEROS` `application.PolyUtilApp.` `realAlgebraicRoots` different algorithm and different result data structure with `RealAlgebraicNumbers` 9.1 `REDTERMS` `gbufd.GroebnerBaseFGLM.redTerms` 9.2 `UNIVPOL` `application.Ideal.` `constructUnivariate` 9.3 `CONVGRÖBNER` `gbufd.GroebnerBaseFGLM.` `convGroebnerToLex` See also `gbufd.GroebnerBaseFGLM.GB`. It computes a Gröbner base with respect to a graded term order and then uses FGLM to convert to a lexicographic term order. See also `gbufd.GroebnerBaseWalk.GB`. It computes a Gröbner base with respect to a term order `t1` and then uses Gröbner Walk to convert to a GB with term order `t2`. 9.4 `LMINTERM` `gbufd.GroebnerBaseFGLM.lMinterm` 9.5 `STRCONST` not implemented 9.6 `DIMENSION` `application.Ideal.dimension` 10.1 `D-GRÖBNER` `gb.DGroebnerBaseSeq.GB` and `gb.EGroebnerBaseSeq.GB`

Heinz Kredel