Publication Details
Title: Structural Gröbner Basis Detection
Author: B. Sturmfels and M. Wiegelmann
Group: ICSI Technical Reports
Date: May 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-017.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-017
Bibliographic Reference:
B. Sturmfels and M. Wiegelmann. Structural Gröbner Basis Detection. ICSI Technical Report TR-96-017, May 1996
Author: B. Sturmfels and M. Wiegelmann
Group: ICSI Technical Reports
Date: May 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-017.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-017
Bibliographic Reference:
B. Sturmfels and M. Wiegelmann. Structural Gröbner Basis Detection. ICSI Technical Report TR-96-017, May 1996