Summary of algorithms from the Gröbner bases 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.
GB book algorithm | JAS interfaces, classes and methods | remarks |
0.1 DIVINT |
arith.BigInteger.divideAndRemainder
|
facade 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
|
|
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 |
not implemented | |
5.6 GRÖBNERNEW1 |
gb.GroebnerBase.GB
|
provided by all classes which implement the interface |
5.7 UPDATE , 5.8 GRÖBNERNEW2 |
not implemented | |
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 only computes a Gröbner base wrt. the
respective 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 |
not implemented
|
|
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 |
not implemented
|
|
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
|
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
|
Last modified: Sun Jul 15 19:12:04 CEST 2012