Home Online Manual
Back: rvar
Forward: setring
FastBack: Functions and system variables
FastForward: Control structures
Up: Functions
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

5.1.133 sba

sba ( ideal_expression)
sba ( ideal_expression, int_expression, int_expression )
returns a standard basis of an ideal with respect to the monomial ordering of the basering. A standard basis is a set of generators such that the leading terms generate the leading ideal, resp. module.
Use optional second and third arguments of type int to determine the respective variant of the signature-based standard basis algorithm:
The second argument specifies the internal module order sba uses:
  • 0: induced Schreyer order on the signatures, non-incremental computation of the basis
  • 1: position over term order, incremental computation of the basis
  • 2: term over position order, non-incremental computation
  • 3: Schreyer-weighted degree over index over leading term

The third argument specifies the rewrite order sba uses:
  • 0: using the rewrite order described in http://dx.doi.org/10.1016/j.jsc.2010.06.019
  • 1: using the rewrite order described in http://dx.doi.org/10.1016/j.jsc.2011.05.004

The standard call of sba(i) corresponds to sba(i,0,1).
The standard basis is computed with an optimized version of known signature-based algorithms like Faugere's F5 Algorithm. Whereas the correctness of the algorithms is only guaranteed for global orderings, timings for pure lexicographical orderings can be slow. In this situation you should try to compute the basis w.r.t. the graded reverse-lexicographic ordering and then convert to a basis for the lexicographical ordering using other methods ( see fglm and see grwalk_lib). If the algorithms tend to use too much memory, you should try the other implemented standard basis algorithms ( see std, see groebner, and see slimgb).
Note that the behaviour of sba on an example can be rather different depending on which variant you choose (second and third argument).
  // incremental F5 computation
  ring r=32003,(x,y,z),dp;
  poly s1=1x2y+151xyz10+169y21;
  poly s2=1xz14+6x2y4+3z24;
  poly s3=5y10z10x+2y20z10+y10z20+11x3;
  ideal i=s1,s2,s3;
  ideal j=sba(i,1,0);
  // non-incremental F5 computation
  ring rhom=32003,(x,y,z,h),dp;
  ideal i=homog(imap(r,i),h);
  ideal j=sba(i,0,0);
  // non-incremental signature-based computation
  ring whom=32003,(x,y,z),dp;
  ideal i=fetch(r,i);
  ideal j=sba(i);
See fglm; groebner; ideal; ring; slimgb; std.