This is GroebnerWalk.info, produced by Macaulay2, version 1.20

GroebnerWalk -- Compute Groebner bases via the Groebner walk
************************************************************

Description
===========

The Groebner walk is a Groebner basis conversion algorithm. This means it takes
a Groebner basis of an ideal with respect to one monomial order and changes it
into a Groebner basis of the same ideal over a different monomial order.
Conversion algorithms can be useful since sometimes when a Groebner basis over
a difficult monomial order (such as lexicographic or an elimination order) is
desired, it can be faster to compute a Groebner basis directly over an easier
order (such as graded reverse lexicographic) and then convert rather than
computing directly in the original order. Other examples of conversion
algorithms include FGLM and Hilbert-driven Buchberger.

The Groebner walk performs conversion by traveling through the Groebner fan.
The Groebner basis is the same for all vectors inside a cone of the fan, and
when crossing a face into a new cone a (hopefully small) adjustment of the
Groebner basis is all that must be computed. Further background and details can
be found in the following resources:

Cox, Little, O'Shea - Using Algebraic Geometry (2005)

Amrhein, Gloor, Kuchlin - On the Walk (1997)

Collart, Kalkbrenner, Mall - Converting Bases with the Groebner Walk (1997)

Fukuda, Jensen, Lauritzen, Thomas - The Generic Grobner Walk (2007)

Tran - A Fast Algorithm for Grobner Basis Conversion and its Applications
(2000)

In Macaulay2, monomial orders must be given as options to rings. For example,
the following ideal has monomial order given by first using a weight vector and
then breaking ties with graded reverse lexicographic.

+-------------------------------------------------------------------+
|i1 : R1 = QQ[x,y,z,u,v, MonomialOrder=>Weights=>{1,1,1,0,0}];      |
+-------------------------------------------------------------------+
|i2 : I1 = ideal(u + u^2 - 2*v - 2*u^2*v + 2*u*v^2 - x,             |
|                -6*u + 2*v + v^2 - 5*v^3 + 2*u*v^2 - 4*u^2*v^2 - y,|
|                -2 + 2*u^2 + 6*v - 3*u^2*v^2 - z);                 |
|                                                                   |
|o2 : Ideal of R1                                                   |
+-------------------------------------------------------------------+

If we want a Groebner basis of I with respect to the monomial order given by
using a different weight vector and then graded reverse lexicographic we could
substitute and compute directly,

+---------------------------------------------------------------------+
|i3 : R2 = QQ[x,y,z,u,v, MonomialOrder=>Weights=>{0,0,0,1,1}];        |
+---------------------------------------------------------------------+
|i4 : I2 = sub(I1, R2);                                               |
|                                                                     |
|o4 : Ideal of R2                                                     |
+---------------------------------------------------------------------+
|i5 : elapsedTime gb I2                                               |
| -- 8.92034 seconds elapsed                                          |
|                                                                     |
|o5 = GroebnerBasis[status: done; S-pairs encountered up to degree 16]|
|                                                                     |
|o5 : GroebnerBasis                                                   |
+---------------------------------------------------------------------+

but it is faster to compute directly in the first order and then use the
Groebner walk.

+--------------------------------------------------------------------+
|i6 : elapsedTime groebnerWalk(gb I1, R2)                            |
| -- 4.3426 seconds elapsed                                          |
|                                                                    |
|o6 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]|
|                                                                    |
|o6 : GroebnerBasis                                                  |
+--------------------------------------------------------------------+

Caveat
======

The target ring must be the same ring as the ring of the starting ideal, except
with different monomial order. The ring must be a polynomial ring over a field.

See also
========

  * groebnerBasis (Macaulay2Doc) -- Gröbner basis, as a
    matrix

Author
======

  * Dylan Peifer (see https://www.math.cornell.edu/~djp282 )
    <djp282@cornell.edu>

Version
=======

This documentation describes version 1.0.0 of GroebnerWalk.

Source code
===========

The source code from which this documentation is derived is in the file
GroebnerWalk.m2 (see common/share/Macaulay2/GroebnerWalk.m2 ).

Exports
=======

  * Functions and commands
      * getWalkTrace -- get current value of walkTrace
      * groebnerWalk -- convert a Groebner basis
      * setWalkTrace -- set value of walkTrace
  * Methods
      * "groebnerWalk(GroebnerBasis,Ring)" -- see groebnerWalk,
        -- convert a Groebner basis
      * "groebnerWalk(Ideal,Ring)" -- see groebnerWalk, --
        convert a Groebner basis
      * "setWalkTrace(ZZ)" -- see setWalkTrace, -- set
        value of walkTrace

For the programmer
==================

The object GroebnerWalk, is a package (Macaulay2Doc).

getWalkTrace -- get current value of walkTrace
**********************************************

Synopsis
========

  * Usage:
        n = getWalkTrace()
  * Outputs:
      * n, an integer (Macaulay2Doc), the current value of walkTrace

Description
===========

The value of walkTrace determines how much additional information is printed
during a call to groebnerWalk. The function
getWalkTrace, allows the user to check the current value of
walkTrace.

Levels of walkTrace are as follows:

Level 0: No additional information is printed. This is the default level.

Level 1: The total number of conversions performed during the algorithm is
printed at the end of the computation. Conversions are sometimes done in
initialization and finalization at the start and end of the path, and otherwise
happen at faces in the Groebner fan.

Level 2: All Level 1 information is printed, and the current vector and size of
the Groebner basis are printed at each conversion step. Since information is
printed at each conversion, this level is helpful for verifying that the
computation is proceeding and noticing where the algorithm gets stuck.

Level 3: All Level 2 information is printed, and the codimension of the face in
the Groebner fan where the conversion is taking place is printed at each
conversion. Note that running on Level 3 will significantly slow down the
computation, and is not recommended except for testing.

+--------------------+
|i1 : getWalkTrace() |
|                    |
|o1 = 0              |
+--------------------+
|i2 : setWalkTrace 2;|
+--------------------+
|i3 : getWalkTrace() |
|                    |
|o3 = 2              |
+--------------------+

See also
========

  * groebnerWalk -- convert a Groebner basis
  * setWalkTrace -- set value of walkTrace

Ways to use getWalkTrace :
==========================

  * getWalkTrace() (missing documentation)

For the programmer
==================

The object getWalkTrace, is a method function (Macaulay2Doc).

groebnerWalk -- convert a Groebner basis
****************************************

Synopsis
========

  * Usage:
        H = groebnerWalk(G, R)
        H = groebnerWalk(I, R)
  * Inputs:
      * G, a Gröbner basis (Macaulay2Doc), the starting
        Groebner basis
      * I, an ideal (Macaulay2Doc), the starting ideal
      * R, a ring (Macaulay2Doc), a ring with the target monomial
        order
  * Optional inputs (Macaulay2Doc),:
      * Strategy, =>
        ..., default value Standard, specify the algorithm for groebnerWalk
  * Outputs:
      * H, a Gröbner basis (Macaulay2Doc), the new
        Groebner basis in the target monomial order

Description
===========

The Groebner walk takes a Groebner basis of an ideal with respect to one
monomial order and changes it into a Groebner basis of the same ideal over a
different monomial order. The initial order is given by the ring of G and the
target order is the order in R. When given an ideal I as input a Groebner basis
of I in the ring of I is initially computed directly, and then this Groebner
basis is converted into a Groebner basis in the ring R.

+--------------------------------------------------------------------+
|i1 : KK = ZZ/32003;                                                 |
+--------------------------------------------------------------------+
|i2 : R1 = KK[x,y,z,u,v, MonomialOrder=>Eliminate 3];                |
+--------------------------------------------------------------------+
|i3 : I1 = ideal(3 - 2*u + 2*u^2 - 2*u^3 - v + u*v + 2*u^2*v^3 - x,  |
|                6*u + 5*u^2 - u^3 + v + u*v + v^2 - y,              |
|                -2 + 3*u - u*v + 2*u*v^2 - z);                      |
|                                                                    |
|o3 : Ideal of R1                                                    |
+--------------------------------------------------------------------+
|i4 : R2 = KK[x,y,z,u,v, MonomialOrder=>Weights=>{0,0,0,1,1}];       |
+--------------------------------------------------------------------+
|i5 : groebnerWalk(I1, R2)                                           |
|                                                                    |
|o5 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]|
|                                                                    |
|o5 : GroebnerBasis                                                  |
+--------------------------------------------------------------------+

Caveat
======

The target ring R must be the same ring as the ring of G or I, except with
different monomial order. R must be a polynomial ring over a field.

See also
========

  * GroebnerWalk -- Compute Groebner bases via the Groebner walk
  * setWalkTrace -- set value of walkTrace
  * getWalkTrace -- get current value of walkTrace
  * groebnerBasis (Macaulay2Doc) -- Gröbner basis, as a
    matrix

Ways to use groebnerWalk :
==========================

  * "groebnerWalk(GroebnerBasis,Ring)"
  * "groebnerWalk(Ideal,Ring)"

For the programmer
==================

The object groebnerWalk, is a method function with options (Macaulay2Doc).

groebnerWalk(...,Strategy=>...) -- specify the algorithm for groebnerWalk
*************************************************************************

Synopsis
========

  * Usage:
        H = groebnerWalk(G, R, Strategy => Generic)

Description
===========

Choose which algorithm to use for the Groebner walk. Options are Standard for
the original algorithm of Collart, Kalkbrener, and Mall and Generic for the
generic walk of Fukuda, Jensen, Lauritzen, and Thomas. The default option is
Standard.

+--------------------------------------------------------------------+
|i1 : KK = ZZ/32003;                                                 |
+--------------------------------------------------------------------+
|i2 : R1 = KK[x,y,z,u,v, MonomialOrder=>Eliminate 3];                |
+--------------------------------------------------------------------+
|i3 : I1 = ideal(3 - 2*u + 2*u^2 - 2*u^3 - v + u*v + 2*u^2*v^3 - x,  |
|                6*u + 5*u^2 - u^3 + v + u*v + v^2 - y,              |
|                -2 + 3*u - u*v + 2*u*v^2 - z);                      |
|                                                                    |
|o3 : Ideal of R1                                                    |
+--------------------------------------------------------------------+
|i4 : R2 = KK[x,y,z,u,v, MonomialOrder=>Weights=>{0,0,0,1,1}];       |
+--------------------------------------------------------------------+
|i5 : groebnerWalk(I1, R2, Strategy=>Generic)                        |
|                                                                    |
|o5 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]|
|                                                                    |
|o5 : GroebnerBasis                                                  |
+--------------------------------------------------------------------+

Further information
===================

  * Default value: Standard (Macaulay2Doc),
  * Function: groebnerWalk, -- convert a Groebner basis
  * Option key: Strategy (Macaulay2Doc), -- an optional argument

See also
========

  * GroebnerWalk -- Compute Groebner bases via the Groebner walk
  * groebnerWalk -- convert a Groebner basis

Functions with optional argument named Strategy :
=================================================

  * "addHook(...,Strategy=>...)" -- see addHook (Macaulay2Doc),
    -- add a hook function to an object for later processing
  * "annihilator(...,Strategy=>...)" -- see annihilator (Saturation),
    -- the annihilator ideal
  * "associatedPrimes(...,Strategy=>...)" -- see associatedPrimes (PrimaryDecomposition),
    -- find associated primes
  * "basis(...,Strategy=>...)" -- see basis (Macaulay2Doc), --
    basis or generating set of all or part of a ring, ideal or module
  * "mingens(...,Strategy=>...)" -- see Complement (Macaulay2Doc),
    -- a Strategy option value
  * "trim(...,Strategy=>...)" -- see Complement (Macaulay2Doc),
    -- a Strategy option value
  * determinant(...,Strategy=>...) (Macaulay2Doc)
    -- choose
    between Bareiss and Cofactor algorithms
  * "dual(MonomialIdeal,List,Strategy=>...)" -- see
    dual(MonomialIdeal,Strategy=>...) (Macaulay2Doc),
  * "dual(MonomialIdeal,RingElement,Strategy=>...)" -- see
    dual(MonomialIdeal,Strategy=>...) (Macaulay2Doc),
  * dual(MonomialIdeal,Strategy=>...) (Macaulay2Doc)
  * exteriorPower(...,Strategy=>...) (Macaulay2Doc)
    -- choose
    between Bareiss and Cofactor algorithms
  * "gb(...,Strategy=>...)" -- see gb (Macaulay2Doc), -- compute a
    Gröbner basis
  * gcdLLL(...,Strategy=>...) (missing documentation)
  * "GF(...,Strategy=>...)" -- see GF (Macaulay2Doc), -- make a finite
    field
  * "groebnerBasis(...,Strategy=>...)" -- see groebnerBasis (Macaulay2Doc),
    -- Gröbner basis, as a matrix
  * groebnerWalk(...,Strategy=>...)
    -- specify the algorithm
    for groebnerWalk
  * hermite(...,Strategy=>...) (missing documentation)
  * "hooks(...,Strategy=>...)" -- see hooks (Macaulay2Doc), -- list
    hooks attached to a key
  * "idealizer(...,Strategy=>...)" -- see idealizer (IntegralClosure),
    -- compute Hom(I,I) as a quotient ring
  * integralClosure(...,Strategy=>...) (IntegralClosure),
    --
    control the algorithm used
  * "intersect(Ideal,Ideal,Strategy=>...)" -- see intersect(Ideal,Ideal) (Macaulay2Doc),
    -- compute an intersection of a
    sequence of ideals or modules
  * "intersect(Module,Module,Strategy=>...)" -- see
    intersect(Ideal,Ideal) (Macaulay2Doc), --
    compute an intersection of a sequence of ideals or modules
  * "intersectInP(...,Strategy=>...)" -- see
    intersectInP(...,BasisElementLimit=>...) (ReesAlgebra),
    --
    Option for intersectInP
  * "isPrimary(...,Strategy=>...)" -- see isPrimary (PrimaryDecomposition),
    -- determine whether a submodule is
    primary
  * "isPrime(Ideal,Strategy=>...)" -- see isPrime(Ideal) (MinimalPrimes),
    -- whether an ideal is prime
  * LLL(...,Strategy=>...) (LLLBases)
    -- choose among
    different algorithms
  * "localize(...,Strategy=>...)" -- see localize (PrimaryDecomposition),
    -- localize an ideal at a prime ideal
  * "match(...,Strategy=>...)" -- see match (Macaulay2Doc), --
    regular expression matching
  * "decompose(Ideal,Strategy=>...)" -- see minimalPrimes (MinimalPrimes),
    -- minimal primes of an ideal
  * "minimalPrimes(...,Strategy=>...)" -- see minimalPrimes (MinimalPrimes),
    -- minimal primes of an ideal
  * minors(...,Strategy=>...) (Macaulay2Doc)
    -- choose
    between Bareiss and Cofactor algorithms
  * "primaryComponent(...,Strategy=>...)" -- see primaryComponent (PrimaryDecomposition),
    -- find a primary component
    corresponding to an associated prime
  * pushForward(...,Strategy=>...) (missing documentation)
  * quotient(...,Strategy=>...) (Saturation)
  * "radical(...,Strategy=>...)" -- see radical (MinimalPrimes),
    -- the radical of an ideal
  * "radicalContainment(...,Strategy=>...)" -- see radicalContainment (MinimalPrimes),
    -- whether an element is contained in
    the radical of an ideal
  * "analyticSpread(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "distinguished(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "isLinearType(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "isReduction(...,Strategy=>...)" -- see reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "minimalReduction(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "multiplicity(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "normalCone(...,Strategy=>...)" -- see reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "reesAlgebra(...,Strategy=>...)" -- see reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * reesIdeal(...,Strategy=>...) (ReesAlgebra)
    -- Choose a
    strategy for the saturation step
  * "specialFiber(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "specialFiberIdeal(...,Strategy=>...)" -- see
    reesIdeal(...,Strategy=>...) (ReesAlgebra),
    -- Choose a
    strategy for the saturation step
  * "regSeqInIdeal(...,Strategy=>...)" -- see regSeqInIdeal (PrimaryDecomposition),
    -- a regular sequence contained in an
    ideal
  * resolution(...,Strategy=>...) (Macaulay2Doc)
  * saturate(...,Strategy=>...) (Saturation)
  * "primaryDecomposition(...,Strategy=>...)" -- see strategies for computing primary decomposition (PrimaryDecomposition),
  * "syz(...,Strategy=>...)" -- see syz(Matrix) (Macaulay2Doc),
    -- compute the syzygy matrix
  * "tangentCone(...,Strategy=>...)" -- see tangentCone(Ideal) (TangentCone),

setWalkTrace -- set value of walkTrace
**************************************

Synopsis
========

  * Usage:
        setWalkTrace(n)
  * Inputs:
      * n, an integer (Macaulay2Doc), the desired value of walkTrace

Description
===========

The value of walkTrace determines how much additional information is printed
during a call to groebnerWalk. The function
setWalkTrace, allows the user to change the value of walkTrace.

Levels of walkTrace are as follows:

Level 0: No additional information is printed. This is the default level.

Level 1: The total number of conversions performed during the algorithm is
printed at the end of the computation. Conversions are sometimes done in
initialization and finalization at the start and end of the path, and otherwise
happen at faces in the Groebner fan.

Level 2: All Level 1 information is printed, and the current vector and size of
the Groebner basis are printed at each conversion step. Since information is
printed at each conversion, this level is helpful for verifying that the
computation is proceeding and noticing where the algorithm gets stuck.

Level 3: All Level 2 information is printed, and the codimension of the face in
the Groebner fan where the conversion is taking place is printed at each
conversion. Note that running on Level 3 will significantly slow down the
computation, and is not recommended except for testing.

For example, running the following code at the default Level 0 prints nothing

+--------------------------------------------------------------------+
|i1 : R1 = ZZ/32003[x,y,z, MonomialOrder=>Weights=>{1,10,100}];      |
+--------------------------------------------------------------------+
|i2 : I1 = ideal(y-x^2, z-x^3);                                      |
|                                                                    |
|o2 : Ideal of R1                                                    |
+--------------------------------------------------------------------+
|i3 : R2 = ZZ/32003[x,y,z, MonomialOrder=>Lex];                      |
+--------------------------------------------------------------------+
|i4 : groebnerWalk(gb I1, R2)                                        |
|                                                                    |
|o4 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]|
|                                                                    |
|o4 : GroebnerBasis                                                  |
+--------------------------------------------------------------------+

while running at Level 2 gives some conversion information.

+--------------------------------------------------------------------+
|i5 : setWalkTrace 2;                                                |
+--------------------------------------------------------------------+
|i6 : groebnerWalk(gb I1, R2)                                        |
|Conversion Number: 1                                                |
|Weight Vector: {1, 10, 100}                                         |
|Size of new Groebner Basis: 2                                       |
|                                                                    |
|Conversion Number: 2                                                |
|Weight Vector: {1, 2, 20}                                           |
|Size of new Groebner Basis: 2                                       |
|                                                                    |
|Conversion Number: 3                                                |
|Weight Vector: {9, 1, 10}                                           |
|Size of new Groebner Basis: 4                                       |
|                                                                    |
|Conversion Number: 4                                                |
|Weight Vector: {1, 0, 0}                                            |
|Size of new Groebner Basis: 4                                       |
|                                                                    |
|Conversion Number: 5                                                |
|Weight Vector: {1, 0, 0}                                            |
|Size of new Groebner Basis: 4                                       |
|                                                                    |
|Total Conversions: 5                                                |
|                                                                    |
|o6 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]|
|                                                                    |
|o6 : GroebnerBasis                                                  |
+--------------------------------------------------------------------+

See also
========

  * groebnerWalk -- convert a Groebner basis
  * getWalkTrace -- get current value of walkTrace

Ways to use setWalkTrace :
==========================

  * "setWalkTrace(ZZ)"

For the programmer
==================

The object setWalkTrace, is a method function (Macaulay2Doc).