up previous next

2.2.24 Finite Point Sets: Buchberger-Moeller

CoCoA includes an implementation of the Buchberger-Moeller algorithm for efficient computations dealing with finite sets of points. These functions include:

* GBM, HGBM -- intersection of ideals for zero-dimensional schemes

* IdealAndSeparatorsOfPoints -- ideal and separators for affine points

* IdealAndSeparatorsOfProjectivePoints -- ideal and separators for points

* IdealOfPoints -- ideal of a set of affine points

* IdealOfProjectivePoints -- ideal of a set of projective points

* Interpolate -- interpolating polynomial

* SeparatorsOfPoints -- separators for affine points

* SeparatorsOfProjectivePoints -- separators for projective points

Details about these functions may be found individually in the online manual. Briefly, the functions above may be used to find the ideal of a set of points in affine or projective space along with a reduced Groebner basis and separators. Separators are polynomials that take the value 1 on one of the points and 0 on the remainder. The Buchberger-Moeller algorithm works much faster than the straightforward technique involving intersecting ideals for the individual points.

Example

Use R ::= QQ[t,x,y,z]; Pts := GenericPoints(20); -- 20 random points in projective 3-space X := IdealAndSeparatorsOfProjectivePoints(Pts); Len(Gens(X.Ideal)); -- number of generators in the ideal 17 ------------------------------- Hilbert(R/X.Ideal); H(0) = 1 H(1) = 4 H(2) = 10 H(t) = 20 for t >= 3 ------------------------------- F := X.Separators[3]; [Eval(F, P)| P In Pts]; [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ------------------------------- Res(R/X.Ideal); -- the resolution of the ideal 0 --> R^10(-6) --> R^24(-5) --> R^15(-4) --> R -------------------------------