@comment -*-texinfo-*-
@comment This file was generated by doc2tex.pl from pdata.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT pdata.doc INSTEAD
@comment Id: pdata.tex,v 1.1 2003/08/08 14:27:06 pertusus Exp $
@comment this file contains the "Polynomial data" appendix.

@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 pdata.hlp
@node Top, Polynomial data
@menu
* Polynomial data::
@end menu
@node Polynomial data, Examples, Mathematical background, Top
@chapter Polynomial data
%**end
@end ignore

@menu
* Representation of mathematical objects::
* Monomial orderings::
@end menu

@c -----------------------------------------------------------------
@node Representation of mathematical objects,Monomial orderings,,Polynomial data
@section Representation of mathematical objects
@cindex mathematical objects
@cindex representation, math objects

@sc{Singular} distinguishes between objects which do not belong to a ring
and those which belong to a specific ring (see @ref{Rings and orderings}).
We comment only on the latter ones.

Internally all ring-dependent objects are polynomials or structures built from
polynomials (and some additional information).
Note that @sc{Singular} stores (and hence prints) a polynomial automatically
w.r.t@:. the monomial ordering.

Hence, in order to define such an object in @sc{Singular},
one has to give a list of polynomials in a specific format.

For ideals, resp.@: matrices, this is straight forward:
The user gives a list of polynomials
which generate the ideal, resp.@: which are the entries of the matrix.
(The number of rows and columns has to be given when creating the matrix.)

A vector  in @sc{Singular} is always an element of a free module over the
basering. It is given as a list of polynomials in one of the following
formats
@tex
$[f_1,...,f_n]$ or $f_1*gen(1)+...+f_n*gen(n)$, where $gen(i)$
@end tex
@ifinfo
[f_1,...,f_n] or f_1*gen(1)+...+f_n*gen(n), where gen(i)
@end ifinfo
denotes the i-th canonical generator of a free module (with 1 at place i and
0 everywhere else).
Both forms are equivalent. A vector is internally represented in
the second form with the
@tex
$gen(i)$
@end tex
@ifinfo
gen(i)
@end ifinfo
being "special" ring variables, ordered accordingly to the monomial ordering.
Therefore, the form
@tex
$[f_1,...,f_n]$
@end tex
@ifinfo
[f_1,...,f_n]
@end ifinfo
is given as output only if the monomial ordering gives priority to the
component, i.e@:., is of the form @code{(c,...)} (see @ref{Module
orderings}).  However, in any case the procedure @code{show} from the
library @code{inout.lib} displays the bracket format.

A vector
@tex
$v=[f_1,...,f_n]$
@end tex
@ifinfo
v=[f_1,...,f_n]
@end ifinfo
should always be considered as a column vector in a free module
of rank equal to
@tex
nrows($v$)
@end tex
@ifinfo
nrows(v)
@end ifinfo
where 
@tex
nrows($v$)
@end tex
@ifinfo
nrows(v) 
@end ifinfo
is equal to the maximal index 
@tex
$r$
@end tex
@ifinfo
r
@end ifinfo
such that
@tex
$f_r \not= 0$.
@end tex
@ifinfo
f_r<>0.
@end ifinfo
This is due to the fact, that internally 
@tex
$v$
@end tex
@ifinfo
v
@end ifinfo
is a polynomial in a sparse representation, i.e.,
@tex
$f_i*gen(i)$
@end tex
@ifinfo
f_i*gen(i)
@end ifinfo
is not stored if
@tex
$f_i=0$
@end tex
@ifinfo
f_i=0
@end ifinfo
(for reasons of efficiency), hence the last 0-entries of 
@tex
$v$
@end tex
@ifinfo
v
@end ifinfo
are lost.
Only more complex structures are able to keep the rank.

A module 
@tex
$M$
@end tex
@ifinfo
M
@end ifinfo
in @sc{Singular} is given by a list of vectors
@tex
$v_1,...,v_k$
@end tex
@ifinfo
v_1,....v_k
@end ifinfo
which generate the module as a submodule of the free module of rank
equal to 
@tex
nrows($M$)
@end tex
@ifinfo
nrows(M)
@end ifinfo
which is the maximum of
@tex
nrows($v_i$).
@end tex
@ifinfo
nrows(v_i).
@end ifinfo

If one wants to create a module with a larger rank than given by its
generators, one has to use the command @code{attrib(M,"rank",r)} (see
@ref{attrib}, @ref{nrows}) or to define a matrix first, then converting it
into a module.  Modules in @sc{Singular} are almost the same as
matrices, they may be considered as sparse representations of matrices.
A module of a matrix is generated by the columns of the matrix and a
matrix of a module has as columns the generators of the module.  These
conversions preserve the rank and the number of generators, resp@:. the
number of rows and columns.

By the above remarks it might appear that @sc{Singular} is only able to handle
submodules of a free module. However, this is not true. @sc{Singular}
can compute with any finitely generated module over the basering 
@tex
$R$.
@end tex 
@ifinfo
R.
@end ifinfo
Such a module, say 
@tex
$N$,
@end tex
@ifinfo
N,
@end ifinfo
is not represented by its generators but by its
(generators and) relations. This means that
@tex
$N = R^n/M$ where $n$ 
@end tex
@ifinfo
N = R^n/M where n
@end ifinfo
is the number of generators of 
@tex
$N$ and $M \subseteq R^n$
@end tex
@ifinfo
N and M in R^n
@end ifinfo
is the module of relations.
In other words, defining  a module 
@tex
$M$
@end tex
@ifinfo
M
@end ifinfo
as a submodule of a free module
@tex
$R^n$
@end tex
@ifinfo
R^n
@end ifinfo
can also be considered as the definition of
@tex
$N = R^n/M$.
@end tex
@ifinfo
N=R^n/M.
@end ifinfo

Note that most functions, when applied to a module 
@tex
$M$,
@end tex
@ifinfo
M,
@end ifinfo
really deal with
@tex
$M$.
@end tex
@ifinfo
M.
@end ifinfo
However, there are some functions which deal with 
@tex
$N = R^n/M$ instead of $M$.
@end tex
@ifinfo
N=R^n/M instead of M.
@end ifinfo

For example, @code{std(M)} computes a standard basis of 
@tex
$M$
@end tex
@ifinfo
M
@end ifinfo
(and thus gives another representation of 
@tex
$N$ as $N = R^n/$std($M$)).
@end tex
@ifinfo
N as N=R^n/std(M)).
@end ifinfo
However, @code{dim(M)}, resp.@: @code{vdim(M)}, returns
@tex
dim$(R^n/M)$, resp.@: dim$_k(R^n/M)$
@end tex
@ifinfo
dim(R^n/M), resp.@: dim_k(R^n/M)
@end ifinfo
(if M is given by a standard basis).

The function @code{syz(M)}  returns the first syzygy module of 
@tex
$M$,
@end tex
@ifinfo
M,
@end ifinfo
i.e@:., the module 
of relations of the given generators of 
@tex
$M$
@end tex
@ifinfo
M
@end ifinfo
which is equal to the second syzygy module of 
@tex
$N$.
@end tex
@ifinfo
N.
@end ifinfo
Refer to the description of each function in
@ref{Functions} to get information which module the function deals with.

The numbering in @code{res} and other commands for computing resolutions
refers to a resolution of
@tex
$N = R^n/M$
@end tex
@ifinfo
N=R^n/M
@end ifinfo
(see @ref{res}; @ref{Syzygies and resolutions}).

It is possible to compute in any field which is a valid ground field in
@sc{Singular}.  For doing so, one has to define a ring with the desired
ground field and at least one variable. The elements of the field are of
type number, but may also be considered as polynomials (of degree
0). Large computations should be faster if the elements of the field are
defined as numbers.

The above remarks do also apply to quotient rings. Polynomial data are
stored internally in the same manner, the only difference is that this
polynomial representation is in general not unique. @code{reduce(f,std(0))}
computes a normal form of a polynomial f in a quotient ring (cf.@:
@ref{reduce}).

@c -----------------------------------------------------------------
@node Monomial orderings,,Representation of mathematical objects,Polynomial data
@section Monomial orderings
@cindex Monomial orderings

@menu
* Introduction to orderings::
* General definitions for orderings::
* Global orderings::
* Local orderings::
* Module orderings::
* Matrix orderings::
* Product orderings::
* Extra weight vector::
@end menu

@c --------------------------------------------------------------------------
@node Introduction to orderings, General definitions for orderings, , Monomial orderings
@subsection Introduction to orderings
@cindex orderings introduction
@cindex term orderings introduction
@cindex monomial orderings introduction

@sc{Singular} offers a great variety of monomial orderings which provide
an enormous functionality, if used diligently. However, this
flexibility might also be confusing for the novice user.  Therefore, we
recommend to those not familiar with monomial orderings to generally use
the ordering @code{dp} for computations in the polynomial ring
@tex
$K[x_1,\ldots,x_n]$, 
@end tex
@ifinfo
K[x1,...,xn], 
@end ifinfo
resp.@:  @code{ds} for computations in the localization 
@tex
$\hbox{Loc}_{(x)}K[x_1,\ldots,x_n]$.
@end tex
@ifinfo
Loc_(x)K[x1,...,xn].
@end ifinfo

For inhomogeneous input ideals,  standard (resp.@: groebner) bases
computations are generally faster 
with the orderings 
@tex
$\hbox{Wp}(w_1, \ldots, w_n)$
@end tex
@ifinfo
Wp(w_1, ..., w_n)
@end ifinfo
(resp.@: 
@tex
$\hbox{Ws}(w_1, \ldots, w_n)$)
@end tex
@ifinfo
Ws(w_1, ..., w_n))
@end ifinfo
if the input is quasihomogeneous w.r.t. the weights 
@tex
$w_1$, $\ldots$, $w_n$ of $x_1$, $\ldots$, $x_n$. 
@end tex
@ifinfo
w_1, ..., w_n of x_1, ..., x_n. 
@end ifinfo

If the output needs to be "triangular" (resp.@: "block-triangular"), the
lexicographical ordering @code{lp} (resp.@: lexicographical
block-orderings) need to be used. However, these orderings usually
result in much less efficient computations.


@c --------------------------------------------------------------------------
@node General definitions for orderings, Global orderings, Introduction to orderings, Monomial orderings
@subsection General definitions for orderings
@cindex orderings
@cindex term orderings
@cindex monomial orderings

@tex
A monomial ordering (term ordering) on $K[x_1, \ldots, x_n]$ is
a total ordering $<$ on the
set of monomials (power products) $\{x^\alpha \mid \alpha \in \bf{N}^n\}$
which is compatible with the
natural semigroup structure, i.e., $x^\alpha < x^\beta$ implies $x^\gamma
x^\alpha < x^\gamma x^\beta$ for any $\gamma \in \bf{N}^n$.
We do not require
$<$ to be  a well ordering.
@end tex
@ifinfo
A monomial ordering (term ordering) on K[x_1, ..., x_n] is
a total ordering < on the
set of monomials (power products) @{x^a | a in N^n@}
which is compatible with the
natural semigroup structure, i.e., x^a < x^b implies x^c*x^a < x^c*x^b for any
c in N^n.
We do not require
< to be  a well ordering.
@end ifinfo
@ifset singularmanual
 See the literature cited in @ref{References}.
@end ifset

It is known that any monomial ordering can be represented by a matrix 
@tex
$M$ in $GL(n,R)$,
@end tex
@ifinfo
M in GL(n,R),
@end ifinfo
but, of course, only integer coefficients are of relevance in
practice.

@tex
Global orderings are well orderings (i.e.,  \hbox{$1 < x_i$} for each variable
$x_i$), local orderings satisfy $1 > x_i$ for each variable.   If some variables are ordered globally and others locally we
call it a mixed ordering.   Local or mixed orderings are not well orderings.

Let $K$ be the ground field, \hbox{$x = (x_1, \ldots, x_n)$} the
variables and $<$ a monomial ordering, then Loc $K[x]$ denotes the
localization of $K[x]$ with respect to the multiplicatively closed set $$\{1 +
g \mid g = 0 \hbox{ or } g \in K[x]\backslash \{0\} \hbox{ and }L(g) <
1\}.$$   Here, $L(g)$ 
denotes the leading monomial of $g$, i.e., the biggest monomial of $g$ with
respect to $<$.   The result of any computation which uses standard basis
computations has to be interpreted in Loc $K[x]$.
@end tex
@ifinfo
Global orderings are well orderings (i.e., 1 < x_i for each variable
x_i), local orderings satisfy 1 > x_i for each variable.
If some variables are ordered globally and others locally we
call it a mixed ordering.   Local or mixed orderings are not well orderings.

If K is the ground field, x = (x_1, @dots{}, x_n) the
variables and < a monomial ordering, then Loc K[x] denotes the
localization of K[x] with respect to the multiplicatively closed set @{1 +
g | g = 0 or g in K[x]\@{0@} and L(g) < 1@}.   L(g)
denotes the leading monomial of g, i.e., the biggest monomial of g with
respect to <.   The result of any computation which uses standard basis
computations has to be interpreted in Loc K[x].
@end ifinfo

Note that the definition of a ring includes the definition of its
monomial ordering (see 
@ref{Rings and orderings}). @sc{Singular} offers the monomial orderings
described in the following sections. 


@c --------------------------------------------------------------------------
@node Global orderings, Local orderings, General definitions for orderings, Monomial orderings
@subsection Global orderings
@cindex Global orderings
@cindex orderings, global

@tex
For all these orderings: Loc $K[x]$ = $K[x]$
@end tex
@ifinfo
For all these orderings: Loc K[x] = K[x]
@end ifinfo

@table @asis
@item lp:
lexicographical ordering:
@cindex lp, global ordering
@cindex lexicographical ordering
@*
@ifinfo
x^a < x^b  <==> there is an i,  1 <= i <= n :
@* a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
$x^\alpha < x^\beta  \Leftrightarrow  \exists\; 1 \le i \le n :
\alpha_1 = \beta_1, \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i <
\beta_i$.
@end tex
@item rp:
reverse lexicographical ordering:
@cindex rp, global ordering
@cindex reverse lexicographical ordering
@*
@ifinfo
x^a < x^b  <==> there is an i,  1 <= i <= n :
@*     a_n = b_n, @dots{}, a_(i+1) = b_(i+1), a_i > b_i.
@end ifinfo
@tex
$x^\alpha < x^\beta  \Leftrightarrow  \exists\; 1 \le i \le n :
\alpha_n = \beta_n,
    \ldots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i.$
@end tex
@item dp:
degree reverse lexicographical ordering:
@cindex degree reverse lexicographical ordering
@cindex dp, global ordering
@*
@ifinfo 
let deg(x^a) = a_1 + @dots{} + a_n, then
@end ifinfo
@tex
let $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ then
@end tex
@ifinfo
@*x^a < x^b <==>
@* deg(x^a) < deg(x^b),
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_n = b_n, @dots{}, a_(i+1) = b_(i+1), a_i > b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) < \deg(x^\beta)$ or
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{$x^\alpha < x^\beta \Leftrightarrow $}$ \deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n: \alpha_n = \beta_n,
    \ldots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i.$
@end tex
@item Dp:
degree lexicographical ordering:
@cindex degree lexicographical ordering
@cindex Dp, global ordering
@*
@ifinfo 
let deg(x^a) = a_1 + @dots{} + a_n, then
@end ifinfo
@tex
let $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ then
@end tex
@ifinfo
@*x^a < x^b <==>
@* deg(x^a) < deg(x^b)
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) < \deg(x^\beta)$ or
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow $} $\deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:\alpha_1 = \beta_1,
    \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i < \beta_i.$
@end tex
@item wp:
weighted reverse lexicographical ordering:
@cindex weighted reverse lexicographical ordering
@cindex wp, global ordering
@*
@ifinfo
 wp(w_1, @dots{}, w_n), w_i  positive integers,
@end ifinfo
@tex
let $w_1, \ldots, w_n$ be positive integers. Then ${\tt wp}(w_1, \ldots,
w_n)$ 
@end tex
 is defined as @code{dp}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@item Wp:
weighted lexicographical ordering:
@cindex weighted lexicographical ordering
@cindex WP, global ordering
@*
@ifinfo
 Wp(w_1, @dots{}, w_n), w_i  positive integers,
@end ifinfo
@tex
let $w_1, \ldots, w_n$ be positive integers. Then ${\tt Wp}(w_1, \ldots,
w_n)$ 
@end tex
 is defined as @code{Dp}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@end table
@c --------------------------------------------------------------------------
@node Local orderings, Module orderings, Global orderings, Monomial orderings
@subsection Local orderings
@cindex Local orderings
@cindex orderings, local

For ls, ds, Ds and, if the weights are positive integers, also for ws and
Ws,  we have
@ifinfo
Loc K[x] = K[x]_(x),
@end ifinfo
@tex
Loc $K[x]$ = $K[x]_{(x)}$,
@end tex
 the localization of 
@tex
$K[x]$
@end tex
@ifinfo
K[x]
@end ifinfo
at the maximal ideal
@ifinfo
 (x_1, @dots{}, x_n).
@end ifinfo
@tex
\ $(x_1, ..., x_n)$.
@end tex

@table @asis
@item ls:
negative lexicographical ordering:
@cindex negative lexicographical ordering
@cindex ls, local ordering
@*
@ifinfo
x^a < x^b  <==> there is an i,  1 <= i <= n :
@* a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i > b_i.
@end ifinfo
@tex
$x^\alpha < x^\beta  \Leftrightarrow  \exists\; 1 \le i \le n :
\alpha_1 = \beta_1, \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i >
\beta_i$.
@end tex
@item ds:
negative degree reverse lexicographical ordering:
@cindex negative degree reverse lexicographical ordering
@cindex ds, local ordering
@*
@ifinfo 
let deg(x^a) = a_1 + @dots{} + a_n, then
@end ifinfo
@tex
let $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ then
@end tex
@ifinfo
@*x^a < x^b <==>
@* deg(x^a) > deg(x^b)
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_n = b_n, @dots{}, a_(i+1) = b_(i+1), a_i > b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) > \deg(x^\beta)$ or
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow$}$ \deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n: \alpha_n = \beta_n,
    \ldots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i.$
@end tex
@item Ds:
negative degree lexicographical ordering:
@cindex negative degree lexicographical ordering
@cindex Ds, local ordering
@*
@ifinfo
let deg(x^a) = a_1 + @dots{} + a_n, then
@end ifinfo
@tex
let $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ then
@end tex
@ifinfo
x^a < x^b <==>
@* deg(x^a) > deg(x^b)
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) > \deg(x^\beta)$ or 
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{ $ x^\alpha < x^\beta \Leftrightarrow$}$ \deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:\alpha_1 = \beta_1,
    \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i < \beta_i.$
@end tex
@item ws:
(general) weighted reverse lexicographical ordering:
@cindex general weighted reverse lexicographical ordering
@cindex local weighted reverse lexicographical ordering
@cindex ws, local ordering
@*
@ifinfo
 ws(w_1, @dots{}, w_n), w_1
@end ifinfo
@tex
${\tt ws}(w_1, \ldots, w_n),\; w_1$
@end tex
 a nonzero integer,
@ifinfo
w_2,@dots{},w_n
@end ifinfo
@tex
$w_2,\ldots,w_n$
@end tex
 any integer (including 0),
 is defined as @code{ds}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@item Ws:
(general) weighted lexicographical ordering:
@cindex general weighted lexicographical ordering
@cindex local weighted lexicographical ordering
@cindex Ws, local ordering
@*
@ifinfo
 Ws(w_1, @dots{}, w_n), w_1
@end ifinfo
@tex
${\tt Ws}(w_1, \ldots, w_n),\; w_1$
@end tex
 a nonzero integer,
@ifinfo
w_2,@dots{},w_n
@end ifinfo
@tex
$w_2,\ldots,w_n$
@end tex
 any integer (including 0),
 is defined as @code{Ds}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@end table

@c --------------------------------------------------------------------------
@node Module orderings, Matrix orderings, Local orderings, Monomial orderings
@subsection Module orderings
@cindex Module orderings

@sc{Singular} offers also orderings on the set of ``monomials''
@ifinfo
@{ x^a*gen(i) | a in N^n, 1 <= i <= r @} in Loc K[x]^r = Loc K[x]gen(1)
+ @dots{} + Loc K[x]gen(r), where gen(1), @dots{}, gen(r) denote the canonical
generators of Loc K[x]^r, the r-fold direct sum of Loc K[x].
@end ifinfo
@tex
$\{ x^a e_i  \mid  a \in N^n, 1 \leq i \leq r \}$ in Loc $K[x]^r$ = Loc
$K[x]e_1 
+ \ldots +$Loc $K[x]e_r$, where $e_1, \ldots, e_r$ denote the canonical
generators of Loc $K[x]^r$, the r-fold direct sum of Loc $K[x]$.
(The function {\tt gen(i)} yields $e_i$).
@end tex

We have two possibilities: either to give priority to the component of a
vector in 
@ifinfo
Loc K[x]^r
@end ifinfo
@tex
 Loc $K[x]^r$
@end tex
or (which is the default in @sc{Singular}) to give priority
to the coefficients.
The orderings @code{(<,c)} and @code{(<,C)} give priority to the
coefficients; whereas
@code{(c,<)} and @code{(C,<)} give priority to the components.
@*Let < be any of the monomial orderings of 
@tex
Loc $K[x]$
@end tex
@ifinfo
Loc K[x]
@end ifinfo
as above.

@table @asis
@item (<,C):
@cindex C, module ordering
@cindex module ordering C
@ifinfo
<_m = (<,C) denotes the module ordering (giving priority to the coefficients):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* x^a < x^b
@* or
@* x^a = x^b  and  i < j.
@end ifinfo
@tex
$<_m = (<,C)$ denotes the module ordering (giving priority to the coefficients):
@end tex
@*
@tex
\quad  \quad  $x^\alpha e_i <_m x^\beta e_j \Leftrightarrow x^\alpha <
x^\beta$ or ($x^\alpha = x^\beta $ and $ i < j$).
@end tex

@strong{Example:}
@smallexample
@c computed example Module_orderings pdata.doc:849 
  ring r = 0, (x,y,z), ds;
  // the same as ring r = 0, (x,y,z), (ds, C);
  [x+y2,z3+xy];
@expansion{} x*gen(1)+xy*gen(2)+y2*gen(1)+z3*gen(2)
  [x,x,x];
@expansion{} x*gen(3)+x*gen(2)+x*gen(1)
@c end example Module_orderings pdata.doc:849
@end smallexample

@item (C,<):
@ifinfo
<_m = (C, <) denotes the module ordering (giving priority to the
component):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* i<j
@* or
@* i = j and x^a < x^b.
@end ifinfo
@tex
$<_m = (C, <)$ denotes the module ordering (giving priority to the component):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad   $x^\alpha e_i <_m x^\beta e_j \Leftrightarrow i < j$ or ($
i = j $ and $ x^\alpha < x^\beta $). 
@end tex

@strong{Example:}
@smallexample
@c computed example Module_orderings_1 pdata.doc:879 
  ring r = 0, (x,y,z), (C,lp);
  [x+y2,z3+xy];
@expansion{} xy*gen(2)+z3*gen(2)+x*gen(1)+y2*gen(1)
  [x,x,x];
@expansion{} x*gen(3)+x*gen(2)+x*gen(1)
@c end example Module_orderings_1 pdata.doc:879
@end smallexample

@item (<,c):
@cindex c, module ordering
@cindex module ordering c
@ifinfo
<_m = (<,c) denotes the module ordering (giving priority to the coefficients):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* x^a < x^b
@* or
@* x^a = x^b  and  i > j.
@end ifinfo
@tex
$<_m = (<,c)$ denotes the module ordering (giving priority to the coefficients):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad $x^\alpha e_i <_m x^\beta e_j \Leftrightarrow x^\alpha <
x^\beta$ or ($x^\alpha = x^\beta $ and $ i > j$).
@end tex

@strong{Example:}
@smallexample
@c computed example Module_orderings_2 pdata.doc:909 
  ring r = 0, (x,y,z), (lp,c);
  [x+y2,z3+xy];
@expansion{} xy*gen(2)+x*gen(1)+y2*gen(1)+z3*gen(2)
  [x,x,x];
@expansion{} x*gen(1)+x*gen(2)+x*gen(3)
@c end example Module_orderings_2 pdata.doc:909
@end smallexample

@item (c,<):
@ifinfo
<_m = (c, <) denotes the module ordering (giving priority to the
component):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* i>j
@* or
@* i = j and x^a < x^b.
@end ifinfo
@tex
$<_m = (c, <)$ denotes the module ordering (giving priority to the component):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad   $x^\alpha e_i <_m x^\beta e_j \Leftrightarrow i > j$ or ($
i = j $ and $ x^\alpha < x^\beta $). 
@end tex

@strong{Example:}
@smallexample
@c computed example Module_orderings_3 pdata.doc:938 
  ring r = 0, (x,y,z), (c,lp);
  [x+y2,z3+xy];
@expansion{} [x+y2,xy+z3]
  [x,x,x];
@expansion{} [x,x,x]
@c end example Module_orderings_3 pdata.doc:938
@end smallexample
@end table

@ifinfo
The output of a vector v in K[x]^r with components v_1,
@dots{}, v_r has the format v_1 * gen(1) + @dots{} + v_r * gen(r)
@end ifinfo
@tex
The output of a vector $v$ in $K[x]^r$ with components $v_1,
\ldots, v_r$ has the format $v_1 * gen(1) + \ldots + v_r * gen(r)$
@end tex
(up to permutation) unless the ordering starts with @code{c}.
@ifinfo
In this case a vector is written as [v_1, @dots{}, v_r].
@end ifinfo
@tex
In this case a vector is written as $[v_1, \ldots, v_r]$.
@end tex
In all cases @sc{Singular} can read input in both formats.

@c --------------------------------------------------------------------------
@node Matrix orderings, Product orderings, Module orderings, Monomial orderings
@subsection Matrix orderings
@cindex Matrix orderings
@cindex orderings, M
@cindex M, ordering

Let 
@tex
$M$
@end tex
@ifinfo
M
@end ifinfo
be an invertible 
@tex
$(n \times n)$-matrix
@end tex
@ifinfo
(n x n)-matrix
@end ifinfo
 with integer coefficients and
@ifinfo
M_1, @dots{}, M_n the rows of M.
@end ifinfo
@tex
$M_1, \ldots, M_n$ the rows of $M$.
@end tex

The M-ordering < is defined as follows:
@*
@ifinfo
x^a < x^b <==> there exists an i: 1 <= i <= n :
M_1*a = M_1*b, @dots{}, M_(i-1)*a = M_(i-1)*b, M_i*a < M_i*b.
@end ifinfo
@tex
\quad \quad $x^a < x^b \Leftrightarrow \exists\  1 \leq i \leq n :
M_1 a = \; M_1 b, \ldots, M_{i-1} a = \; M_{i-1} b$ and $M_i a < \; M_i b$.
@end tex

Thus,
@ifinfo
x^a < x^b
if and only if M*a is smaller than M*b
@end ifinfo
@tex
$x^a < x^b$
if and only if $M a$ is smaller than $M b$
@end tex
with respect to the lexicographical ordering.

The following matrices represent (for 3 variables) the global and
local orderings defined above (note that the matrix is not uniquely determined
by the ordering):

@ifinfo
@table @asis
@item lp:
 1   0   0
@* 0   1   0
@* 0   0   1
@item dp:
 1   1   1
@* 0   0  -1
@* 0  -1   0
@item Dp:
 1   1   1
@* 1   0   0
@* 0   1   0
@item wp(1,2,3):
 1   2   3
@* 0   0  -1
@* 0  -1   0
@item Wp(1,2,3):
 1   2   3
@* 1   0   0
@* 0   1   0
@item ls:
-1   0   0
@* 0  -1   0
@* 0   0  -1
@item ds:
-1  -1  -1
@* 0   0  -1
@* 0  -1   0
@item Ds:
-1  -1  -1
@* 1   0   0
@* 0   1   0
@item ws(1,2,3):
-1  -2  -3
@* 0   0  -1
@* 0  -1   0
@item Ws(1,2,3):
-1  -2  -3
@* 1   0   0
@* 0   1   0
@end table
@end ifinfo
@tex

$\quad$ lp:
$\left(\matrix{
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 0 & 0 & 1 \cr
 }\right)$
\quad dp:
$\left(\matrix{
 1 & 1 & 1 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Dp:
$\left(\matrix{
 1 & 1 & 1 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

$\quad$ wp(1,2,3):
$\left(\matrix{
 1 & 2 & 3 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Wp(1,2,3):
$\left(\matrix{
 1 & 2 & 3 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

$\quad$ ls:
$\left(\matrix{
-1 & 0 & 0 \cr
 0 &-1 & 0 \cr
 0 & 0 &-1 \cr
 }\right)$
\quad ds:
$\left(\matrix{
-1 &-1 &-1 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Ds:
$\left(\matrix{
-1 &-1 &-1 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

$\quad$ ws(1,2,3):
$\left(\matrix{
-1 &-2 &-3 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Ws(1,2,3):
$\left(\matrix{
-1 &-2 &-3 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$
@end tex

Product orderings (see next section) represented by  a matrix:

@ifinfo
@table @asis
@item (dp(3), wp(1,2,3)):
1  1  1  0  0  0
@*0  0  -1  0  0  0
@*0  -1  0  0  0  0
@*0  0  0  1  2  3
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@item (Dp(3), ds(3)):
1  1  1  0  0  0
@*1  0  0  0  0  0
@*0  1  0  0  0  0
@*0  0  0  -1  -1  -1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@end table
@end ifinfo
@tex
$\quad$ (dp(3), wp(1,2,3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
0&  0&  -1&  0&  0&  0 \cr
0&  -1&  0&  0&  0&  0 \cr
0&  0&  0&  1&  2&  3 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$

$\quad$ (Dp(3), ds(3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
1&  0&  0&  0&  0&  0 \cr
0&  1&  0&  0&  0&  0 \cr
0&  0&  0&  -1&  -1&  -1 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@end tex

Orderings with extra weight vector (see below) represented by  a matrix:

@ifinfo
@table @asis
@item (dp(3), a(1,2,3),dp(3)):
1  1  1  0  0  0
@*0  0  -1  0  0  0
@*0  -1  0  0  0  0
@*0  0  0  1  2  3
@*0  0  0  1  1  1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@item (a(1,2,3,4,5),Dp(3), ds(3)):
1  2  3  4  5  0
@*1  1  1  0  0  0
@*1  0  0  0  0  0
@*0  1  0  0  0  0
@*0  0  0  -1  -1  -1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@end table
@end ifinfo
@tex
$\quad$ (dp(3), a(1,2,3),dp(3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
0&  0&  -1&  0&  0&  0 \cr
0&  -1&  0&  0&  0&  0 \cr
0&  0&  0&  1&  2&  3 \cr
0&  0&  0&  1&  1&  1 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$

$\quad$ (a(1,2,3,4,5),Dp(3), ds(3)):
$\left(\matrix{
1&  2&  3&  4&  5&  0 \cr
1&  1&  1&  0&  0&  0 \cr
1&  0&  0&  0&  0&  0 \cr
0&  1&  0&  0&  0&  0 \cr
0&  0&  0&  -1&  -1&  -1 \cr
0&  0&  0&  0&  0 & -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@end tex

@*@strong{Example}:
@smallexample
@c computed example Matrix_orderings pdata.doc:1219 
  ring r = 0, (x,y,z), M(1, 0, 0,   0, 1, 0,   0, 0, 1);
@c end example Matrix_orderings pdata.doc:1219
@end smallexample
@*which may also be written as:
@smallexample
@c computed example Matrix_orderings_1 pdata.doc:1225 
  intmat m[3][3]=1, 0, 0, 0, 1, 0, 0, 0, 1;
  m;
@expansion{} 1,0,0,
@expansion{} 0,1,0,
@expansion{} 0,0,1 
  ring r = 0, (x,y,z), M(m);
  r;
@expansion{} //   characteristic : 0
@expansion{} //   number of vars : 3
@expansion{} //        block   1 : ordering M
@expansion{} //                  : names    x y z 
@expansion{} //                  : weights  1 0 0 
@expansion{} //                  : weights  0 1 0 
@expansion{} //                  : weights  0 0 1 
@expansion{} //        block   2 : ordering C
@c end example Matrix_orderings_1 pdata.doc:1225
@end smallexample

If the ring has 
@tex
$n$
@end tex
@ifinfo
n
@end ifinfo
variables and the matrix contains less than 
@tex
$n \times n$
@end tex
@ifinfo
n x n 
@end ifinfo
entries an error message is given, if there are more entries,
the last ones are ignored.

@strong{WARNING:} @sc{Singular}
does not check whether the matrix has full rank.   In such a case some
computations might not terminate, others might give a nonsense result.

Having these matrix orderings @sc{Singular} can compute standard bases for
any monomial ordering which is compatible with the natural semigroup structure.
In practice the global and local orderings together with block orderings should be
sufficient in most cases. These orderings are faster than the corresponding
matrix orderings, since evaluating a matrix product is time consuming.

@c --------------------------------------------------------------------------
@node Product orderings, Extra weight vector, Matrix orderings, Monomial orderings
@subsection Product orderings
@cindex Product orderings
@cindex orderings, product

Let
@ifinfo
x = (x_1, @dots{}, x_n) = x(1..n) and y = (y_1, @dots{}, y_m) =
y(1..m)
@end ifinfo
@tex
$x = (x_1, \ldots, x_n)$ and $y = (y_1, \ldots, y_m)$
@end tex
be two ordered sets of variables,
@ifinfo
<_1 a monomial
ordering on K[x] and <_2 a monomial ordering on K[y].   The product
ordering (or block ordering) < = (<_1,<_2) on K[x,y] is the following:
@*x^a y^b < x^A y^B <==>
@*x^a <_1 x^A
@*or
@*x^a = x^A  and  y^b <_2 y^B.
@end ifinfo
@iftex
@tex
$<_1$ a monomial
ordering on $K[x]$ and $<_2$ a monomial ordering on $K[y]$.   The product
ordering (or block ordering) $<\ := (<_1,<_2)$ on $K[x,y]$ is the following:
@end tex
@*
@tex
\quad \quad $x^a y^b < x^A y^B \Leftrightarrow x^a <_1 x^A $ or ($x^a =
x^A$ and $y^b <_2 y^B$). 
@end tex
@end iftex

Inductively one defines the product ordering of more than two monomial
orderings.

In @sc{Singular}, any of the above global orderings, local orderings or matrix
orderings may be combined (in an arbitrary manner and length) to a product
ordering.   E.g., @code{(lp(3), M(1, 2, 3, 1, 1, 1, 1, 0, 0), ds(4),
ws(1,2,3))} 
defines: @code{lp} on the first 3 variables, the matrix ordering
@code{M(1, 2, 3, 1, 1, 1, 1, 0, 0)} on the next 3 variables,
@code{ds} on the next 4 variables and
@code{ws(1,2,3)} on the last 3 variables.

@c --------------------------------------------------------------
@node Extra weight vector,  , Product orderings, Monomial orderings
@subsection Extra weight vector
@cindex Extra weight vector
@cindex a, ordering
@cindex orderings, a 

@ifinfo
a(w_1, @dots{}, w_n),
@end ifinfo
@tex
${\tt a}(w_1, \ldots, w_n),\; $
@end tex
@ifinfo
w_1,@dots{},w_n
@end ifinfo
@tex
$w_1,\ldots,w_n$
@end tex
any integers (including 0), defines
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n$
@end tex
and
@*
@ifinfo
deg(x^a) < deg(x^b) ==> x^a < x^b 
@end ifinfo
@tex
    $$\deg(x^\alpha) < \deg(x^\beta) \Rightarrow x^\alpha < x^\beta,$$
@end tex
@ifinfo
@*
deg(x^a) > deg(x^b) ==> x^a > x^b.
@end ifinfo
@tex
    $$\deg(x^\alpha) > \deg(x^\beta) \Rightarrow x^\alpha > x^\beta. $$
@end tex
@*An extra weight vector does not define a monomial ordering by itself:
it can only be used in combination with other orderings
to insert an extra line of weights into the ordering
matrix.

@*@strong{Example}:
@smallexample
ring r = 0, (x,y,z),  (a(1,2,3),wp(4,5,2));
ring s = 0, (x,y,z),  (a(1,2,3),dp);
ring q = 0, (a,b,c,d),(lp(1),a(1,2,3),ds);
@end smallexample