Structural Gröbner Basis Detection
Title | Structural Gröbner Basis Detection |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | Sturmfels, B., & Wiegelmann M. |
Other Numbers | 1027 |
Abstract | We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem is NP-complete in general, but solvable in polynomial time for m fixed and for n-m fixed. Our new algorithm for the latter case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-017.pdf |
Bibliographic Notes | ICSI Technical Report TR-96-017 |
Abbreviated Authors | B. Sturmfels and M. Wiegelmann |
ICSI Publication Type | Technical Report |