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

SubalgebraBases -- A package for finding canonical subalgebra bases (Sagbi bases)
*********************************************************************************

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

Let $R=k[f_1,\ldots,f_k]$ denote the subalgebra of the polynomial ring
$k[x_1,\ldots,x_n]$ generated by $f_1,\ldots ,f_k.$ We say $f_1,\ldots,f_k$
form a subalgebra basis with respect to a monomial order $<$ if the initial
algebra associated to $<$, defined as $in(R) := k[in(f) \mid f \in R],$ is
generated by the elements $in(f_1), \ldots , in(f_k).$ The main functions
provided by this package are for computing these subalgebra bases: sagbi,
see subalgebraBasis, and verifySagbi.

Some references for Subalgebra bases (aka canonical subalgebra bases, SAGBI
bases)

  * Kapur, D., Madlener, K. (1989). A completion procedure for computing a
    canonical basis of a $k$-subalgebra. Proceedings of Computers and
    Mathematics 89 (eds. Kaltofen and Watt), MIT, Cambridge, June 1989
  * Robbiano, L., Sweedler, M. (1990). Subalgebra bases, in W.~Bruns, A.~Simis
    (eds.): Commutative Algebra, Springer Lecture Notes in Mathematics 1430,
    pp.~61--87
  * F. Ollivier, Canonical Bases: Relations with Standard bases, finiteness
    conditions and applications to tame automorphisms, in Effective Methods in
    Algebraic Geometry, Castiglioncello 1990, pp. 379-400, Progress in Math. 94
    Birkhauser, Boston (1991)
  * Stillman, Michael, and Harrison Tsai. Using SAGBI bases to compute
    invariants. J. Pure and Appl. Alg., 1999, pp.~285--302.
  * B. Sturmfels, Groebner bases and Convex Polytopes, Univ. Lecture Series 8,
    Amer Math Soc, Providence, 1996

See also
========

  * Example_colon_ Translation and rotation sub-actions of the adjoint action of SE(3)

Authors
=======

  * Michael Burr (see https://cecas.clemson.edu/~burr2/ ) <burr2@clemson.edu>
  * Oliver Clarke (see https://research-information.bris.ac.uk/en/persons/ollie
    -clarke ) <oc17371@bristol.ac.uk>
  * Timothy Duff (see https://timduff35.github.io/timduff35/ ) <timduff@uw.edu>
  * Jackson Leaman
  * Nathan Nichols <nathannichols454@gmail.com>
  * Elise Walker (see https://sites.google.com/view/elise-walker/home )
    <elise.walker@tamu.edu>
  * Legacy author: Mike Stillman (see http://www.math.cornell.edu/~mike/ )
    <mike@math.cornell.edu>
  * Legacy author: Harrison Tsai
  * We thank the following contributors from the 2020 Macaulay2 workshops at
    Cleveland State University and University of Warwick: Aaron Dall, Alessio
    D'Alì, Alicia Tocino, Ayah Almousa, Dharm Veer, Dipak Kumar Pradhan, Emil
    Sköldberg, Eriola Hoxhaj, Kriti Goel, Liđan Edin, Peter Phelan, Ritika
    Nair, Ilir Dema

Version
=======

This documentation describes version 1.1 of SubalgebraBases.

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

The source code from which this documentation is derived is in the file
SubalgebraBases.m2 (see common/share/Macaulay2/SubalgebraBases.m2 ). The
auxiliary files accompanying it are in the directory SubalgebraBases/ (see
common/share/Macaulay2/SubalgebraBases/ ).

Exports
=======

  * Types
      * SAGBIBasis -- The type of all sagbi bases
      * Subring -- The type of all subrings
  * Functions and commands
      * groebnerMembershipTest -- Extrinsic
        method for subring membership
      * isSAGBI -- Check if the generators are a sagbi basis
      * sagbi -- Compute a subalgebra basis (sagbi basis)
      * sagbiBasis -- Constructs a computation object from a
        subring.
      * subalgebraBasis -- Compute subalgebra basis
        (sagbi basis) generators
      * subring -- Constructs a subring of a polynomial ring.
      * verifySagbi -- Test if the generators form sagbi
        basis
  * Methods
      * ambient(SAGBIBasis) -- The ambient ring
        of a SAGBIBasis computation object
      * ambient(Subring) -- The ambient ring of a
        subring
      * generators(SAGBIBasis) -- Returns a
        partial sagbi generating set
      * generators(Subring) -- A generating set
        of a subring
      * "groebnerMembershipTest(RingElement,Subring)" -- see
        groebnerMembershipTest, -- Extrinsic method for
        subring membership
      * "isSAGBI(SAGBIBasis)" -- see isSAGBI, -- Check if the
        generators are a sagbi basis
      * "isSAGBI(Subring)" -- see isSAGBI, -- Check if the
        generators are a sagbi basis
      * Matrix % SAGBIBasis -- Remainder modulo a
        subring
      * Matrix % Subring -- Remainder modulo a subring
      * net(SAGBIBasis) -- Short summary of a sagbi
        basis computation object
      * net(Subring) -- Short summary of a subring
      * numgens(Subring) -- The number of
        generators of a subring
      * ring(SAGBIBasis) -- The lifted ring of a
        SAGBIBasis computation object
      * RingElement % SAGBIBasis -- Remainder
        modulo a subring
      * RingElement % Subring -- Remainder modulo
        a subring
      * "sagbi(List)" -- see sagbi, -- Compute a subalgebra basis
        (sagbi basis)
      * "sagbi(Matrix)" -- see sagbi, -- Compute a subalgebra
        basis (sagbi basis)
      * "sagbi(SAGBIBasis)" -- see sagbi, -- Compute a subalgebra
        basis (sagbi basis)
      * "sagbi(Subring)" -- see sagbi, -- Compute a subalgebra
        basis (sagbi basis)
      * "sagbiBasis(HashTable)" -- see sagbiBasis, --
        Constructs a computation object from a subring.
      * "sagbiBasis(Subring)" -- see sagbiBasis, --
        Constructs a computation object from a subring.
      * "subalgebraBasis(List)" -- see subalgebraBasis,
        -- Compute subalgebra basis (sagbi basis) generators
      * "subalgebraBasis(Matrix)" -- see subalgebraBasis,
        -- Compute subalgebra basis (sagbi basis) generators
      * "subalgebraBasis(Subring)" -- see subalgebraBasis,
        -- Compute subalgebra basis (sagbi basis) generators
      * "subring(List)" -- see subring, -- Constructs a subring
        of a polynomial ring.
      * "subring(Matrix)" -- see subring, -- Constructs a
        subring of a polynomial ring.
      * "subring(SAGBIBasis)" -- see subring, -- Constructs a
        subring of a polynomial ring.
      * "verifySagbi(List)" -- see verifySagbi, -- Test if
        the generators form sagbi basis
      * "verifySagbi(Matrix)" -- see verifySagbi, -- Test if
        the generators form sagbi basis
      * "verifySagbi(Subring)" -- see verifySagbi, -- Test
        if the generators form sagbi basis
  * Symbols
      * AutoSubduce -- Flag for autosubduction before the
        Sagbi algorithm
      * AutoSubduceOnPartialCompletion,
        -- Subduct sagbi generators at the end of the Sagbi algorithm
      * Limit -- Degree limit for the Sagbi algorithm
      * PrintLevel -- Levels of information displayed during
        Sagbi algorithm
      * ReduceNewGenerators -- Flag for reducing
        new generators in Sagbi algorithm
      * StorePending -- Flag for storing the pending list
        to the result of the Sagbi algorithm
      * Strategy -- Update procedure for the Sagbi algorithm
      * SubductionMethod -- Subduction method for the
        Sagbi algorithm

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

The object SubalgebraBases, is a package (Macaulay2Doc).

ambient(SAGBIBasis) -- The ambient ring of a SAGBIBasis computation object
**************************************************************************

Synopsis
========

  * Function: ambient (Macaulay2Doc),
  * Usage:
        result = ambient S
  * Inputs:
      * S, an instance of the type SAGBIBasis,
  * Outputs:
      * result, a ring (Macaulay2Doc),

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

Returns the ambient ring of S. This may be a PolynomialRing or QuotientRing.

+-----------------------------------------------------------------+
|i1 : R = QQ[x,y,z];                                              |
+-----------------------------------------------------------------+
|i2 : S = sagbi {x^2, y^2, z^2}                                   |
|                                                                 |
|o2 = SAGBIBasis Computation Object with 3 generators, Limit = 10.|
|                                                                 |
|o2 : SAGBIBasis                                                  |
+-----------------------------------------------------------------+
|i3 : ambient S                                                   |
|                                                                 |
|o3 = R                                                           |
|                                                                 |
|o3 : PolynomialRing                                              |
+-----------------------------------------------------------------+
|i4 : Q = R / ideal(x^3 - y);                                     |
+-----------------------------------------------------------------+
|i5 : S' = sagbi {x^3, y^2}                                       |
|                                                                 |
|o5 = SAGBIBasis Computation Object with 1 generators, Limit = 10.|
|                                                                 |
|o5 : SAGBIBasis                                                  |
+-----------------------------------------------------------------+
|i6 : ambient S'                                                  |
|                                                                 |
|o6 = Q                                                           |
|                                                                 |
|o6 : QuotientRing                                                |
+-----------------------------------------------------------------+

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use this method:
========================

  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object

ambient(Subring) -- The ambient ring of a subring
*************************************************

Synopsis
========

  * Function: ambient (Macaulay2Doc),
  * Usage:
        result = ambient S
  * Inputs:
      * S, an instance of the type Subring,
  * Outputs:
      * result, a ring (Macaulay2Doc),

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

Returns the ambient ring of the generating set of the Subring.
This may be a PolynomialRing or QuotientRing.

+----------------------------------+
|i1 : R = QQ[x,y,z];               |
+----------------------------------+
|i2 : S = subring({x^2, y^2, z^2});|
+----------------------------------+
|i3 : ambient S                    |
|                                  |
|o3 = R                            |
|                                  |
|o3 : PolynomialRing               |
+----------------------------------+
|i4 : Q = R / ideal(x^3 - y);      |
+----------------------------------+
|i5 : S' = subring({x^3, y^2});    |
+----------------------------------+
|i6 : ambient S'                   |
|                                  |
|o6 = Q                            |
|                                  |
|o6 : QuotientRing                 |
+----------------------------------+

See also
========

  * Subring -- The type of all subrings
  * subring -- Constructs a subring of a polynomial ring.
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring

Ways to use this method:
========================

  * ambient(Subring) -- The ambient ring of a
    subring

AutoSubduce -- Flag for autosubduction before the Sagbi algorithm
*****************************************************************

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

By default, the function sagbi, performs autosubduction on the
generators of the given subring before starting the main algorithm. This step
is required to guarentee correctness of the result. However, the output of the
sagbi, algorithm is often correct even when this step is skipped.
Setting this flag to false may result in a performance improvement, albeit with
a risk of errors.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named AutoSubduce :
====================================================

  * "sagbi(...,AutoSubduce=>...)" -- see sagbi, -- Compute a
    subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,AutoSubduce=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators

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

The object AutoSubduce, is a symbol (Macaulay2Doc).

AutoSubduceOnPartialCompletion -- Subduct sagbi generators at the end of the Sagbi algorithm
********************************************************************************************

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

During the main loop in sagbi, if no new sagbi generators are
added and the AutoSubduceOnPartialCompletion,
flag is true then all sagbi generators are
subducted against each other. This a significant time investment, however if no
new sagbi generators are to be added then the subduction of the sagbi
generators will speed up the computation of the groebner basis of the reduction
ideal and S-pairs.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named AutoSubduceOnPartialCompletion :
=======================================================================

  * "sagbi(...,AutoSubduceOnPartialCompletion=>...)" -- see sagbi,
    -- Compute a subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,AutoSubduceOnPartialCompletion=>...)" -- see
    subalgebraBasis, -- Compute subalgebra basis (sagbi basis)
    generators

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

The object AutoSubduceOnPartialCompletion,
is a symbol (Macaulay2Doc).

Example: Translation and rotation sub-actions of the adjoint action of SE(3)
****************************************************************************

The following example shows how to use this package to calculate the invariants
of the translation sub-action of the adjoint action of $SE(3)$, as considered
in the preprint Polynomial invariants and SAGBI bases for multi-screws. (see
https://arxiv.org/abs/2001.05417 )

+-----------------------------------------------------------------------------+
|i1 : gndR = QQ[(t_1..t_3)|(w_1..w_3)|(v_1..v_3), MonomialOrder => Lex];      |
+-----------------------------------------------------------------------------+
|i2 : translation := matrix {{w_1}, {w_2}, {w_3}, {t_1*w_2+t_2*w_3+v_1},      |
|                                                                             |
|                6          1                                                 |
|o2 : Matrix gndR  <--- gndR                                                  |
|-----------------------------------------------------------------------------|
|{-t_1*w_1+t_3*w_3+v_2}, {-t_2*w_1-t_3*w_2+v_3}};                             |
+-----------------------------------------------------------------------------+
|i3 : sag := sagbi transpose translation;                                     |
+-----------------------------------------------------------------------------+
|i4 : netList first entries gens sag                                          |
|                                                                             |
|     +------------------+                                                    |
|o4 = |w                 |                                                    |
|     | 3                |                                                    |
|     +------------------+                                                    |
|     |w                 |                                                    |
|     | 2                |                                                    |
|     +------------------+                                                    |
|     |w                 |                                                    |
|     | 1                |                                                    |
|     +------------------+                                                    |
|     |t w  + t w  - v   |                                                    |
|     | 2 1    3 2    3  |                                                    |
|     +------------------+                                                    |
|     |t w  + t w  + v   |                                                    |
|     | 1 2    2 3    1  |                                                    |
|     +------------------+                                                    |
|     |t w  - t w  - v   |                                                    |
|     | 1 1    3 3    2  |                                                    |
|     +------------------+                                                    |
|     |w v  + w v  + w v |                                                    |
|     | 1 1    2 2    3 3|                                                    |
|     +------------------+                                                    |
+-----------------------------------------------------------------------------+

The above is precisely the 5 invariants Crook and Donelon give in equation (9),
plus the additional 6th invariant.

The generators computed below verify Theorem 2 of Crook and Donelan, describing
rotational invariants in the case where m=3.

+-----------------------------------------------------------------------------+
|i5 : R = QQ[x_1..x_9, MonomialOrder => Lex];                                 |
+-----------------------------------------------------------------------------+
|i6 : eqns := {x_1^2+x_2^2+x_3^2-1,                                           |
|              x_4^2+x_5^2+x_6^2-1,                                           |
|              x_7^2+x_8^2+x_9^2-1,                                           |
|-----------------------------------------------------------------------------|
|x_1*x_4+x_2*x_5+x_3*x_6, x_1*x_7+x_2*x_8+x_3*x_9, x_1*x_4+x_2*x_5+x_3*x_6,   |
|x_4*x_7+x_5*x_8+x_6*x_9, x_1*x_7+x_2*x_8+x_3*x_9, x_4*x_7+x_5*x_8+x_6*x_9,   |
|x_1*x_5*x_9-x_1*x_6*x_8-x_2*x_4*x_9+x_2*x_6*x_7+x_3*x_4*x_8-x_3*x_5*x_7-1};  |
+-----------------------------------------------------------------------------+
|i7 : sag1 = subring sagbi eqns;                                              |
+-----------------------------------------------------------------------------+
|i8 : SB = sagbi(sag1, Limit => 100);                                         |
+-----------------------------------------------------------------------------+
|i9 : verifySagbi (gens SB)                                                   |
|                                                                             |
|o9 = true                                                                    |
+-----------------------------------------------------------------------------+
|i10 : netList first entries gens SB                                          |
|                                                                             |
|      +----------------------------------------------------------------------|
|      | 2    2    2                                                          |
|o10 = |x  + x  + x                                                           |
|      | 7    8    9                                                          |
|      +----------------------------------------------------------------------|
|      |x x  + x x  + x x                                                     |
|      | 4 7    5 8    6 9                                                    |
|      +----------------------------------------------------------------------|
|      | 2    2    2                                                          |
|      |x  + x  + x                                                           |
|      | 4    5    6                                                          |
|      +----------------------------------------------------------------------|
|      |x x  + x x  + x x                                                     |
|      | 1 7    2 8    3 9                                                    |
|      +----------------------------------------------------------------------|
|      |x x  + x x  + x x                                                     |
|      | 1 4    2 5    3 6                                                    |
|      +----------------------------------------------------------------------|
|      | 2    2    2                                                          |
|      |x  + x  + x                                                           |
|      | 1    2    3                                                          |
|      +----------------------------------------------------------------------|
|      |x x x  - x x x  - x x x  + x x x  + x x x  - x x x                    |
|      | 1 5 9    1 6 8    2 4 9    2 6 7    3 4 8    3 5 7                   |
|      +----------------------------------------------------------------------|
|      | 2 2    2 2                            2 2    2 2                2 2  |
|      |x x  + x x  - 2x x x x  - 2x x x x  + x x  + x x  - 2x x x x  + x x  +|
|      | 4 8    4 9     4 5 7 8     4 6 7 9    5 7    5 9     5 6 8 9    6 7  |
|      +----------------------------------------------------------------------|
|      |     2        2                                         2        2    |
|      |x x x  + x x x  - x x x x  - x x x x  - x x x x  + x x x  + x x x  - x|
|      | 1 4 8    1 4 9    1 5 7 8    1 6 7 9    2 4 7 8    2 5 7    2 5 9    |
|      +----------------------------------------------------------------------|
|      |                         2        2        2                          |
|      |x x x x  + x x x x  - x x x  - x x x  - x x x  + x x x x  + x x x x  -|
|      | 1 4 5 8    1 4 6 9    1 5 7    1 6 7    2 4 8    2 4 5 7    2 5 6 9  |
|      +----------------------------------------------------------------------|
|      | 2 2    2 2                            2 2    2 2                2 2  |
|      |x x  + x x  - 2x x x x  - 2x x x x  + x x  + x x  - 2x x x x  + x x  +|
|      | 1 8    1 9     1 2 7 8     1 3 7 9    2 7    2 9     2 3 8 9    3 7  |
|      +----------------------------------------------------------------------|
|      | 2        2                                                    2      |
|      |x x x  + x x x  - x x x x  - x x x x  - x x x x  - x x x x  + x x x  +|
|      | 1 5 8    1 6 9    1 2 4 8    1 2 5 7    1 3 4 9    1 3 6 7    2 4 7  |
|      +----------------------------------------------------------------------|
|      | 2 2    2 2                            2 2    2 2                2 2  |
|      |x x  + x x  - 2x x x x  - 2x x x x  + x x  + x x  - 2x x x x  + x x  +|
|      | 1 5    1 6     1 2 4 5     1 3 4 6    2 4    2 6     2 3 5 6    3 4  |
|      +----------------------------------------------------------------------|
|-----------------------------------------------------------------------------|
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|                                               |                             |
|                                               |                             |
|-----------------------------------------------+                             |
|  2 2                                          |                             |
| x x                                           |                             |
|  6 8                                          |                             |
|-----------------------------------------------+                             |
|                                     2        2|                             |
| x x x  - x x x x  - x x x x  + x x x  + x x x |                             |
|2 6 8 9    3 4 7 9    3 5 8 9    3 6 7    3 6 8|                             |
|-----------------------------------------------+                             |
|    2        2                   2             |                             |
| x x x  - x x x  + x x x x  - x x x  + x x x x |                             |
|  2 6 8    3 4 9    3 4 6 7    3 5 9    3 5 6 8|                             |
|-----------------------------------------------+                             |
|  2 2                                          |                             |
| x x                                           |                             |
|  3 8                                          |                             |
|-----------------------------------------------+                             |
|  2                              2        2    |                             |
| x x x  - x x x x  - x x x x  + x x x  + x x x |                             |
|  2 6 9    2 3 5 9    2 3 6 8    3 4 7    3 5 8|                             |
|-----------------------------------------------+                             |
|  2 2                                          |                             |
| x x                                           |                             |
|  3 5                                          |                             |
|-----------------------------------------------+                             |
+-----------------------------------------------------------------------------+

generators(SAGBIBasis) -- Returns a partial sagbi generating set
****************************************************************

Synopsis
========

  * Function: generators (Macaulay2Doc),
  * Usage:
        result = gens S
  * Inputs:
      * S, an instance of the type SAGBIBasis,
  * Optional inputs (Macaulay2Doc),:
      * CoefficientRing (Macaulay2Doc), => a
        Boolean value (Macaulay2Doc), default value null, unused
        option
  * Outputs:
      * result, a matrix (Macaulay2Doc),

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

Returns the current list of sagbiGenerators of the underlying Subring.
If the SAGBIBasis, is not a complete sagbi basis
(for example it is obtained from a partial computation) then the generators
obtained from this command may not be a generating set for the original
subring.

+-------------------------------------+
|i1 : R = QQ[x,y];                    |
+-------------------------------------+
|i2 : S = subring {x*y, x^2*y, x^3*y};|
+-------------------------------------+
|i3 : gens S                          |
|                                     |
|o3 = | xy x2y x3y |                  |
|                                     |
|             1       3               |
|o3 : Matrix R  <--- R                |
+-------------------------------------+
|i4 : SB = sagbi(S, Limit => 3);      |
+-------------------------------------+
|i5 : gens SB                         |
|                                     |
|o5 = | xy x2y |                      |
|                                     |
|             1       2               |
|o5 : Matrix R  <--- R                |
+-------------------------------------+
|i6 : verifySagbi S                   |
|                                     |
|o6 = true                            |
+-------------------------------------+

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use this method:
========================

  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set

generators(Subring) -- A generating set of a subring
****************************************************

Synopsis
========

  * Function: generators (Macaulay2Doc),
  * Usage:
        result = gens S
  * Inputs:
      * S, an instance of the type Subring,
  * Optional inputs (Macaulay2Doc),:
      * CoefficientRing (Macaulay2Doc), => ...,
        default value null, null
  * Outputs:
      * result, a matrix (Macaulay2Doc),

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

Returns a generating set for the Subring, as a one-row matrix.

+----------------------------------+
|i1 : R = QQ[x,y,z];               |
+----------------------------------+
|i2 : S = subring({x^2, y^2, z^2});|
+----------------------------------+
|i3 : gens S                       |
|                                  |
|o3 = | x2 y2 z2 |                 |
|                                  |
|             1       3            |
|o3 : Matrix R  <--- R             |
+----------------------------------+

See also
========

  * Subring -- The type of all subrings
  * subring -- Constructs a subring of a polynomial ring.
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring

Ways to use this method:
========================

  * generators(Subring) -- A generating set of
    a subring

groebnerMembershipTest -- Extrinsic method for subring membership
*****************************************************************

Synopsis
========

  * Usage:
        result = groebnerMembershipTest(f, S)
  * Inputs:
      * f, a ring element (Macaulay2Doc),
      * S, an instance of the type Subring,
  * Outputs:
      * result, a Boolean value (Macaulay2Doc), f belongs to S.

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

Uses the extrinsic method to test membership of a polynomial in a subring. Note
that S must be a subring of a polynomial ring.

+----------------------------------+
|i1 : R = QQ[x,y];                 |
+----------------------------------+
|i2 : S = subring {x^2 - x*y, x^4};|
+----------------------------------+
|i3 : f1 = x^2*y^2 - 2*x^3*y;      |
+----------------------------------+
|i4 : groebnerMembershipTest(f1, S)|
|                                  |
|o4 = true                         |
+----------------------------------+
|i5 : f2 = x^10;                   |
+----------------------------------+
|i6 : groebnerMembershipTest(f2, S)|
|                                  |
|o6 = false                        |
+----------------------------------+

If a sagbi basis is known for S then it is recommended to use RingElement % Subring.

See also
========

  * Subring -- The type of all subrings
  * RingElement % Subring -- Remainder modulo a
    subring
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use groebnerMembershipTest :
====================================

  * "groebnerMembershipTest(RingElement,Subring)"

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

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

isSAGBI -- Check if the generators are a sagbi basis
****************************************************

Synopsis
========

  * Usage:
        result = isSAGBI S
        result = isSAGBI SB
  * Inputs:
      * S, an instance of the type Subring,
      * SB, an instance of the type SAGBIBasis,
  * Outputs:
      * result, a Boolean value (Macaulay2Doc),

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

After running sagbi on a subring, the result of the computation is stored in
that subring. If new sagbi generators need to be added to S to make it a sagbi
basis then isSAGBI will return false. If isSAGBI is run on a ring for which no
sagbi computation has been peformed, then isSAGBI will return null. In this
case it is recommended to use verifySagbi, to check whether
the generators are a sagbi basis.

+------------------------------------------------------------------------+
|i1 : R = QQ[x,y,z];                                                     |
+------------------------------------------------------------------------+
|i2 : S = subring {x+y+z,x*y+x*z+y*z, x*y*z, (x-y)*(x-z)*(y-z)};         |
+------------------------------------------------------------------------+
|i3 : isSAGBI S                                                          |
+------------------------------------------------------------------------+
|i4 : sagbi(S, Limit => 5)                                               |
|                                                                        |
|o4 = Partial SAGBIBasis Computation Object with 6 generators, Limit = 5.|
|                                                                        |
|o4 : SAGBIBasis                                                         |
+------------------------------------------------------------------------+
|i5 : isSAGBI S                                                          |
|                                                                        |
|o5 = false                                                              |
+------------------------------------------------------------------------+
|i6 : S' = subring {x+y+z,x*y+x*z+y*z, x*y*z};                           |
+------------------------------------------------------------------------+
|i7 : isSAGBI S'                                                         |
+------------------------------------------------------------------------+
|i8 : sagbi(S', Limit => 5)                                              |
|                                                                        |
|o8 = SAGBIBasis Computation Object with 3 generators, Limit = 5.        |
|                                                                        |
|o8 : SAGBIBasis                                                         |
+------------------------------------------------------------------------+
|i9 : isSAGBI S'                                                         |
|                                                                        |
|o9 = true                                                               |
+------------------------------------------------------------------------+

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * verifySagbi -- Test if the generators form sagbi basis

Ways to use isSAGBI :
=====================

  * "isSAGBI(SAGBIBasis)"
  * "isSAGBI(Subring)"

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

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

Limit -- Degree limit for the Sagbi algorithm
*********************************************

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

The stopping criteria for the main loop in sagbi, are: a finite
sagbi basis is computed, or the smallest degree of an S-pair exceeds the
Limit. In general, the initial terms of generators of a partial
computation do not generate the initial algebra up to the degree limit. It is
possible that, with a higher degree limit, sagbi generators of lower degree
will be added. One can guarantee that all sagbi generators up to a certain
degree are found by using a graded term-order such as GRevLex and working with
a subring or a polynomial ring (and not a quotient ring).

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named Limit :
==============================================

  * "sagbi(...,Limit=>...)" -- see sagbi, -- Compute a subalgebra
    basis (sagbi basis)
  * "subalgebraBasis(...,Limit=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators
  * "verifySagbi(...,Limit=>...)" -- see verifySagbi, --
    Test if the generators form sagbi basis

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

The object Limit, is a symbol (Macaulay2Doc).

Matrix % SAGBIBasis -- Remainder modulo a subring
*************************************************

Synopsis
========

  * Operator: % (Macaulay2Doc),
  * Usage:
        R = M % SB
  * Inputs:
      * M, a matrix (Macaulay2Doc),
      * SB, an instance of the type SAGBIBasis,
  * Outputs:
      * R, a matrix (Macaulay2Doc), the normal form of entries of
        M modulo the subring

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

Subducts M entry-wise against the sagbi generators of SB.

See also
========

  * RingElement % Subring -- Remainder modulo a
    subring
  * Matrix % Subring -- Remainder modulo a subring
  * RingElement % SAGBIBasis -- Remainder
    modulo a subring
  * Matrix % SAGBIBasis -- Remainder modulo a
    subring
  * Subring -- The type of all subrings
  * SAGBIBasis -- The type of all sagbi bases
  * groebnerMembershipTest -- Extrinsic method
    for subring membership

Ways to use this method:
========================

  * Matrix % SAGBIBasis -- Remainder modulo a
    subring

Matrix % Subring -- Remainder modulo a subring
**********************************************

Synopsis
========

  * Operator: % (Macaulay2Doc),
  * Usage:
        R = M % S
  * Inputs:
      * M, a matrix (Macaulay2Doc),
      * S, an instance of the type Subring,
  * Outputs:
      * R, a matrix (Macaulay2Doc), the normal form of entries of
        M modulo the subring

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

Applies RingElement % Subring, entry-wise to M.

See also
========

  * RingElement % Subring -- Remainder modulo a
    subring
  * Matrix % Subring -- Remainder modulo a subring
  * RingElement % SAGBIBasis -- Remainder
    modulo a subring
  * Matrix % SAGBIBasis -- Remainder modulo a
    subring
  * Subring -- The type of all subrings
  * SAGBIBasis -- The type of all sagbi bases
  * groebnerMembershipTest -- Extrinsic method
    for subring membership

Ways to use this method:
========================

  * Matrix % Subring -- Remainder modulo a subring

net(SAGBIBasis) -- Short summary of a sagbi basis computation object
********************************************************************

Synopsis
========

  * Function: net (Macaulay2Doc),
  * Usage:
        net S
  * Inputs:
      * S, an instance of the type SAGBIBasis,
  * Outputs:
      * a net (Macaulay2Doc),

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

Displays the number of sagbi generators of a S along with the degree limit.

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use this method:
========================

  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object

net(Subring) -- Short summary of a subring
******************************************

Synopsis
========

  * Function: net (Macaulay2Doc),
  * Usage:
        net S
  * Inputs:
      * S, an instance of the type Subring,
  * Outputs:
      * a net (Macaulay2Doc),

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

Displays the ambient ring and number of generators of a Subring.

See also
========

  * Subring -- The type of all subrings
  * subring -- Constructs a subring of a polynomial ring.
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring

Ways to use this method:
========================

  * net(Subring) -- Short summary of a subring

numgens(Subring) -- The number of generators of a subring
*********************************************************

Synopsis
========

  * Function: numgens (Macaulay2Doc),
  * Usage:
        result = numgens S
  * Inputs:
      * S, an instance of the type Subring,
  * Outputs:
      * result, an integer (Macaulay2Doc),

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

Returns the number of generators of the Subring.

+----------------------------------+
|i1 : R = QQ[x,y,z];               |
+----------------------------------+
|i2 : S = subring({x^2, y^2, z^2});|
+----------------------------------+
|i3 : numgens S                    |
|                                  |
|o3 = 3                            |
+----------------------------------+

See also
========

  * Subring -- The type of all subrings
  * subring -- Constructs a subring of a polynomial ring.
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring

Ways to use this method:
========================

  * numgens(Subring) -- The number of generators
    of a subring

PrintLevel -- Levels of information displayed during Sagbi algorithm
********************************************************************

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

PrintLevel 0: no output

PrintLevel 1+: some basic information each loop (no polynomials): computation
degree, number of S-pairs, number of new generators, termination conditions.

PrintLevel 2+: basic polynomials: S-pairs and new sagbi generators

PrintLevel 3+: extra polynomials: reduction ideal generators, zeroGens, current
sagbi generators

PrintLevel 4+: show the input and output of each subduction

Higher levels exist but may be overly verbose. PrintLevel 5 shows the
processPending data and PrintLevel 6 shows the intermediate steps for top-level
subduction.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named PrintLevel :
===================================================

  * "sagbi(...,PrintLevel=>...)" -- see sagbi, -- Compute a
    subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,PrintLevel=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators
  * "verifySagbi(...,PrintLevel=>...)" -- see verifySagbi,
    -- Test if the generators form sagbi basis

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

The object PrintLevel, is a symbol (Macaulay2Doc).

ReduceNewGenerators -- Flag for reducing new generators in Sagbi algorithm
**************************************************************************

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

The function sagbi, computes a sagbi basis by subducting S-pairs.
Any resulting non-zero polynomials are added to the list of sagbi generators.
However if ReduceNewGenerators is set to true (by default) then the new
generators are reduced using gaussian elimination against the other new
generators. This process is quick (as fast as computing a groebner basis for a
linear ideal) and ensures that duplicate generators are not added to the list
of sagbi generators.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named ReduceNewGenerators :
============================================================

  * "sagbi(...,ReduceNewGenerators=>...)" -- see sagbi, -- Compute
    a subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,ReduceNewGenerators=>...)" -- see
    subalgebraBasis, -- Compute subalgebra basis (sagbi basis)
    generators

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

The object ReduceNewGenerators, is a symbol (Macaulay2Doc).

ring(SAGBIBasis) -- The lifted ring of a SAGBIBasis computation object
**********************************************************************

Synopsis
========

  * Function: ring (Macaulay2Doc),
  * Usage:
        result = ring S
  * Inputs:
      * S, an instance of the type SAGBIBasis,
  * Outputs:
      * result, a ring (Macaulay2Doc),

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

Returns the lifted ring of S. This is always a PolynomialRing.

+-----------------------------------------------------------------+
|i1 : R = QQ[x,y,z];                                              |
+-----------------------------------------------------------------+
|i2 : S = sagbi {x^2, y^2, z^2}                                   |
|                                                                 |
|o2 = SAGBIBasis Computation Object with 3 generators, Limit = 10.|
|                                                                 |
|o2 : SAGBIBasis                                                  |
+-----------------------------------------------------------------+
|i3 : ring S                                                      |
|                                                                 |
|o3 = R                                                           |
|                                                                 |
|o3 : PolynomialRing                                              |
+-----------------------------------------------------------------+
|i4 : Q = R / ideal(x^3 - y);                                     |
+-----------------------------------------------------------------+
|i5 : S' = sagbi {x^3, y^2}                                       |
|                                                                 |
|o5 = SAGBIBasis Computation Object with 1 generators, Limit = 10.|
|                                                                 |
|o5 : SAGBIBasis                                                  |
+-----------------------------------------------------------------+
|i6 : ring S'                                                     |
|                                                                 |
|o6 = R                                                           |
|                                                                 |
|o6 : PolynomialRing                                              |
+-----------------------------------------------------------------+

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use this method:
========================

  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object

RingElement % SAGBIBasis -- Remainder modulo a subring
******************************************************

Synopsis
========

  * Operator: % (Macaulay2Doc),
  * Usage:
        r = f % SB
  * Inputs:
      * f, a ring element (Macaulay2Doc),
      * SB, an instance of the type SAGBIBasis,
  * Outputs:
      * r, a ring element (Macaulay2Doc), the normal form of
        f modulo the subring

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

Subducts f against the sagbi generators of SB.

See also
========

  * RingElement % Subring -- Remainder modulo a
    subring
  * Matrix % Subring -- Remainder modulo a subring
  * RingElement % SAGBIBasis -- Remainder
    modulo a subring
  * Matrix % SAGBIBasis -- Remainder modulo a
    subring
  * Subring -- The type of all subrings
  * SAGBIBasis -- The type of all sagbi bases
  * groebnerMembershipTest -- Extrinsic method
    for subring membership

Ways to use this method:
========================

  * RingElement % SAGBIBasis -- Remainder
    modulo a subring

RingElement % Subring -- Remainder modulo a subring
***************************************************

Synopsis
========

  * Operator: % (Macaulay2Doc),
  * Usage:
        r = f % S
  * Inputs:
      * f, a ring element (Macaulay2Doc),
      * S, an instance of the type Subring,
  * Outputs:
      * r, a ring element (Macaulay2Doc), the normal form of
        f modulo the subring

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

The result is zero if and only if the input belongs to the subring. If a sagbi
basis is known for the subring then subduction is used to compute the normal
forms. If no sagbi basis is known then an extrisic method is used, similar to
groebnerMembershipTest.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x1, x2, x3];                                                     |
+-----------------------------------------------------------------------------+
|i2 : S = subring {x1+x2+x3, x1*x2+x1*x3+x2*x3, x1*x2*x3,                     |
|                                                                             |
|o2 = subring of R with 4 generators                                          |
|                                                                             |
|o2 : Subring                                                                 |
|-----------------------------------------------------------------------------|
|(x1-x2)*(x1-x3)*(x2-x3)} --usual invariants of A_3                           |
+-----------------------------------------------------------------------------+
|i3 : f = x1 + x2 + 2*x3                                                      |
|                                                                             |
|o3 = x1 + x2 + 2x3                                                           |
|                                                                             |
|o3 : R                                                                       |
+-----------------------------------------------------------------------------+
|i4 : f % S                                                                   |
|                                                                             |
|o4 = x3                                                                      |
|                                                                             |
|o4 : R                                                                       |
+-----------------------------------------------------------------------------+
|i5 : g = x1^2*x2 + x2^2*x3 + x3^2*x1                                         |
|                                                                             |
|       2       2          2                                                  |
|o5 = x1 x2 + x2 x3 + x1*x3                                                   |
|                                                                             |
|o5 : R                                                                       |
+-----------------------------------------------------------------------------+
|i6 : g % S                                                                   |
|                                                                             |
|o6 = 0                                                                       |
|                                                                             |
|o6 : R                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * RingElement % Subring -- Remainder modulo a
    subring
  * Matrix % Subring -- Remainder modulo a subring
  * RingElement % SAGBIBasis -- Remainder
    modulo a subring
  * Matrix % SAGBIBasis -- Remainder modulo a
    subring
  * Subring -- The type of all subrings
  * SAGBIBasis -- The type of all sagbi bases
  * groebnerMembershipTest -- Extrinsic method
    for subring membership

Ways to use this method:
========================

  * RingElement % Subring -- Remainder modulo a
    subring

sagbi -- Compute a subalgebra basis (sagbi basis)
*************************************************

Synopsis
========

  * Usage:
        N = sagbi M
        N = sagbi A
        N = sagbi L
        N = sagbi B
  * Inputs:
      * A, an instance of the type Subring,
      * M, a matrix (Macaulay2Doc), of generators for a subring
        of a polynomial ring (Macaulay2Doc),
      * L, a list (Macaulay2Doc), containing generators for a
        subring of a polynomial ring (Macaulay2Doc),
      * B, an instance of the type SAGBIBasis, containing a
        partial computation of a sagbi basis
  * Optional inputs (Macaulay2Doc),:
      * AutoSubduce => a Boolean value (Macaulay2Doc), default
        value true, a flag indicating when to perform autosubduction on the
        generators before performing the Sagbi basis computation (See:
        AutoSubduce)
      * ReduceNewGenerators => a Boolean value (Macaulay2Doc),
        default value true, a flag indicating whether to apply gaussian
        elimination to new sagbi generators before adding them to the current
        sagbi basis (See: ReduceNewGenerators)
      * StorePending => a Boolean value (Macaulay2Doc), default
        value true, a flag that indicates whether the pending list should be
        stored in the result. (See: StorePending)
      * Strategy => a string (Macaulay2Doc), default value
        "Master", the update strategy at the beginning of each loop:
        \"DegreeByDegree\", \"Incremental\", and \"Master\". The strategy
        \"Master\" is a hybrid that combines the other two; starting with
        \"DegreeByDegree\" for low degrees and switching to \"Incremental\".
        (See: Strategy)
      * SubductionMethod => a string (Macaulay2Doc), default
        value "Top", the method used for subduction either: \"Top\" or
        \"Engine\". (See: SubductionMethod)
      * Limit => an integer (Macaulay2Doc), default value 10, a
        degree limit for the binomial S-pairs that are computed internally.
      * AutoSubduceOnPartialCompletion => a Boolean value (Macaulay2Doc),
        default value false, apply autosubduction to
        the sagbi generators the first time no new generators are added. Use
        this only if very few new sagbi generators are expected. (See:
        AutoSubduceOnPartialCompletion)
      * PrintLevel => an integer (Macaulay2Doc), default value 0,
        When this is greater than zero, information is printed about the
        progress of the computation (See: PrintLevel)
  * Outputs:
      * N, an instance of the type SAGBIBasis, a computation
        object holding the state of the sagbi basis computation

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

The output of this function is a partial subalgebra basis stored in a
computation object.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[t_(1,1)..t_(3,3),MonomialOrder=>Lex];                            |
+-----------------------------------------------------------------------------+
|i2 : M = genericMatrix(R,3,3);                                               |
|                                                                             |
|             3       3                                                       |
|o2 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i3 : A = subring gens minors(2, M);                                          |
+-----------------------------------------------------------------------------+
|i4 : verifySagbi A                                                           |
|                                                                             |
|o4 = false                                                                   |
+-----------------------------------------------------------------------------+
|i5 : S = sagbi A;                                                            |
+-----------------------------------------------------------------------------+
|i6 : gS = gens S                                                             |
|                                                                             |
|o6 = | t_(2,2)t_(3,3)-t_(2,3)t_(3,2) t_(2,1)t_(3,3)-t_(2,3)t_(3,1)           |
|     ------------------------------------------------------------------------|
|     t_(2,1)t_(3,2)-t_(2,2)t_(3,1) t_(1,2)t_(3,3)-t_(1,3)t_(3,2)             |
|     ------------------------------------------------------------------------|
|     t_(1,2)t_(2,3)-t_(1,3)t_(2,2) t_(1,1)t_(3,3)-t_(1,3)t_(3,1)             |
|     ------------------------------------------------------------------------|
|     t_(1,1)t_(3,2)-t_(1,2)t_(3,1) t_(1,1)t_(2,3)-t_(1,3)t_(2,1)             |
|     ------------------------------------------------------------------------|
|     t_(1,1)t_(2,2)-t_(1,2)t_(2,1)                                           |
|     ------------------------------------------------------------------------|
|     t_(1,1)t_(2,2)t_(3,1)t_(3,3)-t_(1,1)t_(2,3)t_(3,1)t_(3,2)-t_(1,2)t_(2,1)|
|     ------------------------------------------------------------------------|
|     t_(3,1)t_(3,3)+t_(1,2)t_(2,3)t_(3,1)^2+t_(1,3)t_(2,1)t_(3,1)t_(3,2)-t_(1|
|     ------------------------------------------------------------------------|
|     ,3)t_(2,2)t_(3,1)^2 t_(1,1)t_(1,3)t_(2,2)t_(3,3)-t_(1,1)t_(1,3)t_(2,3)t |
|     ------------------------------------------------------------------------|
|     _(3,2)-t_(1,2)t_(1,3)t_(2,1)t_(3,3)+t_(1,2)t_(1,3)t_(2,3)t_(3,1)+t_(1,3 |
|     ------------------------------------------------------------------------|
|     )^2t_(2,1)t_(3,2)-t_(1,3)^2t_(2,2)t_(3,1) |                             |
|                                                                             |
|             1       11                                                      |
|o6 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
|i7 : verifySagbi gS                                                          |
|                                                                             |
|o7 = true                                                                    |
+-----------------------------------------------------------------------------+

Partial subalgebra bases are unavoidable since a subalgebra of a polynomial
ring, endowed with some polynomial order, need not have a finite subalgebra
basis.  Here is a quintessential example of this phenomenon:

+------------------------------------------------+
|i8 : R=QQ[x,y];                                 |
+------------------------------------------------+
|i9 : A = subring matrix{{x+y,x*y,x*y^2}};       |
+------------------------------------------------+
|i10 : gens sagbi(A,Limit=>3)                    |
|                                                |
|o10 = | x+y xy xy2 |                            |
|                                                |
|              1       3                         |
|o10 : Matrix R  <--- R                          |
+------------------------------------------------+
|i11 : gens sagbi(A,Limit=>10)                   |
|                                                |
|o11 = | x+y xy xy2 xy3 xy4 xy5 xy6 xy7 xy8 xy9 ||
|                                                |
|              1       10                        |
|o11 : Matrix R  <--- R                          |
+------------------------------------------------+

Nevertheless, a finite subalgebra basis can be computed in many cases.

See also
========

  * subalgebraBasis -- Compute subalgebra basis (sagbi
    basis) generators

Ways to use sagbi :
===================

  * "sagbi(List)"
  * "sagbi(Matrix)"
  * "sagbi(SAGBIBasis)"
  * "sagbi(Subring)"

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

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

SAGBIBasis -- The type of all sagbi bases
*****************************************

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

This is a computation object for sagbi bases. It stores a partial sagbi
computation for picking up a computation where it left off. An instance of a
SAGBIBasis is constructed with the function sagbiBasis, and
as the output of sagbi.

Every instance of SAGBIBasis contains the following hashtables:

  * data: contains parameters for the sagbi computation
  *   degree: current degree of the S-pairs in the sagbi algorithm.
  *   limit: degree limit of the computation.
  *   sagbiGenerators: generators in the sagbi basis (default none)
  *   subalgebraGenerators: original generating set of the subring.
  * ideals
  *   I: the ideal defining the ambient ring = liftedRing / I
  *   leadTermsI: initial ideal of I
  *   reductionIdeal: SIdeal+I lifted to the tensorRing
  *   SIdeal: ideal generated by (SagbiGenerators - TagVariables)
  * rings
  *   liftedRing: the polynomial ring of the quotient ring
  *   quotientRing: ambient ring of the underlying subring
  *   tensorRing: tensor product of the liftedRing with a polynomial ring that
    has one variable for each sagbi generator
  * maps: a collection of useful maps between the 'rings'
  * options: supplied options for the sagbi computation
  * pending: newly computed sagbi generators before they are added to the
    sagbiGenerators in 'data'

See also
========

  * sagbiBasis -- Constructs a computation object from a
    subring.
  * Subring -- The type of all subrings
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Methods that use an object of class SAGBIBasis :
================================================

  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * "isSAGBI(SAGBIBasis)" -- see isSAGBI, -- Check if the
    generators are a sagbi basis
  * Matrix % SAGBIBasis -- Remainder modulo a
    subring
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * RingElement % SAGBIBasis -- Remainder
    modulo a subring
  * "sagbi(SAGBIBasis)" -- see sagbi, -- Compute a subalgebra
    basis (sagbi basis)
  * "subring(SAGBIBasis)" -- see subring, -- Constructs a
    subring of a polynomial ring.

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

The object SAGBIBasis, is a type (Macaulay2Doc),
with ancestor classes HashTable (Macaulay2Doc), < Thing (Macaulay2Doc).

sagbiBasis -- Constructs a computation object from a subring.
*************************************************************

Synopsis
========

  * Usage:
        B = sagbiBasis S
  * Inputs:
      * S, an instance of the type Subring,
  * Optional inputs (Macaulay2Doc),:
      * VariableBaseName => a string (Macaulay2Doc), default
        value "p", name to be used internally for variables in the tensor ring.
  * Outputs:
      * B, an instance of the type SAGBIBasis,

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

This function serves as the canonical constructor for the SAGBIBasis,
type. It is also the output of the sagbi, function. A
SAGBIBasis, may be cast to a Subring, using
subring.

See also
========

  * SAGBIBasis -- The type of all sagbi bases
  * generators(SAGBIBasis) -- Returns a
    partial sagbi generating set
  * ambient(SAGBIBasis) -- The ambient ring of
    a SAGBIBasis computation object
  * ring(SAGBIBasis) -- The lifted ring of a
    SAGBIBasis computation object
  * net(SAGBIBasis) -- Short summary of a sagbi
    basis computation object
  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use sagbiBasis :
========================

  * "sagbiBasis(HashTable)"
  * "sagbiBasis(Subring)"

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

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

StorePending -- Flag for storing the pending list to the result of the Sagbi algorithm
**************************************************************************************

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

The function sagbi, produces a SAGBIBasis,
computation object. If the StorePending flag is true then the output will
contain a copy of the pending list. The pending list contains all S-pairs
grouped by their degrees. If the Sagbi algorithm terminates without producing a
complete sagbi basis, for example due to Limit, then the
computation may be resumed by calling sagbi, on the resulting
computation object with new options. The resumed computation will use the
pending list stored in the SAGBIBasis, computation object. If
there is no pending list in the computation object then one will be created.
Depending on the computation, the pending list may be very large and it may not
be convenient to save all the data.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named StorePending :
=====================================================

  * "sagbi(...,StorePending=>...)" -- see sagbi, -- Compute a
    subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,StorePending=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators

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

The object StorePending, is a symbol (Macaulay2Doc).

Strategy -- Update procedure for the Sagbi algorithm
****************************************************

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

At the beginning of each loop inside of sagbi, the main
SAGBIBasis, computation object is updated. There are two types of
update procedure; they are selected by setting Strategy to either
\"DegreeByDegree\" or \"Incremental\". The \"DegreeByDegree\" strategy computes
a partial groebner basis of the reduction ideal from scratch. The
\"Incremental\" strategy computes a full groebner basis of the reduction ideal
by using the previous full groebner basis together with the data of the new
sagbi generators. The \"DegreeByDegree\" strategy is better when many new
generators are added during each loop of the Sagbi algorithm. The
\"Incremental\" strategy is better when there is little change to the number of
sagbi generators. For many examples, it is observed that many new generators
are added at the beginning of sagbi basis computations. Then towards the end of
the computation, there are very few new generators that are added. By setting
Strategy to \"Master\" (default), the \"DegreeByDegree\" strategy is used at
the beginning and the strategy switches to \"Incremental\" part of the way
through the algorithm.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

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

  * "sagbi(...,Strategy=>...)" -- see sagbi, -- Compute a
    subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,Strategy=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators
  * "verifySagbi(...,Strategy=>...)" -- see verifySagbi, --
    Test if the generators form sagbi basis

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

The object Strategy, is a symbol (Macaulay2Doc).

subalgebraBasis -- Compute subalgebra basis (sagbi basis) generators
********************************************************************

Synopsis
========

  * Usage:
        N = subalgebraBasis M
        N = subalgebraBasis A
        N = subalgebraBasis L
        N = subalgebraBasis B
  * Inputs:
      * A, an instance of the type Subring,
      * M, a matrix (Macaulay2Doc), of generators for a subring
        of a polynomial ring (Macaulay2Doc),
      * L, a list (Macaulay2Doc), containing generators for a
        subring of a polynomial ring (Macaulay2Doc),
      * B, an instance of the type SAGBIBasis, containing a
        partial computation of a sagbi basis
  * Optional inputs (Macaulay2Doc),:
      * AutoSubduce => a Boolean value (Macaulay2Doc), default
        value true, a flag indicating when to perform autosubduction on the
        generators before performing the Sagbi basis computation (See:
        AutoSubduce)
      * ReduceNewGenerators => a Boolean value (Macaulay2Doc),
        default value true, a flag indicating whether to apply gaussian
        elimination to new sagbi generators before adding them to the current
        sagbi basis (See: ReduceNewGenerators)
      * StorePending => a Boolean value (Macaulay2Doc), default
        value true, a flag that indicates whether the pending list should be
        stored in the result. (See: StorePending)
      * Strategy => a string (Macaulay2Doc), default value
        "Master", the update strategy at the beginning of each loop:
        \"DegreeByDegree\", \"Incremental\", and \"Master\". The strategy
        \"Master\" is a hybrid that combines the other two; starting with
        \"DegreeByDegree\" for low degrees and switching to \"Incremental\".
        (See: Strategy)
      * SubductionMethod => a string (Macaulay2Doc), default
        value "Top", the method used for subduction either: \"Top\" or
        \"Engine\". (See: SubductionMethod)
      * Limit => an integer (Macaulay2Doc), default value 100, a
        degree limit for the binomial S-pairs that are computed internally.
      * AutoSubduceOnPartialCompletion => a Boolean value (Macaulay2Doc),
        default value false, apply autosubduction to
        the sagbi generators the first time no new generators are added. Use
        this only if very few new sagbi generators are expected. (See:
        AutoSubduceOnPartialCompletion)
      * PrintLevel => an integer (Macaulay2Doc), default value 0,
        When this is greater than zero, information is printed about the
        progress of the computation (See: PrintLevel)
  * Outputs:
      * N, a matrix (Macaulay2Doc), whose entries form a partial
        subalgebra basis

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

The command subalgebraBasis, A is equivalent to the
command generators (Macaulay2Doc), sagbi, A.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)

Ways to use subalgebraBasis :
=============================

  * "subalgebraBasis(List)"
  * "subalgebraBasis(Matrix)"
  * "subalgebraBasis(Subring)"

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

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

SubductionMethod -- Subduction method for the Sagbi algorithm
*************************************************************

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

To subduct the S-pairs in sagbi, one can either use \"Top\" or
\"Engine\". Engine level subduction is generally faster. To view each
subduction taking place inside the Sagbi algorithm, use a high value for
PrintLevel, together with top-level subduction.

See also
========

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * AutoSubduce -- Flag for autosubduction before the Sagbi
    algorithm
  * ReduceNewGenerators -- Flag for reducing new
    generators in Sagbi algorithm
  * StorePending -- Flag for storing the pending list to
    the result of the Sagbi algorithm
  * Strategy -- Update procedure for the Sagbi algorithm
  * SubductionMethod -- Subduction method for the
    Sagbi algorithm
  * Limit -- Degree limit for the Sagbi algorithm
  * AutoSubduceOnPartialCompletion, --
    Subduct sagbi generators at the end of the Sagbi algorithm
  * PrintLevel -- Levels of information displayed during
    Sagbi algorithm

Functions with optional argument named SubductionMethod :
=========================================================

  * "sagbi(...,SubductionMethod=>...)" -- see sagbi, -- Compute a
    subalgebra basis (sagbi basis)
  * "subalgebraBasis(...,SubductionMethod=>...)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators
  * "verifySagbi(...,SubductionMethod=>...)" -- see verifySagbi,
    -- Test if the generators form sagbi basis

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

The object SubductionMethod, is a symbol (Macaulay2Doc).

Subring -- The type of all subrings
***********************************

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

Subring is a type that stores information associated to a subring of a
polynomial ring, such as a set of subring generators and a reference to the
polynomial ring it is contained in. An instance of a Subring is constructed
with the function subring.

Every instance of Subring is guaranteed to have the following keys:

  * ambientRing: The polynomial or quotient ring that contains the subring
    instance's generators.
  * generators: A one-row matrix, the generators of the subring.
  * cache: Contains unspecified information. The contents of the cache may
    effect performance, but should never effect the result of a computation.

See also
========

  * subring -- Constructs a subring of a polynomial ring.
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring
  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * SAGBIBasis -- The type of all sagbi bases

Functions and methods returning an object of class Subring :
============================================================

  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * verifySagbi -- Test if the generators form sagbi basis

Methods that use an object of class Subring :
=============================================

  * ambient(Subring) -- The ambient ring of a
    subring
  * generators(Subring) -- A generating set of
    a subring
  * "groebnerMembershipTest(RingElement,Subring)" -- see
    groebnerMembershipTest, -- Extrinsic method for
    subring membership
  * "isSAGBI(Subring)" -- see isSAGBI, -- Check if the
    generators are a sagbi basis
  * Matrix % Subring -- Remainder modulo a subring
  * net(Subring) -- Short summary of a subring
  * numgens(Subring) -- The number of generators
    of a subring
  * RingElement % Subring -- Remainder modulo a
    subring
  * "sagbi(Subring)" -- see sagbi, -- Compute a subalgebra basis
    (sagbi basis)
  * "sagbiBasis(Subring)" -- see sagbiBasis, -- Constructs a
    computation object from a subring.
  * "subalgebraBasis(Subring)" -- see subalgebraBasis,
    -- Compute subalgebra basis (sagbi basis) generators
  * "verifySagbi(Subring)" -- see verifySagbi, -- Test if
    the generators form sagbi basis

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

The object Subring, is a type (Macaulay2Doc), with
ancestor classes HashTable (Macaulay2Doc), < Thing (Macaulay2Doc).

subring -- Constructs a subring of a polynomial ring.
*****************************************************

Synopsis
========

  * Usage:
        A = subring M
        A = subring L
        A = subring S
  * Inputs:
      * M, a matrix (Macaulay2Doc), a one-row matrix whose
        entries are the generators for the constructed Subring.
      * L, a list (Macaulay2Doc), a list of generators for the
        constructed Subring.
      * S, an instance of the type SAGBIBasis,
  * Outputs:
      * A, an instance of the type Subring,

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

This function serves as the canonical constructor for the Subring,
type.

+-----------------------------------+
|i1 : R = QQ[x];                    |
+-----------------------------------+
|i2 : S = subring {x^4+x^3, x^2+x}  |
|                                   |
|o2 = subring of R with 2 generators|
|                                   |
|o2 : Subring                       |
+-----------------------------------+
|i3 : SB = sagbi S;                 |
+-----------------------------------+
|i4 : gens SB                       |
|                                   |
|o4 = | x2+x x3-x |                 |
|                                   |
|             1       2             |
|o4 : Matrix R  <--- R              |
+-----------------------------------+
|i5 : (x^3+x^2)%S                   |
|                                   |
|o5 = 0                             |
|                                   |
|o5 : R                             |
+-----------------------------------+

See also
========

  * Subring -- The type of all subrings
  * generators(Subring) -- A generating set of
    a subring
  * ambient(Subring) -- The ambient ring of a
    subring
  * numgens(Subring) -- The number of generators
    of a subring
  * net(Subring) -- Short summary of a subring
  * sagbi -- Compute a subalgebra basis (sagbi basis)
  * SAGBIBasis -- The type of all sagbi bases

Ways to use subring :
=====================

  * "subring(List)"
  * "subring(Matrix)"
  * "subring(SAGBIBasis)"

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

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

verifySagbi -- Test if the generators form sagbi basis
******************************************************

Synopsis
========

  * Usage:
        result = verifySagbi S
        result = verifySagbi M
        result = verifySagbi L
  * Inputs:
      * S, an instance of the type Subring,
      * M, a matrix (Macaulay2Doc),
      * L, a list (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Limit => ..., default value 100
      * PrintLevel => ..., default value 0
      * Strategy => ..., default value "Master"
      * SubductionMethod => ..., default value "Top"
  * Outputs:
      * result, a Boolean value (Macaulay2Doc), do the
        generators of S form a sagbi basis.

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

+--------------------------------------------------------+
|i1 : R = QQ[x,y,z];                                     |
+--------------------------------------------------------+
|i2 : L = subring {y*(x-1), y*x^2, y*(x^3+x^2+x+1), y^2};|
+--------------------------------------------------------+
|i3 : verifySagbi L                                      |
|                                                        |
|o3 = true                                               |
+--------------------------------------------------------+
|i4 : M = {x+y+z,x*y+x*z+y*z, x*y*z, (x-y)*(x-z)*(y-z)}; |
+--------------------------------------------------------+
|i5 : verifySagbi M                                      |
|                                                        |
|o5 = false                                              |
+--------------------------------------------------------+
|i6 : N = {x+y+z, x*y+x*z+y*z, x*y*z};                   |
+--------------------------------------------------------+
|i7 : verifySagbi N                                      |
|                                                        |
|o7 = true                                               |
+--------------------------------------------------------+

Ways to use verifySagbi :
=========================

  * "verifySagbi(List)"
  * "verifySagbi(Matrix)"
  * "verifySagbi(Subring)"

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

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