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

Last modified: Thu Jul 8 17:47:59 CEST 2021