%%
%% ch7.tex
%%

\chapter{Standard (\Grobner) Basis Computations}
\label{ch-comps}


Computations of standard bases and syzygies are the heart of
\Macaulay.  The command \icmd{std} is the workhorse of \Macaulay\
which computes standard (\Grobner) bases. The commands \icmd{res} and
\icmd{nres} are important commands which compute finite free
resolutions.  These three basic commands are described in
\secref{sec-cstd}.  The other computations are somewhat more
specialized, but still quite useful.  These include \icmd{intersect},
\icmd{lift-std}, \icmd{modulo}, \icmd{quotient} and \icmd{syz}.  These
commands are described in \secref{sec-ccomps}.

Each matrix which is input to the commands of this chapter must be
{\em graded}: see \secref{sec-mgraded} for details.  In fact, the
commands in this section are the {\em only} commands of \Macaulay\
which require that their input parameters be graded.  If the matrix is
not graded, an error message is issued.  In this case, either
homogenize the matrix, or use the \icmd{setdegs} or \icmd{setcoldegs}
command to make the matrix graded.

The commands in this chapter compute a standard basis and/or syzygy
module of a submodule of a free module corresponding to the columns of
a matrix.  (see the introduction of \chapref{ch-matrices}).  For each
computation command except \icmd{res} and \icmd{nres}, the result is a
matrix together with a standard basis for the corresponding submodule.
Both the standard basis and the matrix have the same name, the name
given to the \parm{result computation}.  The result of the commands
\icmd{nres} and \icmd{res} is the set of syzygy matrices and 
corresponding standard bases.  In these cases, the various matrices of
the resolution are indexed starting at 1: e.g.  $w.1$, $w.2$, etc.

In every case except one the result matrix or matrices correspond to
minimal generators of the result submodule(s).  The exception is with
the \icmd{res} command.  The first matrix of the result has a standard
basis computed, but the matrix is the original matrix.  However, the
rest of the matrices do correspond to minimal generators of their
submodules.

Each of these commands is designed to work in the case where the base
ring is a quotient ring.

\section{Standard basis and syzygy computations}
\label{sec-cstd}

The following three commands are the most used standard basis commands
of \Macaulay.

\cmd{std}{\parm{matrix M} \parm{computation}}

Compute a standard (or Groebner) basis of the submodule $I \subset
R^r$ generated by the columns of the matrix $M$ with $r$ rows, where
$R$ is the base ring of $M$.  If $M$ has one row, $I$ is the ideal of
$R$ generated by the entries of the matrix of $M$.  In this case, the
result is the usual standard, or Groebner, basis of this ideal.

To obtain the standard basis as a matrix after the computation has
finished, use the \icmd{putstd} command.  However, there are many other
commands which manipulate standard bases (see \chapref{ch-stdcmds}).

A minimal set of generators for $I$ is computed, but no change of
basis matrix is computed.  If one is desired (e.g. for use with the 
\icmd{reduce} or \icmd{lift} commands), use \icmd{lift-std} instead.

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type j
; ab-c2 bc-d2 cd-e2 

%  std j w
; 23.4.5.
; computation complete after degree 5

%  type w
; ab-c2 bc-d2 cd-e2 

%  putstd w
; 1
; 5
; d3-be2
; cd-e2
; c3-ad2
; bc-d2
; ab-c2

\end{verbatim}
\hrule
\capt{The \icmd{std} command}

\cmd{nres}{\parm{matrix} \parm{computation} \optparm{max depth}}

Compute a minimal free resolution of the module $M$ presented by
\parm{matrix}.  The columns of the $i^{th}$ matrix of the result
minimally generate the $i^{th}$ syzygy module of $M$.  A standard
basis is computed for each of these syzygy modules.

If a maximum depth, $d$, is specified, then only the first $d$
matrices of the resolution are computed.  The default for $d$ is the
number of variables in the base ring of \parm{matrix}.  If the base
ring is a polynomial ring, and not a quotient ring, then Hilbert's
syzygy theorem says that the length of the resolution is bounded by
the number of variables.

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type j
; -bc+ad -bc+ad b3-a2c c3-bd2 -ac2+b2d 

%  nres j w
; 2.3...4...5...
; computation complete after degree 5

%  pres w
; 
; ----------------------------------

; bc-ad b3-a2c c3-bd2 ac2-b2d 
; 
; ----------------------------------

; ac bd c2 b2 
; -d 0  0  -c 
; 0  -a -b 0  
; -b c  d  -a 
; 
; ----------------------------------

; -c 
; -b 
; a  
; d  
; 
; ----------------------------------


\end{verbatim}
\hrule
\capt{The \icmd{nres} command}

Note that the columns of $w.1$ minimally generate the submodule
corresponding to \parm{matrix}, the columns of $w.2$ minimally generate
the syzygies on these columns, the columns of $w.3$ minimally generate
the syzygies on $w.2$, etc.

The computation proceeds degree by (slanted) degree.  For more details, see
\secref{sec-cfine}.

\cmd{res}{\parm{matrix} \parm{computation} \optparm{max depth}}

Compute a free resolution of the module $M$ presented by
\parm{matrix}, such that the first matrix in the resolution is the
specified matrix.  The columns of the $i^{th}$ matrix of the result
minimally generate the $i^{th}$ syzygy module of $M$ for $i \geq 2$.
A standard basis is computed for each of these syzygy modules.

If a maximum depth, $d$, is specified, then only the first $d$
matrices of the resolution are computed.  The default for $d$ is the
number of variables in the base ring of \parm{matrix}.  If the base
ring is a polynomial ring, and not a quotient ring, then Hilbert's
syzygy theorem says that the length of the resolution is bounded by
the number of variables.

This command differs from \icmd{nres} in the following way.  The
columns of the first matrix of the resolution constructed using
\icmd{nres} minimally generate the submodule corresponding to \parm{matrix}.
The first matrix of the resolution constructed using \icmd{res} is
exactly \parm{matrix}.  Thus, \icmd{res} does not necessarily find a 
minimal resolution of $M$.  Instead, the syzygies of the columns of 
\parm{matrix} are found.  

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type j
; -bc+ad -bc+ad b3-a2c c3-bd2 -ac2+b2d 

%  res j w
; 1..2..3...4...5...
; computation complete after degree 5

%  pres w
; 
; ----------------------------------

; -bc+ad -bc+ad b3-a2c c3-bd2 -ac2+b2d 
; 
; ----------------------------------

; -1 ac bd c2 b2 
; 1  0  0  0  0  
; 0  d  0  0  c  
; 0  0  a  b  0  
; 0  -b c  d  -a 
; 
; ----------------------------------

; 0  
; -c 
; -b 
; a  
; d  
; 
; ----------------------------------


\end{verbatim}
\hrule
\capt{The \icmd{res} command}

\section{Other computation commands}
\label{sec-ccomps}

These commands are more specialized than the commands of
\secref{sec-cstd} but are still extremely useful.

\cmd{intersect}{\parm{matrix1} ... \parm{matrix n} \parm{result computation}}

Compute the intersection 
	$$I_1 \cap \ldots \cap I_n$$
of the submodules $I_j$ corresponding to the given matrices.  A
standard basis and a minimal set of generators of this submodule are
also computed.  

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type j1
; b2-ac c2-bd -bc+ad 

%  type j2
; a2 b2 c2 d2 

%  intersect j1 j2 w
; 0.1.2.3..4..5..
; computation complete after degree 5

%  type w
; c2d-bd2 bc2-b2d c3-ad2 ab2-a2c b3-a2d b2c-ac2 b2d2-acd2 a2c2-a2bd 

%  type w.0  ;; this is the auxiliary matrix.
; 1 b2-ac c2-bd -bc+ad 0  0  0  0  
; 1 0     0     0      a2 b2 c2 d2 

\end{verbatim}
\hrule
\capt{The \icmd{intersect} command}

The intersection is computed by creating an auxiliary matrix ($w.0$ in the
above example) and then using the \icmd{syz} command to find the first 
component(s) of each syzygy on the columns of this matrix.

Each matrix \parm{matrix i} must be graded, and have the same number of
rows.  If the resulting auxiliary matrix is not graded, then an error
message is given, and \parm{result computation} itself is set to this
matrix.

\cmd{lift-std} {\parm{matrix} \parm{computation}}

Compute a standard basis of the submodule, $I$, corresponding to
\parm{matrix}, keeping enough information to remember how each
standard basis element can be expressed in terms of the original
columns of \parm{matrix}.  This extra information is called the
"change of basis matrix" by \Macaulay.  It is needed for the
\icmd{reduce} and \icmd{lift} commands.  The \icmd{putchange} command
extracts this matrix from the \parm{computation}.  
The resulting matrix corresponds to minimal generators of $I$.

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type j
; ab-b2 a2-c2 ab2-c3 

%  lift-std j w
; 2.3.4.5.
; computation complete after degree 5

%  type w
; ab-b2 a2-c2 ab2-c3 

%  putstd w 
; 1
; 5
; bc2-c3
; b3-c3
; ac3-c4
; ab-b2
; a2-c2

%  putchange w wc

%  type wc
; a  -b -a2+ab+ac+c2 1 0 
; -b 0  ab-b2-bc     0 1 
; 1  1  -a+b+c       0 0 

\end{verbatim}
\hrule
\capt{The \icmd{lift-std} command}


\cmd{modulo} {\parm{matrix} \parm{matrix} \parm{computation}}

Compute a presentation for $I+J/J$, where $I$ is the submodule generated
by the columns of the first matrix, and $J$ is the submodule generated
by the columns of the second matrix.

If the row degrees for $I$ and $J$ are not the same, or if $I$ or $J$ is not
graded, an error message is given. 

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type f
; a2-b2 

%  type g
; a2c2-b2c2 abcd -c2+ad 

%  modulo f g w
; 2.3.4..5..6..7..
; computation complete after degree 7

%  type w
; c2-ad ad 

%  type w.0
; a2-b2 a2c2-b2c2 abcd -c2+ad 

\end{verbatim}
\hrule
\capt{The \icmd{modulo} command}

\cmd{quotient}{\parm{matrix M} \parm{matrix N} \parm{result computation}}

Compute the ideal or submodule quotient $(I : J)$, where $I \subset
R^r$ and $J$ are the submodules generated by the columns of M and N,
respectively, and $R$ is the base ring of $M$ and $N$.

There are two cases, depending on whether $J$ is an ideal or a
submodule of $R^r$.  If $J$ is an ideal, then 
	$(I : J) = \{ f \in R^r \mid fJ \subset I\}$ 
is a submodule of $R^r$.  If $J \subset R^r$,
then 
	$(J : I) = \{ f \in R \mid fJ \subset I\}$
is an ideal of $R$.

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type m
; a b c d 
; e f g h 

%  type n
; 1 0 
; 0 1 

%  quotient m n w
; 0.1.2..3..
; computation complete after degree 3

%  type w
; de-ah df-bh dg-ch ce-ag cf-bg be-af 

%  type w.0
; 1 a b c d 0 0 0 0 
; 0 e f g h 0 0 0 0 
; 0 0 0 0 0 a b c d 
; 1 0 0 0 0 e f g h 

\end{verbatim}
\hrule
\capt{The \icmd{quotient} command}

The quotient is computed by creating an auxiliary matrix ($w.0$ in the
above example) and then using the \icmd{syz} command to find the first 
component(s) of each syzygy on the columns of this matrix.



\cmd{syz}{\parm{matrix: M} \parm{no. components: d} \parm{computation: N}}

Compute the (partial) syzygies on the columns of the matrix $M$.
Recall that a {\em syzygy} on a set of column vectors $f_1, \ldots,
f_c$, where $f_i \in R^r$, is defined to be a vector $(g_1, \ldots, g_c)$
such that $\sum g_i f_i = 0$.

This command computes (a minimal generating set for) the submodule of
``partial'' syzygies: 	
	$$\{ (g_1, \ldots, g_d) \in R^d \mid \mbox{there exists}\ g_{d+1},
		\ldots, g_c \in R \mbox{\ s.t.} \sum g_i f_i = 0\}.$$

The integer $d$ is any integer expression.  If $d = -1$, then the entire
syzygy module is found.  This is equivalent to ``{\tt res M N 2}''.  If
$d = 0$, then this command is equivalent to ``{\tt std M N}''.

This command is mostly used by the \icmd{modulo}, \icmd{intersect} and
\icmd{quotient} commands, although it is occasionally useful by itself.

For example, 

\vskip 10pt
\hrule
\begin{verbatim}
%  type n
; 1 a b c d 
; 1 e f g h 

%  syz n 1 w
; 0.1.2..
; computation complete after degree 2

%  type w
; de-ah df-bh dg-ch ce-ag cf-bg be-af 

\end{verbatim}
\hrule
\capt{The \icmd{syz} command}

\section {Internal format of a computation}
\label{sec-cint}

When any matrix is defined in \Macaulay, its internal format
includes the following information.
\begin{enumerate}
  \item An array of columns, where each column is a vector of polynomials.
  \item The degree of each row.
  \item The degree of each column.
\end{enumerate}

This information can be obtained by using the \icmd{type}, \icmd{row-degs},
and \icmd{col-degs} commands.

After a computation is performed using one of the computation
commands, each matrix which has had a standard basis computed also
contains the following information.
\begin{enumerate}
  \item The standard basis, represented by an array of columns
  \item The change of basis matrix, $C$, represented by an array of
columns.  The $i^{th}$ column is the representation of the $i^{th}$
standard basis element in terms of the generators of the matrix.
Thus, if there are $s$ elements in the standard basis, and $r$ columns of the
original matrix $M$, then $C$ is a $r$ by $s$ matrix.
\end{enumerate}

Not all computation commands compute a change of basis matrix.  The
commands which do include \icmd{lift-std}, \icmd{res}, and
\icmd{nres}.  The other computation commands do not compute this
matrix.  Most commands of \Macaulay\ do not require the change of
basis matrix $C$.  The only exceptions are the \icmd{reduce} and
\icmd{lift} commands.  The commands \icmd{res} and \icmd{nres} compute
$C$ since this is used to calculate syzygy modules.

The following two commands either display or create a new matrix consisting
of the standard basis or change of basis matrix.

\cmd{putstd}{\parm{standard basis} \optparm{result matrix}}

Create a matrix whose columns are the given standard basis.  If no second
argument is provided, then display the standard basis using the same
format as the \icmd{putmat} command.

If the first argument is a matrix without a computed standard basis, then
a warning message is displayed, and the generators of the matrix are
used instead.

\cmd{putchange}{\parm{standard basis} \optparm{result matrix}}

Create a matrix corresponding to the change of basis matrix of the
given standard basis.  If no second argument is provided, then display
the standard basis using the same format as the \icmd{putmat} command.

If the first argument is a matrix without a computed standard basis,
or if no change of basis matrix has been computed, then create (or display)
a matrix having zero columns.

\section{Fine control of standard basis computations}
\label{sec-cfine}

Each computation command creates an internal graph which describes the
operation to be performed.  After constructing this graph, the
\Macaulay\ parameter ``autocalc'' (\secref{sec-sysparam}) is
examined.  If the value is negative, the computation is instructed to
run to completion.  If the value is positive, the computation is
instructed to proceed until it has finished the degree $d$ part of the
computation, where $d$ is the value of the
\Macaulay\ parameter ``autodegree''.  If the value of ``autocalc'' is
zero, then the computation is not started.

One can use these two parameters ``autocalc'' and ``autodegree'' to
control how much computation \Macaulay\ should do.  Often, one knows
that the desired result must occur in a specific degree, but that there
may be a large amount of computation after this degree.  In this case,
this added control can be essential.

After a computation has been completed though degree $d$, you may
continue the computation in higher degrees using the \icmd{calc}
command.  Also, if the ``autocalc'' parameter is set to zero, the
computation can be started using \icmd{calc}.  This command is no longer
used very much in \Macaulay.

\subsection{Interrupting computations}
	
Interrupting a calculation is very useful since intermediate
results are meaningful.  This is particularly important for
calculations which take a long time to complete.  One might be satisfied
with an intermediate result and decide to terminate a computation
before it runs to completion.

The interrupt feature allows the user to interrupt a
calculation, examine intermediate results and eventually resume the
calculation where it left off, or exit \Macaulay.

To interrupt \Macaulay\ on a Macintosh, simply click the mouse button.
On all other machines, type {\tt (CNTRL)-C}.

Interrupting any computation command causes the system to interrupt the
computation at the next syzygy or standard basis element computed.  In
most cases, the user will not have to wait very long for this event to
occur.  After the interrupt occurs, the user receives a prompt for
more input.  Any legal \Macaulay\ command can be issued here.  For
example, the user may want to view a resolution, write it to disk,
etc.  Caution: using the \icmd{kill} command on any variable while a
calculation is interrupted is likely to cause \Macaulay\ to crash!

To resume the calculation, use the \icmd{continue} command.  To reset the
degree at which to stop, use the \icmd{chcalc} command.
To terminate the calculation as well as the \Macaulay\ session, use
``{\tt exit all}''.

\subsection{Feedback during computations}
    
Certain feedback information is displayed during every computation
(unless it is suppressed by using the \Macaulay\ parameter ``prlevel''
(\secref{sec-sysparam})).  Each computation proceeds degree by degree.
At the start of each degree $d$, the number $d$ is displayed.  Each time a
standard basis is started in a degree which has at least 2 elements (1
if using a quotient ring), a ``.''  is displayed.  It is possible for
numbers to be run together without any ``.'' between them.  

If the \Macaulay\ parameter ``verbose'' is set to a positive value,
then more information is displayed.  Each S-pair computed has one of
three letters displayed: ``m'' means a new standard basis element has
been added. ``s'' means a non-zero syzygy has been constructed (note
that it isn't necessarily minimal).  ``o'' means that a zero syzygy
has been constructed.

\subsection{Controlling computation}

The following three commands are used to provide finer control of
computations, as described above.

\cmd{calc}{\parm{computation} \optparm{top degree}}

Perform the computation which was constructed while the \Macaulay\ parameter
had the value zero, or perform the computation which had previously
been stopped because of the value of the ``autodegree'' parameter.

The computation proceeds degree by degree until the ``top degree'' has been
completed.  If the optional integer is not specified, the default is
positive infinity.

If you wish to change the top degree, or remove it, simply stop the
computation using the interrupt mentioned above, use the \icmd{chcalc}
command, and then restart the computation using the \icmd{continue}
command.

\cmd{chcalc}{\parm{computation} \optparm{new top deg}}

When issued inside an interrupted computation, this command resets
the top degree of the given computation.  If no argument is given, the
new top degree is set to infinity.  Once you continue the
computation with \icmd{continue}, the computation will now proceed to
this new top degree.

\cmd{continue}{}

Continue an interruped computation which had been stopped by using 
either the mouse button (on Macintosh computers) or ``{\tt (CNTRL)-C}'' on
other computers.
 


