This is MultigradedImplicitization.info, produced by Macaulay2, version 1.24.11

MultigradedImplicitization -- Package for levaraging multigradings to solve implicitization problems
****************************************************************************************************

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

The MultigradedImplicitization package provides methods for computing the
maximal $\mathbb{Z}^k$ grading in which the kernel of a polynomial map $F$ is
homogeneous and exploiting it to find generators of $\ker(F)$. This package is
particularly useful for problems from algebraic statistics which often involve
highly structured maps F which are often naturally homogeneous in a larger
multigrading than the standard $\mathbb{Z}$-multigrading given by total degree.
For more information on this approach see the following:

References:

[1] Cummings, J., & Hollering , B. (2023). Computing Implicitizations of
Multi-Graded Polynomial Maps. arXiv preprint arXiv:2311.07678.

[2] Cummings, J., & Hauenstein, J. (2023). Multi-graded Macaulay Dual Spaces.
arXiv preprint arXiv:2310.11587.

[3] Cummings, J., Hollering, B., & Manon, C. (2024). Invariants for level-1
phylogenetic networks under the cavendar-farris-neyman model. Advances in
Applied Mathematics, 153, 102633.

Authors
=======

  * Joseph Cummings (see https://sites.google.com/view/josephcummingsuky/home )
    <josephcummings03@gmail.com>
  * Benjamin Hollering (see https://sites.google.com/view/benhollering )
    <benhollering@gmail.com>

Version
=======

This documentation describes version 1.0 of MultigradedImplicitization.

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

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

Exports
=======

  * Functions and commands
      * componentOfKernel -- Finds all minimal
        generators of a given degree in the kernel of a ring map
      * componentsOfKernel -- Finds all minimal
        generators up to a given total degree in the kernel of a ring map
      * maxGrading -- computes the maximal $\mathbb{Z}^k$
        grading such that $\ker(F)$ is homogeneous
      * trimBasisInDegree -- Finds a basis for the
        homogeneous component of a graded ring but removes basis elements which
        correspond to previously computed generators.
  * Methods
      * "componentOfKernel(List,Ring,RingMap)" -- see componentOfKernel,
        -- Finds all minimal generators of a given degree in
        the kernel of a ring map
      * "componentOfKernel(List,Ring,RingMap,Matrix)" -- see
        componentOfKernel, -- Finds all minimal generators
        of a given degree in the kernel of a ring map
      * "componentOfKernel(List,Ring,RingMap,MutableHashTable)" -- see
        componentOfKernel, -- Finds all minimal generators
        of a given degree in the kernel of a ring map
      * "componentsOfKernel(Number,RingMap)" -- see componentsOfKernel,
        -- Finds all minimal generators up to a given total
        degree in the kernel of a ring map
      * "maxGrading(RingMap)" -- see maxGrading, -- computes
        the maximal $\mathbb{Z}^k$ grading such that $\ker(F)$ is homogeneous
      * "trimBasisInDegree(List,Ring,List,MutableHashTable)" -- see
        trimBasisInDegree, -- Finds a basis for the
        homogeneous component of a graded ring but removes basis elements which
        correspond to previously computed generators.
      * "trimBasisInDegree(List,Ring,MutableHashTable)" -- see
        trimBasisInDegree, -- Finds a basis for the
        homogeneous component of a graded ring but removes basis elements which
        correspond to previously computed generators.
  * Symbols
      * Grading -- optional argument
      * PreviousGens -- optional argument
      * ReturnTargetGrading -- optional argument
      * UseMatroidSpeedup -- optional argument

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

The object MultigradedImplicitization, is a package (Macaulay2Doc).

componentOfKernel -- Finds all minimal generators of a given degree in the kernel of a ring map
***********************************************************************************************

Synopsis
========

  * Usage:
        componentOfKernel(deg, dom, F, M)
        componentOfKernel(deg, dom, F, B)
        componentOfKernel(deg, dom, F)
  * Inputs:
      * deg, a list (Macaulay2Doc), the degree of the homogeneous
        component to compute
      * dom, a ring (Macaulay2Doc), a graded ring which is the
        source of a homogeneous ring map $F$
      * F, a ring map (Macaulay2Doc), a map whose kernel is
        homogeneous in the grading of dom
      * M, a matrix (Macaulay2Doc), a monomial basis for the
        homogeneous component of deg with degree deg
      * B, a mutable hash table (Macaulay2Doc), a
        mutable hashtable which contains all bases of homogeneous components
        which correspond to lower total degrees than deg
  * Optional inputs (Macaulay2Doc),:
      * PreviousGens => a list (Macaulay2Doc), default value {}, a
        list of generators of the kernel which have lower total degree
  * Outputs:
      * a matrix (Macaulay2Doc), A list of minimal generators for
        $\ker(F)$ which are in the homogeneous component of degree deg

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

Computes all minimal generators of $\ker(F)$ which are in the homogeneous
component of degree deg

+-----------------------------------------------------------------------------+
|i1 : A = matrix {{1,1,1,0,0,0}, {0,0,0,1,1,1}, {1,0,0,1,0,0}, {0,1,0,0,1,0}, |
|                                                                             |
|o1 = | 1 1 1 0 0 0 |                                                         |
|     | 0 0 0 1 1 1 |                                                         |
|     | 1 0 0 1 0 0 |                                                         |
|     | 0 1 0 0 1 0 |                                                         |
|     | 0 0 1 0 0 1 |                                                         |
|                                                                             |
|              5       6                                                      |
|o1 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|{0,0,1,0,0,1}}                                                               |
+-----------------------------------------------------------------------------+
|i2 : R = QQ[x_(1,1)..x_(2,3)];                                               |
+-----------------------------------------------------------------------------+
|i3 : S = QQ[t_1..t_2, s_1..s_3];                                             |
+-----------------------------------------------------------------------------+
|i4 : F = map(S, R, {t_1*s_1, t_1*s_2, t_1*s_3, t_2*s_1, t_2*s_2, t_2*s_3})   |
|                                                                             |
|o4 = map (S, R, {t s , t s , t s , t s , t s , t s })                        |
|                  1 1   1 2   1 3   2 1   2 2   2 3                          |
|                                                                             |
|o4 : RingMap S <-- R                                                         |
+-----------------------------------------------------------------------------+
|i5 : dom = newRing(R, Degrees => A);                                         |
+-----------------------------------------------------------------------------+
|i6 : componentOfKernel({1,1,0,1,1}, dom, F)                                  |
|                                                                             |
|o6 = {x   x    - x   x   }                                                   |
|       1,3 2,2    1,2 2,3                                                    |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+

The option PreviousGens can be used to specify a set of previously computed
generators. In the case that a monomial basis or hash table of monomial bases
is not given then trimBasisInDegree, will be used to
compute a monomial basis and PreviousGens will be used to trim this basis.

Ways to use componentOfKernel:
==============================

  * "componentOfKernel(List,Ring,RingMap)"
  * "componentOfKernel(List,Ring,RingMap,Matrix)"
  * "componentOfKernel(List,Ring,RingMap,MutableHashTable)"

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

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

componentsOfKernel -- Finds all minimal generators up to a given total degree in the kernel of a ring map
*********************************************************************************************************

Synopsis
========

  * Usage:
        componentsOfKernel(d, F)
  * Inputs:
      * d, a list (Macaulay2Doc), the total degree at which to stop
        computing generators
      * F, a ring map (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Grading => a matrix (Macaulay2Doc), default value null, a
        matrix whose columns give a homogeneous multigrading on $\ker(F)$
      * UseMatroidSpeedup => a Boolean value (Macaulay2Doc),
        default value true, if true, then the jacobian of $F$ is used to detect
        if it is possible for kernel element to exist in a homogeneous
        component. If the jacobian does not drop rank, then that component
        cannot contain kernel generators and is skipped.
  * Outputs:
      * a mutable hash table (Macaulay2Doc), A mutable
        hashtable whose keys correspond to all homogeneous components of
        $\ker(F)$ and values correspond to generators in $\ker(F)$ with those
        components

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

Computes all minimal generators of $\ker(F)$ which are of total degree at most
d.

+-----------------------------------------------------------------------------+
|i1 : A = matrix {{1,1,1,0,0,0}, {0,0,0,1,1,1}, {1,0,0,1,0,0}, {0,1,0,0,1,0}, |
|                                                                             |
|o1 = | 1 1 1 0 0 0 |                                                         |
|     | 0 0 0 1 1 1 |                                                         |
|     | 1 0 0 1 0 0 |                                                         |
|     | 0 1 0 0 1 0 |                                                         |
|     | 0 0 1 0 0 1 |                                                         |
|                                                                             |
|              5       6                                                      |
|o1 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|{0,0,1,0,0,1}}                                                               |
+-----------------------------------------------------------------------------+
|i2 : R = QQ[x_(1,1)..x_(2,3)];                                               |
+-----------------------------------------------------------------------------+
|i3 : S = QQ[t_1..t_2, s_1..s_3];                                             |
+-----------------------------------------------------------------------------+
|i4 : F = map(S, R, {t_1*s_1, t_1*s_2, t_1*s_3, t_2*s_1, t_2*s_2, t_2*s_3})   |
|                                                                             |
|o4 = map (S, R, {t s , t s , t s , t s , t s , t s })                        |
|                  1 1   1 2   1 3   2 1   2 2   2 3                          |
|                                                                             |
|o4 : RingMap S <-- R                                                         |
+-----------------------------------------------------------------------------+
|i5 : peek componentsOfKernel(2, F)                                           |
|                                                                             |
|o5 = MutableHashTable{{0, 1, 0, 0, 1} => {}                   }              |
|                      {0, 1, 0, 1, 0} => {}                                  |
|                      {0, 1, 1, 0, 0} => {}                                  |
|                      {0, 2, 0, 0, 2} => {}                                  |
|                      {0, 2, 0, 1, 1} => {}                                  |
|                      {0, 2, 0, 2, 0} => {}                                  |
|                      {0, 2, 1, 0, 1} => {}                                  |
|                      {0, 2, 1, 1, 0} => {}                                  |
|                      {0, 2, 2, 0, 0} => {}                                  |
|                      {1, 0, 0, 0, 1} => {}                                  |
|                      {1, 0, 0, 1, 0} => {}                                  |
|                      {1, 0, 1, 0, 0} => {}                                  |
|                      {1, 1, 0, 0, 2} => {}                                  |
|                      {1, 1, 0, 1, 1} => {x   x    - x   x   }               |
|                                           1,3 2,2    1,2 2,3                |
|                      {1, 1, 0, 2, 0} => {}                                  |
|                      {1, 1, 1, 0, 1} => {x   x    - x   x   }               |
|                                           1,3 2,1    1,1 2,3                |
|                      {1, 1, 1, 1, 0} => {x   x    - x   x   }               |
|                                           1,2 2,1    1,1 2,2                |
|                      {1, 1, 2, 0, 0} => {}                                  |
|                      {2, 0, 0, 0, 2} => {}                                  |
|                      {2, 0, 0, 1, 1} => {}                                  |
|                      {2, 0, 0, 2, 0} => {}                                  |
|                      {2, 0, 1, 0, 1} => {}                                  |
|                      {2, 0, 1, 1, 0} => {}                                  |
|                      {2, 0, 2, 0, 0} => {}                                  |
+-----------------------------------------------------------------------------+

If a grading in which $\ker(F)$ is homogeneous is already known or a specific
grading is desired then the option Grading can be used to specify this. In this
case the columns of the matrix Grading are automatically used to grade the
source of $F$.

Ways to use componentsOfKernel:
===============================

  * "componentsOfKernel(Number,RingMap)"

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

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

Grading -- optional argument
****************************

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

The option Grading is a matrix (Macaulay2Doc), that allows one to
specify a specific multigrading in which a polynomial map is homogeneous in.

Functions with optional argument named Grading:
===============================================

  * "componentsOfKernel(...,Grading=>...)" -- see componentsOfKernel,
    -- Finds all minimal generators up to a given total
    degree in the kernel of a ring map

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

The object Grading, is a symbol (Macaulay2Doc).

maxGrading -- computes the maximal $\mathbb{Z}^k$ grading such that $\ker(F)$ is homogeneous
********************************************************************************************

Synopsis
========

  * Usage:
        maxGrading(F)
  * Inputs:
      * F, a ring map (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * ReturnTargetGrading => a Boolean value (Macaulay2Doc),
        default value false, a boolean which encodes whether or not to also
        return the grading on target(F) which induces the grading on $\ker(F)$
  * Outputs:
      * a matrix (Macaulay2Doc), the maximal $\mathbb{Z}^k$
        grading in which $\ker(F)$ is homogeneous

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

Computes the maximal $\mathbb{Z}^k$ grading such that the $\ker(F)$ is
homogeneous. The columns of the output matrix are the degrees of the
corresponding variables in source(F). For example, the snippet below shows that
the maximal grading of a toric ideal is exactly the integer matrix which
encodes the monomial map parameterizing the ideal.

+-----------------------------------------------------------------------------+
|i1 : A = matrix {{1,1,1,0,0,0}, {0,0,0,1,1,1}, {1,0,0,1,0,0}, {0,1,0,0,1,0}, |
|                                                                             |
|o1 = | 1 1 1 0 0 0 |                                                         |
|     | 0 0 0 1 1 1 |                                                         |
|     | 1 0 0 1 0 0 |                                                         |
|     | 0 1 0 0 1 0 |                                                         |
|     | 0 0 1 0 0 1 |                                                         |
|                                                                             |
|              5       6                                                      |
|o1 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|{0,0,1,0,0,1}}                                                               |
+-----------------------------------------------------------------------------+
|i2 : R = QQ[x_(1,1)..x_(2,3)];                                               |
+-----------------------------------------------------------------------------+
|i3 : S = QQ[t_1..t_2, s_1..s_3];                                             |
+-----------------------------------------------------------------------------+
|i4 : F = map(S, R, {t_1*s_1, t_1*s_2, t_1*s_3, t_2*s_1, t_2*s_2, t_2*s_3})   |
|                                                                             |
|o4 = map (S, R, {t s , t s , t s , t s , t s , t s })                        |
|                  1 1   1 2   1 3   2 1   2 2   2 3                          |
|                                                                             |
|o4 : RingMap S <-- R                                                         |
+-----------------------------------------------------------------------------+
|i5 : maxGrading(F)                                                           |
|                                                                             |
|o5 = | 1 1 1 0 0 0 |                                                         |
|     | 0 0 0 1 1 1 |                                                         |
|     | 1 0 0 1 0 0 |                                                         |
|     | 0 1 0 0 1 0 |                                                         |
|     | 0 0 1 0 0 1 |                                                         |
|                                                                             |
|              5       6                                                      |
|o5 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+

The option ReturnTargetGrading returns a matrix which also gives the
corresponding grading on the target ring of $F$ which induces the grading on
$\ker(F)$. This option is false by default.

+-----------------------------------------------+
|i6 : maxGrading(F, ReturnTargetGrading => true)|
|                                               |
|o6 = | 1 1 1 0 0 0 1 0 0 0 0 |                 |
|     | 0 0 0 1 1 1 0 1 0 0 0 |                 |
|     | 1 0 0 1 0 0 0 0 1 0 0 |                 |
|     | 0 1 0 0 1 0 0 0 0 1 0 |                 |
|     | 0 0 1 0 0 1 0 0 0 0 1 |                 |
|                                               |
|              5       11                       |
|o6 : Matrix ZZ  <-- ZZ                         |
+-----------------------------------------------+

Ways to use maxGrading:
=======================

  * "maxGrading(RingMap)"

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

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

PreviousGens -- optional argument
*********************************

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

The option PreviousGens is a list (Macaulay2Doc), of polynomials of
total degree at most $d-1$ which can be used with componentOfKernel,
to trim the monomial basis for that multidegree.

Functions with optional argument named PreviousGens:
====================================================

  * "componentOfKernel(...,PreviousGens=>...)" -- see componentOfKernel,
    -- Finds all minimal generators of a given degree in the
    kernel of a ring map

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

The object PreviousGens, is a symbol (Macaulay2Doc).

ReturnTargetGrading -- optional argument
****************************************

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

The option ReturnTargetGrading is a boolean (Macaulay2Doc), which
can be used with maxGrading. This option is false by
default. If it is set to true then the full grading on the elimination ideal of
a polynomial map $F$ will be returned instead of only returning the part of the
grading which corresponds to the source of $F$.

Functions with optional argument named ReturnTargetGrading:
===========================================================

  * "maxGrading(...,ReturnTargetGrading=>...)" -- see maxGrading,
    -- computes the maximal $\mathbb{Z}^k$ grading such that
    $\ker(F)$ is homogeneous

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

The object ReturnTargetGrading, is a symbol (Macaulay2Doc).

trimBasisInDegree -- Finds a basis for the homogeneous component of a graded ring but removes basis elements which correspond to previously computed generators.
****************************************************************************************************************************************************************

Synopsis
========

  * Usage:
        trimBasisInDegree(deg, dom, G, B)
        trimBasisInDegree(deg, dom, B)
  * Inputs:
      * deg, a list (Macaulay2Doc), the degree of the homogeneous
        component to compute
      * dom, a ring (Macaulay2Doc), a graded ring which is the
        source of a homogeneous ring map $F$
      * G, a list (Macaulay2Doc), a list of previously computed
        generators of $\ker(F)$
      * B, a mutable hash table (Macaulay2Doc), a
        mutable hashtable which contains all bases of homogeneous components
        which correspond to lower total degrees than deg
  * Outputs:
      * a matrix (Macaulay2Doc), A monomial basis for the
        homogeneous component of degree deg of dom with any monomials which
        cannot be involved in new generators of $\ker(F)$ removed.

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

Computes a monomial basis for the homogeneous component of degree deg of the
graded ring dom which is the source of a ring map $F$. Monomials which
correspond to previously computed relations which are in G are automatically
removed since they will not yield new generators in $\ker(F)$ when applying
componentOfKernel, to this basis.

+-----------------------------------------------------------------------------+
|i1 : A = matrix {{1,1,1,0,0,0,0,0,0}, {0,0,0,1,1,1,0,0,0},                   |
|                                                                             |
|              5       9                                                      |
|o1 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|{0,0,0,0,0,0,1,1,1}, {1,0,0,1,0,0,1,0,0}, {0,1,0,0,1,0,0,1,0}};              |
+-----------------------------------------------------------------------------+
|i2 : R = QQ[x_1..x_(numcols A)];                                             |
+-----------------------------------------------------------------------------+
|i3 : S = QQ[t_1..t_(numrows A)];                                             |
+-----------------------------------------------------------------------------+
|i4 : F = map(S, R, apply(numcols(A), i -> S_(flatten entries A_i)));         |
|                                                                             |
|o4 : RingMap S <-- R                                                         |
+-----------------------------------------------------------------------------+
|i5 : dom = newRing(R, Degrees => A);                                         |
+-----------------------------------------------------------------------------+
|i6 : basisHash = new MutableHashTable from apply(gens(dom), i -> degree(i) =>|
|-----------------------------------------------------------------------------|
|i);                                                                          |
+-----------------------------------------------------------------------------+
|i7 : B = basis(2, source F) | basis(3, source F);                            |
|                                                                             |
|             1      210                                                      |
|o7 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i8 : lats = unique apply(flatten entries B, i -> degree(sub(i, dom)));       |
+-----------------------------------------------------------------------------+
|i9 : scan(lats, deg -> basisHash#deg = basis(deg, dom));                     |
+-----------------------------------------------------------------------------+
|i10 : trimBasisInDegree({2,1,0,1,1},  dom, {x_2*x_4-x_1*x_5, x_3*x_4-x_1*x_6,|
|                                                                             |
|o10 = | x_2x_3x_4 |                                                          |
|                                                                             |
|                1        1                                                   |
|o10 : Matrix dom  <-- dom                                                    |
|-----------------------------------------------------------------------------|
|x_3*x_5-x_2*x_6}, basisHash)                                                 |
+-----------------------------------------------------------------------------+

Observe that after trimming we get a smaller monomial basis for this
homogeneous component. The full monomial basis is

+---------------------------------------+
|i11 : basis({2,1,0,1,1}, dom)          |
|                                       |
|o11 = | x_1x_2x_6 x_1x_3x_5 x_2x_3x_4 ||
|                                       |
|                1        3             |
|o11 : Matrix dom  <-- dom              |
+---------------------------------------+

Ways to use trimBasisInDegree:
==============================

  * "trimBasisInDegree(List,Ring,List,MutableHashTable)"
  * "trimBasisInDegree(List,Ring,MutableHashTable)"

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

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

UseMatroidSpeedup -- optional argument
**************************************

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

The option UseMatroidSpeedup is a boolean that allows one to specify if the
matroid given by the jacobian should be used to automatically skip components.
This option is true by default. If it is set to false, then every homogeneous
component will be checked, even if it is impossible for a polynomial with the
necessary support to belong to the kernel. For very small examples, it may be
slightly faster to set this to false.

Functions with optional argument named UseMatroidSpeedup:
=========================================================

  * "componentsOfKernel(...,UseMatroidSpeedup=>...)" -- see
    componentsOfKernel, -- Finds all minimal generators up
    to a given total degree in the kernel of a ring map

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

The object UseMatroidSpeedup, is a symbol (Macaulay2Doc).