Imai Laboratory > Projects > Gröbner Bases
Last Modified: 2000-08-22 (Minor Update on 2003-05-02)

Gröbner Bases

What is Gröbner basis?

In 1960s, Gröbner basis has been introduced:

Recently, Gröbner basis provides the foundation for many algorithms in algebraic geometry and commutative algebra, and is put in many computer algebra systems.

Applications of Gröbner basis

Recently, applications of Gröbner basis for ideals for various fields have been studied. For examples:

and so on. The aim of our research is to study the algebraic approach for the algorithms for many fields using Gröbner basis.

Our results


We have analyzed the structure of Gröbner bases for "toric ideals of graphs" which corresponds the linear space of cycles of graphs. Gröbner bases of undirected graphs have been studied and applied to many fields. On the other hand, Gröbner bases of directed graphs are not well understood since they have bad algebraic properties. We have studied the structure of Gröbner bases of directed graphs which have no directed cycle, and analyzed the complexities such as the degree and the number of elements in the bases. In addition, we applied these results to the following fields:

Minimum cost flow problems
We applied to the minimum cost flow problems and analyzed the complexity. Although the polynomial time algorithms are already known for the minimum cost flow, we approached from the viewpoint of algebra using Gröbner bases.
Computation of the dimension of solutions of a certain hypergeometric systems
For a certain system of linear partial differential equations (which is called "hypergeometric systems") arose from Lie algebra, we have shown that the dimension of the system can be computed using Gröbner bases. Although the dimension of these system have been already studied by Gelfand, Graev and Postnikov, we have given another proof from the algebraic viewpoint.