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 |