#### Date of Award

8-2010

#### Degree Type

Masters Thesis

#### Degree Name

Master of Science (MS)

#### Department

Mathematics

#### Committee Chair

John Perry

#### Committee Chair Department

Mathematics

#### Abstract

How to solve a linear equation system? The echelon form of this system will be obtained by Gaussian elimination then give us the solution. Similarly, Gröbner Basis is the “nice form” of nonlinear equation systems that can span all the polynomials in the given ideal [4]. So we can use Gröbner Basis to analyze the solution of a nonlinear equation system.

But how to compute a Gröbner Basis? There exist several ways to do it. Buchberger’s algorithm is the original method [2]. Gebauer-Möller algorithm [6] is a refined Buchberger’s algorithm. The F4 algorithm [5] uses matrix reduction to compute efficiently. Involutive Basis algorithm [8, 1, 12] is an effective method avoiding much ambiguity in the other algorithms.

In Chapters 1 and 2 we describe two well-known methods of computing Gröbner Basis called Buchberger’s and F4 algorithm. In Chapter 3 after presenting the definition of involutive division we give a detailed formulation of basic and improved Involutive Basis algorithm. We will see that there exists ambiguity both in Buchberger’s and F4 algorithm. But in the method of Involutive Basis Algorithm, the ambiguity for the choice of prolongation has been avoided. So in Chapter 4 we combine the F4 algorithm and Involutive Basis algorithm in order to obtain a new approach that can reduce polynomials faster as well as avoid ambiguity. The combined algorithm called F4-involutive is a partial result due to its efficiency. More work such as implementing Buchberger’s criteria would be done in the future.

#### Copyright

Copyright for this thesis is owned by the author. It may be freely accessed by all users. However, any reuse or reproduction not covered by the exceptions of the Fair Use or Educational Use clauses of U.S. Copyright Law or without permission of the copyright holder may be a violation of federal law. Contact the administrator if you have additional questions.

#### Recommended Citation

Yu, Miao, "An F4-Style Involutive Basis Algorithm" (2010). *Master's Theses*. 2.

http://aquila.usm.edu/masters_theses/2