This is TriangularSets.info, produced by Macaulay2, version 1.22

TriangularSets -- triangular decompositions of polynomial ideals
****************************************************************

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

This package allows to decompose polynomial ideals into triangular sets,
+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..h, MonomialOrder=>Lex];                                       |
+-----------------------------------------------------------------------------+
|i2 : I = ideal {a*d - b*c, c*f - d*e, e*h - f*g};                            |
|                                                                             |
|o2 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i3 : triangularize I                                                         |
|                                                                             |
|o3 = {{c, d, e, f}, {a*d - b*c, c*f - d*e, g, h} / {d, f}, {b, d, f, h}, {c, |
|     ------------------------------------------------------------------------|
|     d, g, h}, {a*d - b*c, e, f} / d, {a*d - b*c, c*f - d*e, e*h - f*g} / {d,|
|     ------------------------------------------------------------------------|
|     f, h}, {c, d, e*h - f*g} / h, {c, d, f, h}, {b, d, e, f}}               |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

The method triangularize, is implemented in M2 only for
monomial and binomial ideals. For the general case we interface to Maple.

This package also provides methods for manipulating triangular sets:
  * dim(TriaSystem) -- dimension of a triangular
    set
  * saturate(TriaSystem) -- saturated ideal of
    a triangular system
  * isRegularChain(TriaSystem) -- whether a triangular
    set is a regular chain
  * isStronglyNormalized(TriaSystem) -- whether a
    triangular set is strongly normalized
  * RingElement % TriaSystem, --
    pseudo-remainder by a triangular set
  * resultant(RingElement,TriaSystem) (missing documentation)

References
==========

  * P. Aubry, D. Lazard, M. Moreno Maza (1999), "On the theories of triangular
    sets", in "Journal of Symbolic Computation", 28(1):105-–124
  * E. Hubert (2003), "Notes on triangular sets and triangulation-decomposition
    algorithms I: Polynomial systems", in "Springer"
  * M. Kalkbrener (1993), "A generalized Euclidean algorithm for computing
    triangular representations of algebraic varieties", in "Journal of Symbolic
    Computation", 15(2):143-–167
  * D. Lazard (1992), "Solving zero-dimensional algebraic systems", in "Journal
    of Symbolic Computation", 13(2):117-–131
  * D. Wang (2001), "Elimination methods", in "Springer Science & Business
    Media"

Author
======

  * Diego Cifuentes (see http://www.mit.edu/~diegcif ) <diegcif@mit.edu>

Version
=======

This documentation describes version 0.1 of TriangularSets.

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

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

Exports
=======

  * Types
      * TriaSystem -- a triangular system
  * Functions and commands
      * checkInterface -- whether the Maple interface is
        working (for developers)
      * checkTriangularize -- tests method
        "triangularize" (for developers)
      * freeVariables -- free variables of a triangular
        set
      * gbList -- list of generators of a Groebner basis
      * ineqs -- inequations of a triangular system
      * initial -- initial of a polynomial
      * isPrimeSimple -- simple primality test of
        triangular systems
      * isRegularChain -- whether a triangular set is a
        regular chain
      * isStronglyNormalized -- whether a
        triangular set is strongly normalized
      * minimalObjects -- minimal elements in a partial
        order
      * mvar -- main variable of a polynomial
      * triangularize -- triangular decomposition of
        polynomial systems
      * triangularizeBatch -- triangularize a batch
        of polynomial systems
      * triaSystem -- a triangular system
  * Methods
      * degree(TriaSystem) -- product of the
        degrees in a triangular set
      * "codim(TriaSystem)" -- see dim(TriaSystem),
        -- dimension of a triangular set
      * dim(TriaSystem) -- dimension of a
        triangular set
      * "freeVariables(TriaSystem)" -- see freeVariables,
        -- free variables of a triangular set
      * generators(TriaSystem) -- equations
        of a triangular system
      * "ineqs(TriaSystem)" -- see ineqs, -- inequations of a
        triangular system
      * "initial(RingElement)" -- see initial, -- initial of a
        polynomial
      * "initial(TriaSystem)" -- see initial, -- initial of a
        polynomial
      * "isPrimeSimple(TriaSystem)" -- see isPrimeSimple,
        -- simple primality test of triangular systems
      * "isRegularChain(TriaSystem)" -- see isRegularChain,
        -- whether a triangular set is a regular chain
      * "isStronglyNormalized(TriaSystem)" -- see isStronglyNormalized,
        -- whether a triangular set is strongly
        normalized
      * "mvar(RingElement)" -- see mvar, -- main variable of a
        polynomial
      * pseudoRemainder(RingElement,RingElement,RingElement),
        --
        pseudo-remainder
      * resultant(RingElement,TriaSystem)
        -- iterated resultant by a
        triangular set
      * "pseudoRemainder(RingElement,TriaSystem)" -- see RingElement % TriaSystem,
        -- pseudo-remainder by a
        triangular set
      * RingElement % TriaSystem, --
        pseudo-remainder by a triangular set
      * RingMap TriaSystem -- apply ring map to a
        triangular system
      * saturate(TriaSystem) -- saturated
        ideal of a triangular system
      * "triangularize(Ideal)" -- see triangularize, --
        triangular decomposition of polynomial systems
      * "triangularize(MonomialIdeal)" -- see triangularize,
        -- triangular decomposition of polynomial systems
      * "triangularize(Ring,List)" -- see triangularize,
        -- triangular decomposition of polynomial systems
      * "triangularize(Ring,List,List)" -- see triangularize,
        -- triangular decomposition of polynomial systems
      * "net(TriaSystem)" -- see TriaSystem, -- a triangular
        system
      * "triaSystem(Ring,List)" -- see triaSystem, -- a
        triangular system
      * "triaSystem(Ring,List,List)" -- see triaSystem, -- a
        triangular system
  * Symbols
      * TriangularDecompAlgorithm -- possible
        values: "Monomial", "Binomial", "Maple", "Epsilon"

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

The object TriangularSets, is a package (Macaulay2Doc).

checkInterface -- whether the Maple interface is working (for developers)
*************************************************************************

Synopsis
========

  * Usage:
        checkInterface i
  * Inputs:
      * i, a string (Macaulay2Doc), either "Maple" or "Epsilon"

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

This function tests whether the interface to Maple (or Epsilon) is working.

See also
========

  * MapleInterface -- Interface to Maple.

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

The object checkInterface, is a function closure (Macaulay2Doc).

checkTriangularize -- tests method "triangularize" (for developers)
*******************************************************************

Synopsis
========

  * Usage:
        checkTriangularize alg
  * Inputs:
      * alg, a string (Macaulay2Doc), either "Binomial" or
        "Maple" or "Epsilon"

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

This function tests that the method triangularize works properly using a given
algorithm.

See also
========

  * triangularize -- triangular decomposition of
    polynomial systems
  * TriangularDecompAlgorithm -- possible
    values: "Monomial", "Binomial", "Maple", "Epsilon"

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

The object checkTriangularize, is a function closure (Macaulay2Doc).

degree(TriaSystem) -- product of the degrees in a triangular set
****************************************************************

Synopsis
========

  * Function: degree (Macaulay2Doc),
  * Usage:
        degree T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * an integer (Macaulay2Doc), product of the main degrees of the
        polynomials in T

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

This method returns the product of degrees of the polynomial in $T$ (the degree
in the main variables). In the zero-dimensional case, this agrees
with degree of the saturated ideal, of $T$.

+----------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex];   |
+----------------------------------------------------+
|i2 : F = {a^2*d - b, c*f*h - d*e, e^3*h - f*g};     |
+----------------------------------------------------+
|i3 : T = triaSystem(R,F)                            |
|                                                    |
|       2                     3                      |
|o3 = {a d - b, c*f*h - d*e, e h - f*g} / {d, f*h, h}|
|                                                    |
|o3 : TriaSystem                                     |
+----------------------------------------------------+
|i4 : degree T                                       |
|                                                    |
|o4 = 6                                              |
+----------------------------------------------------+
|i5 : for f in F list degree(mvar f, f)              |
|                                                    |
|o5 = {2, 1, 3}                                      |
|                                                    |
|o5 : List                                           |
+----------------------------------------------------+

Caveat
======

It is assumed that the triangular set is a regular chain

See also
========

  * TriaSystem -- a triangular system
  * saturate(TriaSystem) -- saturated ideal of
    a triangular system

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

  * degree(TriaSystem) -- product of the degrees
    in a triangular set

dim(TriaSystem) -- dimension of a triangular set
************************************************

Synopsis
========

  * Function: dim (Macaulay2Doc),
  * Usage:
        dim T
        codim T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * an integer (Macaulay2Doc), dimension of the zero set of T

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

This method computes the dimension of the zero set of a triangular system

+--------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex]; |
+--------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};       |
+--------------------------------------------------+
|i3 : T = triaSystem(R,F)                          |
|                                                  |
|o3 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o3 : TriaSystem                                   |
+--------------------------------------------------+
|i4 : dim T                                        |
|                                                  |
|o4 = 5                                            |
+--------------------------------------------------+

Caveat
======

It is assumed that the triangular set is a regular chain

See also
========

  * TriaSystem -- a triangular system
  * isRegularChain -- whether a triangular set is a
    regular chain

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

  * dim(TriaSystem) -- dimension of a triangular
    set

freeVariables -- free variables of a triangular set
***************************************************

Synopsis
========

  * Usage:
        freeVariables T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a list (Macaulay2Doc), of free variables of T

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

The free variables of $T$ are the ones that do not appear as the main variable,
of a polynomial in $T$.

+--------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex]; |
+--------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};       |
+--------------------------------------------------+
|i3 : H = {d, f, h};                               |
+--------------------------------------------------+
|i4 : T = triaSystem(R,F,H)                        |
|                                                  |
|o4 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o4 : TriaSystem                                   |
+--------------------------------------------------+
|i5 : freeVariables T                              |
|                                                  |
|o5 = {b, d, f, g, h}                              |
|                                                  |
|o5 : List                                         |
+--------------------------------------------------+

See also
========

  * initial -- initial of a polynomial

Ways to use freeVariables :
===========================

  * "freeVariables(TriaSystem)"

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

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

gbList -- list of generators of a Groebner basis
************************************************

Synopsis
========

  * Usage:
        gbList I
  * Inputs:
      * I, an ideal (Macaulay2Doc),
  * Outputs:
      * a list (Macaulay2Doc),

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

This is a shortcut for flatten entries gens gb.

+--------------------------------------------+
|i1 : R = QQ[a..d];                          |
+--------------------------------------------+
|i2 : I = ideal(a^3-b^2*c, b*c^2-c*d^2, c^3) |
|                                            |
|             3    2      2      2   3       |
|o2 = ideal (a  - b c, b*c  - c*d , c )      |
|                                            |
|o2 : Ideal of R                             |
+--------------------------------------------+
|i3 : gbList I                               |
|                                            |
|       3     2      2   3    2    2 2     4 |
|o3 = {c , b*c  - c*d , a  - b c, c d , c*d }|
|                                            |
|o3 : List                                   |
+--------------------------------------------+

See also
========

  * gb (Macaulay2Doc) -- compute a Gröbner basis

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

The object gbList, is a function closure (Macaulay2Doc).

generators(TriaSystem) -- equations of a triangular system
**********************************************************

Synopsis
========

  * Function: generators (Macaulay2Doc),
  * Usage:
        gens T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Optional inputs (Macaulay2Doc),:
      * CoefficientRing (Macaulay2Doc), => ...,
        default value null, null
  * Outputs:
      * a list (Macaulay2Doc), of generators of T

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

+--------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex]; |
+--------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};       |
+--------------------------------------------------+
|i3 : T = triaSystem(R,F)                          |
|                                                  |
|o3 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o3 : TriaSystem                                   |
+--------------------------------------------------+
|i4 : gens T                                       |
|                                                  |
|o4 = {a*d - b*c, c*f - d*e, e*h - f*g}            |
|                                                  |
|o4 : List                                         |
+--------------------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * ineqs -- inequations of a triangular system

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

  * generators(TriaSystem) -- equations of a
    triangular system

ineqs -- inequations of a triangular system
*******************************************

Synopsis
========

  * Usage:
        ineqs T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a list (Macaulay2Doc), of inequations of T

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

+--------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex]; |
+--------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};       |
+--------------------------------------------------+
|i3 : T = triaSystem(R,F)                          |
|                                                  |
|o3 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o3 : TriaSystem                                   |
+--------------------------------------------------+
|i4 : ineqs T                                      |
|                                                  |
|o4 = {d, f, h}                                    |
|                                                  |
|o4 : List                                         |
+--------------------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * generators(TriaSystem) -- equations of a
    triangular system

Ways to use ineqs :
===================

  * "ineqs(TriaSystem)"

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

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

initial -- initial of a polynomial
**********************************

Synopsis
========

  * Usage:
        initial f
        initial(x,f)
  * Inputs:
      * f, a ring element (Macaulay2Doc),
  * Outputs:
      * h, a ring element (Macaulay2Doc), the initial of f

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

Returns the initial of a polynomial. The initial of a polynomial $f$ is the
leading coefficient of $f$ viewed as a univariate polynomial in its main variable.

+----------------------------------------------------------+
|i1 : R = QQ[x_0..x_3, MonomialOrder=>Lex];                |
+----------------------------------------------------------+
|i2 : f = x_1^2*(x_2*x_3+2*x_3) + x_1*(x_2^2-1) + (x_2-x_3)|
|                                                          |
|      2         2        2                                |
|o2 = x x x  + 2x x  + x x  - x  + x  - x                  |
|      1 2 3     1 3    1 2    1    2    3                 |
|                                                          |
|o2 : R                                                    |
+----------------------------------------------------------+
|i3 : initial f                                            |
|                                                          |
|o3 = x x  + 2x                                            |
|      2 3     3                                           |
|                                                          |
|o3 : R                                                    |
+----------------------------------------------------------+

See also
========

  * mvar -- main variable of a polynomial
  * pseudoRemainder(RingElement,RingElement,RingElement) (missing
    documentation)

Ways to use initial :
=====================

  * "initial(RingElement)"
  * "initial(TriaSystem)"
  * initial(List) (missing documentation)
  * initial(RingElement,RingElement) (missing documentation)

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

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

isPrimeSimple -- simple primality test of triangular systems
************************************************************

Synopsis
========

  * Usage:
        isPrimeSimple(T)
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a Boolean value (Macaulay2Doc), if the test is positive
        then sat(T) is prime; otherwise, it may or may not be prime

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

Let $T = (t_1,t_2,\cdots,t_k)$ be a triangular set (i.e., their main variables,
are distinct). This method verifies if the following
properties hold:

(i) the main degree of $t_i$ is one for $i=1,\dots,k-1$,

(ii) $t_k$ is an irreducible polynomial.

If these properties hold then the saturated ideal,
of $T$ is a prime ideal.

+--------------------------------------+
|i1 : R = QQ[x,y,z,MonomialOrder=>Lex];|
+--------------------------------------+
|i2 : F = {x*y^2 - y*z, y^3 + z^2};    |
+--------------------------------------+
|i3 : T = triaSystem(R,F,{y});         |
+--------------------------------------+
|i4 : isPrimeSimple(T)                 |
|                                      |
|o4 = true                             |
+--------------------------------------+
|i5 : I = saturate T                   |
|                                      |
|                   2            2     |
|o5 = ideal (x*z + y , x*y - z, x  + y)|
|                                      |
|o5 : Ideal of R                       |
+--------------------------------------+
|i6 : isPrime I                        |
|                                      |
|o6 = true                             |
+--------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * saturate(TriaSystem) -- saturated ideal of
    a triangular system

Ways to use isPrimeSimple :
===========================

  * "isPrimeSimple(TriaSystem)"

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

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

isRegularChain -- whether a triangular set is a regular chain
*************************************************************

Synopsis
========

  * Usage:
        isRegularChain(T)
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a Boolean value (Macaulay2Doc), true if T is a regular
        chain, and false otherwise

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

Let $T = (t_1,t_2,\cdots,t_k)$ be a triangular set (i.e., their main variables,
are distinct), and let $h$ be the product of its
initials. $T$ is a regular chain if the iterated resultant,
is nonzero: $resultant(h,T)\neq 0$.

+--------------------------------------+
|i1 : R = QQ[x,y,z,MonomialOrder=>Lex];|
+--------------------------------------+
|i2 : F = {x*y - y*z, y^2 - z^2};      |
+--------------------------------------+
|i3 : T = triaSystem(R,F,{y});         |
+--------------------------------------+
|i4 : isRegularChain(T)                |
|                                      |
|o4 = true                             |
+--------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * initial(TriaSystem) -- initial of a polynomial
  * resultant(RingElement,TriaSystem) (missing documentation)

Ways to use isRegularChain :
============================

  * "isRegularChain(TriaSystem)"

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

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

isStronglyNormalized -- whether a triangular set is strongly normalized
***********************************************************************

Synopsis
========

  * Usage:
        isStronglyNormalized(T)
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a Boolean value (Macaulay2Doc), true if T is strongly
        normalized, and false otherwise

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

Let $T = (t_1,t_2,\cdots,t_k)$ be a triangular set (i.e., their main variables,
are distinct). $T$ is strongly normalized if the
initial, of each $t_i$ only involves free variables.

+----------------------------------------+
|i1 : R = QQ[x,y,t,s,MonomialOrder=>Lex];|
+----------------------------------------+
|i2 : F = {x + y^2 - t, t^2 -s};         |
+----------------------------------------+
|i3 : T = triaSystem(R,F,{});            |
+----------------------------------------+
|i4 : isStronglyNormalized(T)            |
|                                        |
|o4 = true                               |
+----------------------------------------+
+--------------------------------------+
|i5 : R = QQ[x,y,z,MonomialOrder=>Lex];|
+--------------------------------------+
|i6 : F = {x*y - y*z, y^2 - z^2};      |
+--------------------------------------+
|i7 : T = triaSystem(R,F,{y});         |
+--------------------------------------+
|i8 : isStronglyNormalized(T)          |
|                                      |
|o8 = false                            |
+--------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * initial(TriaSystem) -- initial of a polynomial
  * freeVariables -- free variables of a triangular set

Ways to use isStronglyNormalized :
==================================

  * "isStronglyNormalized(TriaSystem)"

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

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

minimalObjects -- minimal elements in a partial order
*****************************************************

Synopsis
========

  * Usage:
        minimalObjects(objs, cmp)
  * Inputs:
      * objs, a visible list (Macaulay2Doc), list of objects
      * cmp, a function (Macaulay2Doc), comparison function
  * Outputs:
      * a hash table (Macaulay2Doc), indicating the minimal
        elements

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

The comparison function cmp should take values in $\{-1,0,1\}$ as follows:

if $a>b$ then cmp(a,b) = 1,

if $a<b$ then cmp(a,b) = -1,

if $a,b$ are incomparable then cmp(a,b) = 0,

cmp(a,a) can be either -1 or 1.

As an example, consider the poset of divisors.

+-------------------------------------------------------------------------+
|i1 : L = 2..20                                                           |
|                                                                         |
|o1 = (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)|
|                                                                         |
|o1 : Sequence                                                            |
+-------------------------------------------------------------------------+
|i2 : cmp = (i,j) -> if i%j==0 then 1 else if j%i==0 then -1 else 0;      |
+-------------------------------------------------------------------------+
|i3 : prime = minimalObjects(L, cmp);                                     |
+-------------------------------------------------------------------------+
|i4 : select(L, i -> prime#i)                                             |
|                                                                         |
|o4 = (2, 3, 5, 7, 11, 13, 17, 19)                                        |
|                                                                         |
|o4 : Sequence                                                            |
+-------------------------------------------------------------------------+

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

The object minimalObjects, is a function closure (Macaulay2Doc).

mvar -- main variable of a polynomial
*************************************

Synopsis
========

  * Usage:
        mvar f
  * Inputs:
      * f, a ring element (Macaulay2Doc),
  * Outputs:
      * a ring element (Macaulay2Doc), the main variable of
        f

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

Returns the main variable of a polynomial $f$, i.e., the largest variable that
appears in $f$.

+----------------------------------------------------------+
|i1 : R = QQ[x_0..x_3, MonomialOrder=>Lex];                |
+----------------------------------------------------------+
|i2 : f = x_1^2*(x_2*x_3+2*x_3) + x_1*(x_2^2-1) + (x_2-x_3)|
|                                                          |
|      2         2        2                                |
|o2 = x x x  + 2x x  + x x  - x  + x  - x                  |
|      1 2 3     1 3    1 2    1    2    3                 |
|                                                          |
|o2 : R                                                    |
+----------------------------------------------------------+
|i3 : mvar f                                               |
|                                                          |
|o3 = x                                                    |
|      1                                                   |
|                                                          |
|o3 : R                                                    |
+----------------------------------------------------------+

See also
========

  * initial -- initial of a polynomial

Ways to use mvar :
==================

  * "mvar(RingElement)"

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

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

pseudoRemainder(RingElement,RingElement,RingElement) -- pseudo-remainder
************************************************************************

Synopsis
========

  * Function: pseudoRemainder (Macaulay2Doc),
  * Usage:
        pseudoRemainder(x,f,g)
  * Inputs:
      * x, a ring element (Macaulay2Doc),
      * f, a ring element (Macaulay2Doc),
      * g, a ring element (Macaulay2Doc),
  * Outputs:
      * a ring element (Macaulay2Doc), pseudo-remainder of f
        by g with respect to x

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

Returns the pseudo-remainder of $f$ by $g$, viewed as univariate polynomials in
x.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x,y];                                                            |
+-----------------------------------------------------------------------------+
|i2 : f = x^4                                                                 |
|                                                                             |
|      4                                                                      |
|o2 = x                                                                       |
|                                                                             |
|o2 : R                                                                       |
+-----------------------------------------------------------------------------+
|i3 : g = x^2*y + 13*x^2*y^4 +x*y^2-3*x - 1                                   |
|                                                                             |
|        2 4    2       2                                                     |
|o3 = 13x y  + x y + x*y  - 3x - 1                                            |
|                                                                             |
|o3 : R                                                                       |
+-----------------------------------------------------------------------------+
|i4 : pseudoRemainder(x,f,g)                                                  |
|                                                                             |
|        27    6    87    4     2    3    14  4    27    2     6         6  2 |
|o4 = - ----x*y  + ----x*y  - ----x*y  + ----y  - ----x*y  + ----x*y - ----y  |
|       2197       2197       2197       2197     2197       2197      2197   |
|     ------------------------------------------------------------------------|
|        27       1       9                                                   |
|     + ----x + ----y + ----                                                  |
|       2197    2197    2197                                                  |
|                                                                             |
|o4 : R                                                                       |
+-----------------------------------------------------------------------------+
|i5 : pseudoRemainder(y,f,g)                                                  |
|                                                                             |
|      4                                                                      |
|o5 = x                                                                       |
|                                                                             |
|o5 : R                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * pseudoRemainder (Macaulay2Doc) -- compute the
    pseudo-remainder
  * mvar -- main variable of a polynomial
  * initial -- initial of a polynomial
  * pseudoRemainder(RingElement,TriaSystem), --
    pseudo-remainder by a triangular set

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

  * pseudoRemainder(RingElement,RingElement,RingElement),
    --
    pseudo-remainder

resultant(RingElement,TriaSystem) -- iterated resultant by a triangular set
***************************************************************************

Synopsis
========

  * Function: resultant (Elimination),
  * Usage:
        resultant(f,T)
  * Inputs:
      * f, a ring element (Macaulay2Doc),
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a ring element (Macaulay2Doc), iterated resultant of
        f by T

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

Returns the iterated resultant of $f$ by a triangular set $T$. Let $T =
(t_1,t_2,\cdots,t_k)$ where $mvar(t_1)>\cdots>mvar(t_k)$. The resultant of $f$
by $T$ is $$resultant(f,T) =
resultant(\cdots(resultant(resultant(f,t_1),t_2)\cdots,t_k)$$

+----------------------------------------+
|i1 : R = QQ[x,y,t,s,MonomialOrder=>Lex];|
+----------------------------------------+
|i2 : F = {x + y^2 - t, t^2 -s};         |
+----------------------------------------+
|i3 : T = triaSystem(R,F,{});            |
+----------------------------------------+
|i4 : f = x*y*t;                         |
+----------------------------------------+
|i5 : resultant(f,T)                     |
|                                        |
|        6     2 2                       |
|o5 = - y s + y s                        |
|                                        |
|o5 : R                                  |
+----------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * pseudoRemainder(RingElement,TriaSystem), --
    pseudo-remainder by a triangular set

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

  * resultant(RingElement,TriaSystem)
    -- iterated resultant by a
    triangular set

RingElement % TriaSystem -- pseudo-remainder by a triangular set
****************************************************************

Synopsis
========

  * Operator: % (Macaulay2Doc),
  * Usage:
        f % T
        pseudoRemainder(f,T)
  * Inputs:
      * f, a ring element (Macaulay2Doc),
      * T, an instance of the type TriaSystem,
  * Outputs:
      * a ring element (Macaulay2Doc), pseudo-remainder of f
        by T

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

Returns the pseudo-remainder, $prem(f,T)$, of $f$ by a triangular set $T$.

Let $T = (t_1,t_2,\cdots,t_k)$ where $mvar(t_1)>\cdots>mvar(t_k)$. The
pseudo-remainder of $f$ by $T$ is $$prem(f,T) =
prem(\cdots(prem(prem(f,t_1),t_2)\cdots,t_k)$$

Remark:  If $T$ is a regular chain, then $f$ lies in its
saturated ideal, iff $prem(f,T)=0$.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex];                            |
+-----------------------------------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};                                  |
+-----------------------------------------------------------------------------+
|i3 : H = {d, f, h};                                                          |
+-----------------------------------------------------------------------------+
|i4 : T = triaSystem(R,F,H)                                                   |
|                                                                             |
|o4 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}                           |
|                                                                             |
|o4 : TriaSystem                                                              |
+-----------------------------------------------------------------------------+
|i5 : (a*h - b*g) % T                                                         |
|                                                                             |
|o5 = 0                                                                       |
|                                                                             |
|o5 : R                                                                       |
+-----------------------------------------------------------------------------+
|i6 : saturate T                                                              |
|                                                                             |
|o6 = ideal (e*h - f*g, c*h - d*g, c*f - d*e, a*h - b*g, a*f - b*e, a*d - b*c)|
|                                                                             |
|o6 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * pseudoRemainder(RingElement,RingElement,RingElement) (missing
    documentation)
  * saturate(TriaSystem) -- saturated ideal of
    a triangular system

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

  * RingElement % TriaSystem, --
    pseudo-remainder by a triangular set

RingMap TriaSystem -- apply ring map to a triangular system
***********************************************************

Synopsis
========

  * Operator: SPACE (Macaulay2Doc),
  * Usage:
        f T
  * Inputs:
      * f, a ring map (Macaulay2Doc),
      * T, an instance of the type TriaSystem,
  * Outputs:
      * an instance of the type TriaSystem, image of T under
        the ring map f

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

+-----------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex];          |
+-----------------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};                |
+-----------------------------------------------------------+
|i3 : T = triaSystem(R,F)                                   |
|                                                           |
|o3 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}         |
|                                                           |
|o3 : TriaSystem                                            |
+-----------------------------------------------------------+
|i4 : S = QQ[x_0..x_7, MonomialOrder=>Lex];                 |
+-----------------------------------------------------------+
|i5 : f = map(S,R,gens S)                                   |
|                                                           |
|o5 = map (S, R, {x , x , x , x , x , x , x , x })          |
|                  0   1   2   3   4   5   6   7            |
|                                                           |
|o5 : RingMap S <--- R                                      |
+-----------------------------------------------------------+
|i6 : f T                                                   |
|                                                           |
|o6 = {x x  - x x , x x  - x x , x x  - x x } / {x , x , x }|
|       0 3    1 2   2 5    3 4   4 7    5 6      3   5   7 |
|                                                           |
|o6 : TriaSystem                                            |
+-----------------------------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * RingMap RingElement (Macaulay2Doc) -- apply a
    ring map

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

  * RingMap TriaSystem -- apply ring map to a
    triangular system

saturate(TriaSystem) -- saturated ideal of a triangular system
**************************************************************

Synopsis
========

  * Function: saturate (Saturation),
  * Usage:
        saturate T
  * Inputs:
      * T, an instance of the type TriaSystem,
  * Optional inputs (Macaulay2Doc),:
      * BasisElementLimit (Saturation),
        =>
        ..., default value infinity, null
      * DegreeLimit (Saturation),
        => ..., default value {}, null
      * MinimalGenerators (Saturation), => ..., default value
        true, null
      * PairLimit (Saturation),
        => ..., default value infinity, null
      * Strategy (Saturation),
        => ..., default value null, null
  * Outputs:
      * an ideal (Macaulay2Doc), the saturated ideal of T

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

Returns the saturated ideal of a triangular system.

Let $T = (F,H)$ be a triangular system. Denoting $J=ideal(F)$, the saturated
ideal of $T$ is $$sat(T) = J : h^\infty = \{ f: h^k f \in J for some h\in H,
k\in \mathbb{N} \}$$

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex];                            |
+-----------------------------------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};                                  |
+-----------------------------------------------------------------------------+
|i3 : H = {d, f, h};                                                          |
+-----------------------------------------------------------------------------+
|i4 : T = triaSystem(R,F,H)                                                   |
|                                                                             |
|o4 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}                           |
|                                                                             |
|o4 : TriaSystem                                                              |
+-----------------------------------------------------------------------------+
|i5 : saturate T                                                              |
|                                                                             |
|o5 = ideal (e*h - f*g, c*h - d*g, c*f - d*e, a*h - b*g, a*f - b*e, a*d - b*c)|
|                                                                             |
|o5 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * TriaSystem -- a triangular system
  * RingElement % TriaSystem, --
    pseudo-remainder by a triangular set

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

  * saturate(TriaSystem) -- saturated ideal of
    a triangular system

TriangularDecompAlgorithm -- possible values: "Monomial", "Binomial", "Maple", "Epsilon"
****************************************************************************************

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

The package implements triangular decompositions in two restricted cases:

(1) "Monomial" => M2 implementation for monomial ideals

(2) "Binomial" => M2 implementation for binomial ideals

For arbitrary ideals we interface to Maple:

(3) "Maple" => uses library RegularChains (included in Maple)

(4) "Epsilon" => uses Maple's package Epsilon (download from
http://www-polsys.lip6.fr/~wang/epsilon/)

See also
========

  * triangularize -- triangular decomposition of
    polynomial systems

Functions with optional argument named TriangularDecompAlgorithm :
==================================================================

  * "triangularize(...,TriangularDecompAlgorithm=>...)"

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

The object TriangularDecompAlgorithm, is a
symbol (Macaulay2Doc).

triangularize -- triangular decomposition of polynomial systems
***************************************************************

Synopsis
========

  * Usage:
        triangularize(I)
        triangularize(R,F)
        triangularize(R,F,H)
  * Inputs:
      * I, an ideal (Macaulay2Doc),
      * R, a ring (Macaulay2Doc),
      * F, a list (Macaulay2Doc), a list of polynomials
      * H, a list (Macaulay2Doc), a list of polynomials
  * Optional inputs (Macaulay2Doc),:
      * TriangularDecompAlgorithm, => ...,
        default value null, possible values: "Monomial", "Binomial", "Maple",
        "Epsilon"
  * Outputs:
      * a list (Macaulay2Doc), a list of triangular systems

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

Computes a triangular decomposition of a polynomial system. The package
implements algorithms for monomial and binomial sets. For arbitrary systems we
interface to Maple.

A polynomial system is a pair $(F,H)$, where $F\subset k[x]$ is a list of
equations, and and $H\subset k[x]$ is a list of
inequations. The zero set of the system is $$Z(F/H) = \{x : f(x)=
0 for f\in F, h(x)\neq 0 for h\in H\}.$$ A triangular decomposition of $(F,H)$
is a collection of "simpler" polynomial systems $(T_1,U_1),\ldots,(T_r,U_r)$
such that $$Z(F/H) = Z(T_1/U_1)\cup\cdots\cup Z(T_r/U_r).$$ These simpler sets,
called triangular systems, have very nice algorithmic
properties.

As a first example we consider a case without inequations ($H=\emptyset$).

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..h, MonomialOrder=>Lex];                                       |
+-----------------------------------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};                                  |
+-----------------------------------------------------------------------------+
|i3 : TT = triangularize(R,F,{})                                              |
|                                                                             |
|o3 = {{c, d, e, f}, {a*d - b*c, c*f - d*e, g, h} / {d, f}, {b, d, f, h}, {c, |
|     ------------------------------------------------------------------------|
|     d, g, h}, {a*d - b*c, e, f} / d, {a*d - b*c, c*f - d*e, e*h - f*g} / {d,|
|     ------------------------------------------------------------------------|
|     f, h}, {c, d, e*h - f*g} / h, {c, d, f, h}, {b, d, e, f}}               |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : first TT                                                                |
|                                                                             |
|o4 = {c, d, e, f}                                                            |
|                                                                             |
|o4 : TriaSystem                                                              |
+-----------------------------------------------------------------------------+

We now include some inequations.

+-----------------------------------------------------------------------------+
|i5 : H = {b,d};                                                              |
+-----------------------------------------------------------------------------+
|i6 : triangularize(R,F,H)                                                    |
|                                                                             |
|o6 = {{a*d - b*c, c*f - d*e, e*h - f*g} / {b, d, f, h}, {a*d - b*c, e, f} /  |
|     ------------------------------------------------------------------------|
|     {b, d}, {a*d - b*c, c*f - d*e, g, h} / {b, d, f}}                       |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * TriaSystem -- a triangular system

Ways to use triangularize :
===========================

  * "triangularize(Ideal)"
  * "triangularize(MonomialIdeal)"
  * "triangularize(Ring,List)"
  * "triangularize(Ring,List,List)"

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

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

triangularizeBatch -- triangularize a batch of polynomial systems
*****************************************************************

Synopsis
========

  * Usage:
        triangularizeBatch(alg,R,F,H)
  * Inputs:
      * alg, a string (Macaulay2Doc), either "Maple" or "Epsilon"
      * R, a ring (Macaulay2Doc),
      * F, a hash table (Macaulay2Doc), whose values are
        polynomial sets
      * H, a hash table (Macaulay2Doc), whose values are
        polynomial sets
  * Outputs:
      * a hash table (Macaulay2Doc), containing triangular
        decompositions of each system

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

Let $\{F_k: k\in K\}$ and $\{H_k: k\in K\}$ be collections of polynomial sets.
This function computes a triangular decomposition of each of the pairs
$(F_k,H_k)$.

Although triangularizeBatch, is equivalent to calling
triangularize, multiple times, the former is usually
faster since it avoids the cost of starting multiple Maple sessions.

See also
========

  * triangularize -- triangular decomposition of
    polynomial systems

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

The object triangularizeBatch, is a function closure (Macaulay2Doc).

TriaSystem -- a triangular system
*********************************

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

This type represents a triangular system.

A polynomial system is a pair $(F,H)$, where $F\subset k[x]$ is a list of
equations, and and $H\subset k[x]$ is a list of
inequations. The zero set of the system is $$Z(F/H) = \{x : f(x)=
0 for f\in F, h(x)\neq 0 for h\in H\}.$$ A triangular system $(T,U)$ is a
polynomial system that satisfies some additional properties [Wang'01]. The most
basic property, is that the set $T = \{t_1,\ldots,t_m\}$ must be triangular,
i.e., the polynomials $\{t_i\}_i$ have distinct main variables. It
is also usually required that $T$ forms a regular chain.
The set of inequations $U$ often consists of the initials, of
$T$.

Triangular systems have very nice algorithmic properties. In particular, the
zero set of a triangular system $(F,H)$ is always nonempty, and moreover, has
dimension $n-m$. In addition, membership to the saturated ideal,
can be efficiently decided.

Any polynomial system can be decomposed into triangular systems. The method
triangularize, can be used to compute such decomposition.

The constructor of this type is triaSystem.

See also
========

  * triangularize -- triangular decomposition of
    polynomial systems

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

  * RingMap TriaSystem -- apply ring map to a
    triangular system
  * "triaSystem(Ring,List)" -- see triaSystem, -- a
    triangular system
  * "triaSystem(Ring,List,List)" -- see triaSystem, -- a
    triangular system

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

  * degree(TriaSystem) -- product of the degrees
    in a triangular set
  * "codim(TriaSystem)" -- see dim(TriaSystem), --
    dimension of a triangular set
  * dim(TriaSystem) -- dimension of a triangular
    set
  * "freeVariables(TriaSystem)" -- see freeVariables, --
    free variables of a triangular set
  * generators(TriaSystem) -- equations of a
    triangular system
  * "ineqs(TriaSystem)" -- see ineqs, -- inequations of a
    triangular system
  * "initial(TriaSystem)" -- see initial, -- initial of a
    polynomial
  * "isPrimeSimple(TriaSystem)" -- see isPrimeSimple, --
    simple primality test of triangular systems
  * "isRegularChain(TriaSystem)" -- see isRegularChain,
    -- whether a triangular set is a regular chain
  * "isStronglyNormalized(TriaSystem)" -- see isStronglyNormalized,
    -- whether a triangular set is strongly normalized
  * resultant(RingElement,TriaSystem)
    -- iterated resultant by a
    triangular set
  * "pseudoRemainder(RingElement,TriaSystem)" -- see RingElement % TriaSystem,
    -- pseudo-remainder by a triangular
    set
  * RingElement % TriaSystem, --
    pseudo-remainder by a triangular set
  * saturate(TriaSystem) -- saturated ideal of
    a triangular system
  * "net(TriaSystem)"

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

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

triaSystem -- a triangular system
*********************************

Synopsis
========

  * Usage:
        triaSystem(R,F)
        triaSystem(R,F,H)
  * Inputs:
      * R, a ring (Macaulay2Doc),
      * F, a list (Macaulay2Doc), a list of polynomials
      * H, a list (Macaulay2Doc), a list of polynomials (optional)
  * Outputs:
      * an instance of the type TriaSystem, given by the
        pair (F,H)

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

By default $H$ is chosen to be the set of initials, of $F$.

+--------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e,f,g,h, MonomialOrder=>Lex]; |
+--------------------------------------------------+
|i2 : F = {a*d - b*c, c*f - d*e, e*h - f*g};       |
+--------------------------------------------------+
|i3 : H = {d, f, h};                               |
+--------------------------------------------------+
|i4 : triaSystem(R,F,H)                            |
|                                                  |
|o4 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o4 : TriaSystem                                   |
+--------------------------------------------------+
|i5 : triaSystem(R,F)                              |
|                                                  |
|o5 = {a*d - b*c, c*f - d*e, e*h - f*g} / {d, f, h}|
|                                                  |
|o5 : TriaSystem                                   |
+--------------------------------------------------+

Caveat
======

It is not checked that $(F,H)$ is indeed a triangular system.

See also
========

  * TriaSystem -- a triangular system
  * initial -- initial of a polynomial

Ways to use triaSystem :
========================

  * "triaSystem(Ring,List)"
  * "triaSystem(Ring,List,List)"

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

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