code:
@ifclear singularmanual
@strong{Important:} Please see
@ifhtml
@uref{COPYING.html, COPYING}
@end ifhtml
@ifnothtml
the file COPYING contained in the distribution
@end ifnothtml
for license information on @sc{Singular}. Please register yourself as a
@sc{Singular} user by using the registration form on the @sc{Singular}
homepage @uref{http://www.singular.uni-kl.de}.
If for some reason you cannot access the registration form, you can also
register by sending an email to @email{singular@@mathematik.uni-kl.de}
with subject line @code{register} and body containing the following data:
your name, email address, organisation, country and platform(s).
@end ifclear

repo_name: mthl/texinfo

license: mit


code:
% Id: singcard.tex,v 1.1 2003/08/08 14:27:06 pertusus Exp $

%
% singcard.tex - common macros for Singular reference cards.
%
% Some of the macros/settings ripped from gdb reference card.
%

%
% - declare configurable parameters.
%
\newdimen\totalwidth
\newdimen\totalheight
\newdimen\hmargin
\newdimen\vmargin

\newdimen\barwidth
\newdimen\barheight

%%% START CONFIGURABLE SECTION

%
% - configure your papersize.
%

% US letter paper (8.5x11in)
%\totalwidth=11in		% total width of paper
%\totalheight=8.5in		% total height of paper
%\hmargin=.25in			% horizontal margin width
%\vmargin=.25in			% vertical margin width

% A4 paper
\totalwidth=29.7cm
\totalheight=21cm
\hmargin=6mm
\vmargin=6mm

%
% - configure your folding guides.
%
\barwidth=.1pt			% width of the folding guide
\barheight=2pt			% height of the folding guide

% For NO printed folding guide,
% comment out other \def\vdecor's and uncomment:
%\def\vdecor{\hskip\hmargin plus1fil\hskip\barwidth plus1fil\hskip\hmargin plus1fil}

% For SOLID LINE folding guide,
% comment out other \def\vdecor's and uncomment:
%\def\vdecor{\hskip\hmargin plus1fil \vrule width \barwidth \hskip\hmargin plus1fil}

% For SMALL MARKS NEAR TOP AND BOTTOM as folding guide,
% comment out other \def\vdecor's and uncomment:
\def\vdecor{\hskip\hmargin plus1fil
\vbox to \vsize{\hbox to \barwidth{\vrule height\barheight width\barwidth}\vfill
\hbox to \barwidth{\vrule height\barheight width\barwidth}}%THIS PERCENT SIGN IS ESSENTIAL
\hskip\hmargin plus1fil}

%%% END CONFIGURABLE SECTION

%
% - compute parameters of three column format.
%
\newdimen\fullhsize		% width of area without margins
\newdimen\itemwidth		% width of item column
\newdimen\definitionwidth	% width of definition column
\newdimen\temp			% only for temporary use

% adjust the offsets so the margins are measured *from paper edge*
\hoffset=-1in \advance \hoffset by \hmargin
\voffset=-1in \advance \voffset by \vmargin

% fullhsize = totalwidth - (2 * hmargin)
\fullhsize=\totalwidth
\temp=\hmargin \multiply \temp by 2 \advance \fullhsize by -\temp

% hsize = (fullhsize - (4 * hmargin) - (2 * barwidth)) / 3
\hsize=\fullhsize
\temp=\hmargin \multiply \temp by 4 \advance \hsize by -\temp
\temp=\barwidth \multiply \temp by 2 \advance \hsize by -\temp
\divide \hsize by 3

% vsize = totalheight - (2 * vmargin)
\vsize=\totalheight
\temp=\vmargin \multiply \temp by 2 \advance \vsize by -\temp

% default itemwidth = hsize * 1/4
% default definitionwidth = hsize * 3/4
\temp=\hsize \divide \temp by 4
\itemwidth=\temp
\definitionwidth=\hsize \advance \definitionwidth by -\itemwidth

%
% - miscellaneous parameters.
%
\tolerance=2000
\hyphenpenalty=500

\parindent=0pt
\parskip=0pt
\baselineskip=9pt

\footline={\vbox to0pt{\hss}}

%
% - font definitions.
%
\font\rm=cmr7
\font\bf=cmbx7
\font\it=cmti7
\font\bit=cmbxti10 at 7pt
\font\tt=cmtt8			% cmtt7 seems too small
\font\sc=cmcsc10 at 7pt

% huge fonts
\font\hbf=cmbx12

% large fonts
\font\lbf=cmbx10

% small fonts
\font\srm=cmr6
\font\ssc=cmcsc10 at 6pt

% tiny fonts
\font\tit=cmti7 at 5pt

% math fonts
\font\mathrm=cmr7
\font\smathrm=cmr5
\font\mathit=cmmi7
\font\smathit=cmmi5
\font\mathsy=cmsy7
\font\smathsy=cmsy5
\font\mathex=cmex7

\textfont0=\mathrm \scriptfont0=\smathrm
\textfont1=\mathit \scriptfont1=\smathit
\textfont2=\mathsy \scriptfont2=\smathsy
\textfont3=\mathex \scriptfont3=\mathex

%
% - macros for tree column format.
%
\def\fulline{\hbox to \fullhsize}
\def\columnbox{\leftline{\pagebody}}
\def\tripleformat{\shipout
		  \vbox{\fulline{\box\leftcolumn\vdecor
				 \box\centercolumn\vdecor
				 \columnbox}}%
		  \advancepageno}
\def\bye{\par\vfill
	 \supereject
	 \if R\currentcolumn\null\vfill\eject\fi
	 \end}

%
% - miscellaneous macros.
%
% \Singular: for sake of corporate identity
% \ctl: print control keys
% \opt: print optional arguments
% \alt: separate alternative arguments
% \rep: denote repitition of arguments
% \rmslash: print a slash in roman type face
% \eg, \ie: obvious
% \verysmallskip: skip a very small amount (used between \sec entries).
%   Extra skip does not harm in the applications of \verysmallskip,
%   so we choose a large stretch for it.
% \strut: redefinition of TeX's \strut macro
%
\def\Singular{{\sc Singular}}
\def\ctl#1{{\tt C-#1}}
\def\opt#1{{\rm[{\tt #1}]}}
\def\alt{\hbox{\hskip 1pt$\mid$\hskip 1pt}}
\def\rep{$\ldots$}
\def\rmslash{{\rm /}}
\def\eg{e.g.~}
\def\ie{i.e.~}

\newskip\verysmallskipamount
\verysmallskipamount=1pt plus 0.333333pt minus 0.333333pt
\def\verysmallskip{\vskip \verysmallskipamount}

\newbox\sevenptstrutbox
\setbox\sevenptstrutbox=\hbox{\vrule height6pt depth3pt width0pt}
\def\strut{\relax\ifmmode\copy\sevenptstrutbox\else\unhcopy\sevenptstrutbox\fi}

%
% \sec - insert a new section into the card.
%
% First argument is section title, second argument the item column
% width (defaults to 1/4*hsize), third the section itself.
%
% \setitemwidth: auxiliary macro
%
\def\setitemwidth#1{\itemwidth=#1
		    \definitionwidth=\hsize
		    \advance\definitionwidth by -\itemwidth}
\long\def\sec#1(#2)#3\endsec{{%
	\def\\{#2}\ifx\empty\\ \else\setitemwidth{#2}\fi
	\halign{% column 1
		\vtop{\hsize=\itemwidth\strut\tt##\strut}&
		% column 2
		\vtop{\hsize=\definitionwidth\strut\rm##\strut}\cr
		% tail of \long\def fills in halign body with argument
		\noalign{\bigskip\lbf #1\verysmallskip}%
		#3}}}

%
% - macros to use inside a \sec.
%
% \subsec: insert a sub heading into a \sec
% \sectext: insert non-aligned text into a \sec
% \longentry: insert an entry with a long item field into a \sec
% \longitem: insert an entry with a long item field and no
%   definition field into a \sec
% \entryskip: insert glue between two entries
%
\def\subsec#1{\noalign{\smallskip\bf #1}}
\long\def\sectext#1\cr{\noalign{\strut\hyphenpenalty=50 #1\strut}}
% the `\ ' forces a non empty item field
\long\def\longentry#1&#2\cr{\noalign{\strut\tt #1\strut}\ &#2\cr}
\long\def\longitem#1\cr{\noalign{\strut\tt #1\strut}}

\newskip\entryskipamount
\entryskipamount=\smallskipamount
\def\entryskip{\noalign{\vskip \entryskipamount}}

%
% - initialization.
%

% set output routine
\newbox\leftcolumn
\newbox\centercolumn
\let\currentcolumn=L
\output={\if L\currentcolumn
	    \global\setbox\leftcolumn=\columnbox \global\let\currentcolumn=C%
	 \else
	    \if C\currentcolumn
	       \global\setbox\centercolumn=\columnbox \global\let\currentcolumn=R%
	    \else
	       \tripleformat \global\let\currentcolumn=L%
	    \fi
	 \fi}

% switch to our default font
\rm

% ragged format
\raggedbottom
\raggedright


code:
\input texinfo    @c -*-texinfo-*-
@comment Id: singular.tex,v 1.1 2003/08/08 14:27:06 pertusus Exp $
@comment This file was generated by doc2tex.pl from singular.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT singular.doc INSTEAD
@comment this file contains the main structure of the manual

@c ------------------------
@c %**start of header
@c ------------------------
@include version.texi
@setfilename singular.hlp
@settitle Singular @value{VERSION} Manual
@c @setchapternewpage odd
@paragraphindent 0
@c ------------------------
@c %**end of header
@c ------------------------

@c --------------------- general settings --------------------
@iftex
@afourpaper
@finalout
@pagesizes 23cm, 16.5cm
@end iftex

@set singularmanual 1
@c @set namespaces 1
@include uname.texi
@c --------------------- end general setting --------------------

@c --------------------- invisible Info header ------------------------
@ifinfo
This is the texinfo file describing Singular (version @value{VERSION})
@end ifinfo
@c --------------------- end Info invisible header --------------------

@c --------------------- tex titlepage --------------------
@titlepage
@sp 2
@center @titlefont{Singular}
@sp 2
@center A Computer Algebra System for Polynomial Computations
@sp 5
@center @titlefont{Manual}
@center Version @value{VERSION}
@sp 2
@center Singular is created and its development is directed and coordinated by
@center G.-M. Greuel, G. Pfister, and H. Sch@"onemann
@sp 2
@center with contributions by
@center O. Bachmann, W. Decker, S. Endra@ss{}, I. Farran, A. Fr@"uhbis-Kr@"uger, C. Gorzel,
@center H. Grassmann, A. Heydtmann, D. Hillebrand, T. Keilen, U. Klein, K. Kr@"uger, M. Lamm,
@center C. Lossen, B. Martin, M. Me@ss{}ollen, W. Neumann, T. N@"u@ss{}ler, W. Pohl, T. Siebert,
@center J. Schmidt, M. Schulze, R. Stobbe, M. Wenk, T. Wichmann
@sp 2
@author Fachbereich Mathematik
@author Zentrum f@"ur Computeralgebra
@author Universit@"at Kaiserslautern
@author D-67653 Kaiserslautern
@end titlepage

@c print short table of contents in tex right after titlepage
@c Detailed ToC is printed at the end of the manual
@shortcontents

@c -----------------------Top node-----------------------------------
@node Top, Preface, (dir), (dir)

@ifnothtml
@ifinfo
@center @strong{SINGULAR}
@center A Computer Algebra System for Polynomial Computations
@center User Manual for @sc{Singular} Version @value{VERSION}
@center @uref{http://www.singular.uni-kl.de}
@end ifinfo
@end ifnothtml

@ifhtml
@html

 A Computer Algebra System for Polynomial Computations

HTML User Manual for Singular Version
@end html
@value{VERSION}, @value{VERSION_DATE}
@html

University of Kaiserslautern
Department of Mathematics

Centre for Computer Algebra

@end html
@end ifhtml

@menu
* Preface::
* Introduction::
* General concepts::
* Data types::
* Functions and system variables::
* Tricks and pitfalls::
* Examples::
* Polynomial data::
* Mathematical background::
* SINGULAR libraries::
* Release Notes::
* Index::
@end menu

@c ----------------------------------------------------------------------------
@node Preface, Introduction, Top, Top
@chapter Preface
@cindex Preface
@include COPYING.texi

@c ----------------------------------------------------------------------------
@node Introduction, General concepts, Preface, Top
@chapter Introduction
@cindex Introduction

@include start.tex
@c ----------------------------------------------------------------------------
@node General concepts, Data types, Introduction, Top
@chapter General concepts
@cindex General concepts
@include general.tex

@c ----------------------------------------------------------------------------
@node Data types, Functions and system variables, General concepts, Top
@chapter Data types
@cindex Data types
@include types.tex

@c ----------------------------------------------------------------------------
@node Functions and system variables, Tricks and pitfalls, Data types, Top
@chapter Functions and system variables
@cindex Commands
@include reference.tex

@c ----------------------------------------------------------------------------
@node Tricks and pitfalls, Examples, Functions and system variables, Top
@chapter Tricks and pitfalls
@cindex Tricks and pitfalls
@include tricks.tex

@c ----------------------------------------------------------------------------
@node Examples, Polynomial data, Tricks and pitfalls, Top
@appendix Examples
@cindex Examples
@include examples.tex

@c ----------------------------------------------------------------------------
@node Polynomial data,Mathematical background, Examples, Top
@appendix Polynomial data
@cindex Polynomial data
@include pdata.tex

@c ----------------------------------------------------------------------------
@node Mathematical background, SINGULAR libraries, Polynomial data, Top
@appendix Mathematical background
@cindex Mathematical background
@include math.tex
@c ----------------------------------------------------------------------------
@node SINGULAR libraries, Release Notes, Mathematical background, Top
@appendix SINGULAR libraries
@cindex SINGULAR libraries
@cindex LIBs

@sc{Singular} comes with a set of standard libraries. Their content is
described in the following subsections.

Use the @ref{LIB} command for loading of single libraries, and the
command @code{LIB "all.lib";} for loading all libraries.

@menu
* standard_lib:: extensions of Singular kernel
* General purpose::
* Linear algebra::
* Commutative algebra::
* Singularities::
* Invariant theory::
* Symbolic-numerical solving::
* Visualization::
* Coding theory::
@end menu
@c ----------------------------------------------------------
@node standard_lib, General purpose, SINGULAR libraries, SINGULAR libraries
@section standard_lib

The library @code{standard.lib} provides extensions to the
set of built-in commands and is automatically loaded
during the start of @sc{Singular}, unless @sc{Singular} is started up
with the @code{--no-stdlib} command line option (see
@ref{Command line options}).

@c start include of docu for standard.lib:LibInfo
@c ---content LibInfo---
@comment This file was generated by doc2tex.pl from d2t_singular/standard_lib.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT d2t_singular/standard_lib.doc INSTEAD
@c library version: (1.58.2.9,2003/06/16)
@c library file: ../Singular/LIB/standard.lib
@cindex standard.lib
@cindex standard_lib
@table @asis
@item @strong{Library:}
standard.lib
@item @strong{Purpose:}
   Procedures which are always loaded at Start-up

@end table

@strong{Procedures:}
@menu
* stdfglm:: standard basis of ideal via fglm [and ordering ord]
* stdhilb:: standard basis of ideal using the Hilbert function
* groebner:: standard basis using a heuristically chosen method
* quot:: quotient using heuristically chosen method
* res:: free resolution of ideal or module
* sprintf:: returns formatted string
* fprintf:: writes formatted string to link
* printf:: displays formatted string
@end menu
@c ---end content LibInfo---
@c generated lib proc docu for standard.lib:LibInfo singular.doc:200
@c end include of docu for standard.lib:LibInfo

@c ----------------------------------------------------------------------------
@node General purpose, Linear algebra, standard_lib, SINGULAR libraries
@section General purpose
@cindex General purpose

@menu
* all_lib:: load all other libraries
* general_lib:: procedures of general type
* inout_lib:: procedures for manipulating in- and output
* poly_lib:: procedures for manipulating polynomials and ideals
* random_lib:: procedures of random/sparse  matrix and poly operations
* ring_lib:: procedures for manipulating rings and maps
@end menu

@c ----------------------------------------------------------
@node all_lib, general_lib, General purpose, General purpose
@subsection all_lib
@cindex all_lib
@cindex all.lib

The library @code{all.lib} provides a convenient way to load all
libraries of the @sc{Singular} distribution.

@strong{Example:}
@smallexample
@c reused example all_lib singular.doc:227
option(loadLib);
LIB "all.lib";
@expansion{} // ** loaded all.lib (1.35.2.4,2003/02/25)
@expansion{} // ** loaded makedbm.lib (1.11,2000/12/22)
@expansion{} // ** loaded brnoeth.lib (1.11.2.5,2002/10/18)
@expansion{} // ** loaded paramet.lib (1.11.2.1,2002/10/21)
@expansion{} // ** loaded surf.lib (1.19.2.6,2002/07/17)
@expansion{} // ** loaded latex.lib (1.19.2.1,2002/02/20)
@expansion{} // ** loaded graphics.lib (1.10,2001/02/19)
@expansion{} // ** loaded zeroset.lib (1.7.2.2,2002/02/20)
@expansion{} // ** loaded ntsolve.lib (1.12.2.1,2002/04/12)
@expansion{} // ** loaded triang.lib (1.7,2001/02/19)
@expansion{} // ** loaded solve.lib (1.21.2.13,2002/10/21)
@expansion{} // ** loaded presolve.lib (1.17.2.6,2003/03/26)
@expansion{} // ** loaded stratify.lib (1.7.2.4,2002/04/11)
@expansion{} // ** loaded rinvar.lib (1.7.2.3,2002/02/20)
@expansion{} // ** loaded finvar.lib (1.32.2.2,2002/08/13)
@expansion{} // ** loaded ainvar.lib (1.6.2.2,2002/04/12)
@expansion{} // ** loaded spectrum.lib (1.12.2.3,2002/03/06)
@expansion{} // ** loaded spcurve.lib (1.15.2.1,2002/02/20)
@expansion{} // ** loaded sing.lib (1.24.2.5,2003/04/15)
@expansion{} // ** loaded qhmoduli.lib (1.0,2000/12/12)
@expansion{} // ** loaded mondromy.lib (1.22.2.2,2002/02/20)
@expansion{} // ** loaded hnoether.lib (1.29.2.14,2002/10/21)
@expansion{} // ** loaded gaussman.lib (1.33.2.26,2003/02/10)
@expansion{} // ** loaded equising.lib (1.7.2.5,2003/02/25)
@expansion{} // ** loaded deform.lib (1.25.2.2,2003/02/24)
@expansion{} // ** loaded classify.lib (1.48.2.4,2002/04/11)
@expansion{} // ** loaded toric.lib (1.11,2001/02/06)
@expansion{} // ** loaded intprog.lib (1.5,2001/02/06)
@expansion{} // ** loaded reesclos.lib (1.50,2001/08/06)
@expansion{} // ** loaded primitiv.lib (1.15,2001/02/05)
@expansion{} // ** loaded primdec.lib (1.98.2.14,2003/04/07)
@expansion{} // ** loaded normal.lib (1.34.2.17,2002/10/21)
@expansion{} // ** loaded mregular.lib (1.6.2.1,2002/02/20)
@expansion{} // ** loaded mprimdec.lib (1.1.2.3,2002/03/19)
@expansion{} // ** loaded homolog.lib (1.15.2.2,2002/10/07)
@expansion{} // ** loaded elim.lib (1.14.2.4,2003/04/16)
@expansion{} // ** loaded algebra.lib (1.9.2.3,2002/04/11)
@expansion{} // ** loaded linalg.lib (1.10.2.15,2003/04/04)
@expansion{} // ** loaded matrix.lib (1.26.2.2,2002/10/07)
@expansion{} // ** loaded ring.lib (1.17.2.1,2002/02/20)
@expansion{} // ** loaded random.lib (1.16.2.1,2002/02/20)
@expansion{} // ** loaded poly.lib (1.33.2.6,2003/02/10)
@expansion{} // ** loaded inout.lib (1.21.2.5,2002/06/12)
@expansion{} // ** loaded general.lib (1.38.2.9,2003/04/04)
@c end example all_lib singular.doc:227
@end smallexample
@c ----------------------------------------------------------
@node general_lib, inout_lib, all_lib, General purpose
@subsection general_lib
@c include of docu for general.lib
@include d2t_singular/general_lib.tex
@c ----------------------------------------------------------
@node inout_lib, poly_lib, general_lib, General purpose
@subsection inout_lib
@c include of docu for inout.lib
@include d2t_singular/inout_lib.tex
@c ----------------------------------------------------------
@node poly_lib, random_lib, inout_lib, General purpose
@subsection poly_lib
@c include of docu for poly.lib
@include d2t_singular/poly_lib.tex
@c ----------------------------------------------------------
@node random_lib, ring_lib, poly_lib, General purpose
@subsection random_lib
@c include of docu for random.lib
@include d2t_singular/random_lib.tex
@c ----------------------------------------------------------
@node ring_lib, , random_lib, General purpose
@subsection ring_lib
@c include of docu for ring.lib
@include d2t_singular/ring_lib.tex
@c ----------------------------------------------------------------------------
@node Linear algebra, Commutative algebra, General purpose, SINGULAR libraries
@section Linear algebra
@cindex Linear algebra

@menu
* matrix_lib:: procedures for matrix operations
* linalg_lib:: procedures for algorithmic linear algebra
@end menu

@c ----------------------------------------------------------
@node matrix_lib, linalg_lib,  Linear algebra, Linear algebra
@subsection matrix_lib
@c include of docu for matrix.lib
@include d2t_singular/matrix_lib.tex
@c ---------------------------------------------------------
@node linalg_lib, , matrix_lib, Linear algebra
@subsection linalg_lib
@c include of docu for linalg.lib
@include d2t_singular/linalg_lib_noEx.tex
@c ----------------------------------------------------------------------------
@node Commutative algebra, Singularities, Linear algebra, SINGULAR libraries
@section Commutative algebra
@cindex Commutative algebra

@menu
* algebra_lib:: procedures for computing with algebras and maps
* elim_lib:: procedures for elimination, saturation and blowing up
* homolog_lib:: procedures for homological algebra
* mprimdec_lib:: procedures for primary decomposition of modules
* mregular_lib:: procedures for Castelnuovo-Mumford regularity
* normal_lib:: procedure for normalization
* primdec_lib:: procedures for primary decomposition
* primitiv_lib:: procedures for finding a primitive element
* reesclos_lib:: Rees Algebra and integral closure of an ideal
* intprog_lib:: Integer Programming
* toric_lib:: toric ideals
@end menu

@c ---------------------------------------------------------
@node algebra_lib, elim_lib, Commutative algebra, Commutative algebra
@subsection algebra_lib
@c include of docu for algebra.lib
@include d2t_singular/algebra_lib.tex
@c ----------------------------------------------------------
@node elim_lib, homolog_lib, algebra_lib, Commutative algebra
@subsection elim_lib
@c include of docu for elim.lib
@include d2t_singular/elim_lib.tex
@c ----------------------------------------------------------
@node homolog_lib, mprimdec_lib, elim_lib, Commutative algebra
@subsection homolog_lib
@c include of docu for homolog.lib
@include d2t_singular/homolog_lib.tex
@c ----------------------------------------------------------
@node mprimdec_lib, mregular_lib, homolog_lib, Commutative algebra
@subsection mprimdec_lib
@c include of docu for mprimdec.lib
@include d2t_singular/mprimdec_lib.tex
@c ----------------------------------------------------------
@node mregular_lib, normal_lib, mprimdec_lib, Commutative algebra
@subsection mregular_lib
@c include of docu for mregular.lib
@include d2t_singular/mregular_lib.tex
@c ---------------------------------------------------------
@node normal_lib, primdec_lib, mregular_lib, Commutative algebra
@subsection normal_lib
@c include of docu for normal.lib
@include d2t_singular/normal_lib.tex
@c ----------------------------------------------------------
@node primdec_lib, primitiv_lib, normal_lib, Commutative algebra
@subsection primdec_lib
@c include of docu for primdec.lib
@include d2t_singular/primdec_lib.tex
@c ---------------------------------------------------------
@node primitiv_lib, reesclos_lib, primdec_lib, Commutative algebra
@subsection primitiv_lib
@c include of docu for primitiv.lib
@include d2t_singular/primitiv_lib.tex
@c ---------------------------------------------------------
@node reesclos_lib, intprog_lib, primitiv_lib, Commutative algebra
@subsection reesclos_lib
@c include of docu for reesclos.lib
@include d2t_singular/reesclos_lib.tex
@c ---------------------------------------------------------
@node intprog_lib, toric_lib, reesclos_lib, Commutative algebra
@subsection intprog_lib
@c include of docu for intprog.lib
@include d2t_singular/intprog_lib.tex
@c ---------------------------------------------------------
@node toric_lib, ,intprog_lib, Commutative algebra
@subsection toric_lib
@c include of docu for toric.lib
@include d2t_singular/toric_lib.tex
@c ----------------------------------------------------------------------------
@node Singularities, Invariant theory, Commutative algebra, SINGULAR libraries
@section Singularities
@cindex Singularities

@menu
@c * alexpoly_lib:: Resolution Graph and Alexander Polynomial
* classify_lib:: procedures for the Arnold-classifier of singularities
* deform_lib:: procedures for computing miniversal deformation
* equising_lib:: procedures for equisingularity strata
* gaussman_lib:: procedures for gauss-manin connection of a singularity
* hnoether_lib:: procedures for the Hamburger-Noether (Puiseux) development
* mondromy_lib:: procedures to compute the monodromy of a singularity
* qhmoduli_lib:: procedures for moduli spaces of sqh-singularities
* sing_lib:: procedures for computing invariants of singularities
* spcurve_lib:: procedures for cm codimension 2 singularities
* spectrum_lib:: procedures for computing singularity spectra
@end menu

@c ---------------------------------------------------------
@c @node alexpoly_lib, classify_lib, Singularities, Singularities
@c @subsection alexpoly_lib
@c @c lib alexpoly.lib
@c ---------------------------------------------------------
@c @node classify_lib, deform_lib, alexpoly_lib, Singularities
@node classify_lib, deform_lib, Singularities, Singularities
@subsection classify_lib
@c include of docu for classify.lib
@include d2t_singular/classify_lib.tex
@c ----------------------------------------------------------
@node deform_lib, equising_lib, classify_lib, Singularities
@subsection deform_lib
@c include of docu for deform.lib
@include d2t_singular/deform_lib.tex
@c ----------------------------------------------------------
@node equising_lib, gaussman_lib, deform_lib, Singularities
@subsection equising_lib
@c include of docu for equising.lib
@include d2t_singular/equising_lib.tex
@c ----------------------------------------------------------
@node gaussman_lib, hnoether_lib, equising_lib, Singularities
@subsection gaussman_lib
@c include of docu for gaussman.lib
@include d2t_singular/gaussman_lib.tex
@c ---------------------------------------------------------
@node hnoether_lib, mondromy_lib, gaussman_lib, Singularities
@subsection hnoether_lib
@c include of docu for hnoether.lib
@include d2t_singular/hnoether_lib.tex
@c ---------------------------------------------------------
@node mondromy_lib, qhmoduli_lib, hnoether_lib, Singularities
@subsection mondromy_lib
@c include of docu for mondromy.lib
@include d2t_singular/mondromy_lib.tex
@c ---------------------------------------------------------
@node qhmoduli_lib, sing_lib, mondromy_lib, Singularities
@subsection qhmoduli_lib
@c include of docu for qhmoduli.lib
@include d2t_singular/qhmoduli_lib.tex
@c ----------------------------------------------------------
@node sing_lib, spcurve_lib, qhmoduli_lib, Singularities
@subsection sing_lib
@c include of docu for sing.lib
@include d2t_singular/sing_lib.tex
@c ---------------------------------------------------------
@node spcurve_lib, spectrum_lib, sing_lib, Singularities
@subsection spcurve_lib
@c include of docu for spcurve.lib
@include d2t_singular/spcurve_lib.tex
@c ---------------------------------------------------------
@node spectrum_lib, , spcurve_lib, Singularities
@subsection spectrum_lib
@c include of docu for spectrum.lib
@include d2t_singular/spectrum_lib.tex
@c ----------------------------------------------------------------------------
@node Invariant theory, Symbolic-numerical solving, Singularities, SINGULAR libraries
@section Invariant theory
@cindex Invariant theory

@menu
* finvar_lib:: procedures to compute invariant rings of finite groups
* ainvar_lib:: procedures to compute invariants rings of the additive group
* rinvar_lib:: procedures to compute invariants ring of reductive groups
* stratify_lib:: algorithmic stratification by the Greuel-Pfister algorithm
@end menu

@c ----------------------------------------------------------
@node finvar_lib, ainvar_lib, Invariant theory, Invariant theory
@subsection finvar_lib
@c include of docu for finvar.lib
@include d2t_singular/finvar_lib.tex
@c ----------------------------------------------------------
@node ainvar_lib, rinvar_lib, finvar_lib, Invariant theory
@subsection ainvar_lib
@c include of docu for ainvar.lib
@include d2t_singular/ainvar_lib.tex
@c ----------------------------------------------------------
@node rinvar_lib, stratify_lib, ainvar_lib, Invariant theory
@subsection rinvar_lib
@c include of docu for rinvar.lib
@include d2t_singular/rinvar_lib.tex
@c ----------------------------------------------------------
@node stratify_lib, ,rinvar_lib, Invariant theory
@subsection stratify_lib
@c include of docu for stratify.lib
@include d2t_singular/stratify_lib.tex
@c ----------------------------------------------------------------------------
@node Symbolic-numerical solving, Visualization, Invariant theory, SINGULAR libraries
@section Symbolic-numerical solving
@cindex Symbolic-numerical solving

@menu
* presolve_lib:: procedures for pre-solving polynomial equations
* solve_lib:: procedures to solve polynomial systems
* triang_lib:: procedures for decomposing zero-dimensional ideals
* ntsolve_lib:: one real solution of polynomial systems (Newton iteration)
* zeroset_lib:: procedures for roots and factorization
@end menu

@c ---------------------------------------------------------
@node presolve_lib, solve_lib, Symbolic-numerical solving, Symbolic-numerical solving
@subsection presolve_lib
@c include of docu for presolve.lib
@include d2t_singular/presolve_lib.tex
@c ---------------------------------------------------------
@node solve_lib, triang_lib, presolve_lib, Symbolic-numerical solving
@subsection solve_lib
@c include of docu for solve.lib
@include d2t_singular/solve_lib.tex
@c ---------------------------------------------------------
@node triang_lib, ntsolve_lib,  solve_lib, Symbolic-numerical solving
@subsection triang_lib
@c include of docu for triang.lib
@include d2t_singular/triang_lib_noEx.tex
@c ---------------------------------------------------------
@node ntsolve_lib, zeroset_lib, triang_lib, Symbolic-numerical solving
@subsection ntsolve_lib
@c include of docu for ntsolve.lib
@include d2t_singular/ntsolve_lib.tex
@c ---------------------------------------------------------
@node zeroset_lib, , ntsolve_lib, Symbolic-numerical solving
@subsection zeroset_lib
@c include of docu for zeroset.lib
@include d2t_singular/zeroset_lib.tex

@c ----------------------------------------------------------------------------
@node Visualization, Coding theory, Symbolic-numerical solving, SINGULAR libraries
@section Visualization
@cindex Visualization

@menu
* graphics_lib:: procedures to draw  with Mathematica
* latex_lib:: procedures for typesetting in TeX
* paramet_lib:: procedures for parametrizations
* surf_lib:: interface to the surf program
@end menu

@c ---------------------------------------------------------
@node graphics_lib, latex_lib, Visualization, Visualization
@subsection graphics_lib
@c include of docu for graphics.lib
@include d2t_singular/graphics_lib_noEx.tex
@c ---------------------------------------------------------
@node latex_lib, paramet_lib, graphics_lib, Visualization
@subsection latex_lib
@c include of docu for latex.lib
@include d2t_singular/latex_lib.tex
@c ---------------------------------------------------------
@node paramet_lib, surf_lib, latex_lib, Visualization
@subsection paramet_lib
@c include of docu for paramet.lib
@include d2t_singular/paramet_lib.tex
@c ---------------------------------------------------------
@node surf_lib,, paramet_lib, Visualization
@subsection surf_lib
@c include of docu for surf.lib
@include d2t_singular/surf_lib_noEx.tex

@c ----------------------------------------------------------------------------
@node Coding theory, , Visualization, SINGULAR libraries
@section Coding theory
@cindex Coding theory

@menu
* brnoeth_lib:: Brill-Noether algorithm, Weierstrass semigroups and AG codes
@end menu

@c ---------------------------------------------------------
@node brnoeth_lib, , , Coding theory
@subsection brnoeth_lib
@c include of docu for brnoeth.lib
@include d2t_singular/brnoeth_lib.tex
@c ----------------------------------------------------------
@node Release Notes, Index, SINGULAR libraries, Top
@chapter Release Notes
@cindex Release Notes
@include platform.tex

@c ----------------------------------------------------------
@node Index, , Release Notes, Top
@chapter Index
@cindex Index
@printindex cp
@c ---------------------------------------------------------

@c generate table of content and short table of content
@contents
@bye


code:
@comment -*-texinfo-*-
@comment This file was generated by doc2tex.pl from start.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT start.doc INSTEAD
@comment Id: start.tex,v 1.1 2003/08/08 14:27:06 pertusus Exp $
@comment this file contains the "Introduction" chapter.
@c * wichmann: + added changes by GMG.

@c The following directives are necessary for proper compilation
@c with emacs (C-c C-e C-r).  Please keep it as it is.  Since it
@c is wrapped in `@ignore' and `@end ignore' it does not harm `tex' or
@c `makeinfo' but is a great help in editing this file (emacs
@c ignores the `@ignore').
@ignore
%**start
\input texinfo.tex
@setfilename start.hlp
@node Top, Introduction
@menu
* Introduction::
@end menu
@node Introduction, General concepts, Preface, Top
@chapter Introduction
%**end
@end ignore

@ifset singularmanual
@menu
* Background::
* How to use this manual::
* Getting started::
@end menu
@end ifset
@ifclear singularmanual
@menu
* Background::
* How to use this tutorial::
* Getting started::
@end menu
@end ifclear

@c ------------------------------------------------------------------
@ifset singularmanual
@node Background, How to use this manual, Introduction, Introduction
@end ifset
@ifclear singularmanual
@node Background, How to use this tutorial, Introduction, Introduction
@end ifclear
@section Background
@cindex Background

@sc{Singular} is a Computer Algebra system for polynomial
computations with emphasis on the special needs of commutative
algebra, algebraic geometry, and singularity theory.

@sc{Singular}'s main computational objects are ideals and
modules over a large variety of baserings. The baserings are polynomial
rings or localizations thereof over a field (e.g., finite fields, the
rationals, floats, algebraic extensions, transcendental extensions) or
quotient rings with respect to an ideal.

@sc{Singular} features one of the fastest and most general
implementations of various algorithms for computing Groebner
resp.@: standard bases. The implementation includes Buchberger's algorithm
(if the ordering is a well ordering) and Mora's algorithm (if the
ordering is a tangent cone ordering) as special cases.  Furthermore, it
provides polynomial factorizations, resultant, characteristic set and
gcd computations, syzygy and free-resolution computations, and many more
related functionalities.

Based on an easy-to-use interactive shell and a C-like programming
language, @sc{Singular}'s internal functionality is augmented and
user-extendible by libraries written in the @sc{Singular} programming
language. A general and efficient implementation of communication links
allows @sc{Singular} to make its functionality available to other
programs.

@sc{Singular}'s development started in 1984 with an implementation of
Mora's Tangent Cone algorithm in Modula-2 on an Atari computer (K.P.
Neuendorf, G. Pfister,
@ifinfo
H.@: Schoenemann; Humboldt-Universitaet
@end ifinfo
@tex
H.\ Sch\"onemann; Humboldt-Universit\"at
@end tex
 zu Berlin).  The need for a new system arose from the investigation of
mathematical problems coming from singularity theory which none of the
existing systems was able to compute.

In the early 1990s @sc{Singular}'s "home-town" moved to
Kaiserslautern, a general standard basis algorithm was implemented in C
and @sc{Singular} was ported to Unix, MS-DOS, Windows NT, and MacOS.

Continuous extensions (like polynomial factorization, gcd computations,
links) and refinements led in 1997 to the release of @sc{Singular}
version 1.0 and in 1998 to the release of version 1.2
(much faster standard and Groebner bases computations based on Hilbert series
and on improved implementations of the algorithms,
libraries for primary decomposition, ring normalization, etc.)

For the highlights of the new @sc{Singular} version @value{VERSION} see @ref{News and changes}.

@c Thus, we hope to offer a useful system
@c for dealing with local and global computational aspects
@c of systems of polynomial equations.

@c ------------------------------------------------------------------
@ifset singularmanual
@node How to use this manual, Getting started, Background, Introduction
@section How to use this manual
@cindex How to use this manual
@end ifset
@ifclear singularmanual
@node How to use this tutorial, Getting started, Background, Introduction
@section How to use this tutorial
@cindex How to use this tutorial
@end ifclear

@ifset singularmanual
@subsubheading For the impatient user
@end ifset
In @ref{Getting started}, some simple examples explain how to use
@sc{Singular}  in a step-by-step manner.

@ref{Examples} should come next for real learning-by-doing or to quickly
solve some given mathematical problems without dwelling too deeply into
@sc{Singular}.
@ifset singularmanual
This chapter contains a lot of real-life examples and
detailed instructions and explanations on how to solve mathematical
problems using @sc{Singular}.
@end ifset

@c ------------------------------------------------------------------------
@ifset singularmanual
@subsubheading For the systematic user
In @ref{General concepts}, all basic concepts which are important to use
and to understand @sc{Singular} are developed.  But even for users
preferring the systematic approach it will be helpful to have a look at
the examples in @ref{Getting started}, every now and then. The topics in
the chapter are organized more or less in the order the novice user has
to deal with them.

@itemize @bullet
@item
In @ref{Interactive use}, and its subsections there are some words on
entering and exiting @sc{Singular}, followed by a number of other
aspects concerning the interactive user-interface.

@item
To do anything more than trivial integer computations, one needs to
define a basering in @sc{Singular}.  This is explained in detail in
@ref{Rings and orderings}.

@item
An overview of the algorithms implemented in the kernel of @sc{Singular}
is given in @ref{Implemented algorithms}.

@item
In @ref{The SINGULAR language}, language specific concepts are
introduced such as the notions of names and objects, data types and
conversion between them, etc.

@item
In @ref{Input and output}, @sc{Singular}'s mechanisms to store and
retrieve data are discussed.

@item
The more complex concepts of procedures and libraries as
well as tools to debug them are considered in the following sections:
@ref{Procedures}, @ref{Libraries}, and @ref{Debugging tools}.

@end itemize

@ref{Data types}, is a complete treatment for @sc{Singular}'s data types
where each section corresponds to one data type, alphabetically sorted.
For each data type, its purpose is explained, the syntax of its
declaration is given, and related operations and functions are
listed. Examples illustrate its usage.

@ref{Functions and system variables}, is an alphabetically ordered
reference list of all of @sc{Singular}'s functions, control structures,
and system variables.  Each entry includes a description of the syntax
and semantics of the item being explained as well as one or more
examples on how to use it.

@subsubheading Miscellaneous
@ref{Tricks and pitfalls}, is a loose collection of limitations and
features which may be unexpected by those who expect the
@sc{Singular} language to be an exact copy of the C programming language or of
some Computer Algebra system's languages.  But some mathematical hints are
collected there, as well.

@ref{Mathematical background}, introduces some of the mathematical
notions and definitions used throughout this manual.  For example, if in
doubt what exactly @sc{Singular} means by a ``negative degree reverse
lexicographical ordering'' one should refer to this chapter.

@ref{SINGULAR libraries}, lists the
libraries which come with @sc{Singular} and the functions contained in
them, respectively.
@end ifset
@c ------------------------------------------------------------------------

@subsubheading Typographical conventions
Throughout this manual, the following typographical conventions are
adopted:

@itemize @bullet
@item
text in @code{typewriter} denotes @sc{Singular} input and output as well
as reserved names:

@itemize @asis
@item The basering can be set using the command @code{setring}.
@end itemize

@item
the arrow @expansion{} denotes @sc{Singular} output:

@itemize @asis
@item @code{poly p=x+y+z;}
@item @code{p*p;}
@item @code{@expansion{} x2+2xy+y2+2xz+2yz+z2}
@end itemize

@item
square brackets are used to denote parts of syntax descriptions which
are optional:

@itemize @asis
[optional_text] required_text
@end itemize

@item
keys are denoted using typewriter, for example:

@itemize @asis
@item @code{N} (press the key @code{N} to get to the next node in help
mode)
@item @code{RETURN} (press @code{RETURN} to finish an input line)
@item @code{CTRL-P} (press control key together with the key @code{P} to
get the previous input line)
@end itemize

@end itemize

@c ------------------------------------------------------------------
@ifset singularmanual
@node Getting started,  , How to use this manual, Introduction
@section Getting started
@end ifset
@ifclear singularmanual
@node Getting started,  , How to use this tutorial, Introduction
@chapter Getting started
@end ifclear
@cindex Getting started

@sc{Singular} is a special purpose system for polynomial
computations. Hence, most of the powerful computations in @sc{Singular}
require the prior definition of a ring. Most important rings are
polynomial rings over a field, localizations hereof, or quotient rings of
such rings modulo an ideal. However, some simple computations with
integers (machine integers of limited size) and manipulations of strings
are available without a ring.

@menu
* First steps::
* Rings and standard bases::
* Procedures and libraries::
* Change of rings::
* Modules and their annihilator::
* Resolution::
@end menu

@c ------------------------------------------------------------------
@node First steps, Rings and standard bases, Getting started, Getting started
@ifset singularmanual
@subsection First steps
@end ifset
@ifclear singularmanual
@section First steps
@end ifclear
@cindex First steps

Once @sc{Singular} is started, it awaits an input after the prompt
@code{>}.  Every statement has to be terminated by @code{;} .

@smallexample
37+5;
@expansion{} 42
@end smallexample

All objects have a type, e.g., integer variables are defined by
the word @code{int}. An assignment is done by the symbol @code{=} .

@smallexample
int k = 2;
@end smallexample

@noindent Test for equality resp.@: inequality is done using @code{==}
resp.@: @code{!=} (or @code{<>}), where @code{0} represents the boolean
value FALSE, any other value represents TRUE.

@smallexample
k == 2;
@expansion{} 1
k != 2;
@expansion{} 0
@end smallexample

@noindent The value of an object is displayed by simply typing its name.

@smallexample
k;
@expansion{} 2
@end smallexample

@noindent On the other hand the output is suppressed if an assignment
is made.

@smallexample
int j;
j = k+1;
@end smallexample

@noindent The last displayed (!) result is always available
with the special symbol @code{_} .

@smallexample
2*_;   // the value from k displayed above
@expansion{} 4
@end smallexample

Text starting with @code{//} denotes a comment and is ignored in
calculations, as seen in the previous example. Furthermore @sc{Singular}
maintains a history of the previous lines of input, which may be accessed by
@code{CTRL-P} (previous) and @code{CTRL-N} (next) or the arrows on the
keyboard. Note that the history is not available on Macintosh systems.

The whole manual is available online by typing the command @code{help;} .
Explanation on single topics, e.g., on @code{intmat}, which defines a
matrix of integers, are obtained by

@smallexample
help intmat;
@end smallexample

@ifset singularmanual
@noindent This shows the text of @ref{intmat}, in the printed manual.
@end ifset
@ifclear singularmanual
@noindent This shows the text from node @code{intmat}, in the printed manual.
@end ifclear

Next, we define a
@tex
$3 \times 3$
@end tex
@ifinfo
3 x 3
@end ifinfo
 matrix of integers and initialize it with some values, row by row
from left to right:

@smallexample
intmat m[3][3] = 1,2,3,4,5,6,7,8,9;
@end smallexample

@noindent A single matrix entry may be selected and changed using
square brackets @code{[} and @code{]}.

@smallexample
m[1,2]=0;
m;
@expansion{} 1,0,3,
@expansion{} 4,5,6,
@expansion{} 7,8,9
@end smallexample

To calculate the trace of this matrix, we use a @code{for} loop. The
curly brackets @code{@{} and @code{@}} denote the beginning resp.@:
end of a block. If you define a variable without giving an initial
value, as the variable @code{tr} in the example below, @sc{Singular}
assigns a default value for the specific type. In this case, the default
value for integers is @code{0}. Note that the integer variable @code{j}
has already been defined above.

@smallexample
int tr;
for ( j=1; j <= 3; j++ ) @{ tr=tr + m[j,j]; @}
tr;
@expansion{} 15
@end smallexample

Variables of type string can also be defined and used without a ring
being active. Strings are delimited by @code{"} (double quotes). They
may be used to comment the output of a computation or to give it a nice
format. If a string contains valid @sc{Singular} commands, it can be
executed using the function @code{execute}. The result is the same as if
the commands would have been written on the command line. This feature
is especially useful to define new rings inside procedures.

@smallexample
"example for strings:";
@expansion{} example for strings:
string s="The element of m ";
s = s + "at position [2,3] is:";  // concatenation of strings by +
s , m[2,3] , ".";
@expansion{} The element of m at position [2,3] is: 6 .
s="m[2,1]=0; m;";
execute(s);
@expansion{} 1,0,3,
@expansion{} 0,5,6,
@expansion{} 7,8,9
@end smallexample

This example shows that expressions can be separated by @code{,} (comma)
giving a list of expressions. @sc{Singular} evaluates each expression in
this list and prints all results separated by spaces.

@c ------------------------------------------------------------------
@node Rings and standard bases, Procedures and libraries, First steps, Getting started
@ifset singularmanual
@subsection Rings and standard bases
@end ifset
@ifclear singularmanual
@section Rings and standard bases
@end ifclear
@cindex Rings and standard bases

To calculate with objects as ideals, matrices, modules, and polynomial
vectors, a ring has to be defined first.

@smallexample
ring r = 0,(x,y,z),dp;
@end smallexample

The definition of a ring consists of three parts: the first part
determines the ground field, the second part determines the names of the
ring variables, and the third part determines the monomial ordering to
be used. So the example above declares a polynomial ring called @code{r}
with a ground field of characteristic
@ifinfo
@math{0}
@end ifinfo
@tex
$0$
@end tex
 (i.e., the rational
numbers) and ring variables called @code{x}, @code{y}, and @code{z}. The
@code{dp} at the end means that the degree reverse lexicographical
ordering should be used.

Other ring declarations:

@table @code
@item ring r1=32003,(x,y,z),dp;
characteristic 32003, variables @code{x}, @code{y}, and @code{z} and
ordering @code{dp}.

@item ring r2=32003,(a,b,c,d),lp;
characteristic 32003, variable names @code{a}, @code{b}, @code{c},
@code{d} and lexicographical ordering.

@item ring r3=7,(x(1..10)),ds;
characteristic 7, variable names @code{x(1)},@dots{},@code{x(10)}, negative
degree reverse lexicographical ordering (@code{ds}).

@item ring r4=(0,a),(mu,nu),lp;
transcendental extension of
@ifinfo
@math{Q}
@end ifinfo
@tex
$Q$
@end tex
 by
@ifinfo
@math{a}
@end ifinfo
@tex
$a$
@end tex
, variable names
@code{mu} and @code{nu}.

@item ring r5=real,(a,b),lp;
floating point numbers (single machine precision),
variable names @code{a} and @code{b}.

@item ring r6=(real,50),(a,b),lp;
floating point numbers with extended precision of 50 digits,
variable names @code{a} and @code{b}.

@item ring r7=(complex,50,i),(a,b),lp;
complex floating point numbers with extended precision of 50 digits
and imaginary unit @code{i},
variable names @code{a} and @code{b}.
@end table

@c Another valid characteristic would be, for example, a prime number less
@c or equal to 32003. The name of the ring variables may be any
@c valid @sc{Singular} name. Even indexed names are allowed, so
@c @code{x(1..10)} specifies the ring variables @code{x(1)}, @dots{},
@c @code{x(10)}. @sc{Singular} offers the possibility to calculate with any
@c monomial ordering, some orderings are predefined with special names like
@c @code{dp} in the example above. Another important example is the
@c lexicographical ordering called @code{lp}.
@c
Typing the name of a ring prints its definition. The example below
shows that the default ring in @sc{Singular} is
@ifinfo
@math{Z/32003[x,y,z]}
@end ifinfo
@tex
$Z/32003[x,y,z]$
@end tex

with degree reverse lexicographical ordering:

@smallexample
@c computed example Rings_and_standard_bases start.doc:494
ring r8;
r8;
@expansion{} //   characteristic : 32003
@expansion{} //   number of vars : 3
@expansion{} //        block   1 : ordering dp
@expansion{} //                  : names    x y z
@expansion{} //        block   2 : ordering C
@c end example Rings_and_standard_bases start.doc:494
@end smallexample

Defining a ring makes this ring the current active basering, so each
ring definition above switches to a new basering. The concept of rings
in @sc{Singular} is discussed in detail in
@ifset singularmanual
@ref{Rings and orderings}.
@end ifset
@ifclear singularmanual
the chapter "Rings and orderings" of the @sc{Singular} manual.
@end ifclear

The basering is now @code{r8}. Since we want to calculate in the ring
@code{r}, which we defined first, we have to switch back to it. This can
be done using the function @code{setring}:

@smallexample
setring r;
@end smallexample

Once a ring is active, we can define polynomials. A monomial, say
@tex
$x^3$
@end tex
@ifinfo
x^3
@end ifinfo
may be entered in two ways: either using the power operator @code{^},
saying @code{x^3}, or in short-hand notation without operator, saying
@code{x3}. Note that the short-hand notation is forbidden if the name
of the ring variable consists of more than one character. Note, that
@sc{Singular} always expands brackets and automatically sorts the terms
with respect to the monomial ordering of the basering.

@smallexample
poly f =  x3+y3+(x-y)*x2y2+z2;
f;
@expansion{} x3y2-x2y3+x3+y3+z2
@end smallexample

The command @code{size} determines in general the number of ''single
entries`` in an object. In particular, for polynomials, @code{size}
determines the number of monomials.

@smallexample
size(f);
@expansion{} 5
@end smallexample

A natural question is to ask if a point, e.g., @code{(x,y,z)=(1,2,0)}, lies
on the variety defined by the polynomials @code{f} and @code{g}. For
this we define an ideal generated by both polynomials, substitute the
coordinates of the point for the ring variables, and check if the result
is zero:

@smallexample
poly g =  f^2 *(2x-y);
ideal I = f,g;
ideal J = subst(I,var(1),1);
J = subst(J,var(2),2);
J = subst(J,var(3),0);
J;
@expansion{} J[1]=5
@expansion{} J[2]=0
@end smallexample

@noindent Since the result is not zero, the point @code{(1,2,0)} does
not lie on the variety @code{V(f,g)}.

Another question is to decide whether some function vanishes on a
variety, or in algebraic terms if a polynomial is contained in a given
ideal. For this we calculate a standard basis using the command
@code{groebner} and afterwards reduce the polynomial with respect to
this standard basis.

@smallexample
ideal sI = groebner(f);
reduce(g,sI);
@expansion{} 0
@end smallexample

@noindent As the result is @code{0} the polynomial @code{g} belongs to the
ideal defined by @code{f}.

The function @code{groebner}, like many other functions in
@sc{Singular}, prints a protocol during calculations, if desired. The
command @code{option(prot);} enables protocolling whereas
@code{option(noprot);} turns it off.
@ifset singularmanual
@ref{option}, explains the meaning
of the different symbols printed during calculations.
@end ifset

The command @code{kbase} calculates a basis of the polynomial ring
modulo an ideal, if the quotient ring is finite dimensional.
As an example we calculate the Milnor number of a
hypersurface singularity in the global and local case. This is the
vector space dimension of the polynomial ring modulo the Jacobian ideal
in the global case resp.@: of the power series ring modulo the Jacobian
ideal in the local case. @xref{Critical points}, for a detailed
explanation.

The Jacobian ideal is obtained with the command @code{jacob}.

@smallexample
ideal J = jacob(f);
@expansion{} // ** redefining J **
J;
@expansion{} J[1]=3x2y2-2xy3+3x2
@expansion{} J[2]=2x3y-3x2y2+3y2
@expansion{} J[3]=2z
@end smallexample

@noindent @sc{Singular} prints the line @code{// ** redefining J
**}. This indicates that we have previously defined a variable with name
@code{J} of type ideal (see above).

To obtain a representing set of the quotient vector space we first
calculate a standard basis, then we apply the function @code{kbase} to
this standard basis.

@smallexample
J = groebner(J);
ideal K = kbase(J);
K;
@expansion{} K[1]=y4
@expansion{} K[2]=xy3
@expansion{} K[3]=y3
@expansion{} K[4]=xy2
@expansion{} K[5]=y2
@expansion{} K[6]=x2y
@expansion{} K[7]=xy
@expansion{} K[8]=y
@expansion{} K[9]=x3
@expansion{} K[10]=x2
@expansion{} K[11]=x
@expansion{} K[12]=1
@end smallexample

@noindent Then

@smallexample
size(K);
@expansion{} 12
@end smallexample

@noindent gives the desired vector space dimension
@tex
$K[x,y,z]/\hbox{\rm jacob}(f)$.
@end tex
@ifinfo
K[x,y,z]/jacob(f).
@end ifinfo
As in @sc{Singular} the functions may take the input directly from
earlier calculations, the whole sequence of commands may be written
in one single statement.

@smallexample
size(kbase(groebner(jacob(f))));
@expansion{} 12
@end smallexample

When we are not interested in a basis of the quotient vector space, but
only in the resulting dimension we may even use the command @code{vdim}
and write:

@smallexample
vdim(groebner(jacob(f)));
@expansion{} 12
@end smallexample

@c ------------------------------------------------------------------
@node Procedures and libraries, Change of rings, Rings and standard bases, Getting started
@ifset singularmanual
@subsection Procedures and libraries
@end ifset
@ifclear singularmanual
@section Procedures and libraries
@end ifclear
@cindex Procedures and libraries

@sc{Singular} offers a comfortable programming language, with a syntax
close to C. So it is possible to define procedures which collect several
commands to a new one. Procedures are defined with the keyword
@code{proc} followed by a name and an optional parameter list with
specified types.  Finally, a procedure may return values using the
command @code{return}.

Define the following procedure called @code{Milnor}:

@smallexample
proc Milnor (poly h)
@{
  return(vdim(groebner(jacob(h))));
@}
@end smallexample

Note: if you have entered the first line of the procedure and pressed
@code{RETURN}, @sc{Singular} prints the prompt @code{.} (dot) instead of
the usual prompt @code{>} . This shows that the input is incomplete and
@sc{Singular} expects more lines. After typing the closing curly
bracket, @sc{Singular} prints the usual prompt indicating that the input
is now complete.

@noindent Then call the procedure:

@smallexample
Milnor(f);
@expansion{} 12
@end smallexample

@noindent Note that the result may depend on the basering as we will
see in the next chapter.

The distribution of  @sc{Singular} contains  several libraries, each of
which is a collection of useful
procedures based on the kernel commands, which extend the functionality
of @sc{Singular}. The command @code{help "all.lib";} lists all libraries
together with a one-line explanation.
@c The command @code{help}
@c library_name@code{;} lists all procedures of the library, @code{help}
@c proc_name@code{;} shows an explanation of the procedure after the
@c library has been loaded. The command @code{LIB "all.lib";} loads all
@c libraries.

One of these libraries is @code{sing.lib} which already contains a
procedure called @code{milnor} to calculate the Milnor number not only
for hypersurfaces but more generally for complete intersection
singularities.

Libraries are loaded with the command @code{LIB}. Some additional
information during the process of loading is displayed on the screen,
which we omit here.

@smallexample
LIB "sing.lib";
@end smallexample

As all input in @sc{Singular} is case sensitive, there is no conflict with
the previously  defined procedure @code{Milnor}, but the result is the same.

@smallexample
milnor(f);
@expansion{} 12
@end smallexample

The procedures in a library have a help part
which is displayed by typing

@smallexample
help milnor;
@c @expansion{} // proc milnor from lib sing.lib
@c @expansion{} proc milnor (ideal i)
@c @expansion{} USAGE:   milnor(i); i ideal or poly
@c @expansion{} RETURN:  Milnor number of i, if i is ICIS (isolated complete intersection
@c @expansion{}          singularity) in generic form, resp. -1 if not
@c @expansion{} NOTE:    use proc nf_icis to put generators in generic form
@c @expansion{}          printlevel >=0: display comments (default)
@c @expansion{} EXAMPLE: example milnor; shows an example
@c @expansion{}
@end smallexample

@noindent as well as some examples, which are executed by

@smallexample
example milnor;
@c @expansion{} // proc milnor from lib sing.lib
@c @expansion{} EXAMPLE:
@c @expansion{}    int p      = printlevel;
@c @expansion{}    printlevel = 1;
@c @expansion{}    ring r     = 32003,(x,y,z),ds;
@c @expansion{}    ideal j    = x5+y6+z6,x2+2y2+3z2,xyz+yx;
@c @expansion{}    milnor(j);
@c @expansion{} //sequence of discriminant numbers: 100,149,70
@c @expansion{} 21
@c @expansion{}    poly f     = x7+y7+(x-y)^2*x2y2+z2;
@c @expansion{}    milnor(f);
@c @expansion{} 28
@c @expansion{}    printlevel = p;
@c @expansion{}
@end smallexample

@noindent Likewise, the library itself has a help part, to show a list of
all the functions
available for the user which are contained in the library.

@smallexample
help sing.lib;
@end smallexample

@noindent The output of the help commands is omitted here.

@c ------------------------------------------------------------------
@node Change of rings, Modules and their annihilator, Procedures and libraries, Getting started
@ifset singularmanual
@subsection Change of rings
@end ifset
@ifclear singularmanual
@section Change of rings
@end ifclear
@cindex Change of rings

To calculate the local Milnor number we have to do the calculation with the
same commands in a ring with local ordering.
@ifset singularmanual
Define the localization of the polynomial ring at the origin
(@pxref{Polynomial data}, and @ref{Mathematical background}).
@end ifset
@ifclear singularmanual
Define the localization of the polynomial ring at the origin.
@end ifclear

@smallexample
ring rl = 0,(x,y,z),ds;
@end smallexample

This ordering determines the standard basis which will be calculated.
Fetch the polynomial defined in the ring @code{r} into this new ring,
thus avoiding retyping the input.

@smallexample
poly f = fetch(r,f);
f;
@expansion{} z2+x3+y3+x3y2-x2y3
@end smallexample

@noindent Instead of @code{fetch} we can use the function @code{imap}
which is more general but less efficient.
@ifset singularmanual
The most general way to fetch data from one ring to another is to use maps,
this will be explained in @ref{map}.
@end ifset
@ifclear singularmanual
The most general way to fetch data from one ring to another is to use maps.
@end ifclear

In this ring the terms are ordered by increasing exponents. The local Milnor
number is now

@smallexample
Milnor(f);
@expansion{} 4
@end smallexample

This shows that @code{f} has outside the origin in affine 3-space
singularities with local Milnor number adding up to
@tex
$12-4=8$.
@end tex
@ifinfo
12-4=8.
@end ifinfo
Using global and local orderings as above is a convenient way to check
whether a variety has singularities outside the origin.

The command @code{jacob} applied twice gives the Hessian of @code{f}, a
3x3 - matrix.

@smallexample
matrix H = jacob(jacob(f));
H;
@expansion{} H[1,1]=6x+6xy2-2y3
@expansion{} H[1,2]=6x2y-6xy2
@expansion{} H[1,3]=0
@expansion{} H[2,1]=6x2y-6xy2
@expansion{} H[2,2]=6y+2x3-6x2y
@expansion{} H[2,3]=0
@expansion{} H[3,1]=0
@expansion{} H[3,2]=0
@expansion{} H[3,3]=2
@end smallexample

The @code{print} command displays the matrix in a nicer form.

@smallexample
print(H);
@expansion{} 6x+6xy2-2y3,6x2y-6xy2,  0,
@expansion{} 6x2y-6xy2,  6y+2x3-6x2y,0,
@expansion{} 0,          0,          2
@end smallexample

We may calculate the determinant and (the ideal generated by all) minors of
a given size.

@smallexample
det(H);
@expansion{} 72xy+24x4-72x3y+72xy3-24y4-48x4y2+64x3y3-48x2y4
minor(H,1);  // the 1x1 - minors
@expansion{} _[1]=2
@expansion{} _[2]=6y+2x3-6x2y
@expansion{} _[3]=6x2y-6xy2
@expansion{} _[4]=6x2y-6xy2
@expansion{} _[5]=6x+6xy2-2y3
@end smallexample

The algorithm of the standard basis computations may be
affected by the command @code{option}. For example, a reduced standard
basis of the ideal generated by the
@tex
$1 \times 1$-minors
@end tex
@ifinfo
1 x 1 - minors
@end ifinfo
 of H  is obtained in the following way:
@smallexample
option(redSB);
groebner(minor(H,1));
@expansion{} _[1]=1
@end smallexample

This shows that 1 is contained in the ideal of the
@tex
$1 \times 1$-minors,
@end tex
@ifinfo
1 x 1 - minors,
@end ifinfo
hence the corresponding variety is empty.
@c Coming back to some mathematical considerations, we study the problem how
@c to calculate some ....

@c ------------------------------------------------------------------
@c REMEMBER TO EDIT NEXT AND PREVIOUS NODE IF YOU UNCOMMENT THIS NODE!
@c @node Maps and elimination, Modules and their annihilator, Change of rings, Getting started
@c @subsection Maps and elimination
@c @cindex Maps and elimination

@c ------------------------------------------------------------------
@node Modules and their annihilator, Resolution, Change of rings, Getting started
@ifset singularmanual
@subsection Modules and their annihilator
@end ifset
@ifclear singularmanual
@section Modules and their annihilator
@end ifclear
@cindex Modules and and their annihilator

Now we shall give three more advanced examples.

@sc{Singular} is able to handle modules over all the rings,
which can be defined as a basering. A free module of rank @code{n}
is defined as follows:

@smallexample
ring rr;
int n = 4;
freemodule(4);
@expansion{} _[1]=gen(1)
@expansion{} _[2]=gen(2)
@expansion{} _[3]=gen(3)
@expansion{} _[4]=gen(4)
typeof(_);
@expansion{} module
print(freemodule(4));
@expansion{} 1,0,0,0,
@expansion{} 0,1,0,0,
@expansion{} 0,0,1,0,
@expansion{} 0,0,0,1
@end smallexample

To define a module, we give a list of vectors generating a submodule of
a free module. Then this set of vectors may be identified with the
columns of a matrix.  For that reason in @sc{Singular} matrices and
modules may be interchanged. However, the representation is different
(modules may be considered as sparse represented matrices).

@smallexample
ring r =0,(x,y,z),dp;
module MD = [x,0,x],[y,z,-y],[0,z,-2y];
matrix MM = MD;
print(MM);
@expansion{} x,y,0,
@expansion{} 0,z,z,
@expansion{} x,-y,-2y
@end smallexample

However the submodule
@ifinfo
@math{MD}
@end ifinfo
@tex
$MD$
@end tex
 may also be considered as the module
of relations of the factor module
@tex
$r^3/MD$.
@end tex
@ifinfo
r^3/MD.
@end ifinfo
In this way, @sc{Singular} can treat arbitrary finitely generated modules
over the
@ifset singularmanual
basering (@pxref{Representation of mathematical objects}).
@end ifset
@ifclear singularmanual
basering.
@end ifclear

In order to get the module of relations of
@ifinfo
@math{MD}
@end ifinfo
@tex
$MD$
@end tex
,
we use the command @code{syz}.

@smallexample
syz(MD);
@expansion{} _[1]=x*gen(3)-x*gen(2)+y*gen(1)
@end smallexample

We want to calculate, as an application, the annihilator of a given module.
Let
@tex
$M = r^3/U$,
@end tex
@ifinfo
M = r^3/U,
@end ifinfo
where U is our defining module of relations for the module
@tex
$M$.
@end tex
@ifinfo
M.
@end ifinfo

@smallexample
module U = [z3,xy2,x3],[yz2,1,xy5z+z3],[y2z,0,x3],[xyz+x2,y2,0],[xyz,x2y,1];
@end smallexample

Then, by definition, the annihilator of M is the ideal
@tex
$\hbox{ann}(M) = \{a \mid aM = 0 \}$
@end tex
@ifinfo
ann(M) = @{a | aM = 0 @}
@end ifinfo
which is by the description of M the same as
@tex
$\{ a \mid ar^3 \in U \}$.
@end tex
@ifinfo
@{ a | ar^3 contained in U@}.
@end ifinfo
Hence we have to calculate the quotient
@tex
$U \colon r^3 $.
@end tex
@ifinfo
U:r^3.
@end ifinfo
The rank of the free module is determined by the choice of U and is the
number of rows of the corresponding matrix. This may be determined by
the function @code{nrows}. All we have to do now is the following:

@smallexample
quotient(U,freemodule(nrows(U)));
@end smallexample

@noindent The result is too big to be shown here.

@c ------------------------------------------------------------------
@node Resolution,  , Modules and their annihilator, Getting started
@ifset singularmanual
@subsection Resolution
@end ifset
@ifclear singularmanual
@section Resolution
@end ifclear
@cindex Resolution

There are several commands in @sc{Singular} for computing free resolutions.
The most general command is @code{res(... ,n)} which determines heuristically
what method to use for the given problem. It computes the free resolution
up to the length
@ifinfo
@math{n}
@end ifinfo
@tex
$n$
@end tex
, where
@ifinfo
@math{n=0}
@end ifinfo
@tex
$n=0$
@end tex
 corresponds to the full resolution.

Here we use the possibility to inspect the calculation process using the
option @code{prot}.

@smallexample
ring R;      // the default ring in char 32003
R;
@expansion{} //   characteristic : 32003
@expansion{} //   number of vars : 3
@expansion{} //        block   1 : ordering dp
@expansion{} //                  : names    x y z
@expansion{} //        block   2 : ordering C
ideal I = x4+x3y+x2yz,x2y2+xy2z+y2z2,x2z2+2xz3,2x2z2+xyz2;
option(prot);
resolution rs = res(I,0);
@expansion{} using lres
@expansion{} 4(m0)4(m1).5(m1)g.g6(m1)...6(m2)..
@end smallexample

@noindent Disable this protocol with

@smallexample
option(noprot);
@end smallexample

When we enter the name of the calculated resolution, we get a pictorial
description of the minimized resolution where the exponents denote the rank of the
free modules. Note that the calculated resolution itself may not yet be minimal.

@smallexample
rs;
@expansion{} 1      4      5      2      0
@expansion{}R  <-- R  <-- R  <-- R  <-- R
@expansion{}
@expansion{}0      1      2      3      4
print(betti(rs),"betti");
@expansion{}            0     1     2     3
@expansion{} ------------------------------
@expansion{}     0:     1     -     -     -
@expansion{}     1:     -     -     -     -
@expansion{}     2:     -     -     -     -
@expansion{}     3:     -     4     1     -
@expansion{}     4:     -     -     1     -
@expansion{}     5:     -     -     3     2
@expansion{} ------------------------------
@expansion{} total:     1     4     5     2
@end smallexample

In order to minimize the resolution, that is to calculate the maps of the minimal
free resolution, we use the command @code{minres}:

@smallexample
rs=minres(rs);
@end smallexample

A single module in this resolution is obtained (as usual) with the
brackets @code{[} and @code{]}. The @code{print} command can be used to
display a module in a more readable format:

@smallexample
print(rs[3]);
@expansion{} z3,   -xyz-y2z-4xz2+16z3,
@expansion{} 0,    -y2,
@expansion{} -y+4z,48z,
@expansion{} x+2z, 48z,
@expansion{} 0,    x+y-z
@end smallexample

In this case, the output is to be interpreted as follows: the 3rd syzygy
module of R/I, @code{rs[3]}, is the rank-2-submodule of
@tex
$R^5$
@end tex
@ifinfo
R^5
@end ifinfo
generated by the vectors
@tex
$(z^3,0,-y+4z,x+2z,0)$ and $(-xyz-y^2z-4xz^2+16z^3,-y^2,48z,48z,x+y-z)$.
@end tex
@ifinfo
(z^3,0,-y+4z,x+2z,0) and (-xyz-y^2z-4xz^2+16z^3,-y^2,48z,48z,x+y-z).
@end ifinfo


code:
texi singular.texi
singular_plain singular.texi --split chapter
#singular_html singular.texi --init-file t2h_singular.init --no-verbose --html


code:
texi singular.texi
singular_plain singular.texi --split chapter


code:
@menu
* Toric ideals::                Definition and computation.
* Integer programming::         An algorithm using toric ideals.
* Relevant References::
@end menu

@node Toric ideals, Integer programming, , Toric ideals and integer programming

@subsection Toric ideals
@cindex toric ideals
@comment This file was generated by doc2tex.pl from ti_ip.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT ti_ip.doc INSTEAD
@cindex ideal, toric

@tex
Let $A$ denote an $m\times n$ matrix with integral coefficients. For $u
\in Z\!\!\! Z^n$, we define $u^+,u^-$ to be the uniquely determined
vectors with nonnegative coefficients and disjoint support (i.e.,
$u_i^+=0$ or $u_i^-=0$ for each component $i$) such that
$u=u^+-u^-$. For $u\geq 0$ component-wise, let $x^u$ denote the monomial
$x_1^{u_1}\cdot\ldots\cdot x_n^{u_n}\in K[x_1,\ldots,x_n]$.

The ideal
$$ I_A:=<x^{u^+}-x^{u^-} | u\in\ker(A)\cap Z\!\!\! Z^n>\ \subset
K[x_1,\ldots,x_n] $$
is called a \bf toric ideal. \rm

The first problem in computing toric ideals is to find a finite
generating set: Let $v_1,\ldots,v_r$ be a lattice basis of $\ker(A)\cap
Z\!\!\! Z^n$ (i.e, a basis of the $Z\!\!\! Z$-module). Then
$$ I_A:=I:(x_1\cdot\ldots\cdot x_n)^\infty $$
where
$$ I=<x^{v_i^+}-x^{v_i^-}|i=1,\ldots,r> $$
@end tex

@ifinfo
Let A denote an mxn matrix with integral coefficients. For u in
Z^n, we define u+,u- to be the uniquely determined vectors with
nonnegative coefficients and disjoint support (i.e., u+[i]=0 or u-[i]=0
for each component i) such that u = u+ - u-.
For u>=0 component-wise, let x^u
denote the monomial x(1)^u[1] *@dots{}* x(n)^u[n] in K[x(1),@dots{},x(n)].

The ideal in K[x(1),@dots{},x(n)] @*
@display
I(A):= < x^u+ - x^u- | u in ker(A), u in Z^n >
@end display
is called a @strong{toric ideal}.

The first problem in computing toric ideals is to find a finite
generating set: Let v(1),@dots{},v(r) be a lattice basis of ker(A) as a
subset of Z^n (i.e., a basis of the Z-module). Then @*
@display
I(A):= sat( I, x[1] *@dots{}* x[n])
@end display
where @*
@display
I= < x^v(i)+ - x^v(i)- | i=1,@dots{},r >.
@end display
@end ifinfo

The required lattice basis can be computed using the LLL-algorithm (@pxref{[Coh93]}). For the computation of the saturation, there are various
possibilities described in the
@tex
section Algorithms.
@end tex
@ifinfo
menu entry Algorithms.
@end ifinfo

@menu
* Algorithms::             Various algorithms for computing toric ideals.
* Buchberger algorithm::   Specializing it for toric ideals.
@end menu

@node Algorithms, Buchberger algorithm, , Toric ideals
@subsection Algorithms

The following algorithms are implemented in @ref{toric_lib}.

@menu
* Conti and Traverso::
* Pottier::
* Hosten and Sturmfels::
* Di Biase and Urbanke::
* Bigatti and La Scala and Robbiano::
@end menu

@node Conti and Traverso, Pottier, , Algorithms

@subsubsection The algorithm of Conti and Traverso
@cindex Conti-Traverso algorithm
@cindex algorithm of Conti and Traverso

The algorithm of Conti and Traverso (@pxref{[CoTr91]})
@tex
computes $I_A$ via the
extended matrix $B=(I_m|A)$,
where $I_m$ is the $m\times m$ unity matrix. A lattice basis of $B$ is
given by the set of vectors $(a^j,-e_j)\in Z\!\!\! Z^{m+n}$, where $a^j$
is the $j$-th row of $A$ and $e_j$ the $j$-th coordinate vector. We
look at the ideal in $K[y_1,\ldots,y_m,x_1,\ldots,x_n]$ corresponding to
these vectors, namely
$$ I_1=<y^{a_j^+}- x_j y^{a_j^-} | j=1,\ldots, n>.$$
We introduce a further variable $t$ and adjoin the binomial $t\cdot
y_1\cdot\ldots\cdot y_m -1$ to the generating set of $I_1$, obtaining
an ideal $I_2$ in the polynomial ring $K[t,
y_1,\ldots,y_m,x_1,\ldots,x_n]$. $I_2$ is saturated w.r.t. all
variables because all variables are invertible modulo $I_2$. Now $I_A$
can be computed from $I_2$ by eliminating the variables
$t,y_1,\ldots,y_m$.
@end tex
@ifinfo
computes I(A) via the extended matrix B= ( I | A ),
where I is the mxm unity matrix. A lattice basis of B is given by the
set of vectors (a^j,-e_j) in Z^(m+n), where a^j is the j-th row of A and
e_j the j-th coordinate vector. We look at the ideal in
K[y(1),@dots{},y(m),x(1),@dots{},x(n)] corresponding to these vectors,
namely @*
@display
I1= < y^(a_j)+ - x(j) * y^(a_j)- | j=1,@dots{},n >.
@end display
We introduce a further variable t and adjoin the binomial t * y(1)
*@dots{}* y(m) -1 to the generating set of I1, obtaining an ideal I2 in
the polynomial ring K[t,y(1),@dots{},y(m),x(1),@dots{},x(n)]. I2 is
saturated w.r.t.@: all variables because all variables are invertible
modulo I2. Now I(A) can be computed from I2 by eliminating the variables
t,y(1),@dots{},y(m).
@end ifinfo

Because of the big number of auxiliary variables needed to compute a
toric ideal, this algorithm is rather slow in practice. However, it has
a special importance in the application to integer programming
(@pxref{Integer programming}).

@node Pottier, Hosten and Sturmfels, Conti and Traverso, Algorithms

@subsubsection The algorithm of Pottier
@cindex Pottier algorithm
@cindex algorithm of Pottier

The algorithm of Pottier (@pxref{[Pot94]}) starts by computing a lattice
@tex
basis $v_1,\ldots,v_r$ for the integer kernel of $A$ using the
LLL-algorithm. The ideal corresponding to the lattice basis vectors
$$ I_1=<x^{v_i^+}-x^{v_i^-}|i=1,\ldots,r> $$
is saturated -- as in the algorithm of Conti and Traverso -- by
inversion of all variables: One adds an auxiliary variable $t$ and the
generator $t\cdot x_1\cdot\ldots\cdot x_n -1$ to obtain an ideal $I_2$
in $K[t,x_1,\ldots,x_n]$ from which one computes $I_A$ by elimination of
$t$.
@end tex
@ifinfo
basis v(1),@dots{},v(r) for the integer kernel of A using the
LLL-algorithm. The ideal corresponding to the lattice basis vectors @*
@display
I1= < x^v(i)+ - x^v(i)- | i=1,@dots{},r >
@end display
is saturated -- as in the algorithm of Conti and Traverso -- by
inversion of all variables: One adds an auxiliary variable t and the
generator t * x(1) *@dots{}* x(n) -1 to obtain an ideal I2 in
K[t,x(1),@dots{},x(n)] from which one computes I(A) by elimination of
t.
@end ifinfo

@node Hosten and Sturmfels, Di Biase and Urbanke, Pottier, Algorithms

@subsubsection The algorithm of Hosten and Sturmfels
@cindex Hosten-Sturmfels algorithm
@cindex algorithm of Hosten and Sturmfels

The algorithm of Hosten and Sturmfels (@pxref{[HoSt95]}) allows to
@tex
compute $I_A$ without any auxiliary variables, provided that $A$ contains a vector $w$
with positive coefficients in its row space. This is a real restriction,
i.e., the algorithm will not necessarily work in the general case.

A lattice basis $v_1,\ldots,v_r$ is again computed via the
LLL-algorithm. The saturation step is performed in the following way:
First note that $w$ induces a positive grading w.r.t. which the ideal
$$ I=<x^{v_i^+}-x^{v_i^-}|i=1,\ldots,r> $$
corresponding to our lattice basis is homogeneous. We use the following
lemma:

Let $I$ be a homogeneous ideal w.r.t. the weighted reverse
lexicographical ordering with weight vector $w$ and variable order $x_1
> x_2 > \ldots > x_n$. Let $G$ denote a Groebner basis of $I$ w.r.t. to
this ordering.  Then a Groebner basis of $(I:x_n^\infty)$ is obtained by
dividing each element of $G$ by the highest possible power of $x_n$.

From this fact, we can successively compute
$$ I_A= I:(x_1\cdot\ldots\cdot x_n)^\infty
=(((I:x_1^\infty):x_2^\infty):\ldots :x_n^\infty); $$
in the $i$-th step we take $x_i$ as the cheapest variable and apply the
lemma with $x_i$ instead of $x_n$.

This procedure involves $n$ Groebner basis computations. Actually, this
number can be reduced to at most $n/2$
@end tex
@ifinfo
compute I(A) without any auxiliary variables, provided that A contains a vector w
with positive coefficients in its row space. This is a real restriction,
i.e., the algorithm will not necessarily work in the general case.

A lattice basis v(1),@dots{},v(r) is again computed via the
LLL-algorithm. The saturation step is performed in the following way:
First note that w induces a positive grading w.r.t.@: which the ideal @*
@display
I= < x^v(i)+ - x^v(i)- | i=1,@dots{},r >
@end display
corresponding to our lattice basis is homogeneous. We use the following
lemma:

Let I be a homogeneous ideal w.r.t.@: the weighted reverse lexicographical
ordering with weight vector w and variable order x(1) > x(2) > @dots{} >
x(n). Let G denote a Groebner basis of I w.r.t.@: to this ordering.  Then
a Groebner basis of sat(I,x(n)) is obtained by dividing each element
of G by the highest possible power of x(n).

From this fact, we can successively compute @*
@display
I(A)= sat(I, x(1) *@dots{}* x(n))
@ @ @ @ = sat(@dots{}(sat(sat(I,x(1)), x(2)), @dots{}, x(n)));
@end display
in the i-th step we take x(i) as the cheapest variable and apply the
lemma with x(i) instead of x(n).

This procedure involves n Groebner basis computations. Actually, this
number can be reduced to at most n/2
@end ifinfo
(@pxref{[HoSh98]}), and the single
computations -- except from the first one -- show to be easy and fast in
practice.

@node Di Biase and Urbanke, Bigatti and La Scala and Robbiano, Hosten and Sturmfels, Algorithms

@subsubsection The algorithm of Di Biase and Urbanke
@cindex Di Biase-Urbanke algorithm
@cindex algorithm of Di Biase and Urbanke

Like the algorithm of Hosten and Sturmfels, the algorithm of Di Biase
and Urbanke (@pxref{[DBUr95]}) performs up
@tex
to $n/2$ Groebner basis
computations. It needs no auxiliary variables, but a supplementary
precondition; namely, the existence of a vector without zero components
in the kernel of $A$.

The main idea comes from the following observation:

Let $B$ be an integer matrix, $u_1,\ldots,u_r$ a lattice basis of the
integer kernel of $B$. Assume that all components of $u_1$ are
positive. Then
$$ I_B=<x^{u_i^+}-x^{u_i^-}|i=1,\ldots,r>, $$
i.e., the ideal on the right is already saturated w.r.t. all variables.

The algorithm starts by finding a lattice basis $v_1,\ldots,v_r$ of the
kernel of $A$ such that $v_1$ has no zero component. Let
$\{i_1,\ldots,i_l\}$ be the set of indices $i$ with
$v_{1,i}<0$. Multiplying the components $i_1,\ldots,i_l$ of
$v_1,\ldots,v_r$ and the columns $i_1,\ldots,i_l$ of $A$ by $-1$ yields
a matrix $B$ and a lattice basis $u_1,\ldots,u_r$ of the kernel of $B$
that fulfill the assumption of the observation above. We are then able
to compute a generating set of $I_A$ by applying the following
``variable flip'' successively to $i=i_1,\ldots,i_l$:

Let $>$ be an elimination ordering for $x_i$. Let $A_i$ be the matrix
obtained by multiplying the $i$-th column of $A$ with $-1$. Let
$$\{x_i^{r_j} x^{a_j} - x^{b_j} | j\in J \}$$
be a Groebner basis of $I_{A_i}$ w.r.t. $>$ (where $x_i$ is neither
involved in $x^{a_j}$ nor in $x^{b_j}$). Then
$$\{x^{a_j} - x_i^{r_j} x^{b_j} | j\in J \}$$
is a generating set for $I_A$.
@end tex
@ifinfo
to n/2 Groebner basis
computations. It needs no auxiliary variables, but a supplementary
precondition; namely, the existence of a vector without zero components
in the kernel of A.

The main idea comes from the following observation:

Let B be an integer matrix, u(1),@dots{},u(r) a lattice basis of the
integer kernel of B. Assume that all components of u(1) are
positive. Then @*
@display
I(B)= < x^u(i)+ - x^u(i)- | i=1,@dots{},r >,
@end display
i.e., the ideal on the right is already saturated w.r.t.@: all variables.

The algorithm starts by finding a lattice basis v(1),@dots{},v(r) of the
kernel of A such that v(1) has no zero component. Let @{ i1,@dots{},il
@} be the set of indices i with v(1)_i <0. Multiplying the components
i1,@dots{},il of v(1),@dots{},v(r) and the columns i1,@dots{},il of A by
-1 yields a matrix B and a lattice basis u(1),@dots{},u(r) of the kernel
of B that fulfill the assumption of the observation above. We are then
able to compute a generating set of I(A) by applying the following
``variable flip'' successively to i=i1,@dots{},il:

Let > be an elimination ordering for x(i). Let A(i) be the matrix
obtained by multiplying the i-th column of A with -1. Let @*
@display
@{ x(i)^r(j) * x^a(j) - x^b(j) | j in J @}
@end display
be a Groebner basis of I(A(i)) w.r.t.@: > (where x(i) is neither
involved in x^a(j) nor in x^b(j)). Then @*
@display
@{ x^a(j) - x(i)^r(j) * x^b(j) | j in J @}
@end display
is a generating set for I(A).
@end ifinfo

@node Bigatti and La Scala and Robbiano, , Di Biase and Urbanke, Algorithms

@subsubsection The algorithm of Bigatti, La Scala and Robbiano
@cindex Bigatti-La Scala-Robbiano algorithm
@cindex algorithm of Bigatti, La Scala and Robbiano

The algorithm of Bigatti, La Scala and Robbiano (@pxref{[BLR98]}) combines the ideas of
the algorithms of Pottier and of Hosten and Sturmfels. The
computations are performed on a graded ideal with one auxiliary
@tex
variable $u$ and one supplementary generator $x_1\cdot\ldots\cdot x_n -
u$ (instead of the generator $t\cdot x_1\cdot\ldots\cdot x_n -1$ in
the algorithm of Pottier). The algorithm uses a quite unusual technique to
get rid of the variable $u$ again.
@end tex
@ifinfo
variable u and one supplementary generator x(1) *@dots{}* x(n) -u (instead of the
generator t * x(1) *@dots{}* x(n) -1 in
the algorithm of Pottier). The algorithm uses a quite unusual technique to
get rid of the variable u again.
@end ifinfo

There is another algorithm of the authors which tries to parallelize
the computations (but which is not implemented in this library).

@node Buchberger algorithm, , Algorithms, Toric ideals

@subsection The Buchberger algorithm for toric ideals
@cindex Buchberger algorithm for toric ideals

Toric ideals have a very special structure that allows us to improve
the Buchberger algorithm in many respects: They are prime ideals and
generated by binomials. Pottier used this fact to describe all
operations of the Buchberger algorithm on the ideal generators in terms
of vector additions and subtractions. Some other strategies like
multiple reduction (@pxref{[CoTr91]}) or the use of bit
vectors to represent the support of a monomial (@pxref{[Big97]}) may be
applied to more general ideals, but show to
be especially useful in the toric case.

@node Integer programming, Relevant References, Toric ideals, Toric ideals and integer programming

@subsection Integer programming
@cindex integer programming

@tex
Let $A$ be an $m\times n$ matrix with integral coefficients, $b\in
Z\!\!\! Z^m$ and $c\in Z\!\!\! Z^n$. The problem
$$ \min\{c^T x | x\in Z\!\!\! Z^n, Ax=b, x\geq 0\hbox{
component-wise}\} $$
is called an instance of the \bf integer programming problem \rm or
\bf IP problem. \rm

The IP problem is very hard; namely, it is NP-complete.

For the following discussion let $c\geq 0$ (component-wise). We
consider $c$ as a weight vector; because of its non-negativity, $c$ can
be refined into a monomial ordering $>_c$. It turns out that we can
solve such an IP instance with the help of toric ideals:

First we assume that an initial solution $v$ (i.e., $v\in Z\!\!\!
Z^n, v\geq 0, Av=b$) is already known. We obtain the optimal solution
$v_0$ (i.e., with $c^T v_0$ minimal) by the following procedure:
@end tex
@c \begin{itemize}
@c \item (1) Compute the toric ideal $I_A$ using one of the algorithms in the
@c       previous section.
@c \item (2) Compute the reduced Groebner basis $G_c$ of $I_A$ w.r.t.
@c       $>_c$.
@c \item (3) Reduce $x^v$ modulo $G_c$ using the Hironaka division algorithm.
@c       If the result of this reduction is $x^{v_0}$, then $v_0$ is an
@c       optimal solution of the given instance.
@c \end{itemize}

@ifinfo
Let A be an mxn matrix with integral coefficients, b in Z^m and c in
Z^n. The problem @*
@display
min @{ c*x | x in Z^n, A*x=b, x>=0 component-wise @}
@end display
is called an instance of the @strong{integer programming problem} or
@strong{IP problem}.

The IP problem is very hard; namely, it is NP-complete.

For the following discussion let c>=0 (component-wise). We
consider c as a weight vector; because of its non-negativity, c can
be refined into a monomial ordering >_c. It turns out that we can
solve such an IP instance with the help of toric ideals:

First we assume that an initial solution v (i.e., v in Z^n, v>=0,
A*v=b) is already known. We obtain the optimal solution v(opt) (i.e.,
with c*v(opt) minimal) by the following procedure:
@end ifinfo

@itemize @bullet
@item (1) Compute the toric ideal I(A) using one of the algorithms in the previous section.
@item (2) Compute the reduced Groebner basis G(c) of I(A) w.r.t.@:
@ifinfo
@math{>_c}
@end ifinfo
@tex
$>_c$
@end tex
.
@item (3) Reduce
@ifinfo
@math{x^v}
@end ifinfo
@tex
$x^v$
@end tex
 modulo G(c) using the Hironaka division algorithm.
If the result of this reduction is
@ifinfo
@math{x^(v_0)}
@end ifinfo
@tex
$x^(v_0)$
@end tex
, then
@ifinfo
@math{v_0}
@end ifinfo
@tex
$v_0$
@end tex
 is an optimal
solution of the given instance.
@end itemize

If no initial solution is known, we are nevertheless able to solve the
problem with similar techniques. For this purpose we replace our
instance by an extended instance with the matrix used
in the Conti-Traverso algorithm. Indeed, the Conti-Traverso
algorithm offers the possibility to verify solvability of a given
instance and to find an initial solution in the case of existence (but
none of the other algorithms does!). Details can be found in [CoTr91]
and [The99].

An implementation of the above algorithm and some examples can be found in @ref{intprog_lib}.

Classical methods for solving IP instances like Branch-and-Bound
methods seem to be faster in general than the methods using toric
ideals. But the latter have one great advantage: If one wants to solve
various instances that differ only by the vector
@ifinfo
@math{b}
@end ifinfo
@tex
$b$
@end tex
, one has to
perform steps (1) and (2) above only once. As the running time of step (3)
is very short, solving all the instances is not much harder than
solving one single instance.

For a detailed discussion see [The99].

@node Relevant References, , Integer programming, Toric ideals and integer programming
@subsection Relevant References

@itemize @bullet
@item [Big97]  Bigatti, A.M.: @anchor{[Big97]}
   Computation of Hilbert-Poincare series.
   Journal of Pure and Applied Algebra (1997) 199, 237-253

@item [BLR98]  Bigatti, A.M.; La Scala, R.; Robbiano, L.: @anchor{[BLR98]}
   Computing toric ideals.
   Journal of Symbolic Computation (to appear)

@item [Coh93]  Cohen, H.: @anchor{[Coh93]}
   A Course in Computational Algebraic Number Theory.
   Springer (1997)

@item [CoTr91]  Conti, P.; Traverso, C.: @anchor{[CoTr91]}
   Buchberger algorithm and integer programming.
   Proceedings AAECC-9 (new Orleans), Springer LNCS (1991) 539,
   130-139

@item [DBUr95]  Di Biase, F.; Urbanke, R.: @anchor{[DBUr95]}
   An algorithm to calculate the kernel of certain polynomial ring
   homomorphisms.
   Experimental Mathematics (1995) 4, 227-234

@item [HoSh98]  Hosten, S.; Shapiro, J.: @anchor{[HoSh98]}
   Primary decomposition of lattice basis ideals.
   (to appear)

@item [HoSt95]  Hosten, S.; Sturmfels, B.: @anchor{[HoSt95]}
   GRIN: An implementation of Groebner bases for integer programming.
   in Balas, E.; Clausen, J. (editors): Integer Programming and
   Combinatorial Optimization.
   Springer LNCS (1995) 920, 267-276

@item [Pot94]  Pottier, L.: @anchor{[Pot94]}
   Groebner bases of toric ideals.
   Rapport de recherche 2224 (1997), INRIA Sophia Antipolis

@item [Stu96]  Sturmfels, B.: @anchor{[Stu96]}
   Groebner Bases and Convex Polytopes.
   University Lecture Series, Volume 8 (1996), American Mathematical
   Society

@item [The99]  Theis, C.: @anchor{[The99]}
   Der Buchberger-Algorithmus fuer torische Ideale und seine Anwendung
   in der ganzzahligen Optimierung.
   Diplomarbeit, Universitaet des Saarlandes (1999), Saarbruecken
   (Germany)

@end itemize