Computing border bases without using a term ordering (Q1943354)

The article describes a new algorithm to compute border bases, a generalization of Gröbner bases suitable for computation with ``approximate'' data obtained from empirical measurements, as in the ApCoCoA computer algebra system. In fact, the algorithm described has been implemented in ApCoCoA, and border bases are of great interest for zero-dimensional ideals, on which this article focuses. Several algorithms to compute a border basis exist already, so why is a new one necessary? The primary aim is to extend an algorithm of \textit{A. Kehrein} and \textit{M. Kreuzer} [J. Pure Appl. Alg. 196, 251--270 (2005; Zbl 1097.13036)], which requires a degree-compatible term ordering and computes a reduced Gröbner basis of the ideal. Example 2.6 of the article shows that this aspect of the algorithm prevents it from computing certain border bases. The main idea in the paper is to generalize the traditional notion of a term ordering to a more general notion, called a ``term marking strategy'', which selects one of the maximal-degree terms of the polynomial. Marked polynomials seem to originate in [\textit{A. Reeves} and \textit{B. Sturmfels}, J. Symb. Comput. 16, No. 3, 273--277 (1993; Zbl 0794.12006)], but have shown up elsewhere in recent literature, as in [\textit{F. Cioffi} and \textit{M. Roggero}, J. Symb. Comput. 46, No. 9, 1070--1084 (2011; Zbl 1231.13024)]. A degree-compatible term ordering is always a term marking strategy, but the converse is not true, such as when the support of a polynomial contains a term desirable for the border basis, but impossible to select as a leading term according to the usual definition. One effective example in the article uses the set \(\left\{x^2,xy,y^2\right\}\), where \(xy\) needs to appear in the border basis; a degree-compatible ordering would prevent this, as either \(x^2>xy\) or \(y^2>xy\). Term-marking strategies allow the formulation of an algorithm to interreduce the input linearly, and to extend the algorithm of Kehrein and Kreuzer to compute a border basis with this new approach. Unsurprisingly, the effectiveness of the algorithm depends on the term marking strategy. Examples illustrate how some strategies produce results, while others terminate without a border basis. The reasons for this latter result are explained. To determine which strategies work, the article suggests a brute-force approach, slightly refined: try one, and if it fails, a bookkeeping approach allows one to backtrack. The author took care to write a clear, well-structured narrative, with remarks and examples that illustrate the main ideas effectively. No formal complexity analysis appears, although the final section's comparison of the new algorithm with those of [\textit{B. Mourrain} and \textit{P. Trébuchet}, ``Generalised normal forms and polynomial system solving'', In: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation. 253--260 (2005)] and [\textit{G. Braun} and \textit{S. Pokutta}, ``Border bases and order ideals: a polyhedral characterization'', \url{arxiv:0912.1502} (2009)] describes advantages for the new algorithm, as well as illustrating a drawback, to which we have already alluded: it cannot compute all border bases, as illustrated by a system and a term marking strategy based on a degree-compatible ordering.