A new class of term orders for elimination (Q2455741): Difference between revisions

For any ideal \(I\) in \(K[X][U]\), one can eliminate the \(U\) variables by computing a Gröbner basis under an elimination term order. This is especially useful in computer-aided geometric design, where such a process can be used to calculate the implicit representation of a surface given parametrically. Practically, however, such Gröbner bases are notoriously difficult to compute. In an earlier paper [Comput. Aided Geom. Des. 21, No. 9, 837--857 (2004; Zbl 1069.65569)], the author presented several methods for speeding up this type of computation. In particular, he noted that the polynomial system given in the implicitization problem is already a Gröbner basis under one order, and employed the Gröbner walk to arrive at the appropriate elimination order. Further, he provided an effective means of determining when one has arrived at an elimination order for the given ideal so that, in practice, one need not complete the walk. Rather, one can stop at an order defined by a weight vector which is only an elimination term order for the given ideal. This is important, as the last conversion (to the specified target term order) is usually the most difficult. While heuristic methods have been proposed that perturb the final point to something still (probably) valid but which is easier to compute, the heuristic guess may fail, leaving one with the original, difficult computation. In the current paper, the author gives more of the theoretical underpinnings of these ideas, providing a classification of ideal-specific term orders for elimination and a necessary and sufficient condition for elimination term orders in terms of Gröbner bases. The author also presents experimental results for patches from the well-known Newell's teapot. The results show that computation time under the new algorithm is usually less than half that of the computation time for the author's algorithm in [J. Symb. Comput. 30, 451--468, (2000; Zbl 0988.13016)]. The author points out that approximate Gröbner basis computations using coefficients with respect to a modulus of a prime number or floating-point coefficients fail to find solutions to these problems within a reasonable time.