ApCoCoALib:BBasis

User documentation for files BorderBasis.C and BorderBasis.H

About

These files contain an implementation of the Improved Border Basis Algorithm found in [1]. If gens is set of polynomials that generate a zero-dimensional ideal Id(gens) and sigma is a degree-compatible term ordering then the algorithm computes a O_\sigma{Id(gens)}-border basis.

Currently there is one function to apply the Improved Border Basis Algorithm to a set of polynomials:

void BorderBasis(BBasis, gens, N)

Applies the algorithm to the set of polynomials gens and returns the computed polynomials in BBasis. gens and BBasis should be std::vector objects. The third parameter N is an optional integer value > 0 and defaults to 12345 if not specified. It controls the enlargement of the computing universe (see [1] for details).

Maintainer documentation for files BorderBasis.C and BorderBasis.H

The current implementation will work correctly but it is not very efficient.

The functions ComputeKBasisExtension and FinalReduction are straight forward implementations of the algorithms stated in [1].

Details for construction of order ideal O in step (I7)

---

[Not yet included.]

Details for check if border of order ideal is contained in universe L in step (I8)

---

Universe L is spanned by its corner terms, order ideal O from step (I7) is spanned by its corner terms. It suffices to check if t_c*x_i is not contained in L for every corner term t_c of O and every indeterminant x_i in order to determine if the border of O is contained in L and if L needs to be updated or not. It also suffices to use the terms t_c*x_i that are not contained in L to update L. Explanation: Let b = x_i*t a border term not contained in L, t in O, x_i in {x_1, ..., x_n}. t_c = s*t for a corner term t_c of O and a term s. Then the border term x_i*t_c = x_i*s*t is divisible by b and because L is an order ideal, x_i*t_c cannot be contained in L. This shows why L needs only be enlarged by x_i*t_c, too.

Bugs, Shortcomings and other ideas

The current implementation will work correctly but it is not very efficient. Profiling should be done to see where the bottlenecks really are.

References

[1] A. Kehrein und M. Kreuzer, Computing border bases,

   J. Pure Appl. Alg. 205 (2006), S. 279 - 295