Last Modified: 2000-08-22 (Minor Update on 2003-05-02)
What is Gröbner basis?
In 1960s, Gröbner basis has been introduced:
- for polynomial ring:
Buchberger introduced Gröbner basis to compute
the structure of ideals and modules of polynomial ring.
- for power series ring:
Hironaka introduced "standard basis" (similar to Gröbner basis)
in his paper about the resolution of simgularities.
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:
- Integer programmings
- System of linear equations
- Coding theory
- Computer graphics
- Triangulations of polytopes
- Enumeration and sampling of contingency tables
in computational statistics
- Symmetric bifurcation theory and orbit space reduction in physics
and so on.
The aim of our research is to study the algebraic approach
for the algorithms for many fields using Gröbner basis.
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.