Improving Suzuki-Sato's CGS Algorithm by Using Stability of Gröbner Bases and Basic Manipulations for Efficient Implementation
Yosuke Kurata · 2012
In this paper, we propose improving Suzuki-Sato’s algorithm for computing CGS. This paper consists of two parts. In the first part, using known algebraic manipulations on affine varieties, we describe a detail of basic manipulations to improve Suzuki-Sato’s algorithm. In the second part, we present a new algorithm which improves Nabeshima’s approach to compute a CGS. Nabeshima’s approach uses Grobner basis computations together with inequations, which involves an additional temporary variable. The approach sometimes generates time-consuming Grobner basis computations. As a result, Nabeshima’s approach is not always faster than Suzuki-Sato’s original one. Our new algorithm also uses inequations without the additional variable and works like Suzuki-Sato’s algorithm. So that, it is expected that the new algorithm reduces generating time-consuming Grobner basis computations. We compare the runtime and number of segments measured by the both algorithms and find our algorithm superior in several cases.