Mathematical Sciences

Clemson University

Martin Hall O-110

Clemson, SC 29634, USA

OFFICE: Martin Hall O-301

EMAIL: sgao@math.clemson.edu

PHONE: +1 (864) 656-2729

## A New Framework for Computing Grobner Bases (with Frank Volny IV and Mingsheng Wang)

Mathematics of Computation, 85:449--465, 2016.ABSTRACT: This paper presents a new framework for computing Gröbner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Gröbner basis for this module contains Gröbner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gröbner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing Gröbner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice.

[DOI]## Factoring multivariate polynomials via partial differential equations

Mathematics of Computation, 72:801--822, February 2003.ABSTRACT: A new method is presented for factorization of bivariate polynomials over any field of characteristic zero or of relatively large characteristic. It is based on a simple partial differential equation that gives a system of linear equations. As in Berlekamp’s and Niederreiter’s algorithms for factoring univariate polynomials, the dimension of the solution space of the linear system is equal to the number of absolutely irreducible factors of the polynomial to be factored, and any basis for the solution space gives a complete factorization by computing gcd’s and by factoring univariate polynomials over the ground field. The new method finds absolute and rational factorizations simultaneously and is easy to implement for finite fields, local fields, number fields, and the complex number field. The theory of the new method allows an effective Hilbert irreducibility theorem, thus an efficient reduction of polynomials from multivariate to bivariate.

[DOI]## Optimal normal bases (with Hendrik W. Lenstra, Jr.)

Designs, Codes and Cryptography, 2:315-323, 1992.ABSTRACT: Let K ⊂ L be a finite Galois extension of fields, of degree n. Let G be the Galois group, and let (<α)<∈G be a normal basis for L over K. An argument due to Mullin, Onyszchuk, Vanstone and Wilson (Discrete Appl. Math. 22 (1988/89), 149–161) shows that the matrix that describes the map x → αx on this basis has at least 2n - 1 nonzero entries. If it contains exactly 2n - 1 nonzero entries, then the normal basis is said to be optimal. In the present paper we determine all optimal normal bases. In the case that K is finite our result confirms a conjecture that was made by Mullin et al. on the basis of a computer search.

[DOI]

## MATH 3110 - Linear Algebra

Introduction to the algebra of matrices, vector spaces, polynomials, and linear transformations. Includes Honors sections.