@c ---content LibInfo---
@comment This file was generated by doc2tex.pl from d2t_singular/zeroset_lib.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT d2t_singular/zeroset_lib.doc INSTEAD
@c library version: (1.7.2.2,2002/02/20)
@c library file: ../Singular/LIB/zeroset.lib
@cindex zeroset.lib
@cindex zeroset_lib
@table @asis
@item @strong{Library:}
zeroset.lib
@item @strong{Purpose:}
      Procedures For Roots and Factorization
@item @strong{Author:}
Thomas Bayer, email: tbayer@@mathematik.uni-kl.de
@*http://wwwmayr.informatik.tu-muenchen.de/personen/bayert/
Current Adress: Institut fuer Informatik, TU Muenchen

@item @strong{Overview:}
Algorithms for finding the zero-set of a zero-dim. ideal in Q(a)[x_1,..,x_n],
Roots and Factorization of univariate polynomials over Q(a)[t]
where a is an algebraic number. Written in the frame of the
diploma thesis (advisor: Prof. Gert-Martin Greuel) 'Computations of moduli
spaces of semiquasihomogeneous singularities and an implementation in Singular'.
This library is meant as a preliminary extension of the functionality
of Singular for univariate factorization of polynomials over simple algebraic
extensions in characteristic 0.
@*Subprocedures with postfix 'Main' require that the ring contains a variable
'a' and no parameters, and the ideal 'mpoly', where 'minpoly' from the
basering is stored.

@end table

@strong{Procedures:}
@menu
* EGCD:: gcd over an algebraic extension field of Q
* Factor:: factorization of f over an algebraic extension field
* Quotient:: quotient q of f w.r.t. g (in f = q*g + remainder)
* Remainder:: remainder of the division of f by g
* Roots:: computes all roots of f in an extension field of Q
* SQFRNorm:: norm of f (f must be squarefree)
* ZeroSet:: zero-set of the 0-dim. ideal I
@end menu
@strong{Auxiliary procedures:}
@menu
* EGCDMain:: gcd over an algebraic extension field of Q
* FactorMain:: factorization of f over an algebraic extension field
* InvertNumberMain:: inverts an element of an algebraic extension field
* QuotientMain:: quotient of f w.r.t. g
* RemainderMain:: remainder of the division of f by g
* RootsMain:: computes all roots of f, might extend the ground field
* SQFRNormMain:: norm of f (f must be squarefree)
* ContainedQ:: f in data ?
* SameQ:: a == b (list a,b)
@end menu
@c ---end content LibInfo---

@c ------------------- EGCD -------------
@node EGCD, Factor,, zeroset_lib
@subsubsection EGCD
@cindex EGCD
@c ---content EGCD---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
EGCD(f, g); where f,g are polynomials

@item @strong{Purpose:}
compute the polynomial gcd of f and g over Q(a)[x]

@item @strong{Return:}
polynomial h s.t. h is a greatest common divisor of f and g (not nec.
monic)

@item @strong{Assume:}
basering = Q(a)[t]

@end table
@strong{Example:}
@smallexample
@c computed example EGCD d2t_singular/zeroset_lib.doc:79 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 1;
poly g = x2 - 2*a*x - 1;
EGCD(f, g);
@expansion{} (-4a)*x-4
@c end example EGCD d2t_singular/zeroset_lib.doc:79
@end smallexample
@c ---end content EGCD---

@c ------------------- Factor -------------
@node Factor, Quotient, EGCD, zeroset_lib
@subsubsection Factor
@cindex Factor
@c ---content Factor---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
Factor(f); where f is a polynomial

@item @strong{Purpose:}
compute the factorization of the squarefree poly f over Q(a)[t]

@item @strong{Return:}
list with two entries
  @format
  _[1] = factors (monic), first entry is the leading coefficient
  _[2] = multiplicities (not yet implemented)
  @end format

@item @strong{Assume:}
basering must be the univariate polynomial ring over a field, which
is Q or a simple extension of Q given by a minpoly.

@item @strong{Note:}
if basering = Q[t] then this is the built-in @code{factorize}

@end table
@strong{Example:}
@smallexample
@c computed example Factor d2t_singular/zeroset_lib.doc:121 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 1;
list fl = Factor(f);
fl;
@expansion{} [1]:
@expansion{}    _[1]=1
@expansion{}    _[2]=(40a+60)*x+(40a+60)
@expansion{}    _[3]=(1/65a-29/130)*x+(-1/65a+29/130)
@expansion{}    _[4]=(4a)*x+4
@expansion{}    _[5]=(7/520a+1/130)*x+(1/130a-7/520)
@expansion{} [2]:
@expansion{}    _[1]=1
@expansion{}    _[2]=1
@expansion{}    _[3]=1
@expansion{}    _[4]=1
@expansion{}    _[5]=1
fl[1][1]*fl[1][2]*fl[1][3]*fl[1][4]*fl[1][5] - f;
@expansion{} 0
@c end example Factor d2t_singular/zeroset_lib.doc:121
@end smallexample
@c ---end content Factor---

@c ------------------- Quotient -------------
@node Quotient, Remainder, Factor, zeroset_lib
@subsubsection Quotient
@cindex Quotient
@c ---content Quotient---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
Quotient(f, g); where f,g are polynomials;

@item @strong{Purpose:}
compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < deg(g)

@item @strong{Return:}
list of polynomials
  @format
  _[1] = quotient  q
  _[2] = remainder r
  @end format

@item @strong{Assume:}
basering = Q[x] or Q(a)[x]

@end table
@strong{Example:}
@smallexample
@c computed example Quotient d2t_singular/zeroset_lib.doc:160 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 2;
poly g = x - a;
list qr = Quotient(f, g);
qr;
@expansion{} [1]:
@expansion{}    x3+(a)*x2-x+(-a)
@expansion{} [2]:
@expansion{}    0
qr[1]*g + qr[2] - f;
@expansion{} 1
@c end example Quotient d2t_singular/zeroset_lib.doc:160
@end smallexample
@c ---end content Quotient---

@c ------------------- Remainder -------------
@node Remainder, Roots, Quotient, zeroset_lib
@subsubsection Remainder
@cindex Remainder
@c ---content Remainder---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
Remainder(f, g); where f,g are polynomials

@item @strong{Purpose:}
compute the remainder of the division of f by g, i.e. a polynomial r
s.t. f = g*q + r, deg(r) < deg(g).

@item @strong{Return:}
poly

@item @strong{Assume:}
basering = Q[x] or Q(a)[x]

@end table
@strong{Example:}
@smallexample
@c computed example Remainder d2t_singular/zeroset_lib.doc:197 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 1;
poly g = x3 - 1;
Remainder(f, g);
@expansion{} x-1
@c end example Remainder d2t_singular/zeroset_lib.doc:197
@end smallexample
@c ---end content Remainder---

@c ------------------- Roots -------------
@node Roots, SQFRNorm, Remainder, zeroset_lib
@subsubsection Roots
@cindex Roots
@c ---content Roots---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
Roots(f); where f is a polynomial

@item @strong{Purpose:}
compute all roots of f in a finite extension of the ground field
without multiplicities.

@item @strong{Return:}
ring, a polynomial ring over an extension field of the ground field,
containing a list 'roots' and polynomials 'newA' and 'f':
  @format
  - 'roots' is the list of roots of the polynomial f (no multiplicities)
  - if the ground field is Q(a') and the extension field is Q(a), then
    'newA' is the representation of a' in Q(a). 
    If the basering contains a parameter 'a' and the minpoly remains unchanged
    then 'newA' = 'a'.
    If the basering does not contain a parameter then 'newA' = 'a' (default).
  - 'f' is the polynomial f in Q(a) (a' being substituted by 'newA')
  @end format

@item @strong{Assume:}
ground field to be Q or a simple extension of Q given by a minpoly

@end table
@strong{Example:}
@smallexample
@c computed example Roots d2t_singular/zeroset_lib.doc:242 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f = x3 - a;
def R1 = Roots(f);
@expansion{} 
@expansion{} // 'Roots' created a new ring which contains the list 'roots' and
@expansion{} // the polynomials 'f' and 'newA'
@expansion{} // To access the roots, newA and the new representation of f, type
@expansion{}    def R = Roots(f); setring R; roots; newA; f;
@expansion{} 
setring R1;
minpoly;
@expansion{} (a4-a2+1)
newA;
@expansion{} (a3)
f;
@expansion{} x3+(-a3)
roots;
@expansion{} [1]:
@expansion{}    (-a3)
@expansion{} [2]:
@expansion{}    (a3-a)
@expansion{} [3]:
@expansion{}    (a)
map F;
F[1] = roots[1];
F(f);
@expansion{} 0
@c end example Roots d2t_singular/zeroset_lib.doc:242
@end smallexample
@c ---end content Roots---

@c ------------------- SQFRNorm -------------
@node SQFRNorm, ZeroSet, Roots, zeroset_lib
@subsubsection SQFRNorm
@cindex SQFRNorm
@c ---content SQFRNorm---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
SQFRNorm(f); where f is a polynomial

@item @strong{Purpose:}
compute the norm of the squarefree polynomial f in Q(a)[x].

@item @strong{Return:}
list with 3 entries
  @format
  _[1] = squarefree norm of g (poly)
  _[2] = g (= f(x - s*a)) (poly)
  _[3] = s (int)
  @end format

@item @strong{Assume:}
f must be squarefree, basering = Q(a)[x] and minpoly != 0.

@item @strong{Note:}
the norm is an element of Q[x]

@end table
@strong{Example:}
@smallexample
@c computed example SQFRNorm d2t_singular/zeroset_lib.doc:291 
LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 2*x + 1;
SQFRNorm(f);
@expansion{} [1]:
@expansion{}    x8+4*x6-4*x5+8*x4+8*x3-4*x2+8*x+8
@expansion{} [2]:
@expansion{}    x4+(-4a)*x3-6*x2+(4a-2)*x+(2a+2)
@expansion{} [3]:
@expansion{}    1
@c end example SQFRNorm d2t_singular/zeroset_lib.doc:291
@end smallexample
@c ---end content SQFRNorm---

@c ------------------- ZeroSet -------------
@node ZeroSet, EGCDMain, SQFRNorm, zeroset_lib
@subsubsection ZeroSet
@cindex ZeroSet
@c ---content ZeroSet---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
ZeroSet(I [,opt] ); I=ideal, opt=integer

@item @strong{Purpose:}
compute the zero-set of the zero-dim. ideal I, in a finite extension
of the ground field.

@item @strong{Return:}
ring, a polynomial ring over an extension field of the ground field,
containing a list 'zeroset', a polynomial 'newA', and an
ideal 'id':
  @format
  - 'zeroset' is the list of the zeros of the ideal I, each zero is an ideal.
  - if the ground field is Q(a') and the extension field is Q(a), then
    'newA' is the representation of a' in Q(a).
    If the basering contains a parameter 'a' and the minpoly remains unchanged
    then 'newA' = 'a'.
    If the basering does not contain a parameter then 'newA' = 'a' (default).    
  - 'id' is the ideal I in Q(a)[x_1,...] (a' substituted by 'newA')
  @end format

@item @strong{Assume:}
dim(I) = 0, and ground field to be Q or a simple extension of Q given
by a minpoly.

@item @strong{Options:}
opt = 0 no primary decomposition (default)
@*opt > 0 primary decomposition

@item @strong{Note:}
If I contains an algebraic number (parameter) then 'I' must be
transformed w.r.t. 'newA' in the new ring.

@end table
@strong{Example:}
@smallexample
@c computed example ZeroSet d2t_singular/zeroset_lib.doc:345 
LIB "zeroset.lib";
ring R = (0,a), (x,y,z), lp;
minpoly = a2 + 1;
ideal I = x2 - 1/2, a*z - 1, y - 2;
def T = ZeroSet(I);
@expansion{} 1
setring T;
minpoly;
@expansion{} (4a4+4a2+9)
newA;
@expansion{} (1/3a3+5/6a)
id;
@expansion{} id[1]=(1/3a3+5/6a)*z-1
@expansion{} id[2]=y-2
@expansion{} id[3]=2*x2-1
zeroset;
@expansion{} [1]:
@expansion{}    _[1]=(1/3a3-1/6a)
@expansion{}    _[2]=2
@expansion{}    _[3]=(-1/3a3-5/6a)
@expansion{} [2]:
@expansion{}    _[1]=(-1/3a3+1/6a)
@expansion{}    _[2]=2
@expansion{}    _[3]=(-1/3a3-5/6a)
map F1 = basering, zeroset[1];
map F2 = basering, zeroset[2];
F1(id);
@expansion{} _[1]=0
@expansion{} _[2]=0
@expansion{} _[3]=0
F2(id);
@expansion{} _[1]=0
@expansion{} _[2]=0
@expansion{} _[3]=0
@c end example ZeroSet d2t_singular/zeroset_lib.doc:345
@end smallexample
@c ---end content ZeroSet---

@c ------------------- EGCDMain -------------
@node EGCDMain, FactorMain, ZeroSet, zeroset_lib
@subsubsection EGCDMain
@cindex EGCDMain
@c ---content EGCDMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Purpose:}
compute the polynomial gcd of f and g over Q(a)[x]

@item @strong{Return:}
poly

@item @strong{Assume:}
basering = Q[x,a] and ideal mpoly is defined (it might be 0),
this represents the ring Q(a)[x] together with its minimal polynomial.

@end table
@c ---end content EGCDMain---

@c ------------------- FactorMain -------------
@node FactorMain, InvertNumberMain, EGCDMain, zeroset_lib
@subsubsection FactorMain
@cindex FactorMain
@c ---content FactorMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Purpose:}
compute the factorization of the squarefree poly f over Q(a)[t],
minpoly = p(a).

@item @strong{Return:}
list with 2 entries
  @format
  _[1] = factors, first is a constant
  _[2] = multiplicities (not yet implemented)
  @end format

@item @strong{Assume:}
basering = Q[x,a], representing Q(a)[x]. An ideal mpoly must
be defined, representing the minimal polynomial (it might be 0!).

@end table
@c ---end content FactorMain---

@c ------------------- InvertNumberMain -------------
@node InvertNumberMain, QuotientMain, FactorMain, zeroset_lib
@subsubsection InvertNumberMain
@cindex InvertNumberMain
@c ---content InvertNumberMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
InvertNumberMain(f); where f is a polynomial

@item @strong{Purpose:}
compute 1/f if f is a number in Q(a) i.e., f is represented by a
polynomial in Q[a].

@item @strong{Return:}
poly 1/f

@item @strong{Assume:}
basering = Q[x_1,...,x_n,a], ideal mpoly must be defined and != 0 !

@end table
@c ---end content InvertNumberMain---

@c ------------------- QuotientMain -------------
@node QuotientMain, RemainderMain, InvertNumberMain, zeroset_lib
@subsubsection QuotientMain
@cindex QuotientMain
@c ---content QuotientMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
QuotientMain(f, g); where f,g are polynomials

@item @strong{Purpose:}
compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < deg(g)

@item @strong{Return:}
list of polynomials
  @format
  _[1] = quotient  q
  _[2] = remainder r
  @end format

@item @strong{Assume:}
basering = Q[x,a] and ideal mpoly is defined (it might be 0),
this represents the ring Q(a)[x] together with its minimal polynomial.

@end table
@c ---end content QuotientMain---

@c ------------------- RemainderMain -------------
@node RemainderMain, RootsMain, QuotientMain, zeroset_lib
@subsubsection RemainderMain
@cindex RemainderMain
@c ---content RemainderMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
RemainderMain(f, g); where f,g are polynomials

@item @strong{Purpose:}
compute the remainder r s.t. f = g*q + r, deg(r) < deg(g)

@item @strong{Return:}
poly

@item @strong{Assume:}
basering = Q[x,a] and ideal mpoly is defined (it might be 0),
this represents the ring Q(a)[x] together with its minimal polynomial.

@end table
@c ---end content RemainderMain---

@c ------------------- RootsMain -------------
@node RootsMain, SQFRNormMain, RemainderMain, zeroset_lib
@subsubsection RootsMain
@cindex RootsMain
@c ---content RootsMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
RootsMain(f); where f is a polynomial

@item @strong{Purpose:}
compute all roots of f in a finite extension of the ground field
without multiplicities.

@item @strong{Return:}
list, all entries are polynomials
  @format
  _[1] = roots of f, each entry is a polynomial
  _[2] = 'newA' - if the ground field is Q(a') and the extension field
         is Q(a), then 'newA' is the representation of a' in Q(a)
  _[3] = minpoly of the algebraic extension of the ground field
  @end format

@item @strong{Assume:}
basering = Q[x,a] ideal mpoly must be defined, it might be 0!

@item @strong{Note:}
might change the ideal mpoly !!

@end table
@c ---end content RootsMain---

@c ------------------- SQFRNormMain -------------
@node SQFRNormMain, ContainedQ, RootsMain, zeroset_lib
@subsubsection SQFRNormMain
@cindex SQFRNormMain
@c ---content SQFRNormMain---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
SQFRNorm(f); where f is a polynomial

@item @strong{Purpose:}
compute the norm of the squarefree polynomial f in Q(a)[x].

@item @strong{Return:}
list with 3 entries
  @format
  _[1] = squarefree norm of g (poly)
  _[2] = g (= f(x - s*a)) (poly)
  _[3] = s (int)
  @end format

@item @strong{Assume:}
f must be squarefree, basering = Q[x,a] and ideal mpoly is equal to
'minpoly',this represents the ring Q(a)[x] together with 'minpoly'.

@item @strong{Note:}
the norm is an element of Q[x]

@end table
@c ---end content SQFRNormMain---

@c ------------------- ContainedQ -------------
@node ContainedQ, SameQ, SQFRNormMain, zeroset_lib
@subsubsection ContainedQ
@cindex ContainedQ
@c ---content ContainedQ---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
ContainedQ(data, f [, opt]); data=list; f=any type, opt=integer

@item @strong{Purpose:}
test if f is an element of data.

@item @strong{Return:}
int
@*0 if f not contained in data
@*1 if f contained in data

@item @strong{Options:}
opt = 0 : use '==' for comparing f with elements from data@*
opt = 1 : use @code{SameQ} for comparing f with elements from data

@end table
@c ---end content ContainedQ---

@c ------------------- SameQ -------------
@node SameQ,, ContainedQ, zeroset_lib
@subsubsection SameQ
@cindex SameQ
@c ---content SameQ---
Procedure from library @code{zeroset.lib} (@pxref{zeroset_lib}).

@table @asis
@item @strong{Usage:}
SameQ(a, b); a,b=list/intvec

@item @strong{Purpose:}
test a == b elementwise, i.e., a[i] = b[i].

@item @strong{Return:}
int
@*0 if a != b
@*1 if a == b

@end table
@c ---end content SameQ---