# <span class=strong>Reception and Poster Session<br/><br/></span>

Monday, September 18, 2006 - 4:30pm - 6:00pm

Lind 400

**Zhuang-Zi: A New algorithm for Solving Multivariate Polynomial Equations Over a Finite Field**

Jintai Ding (University of Cincinnati)

We present the Zhuang-Zi algorithm, a new method for solving

multivariate polynomial equations over a finite field. The main idea of

this new algorithm is the usage of Frobenius map. We will describe the

algorithm and present some interesting examples, where this new algorithm

works, but other known fast algorithms do not.**Computing Holes in Semi-groups**

Ruriko Yoshida (University of Kentucky)

Does a given system of linear equations with nonnegative constraints have

an integer solution? This is a fundamental question in many areas. In

statistics this problem arises in data security problems for contingency

table data and also is closely related to non-squarefree elements of

Markov bases for sampling contingency tables with given marginals. To

study a family of systems with no integer solution, we focus on a

commutative semigroup generated by a finite subset of $Z^d$ and its

saturation. An element in the difference of the semigroup and its

saturation is called a hole.

We present an algorithm to compute an explicit description for the

difference of a semi-group $Q$ generated by vectors in $Z^d$ and its

saturation $Q_{sat}$. If $H=Q_{sat}setminus Q$ is finite, we give an

upper bound for the entries of $hin H$. Finally, we present an algorithm

to find all $Q$-minimal saturation points in $Q$.

This is joint work with Raymond Hemmecke and Akimichi Takemura.**Approximate Radicals for Clusters: An Approach Based on Gaussian Elimination or SVD**

Itnuit Janovitz-Freireich (North Carolina State University)

We present a method based on Dickson's lemma to compute the approximate

radical of a zero dimensional ideal I which has zero clusters: the

approximate radical ideal has exactly one root in each cluster for

sufficiently small clusters. Our method is global in the sense that it

does not require any local approximation of the zero clusters: it reduces

the problem to the computation of the numerical nullspace of the so called

matrix of traces, a matrix computable from the generating polynomials of

I. To compute the numerical nullspace of the matrix of traces we propose

to use Gauss elimination with pivoting or singular value decomposition. We

prove that if I has k distinct zero clusters each of radius at most

epsilon in the infinity-norm, then k steps of Gauss elimination on the

matrix of traces yields a submatrix with all entries asymptotically equal

to epsilon square. We also show that the (k+1)-th singular value of the

matrix of traces is proportional to epsilon square. The resulting

approximate radical

has one root in each cluster with coordinates which are the arithmetic

mean of the cluster, up to an error term asymptotically equal to epsilon

square. In the univariate case our method gives an alternative to known

approximate square-free factorization algorithms which is simpler and its

accuracy is better understood.

This is joint work with Lajos Ronyai and Agnes Szanto.**Representing NP-complete Problems with Polynomials Ideals: An Exploration of**

Computational Complexity Based on Gröbner Bases and Hilbert's

Nullstellensatz

Susan Margulies (University of California)

We model NP-complete problems using zero-dimensional polynomial ideals. This

encoding adds tools for the understanding of NP-Complete problems based on

their algebraic invariants.

We have done this for several problems, but for this preliminary report we

focus on the graph k-coloring problem.

1) We investigated polynomial ideal models of varying degrees and/or number

of variables, and their accompanying Grobner bases.

2) Based on Hilbert's Nullstellsatz, we certify infeasibility. We show that

for NP-Complete problems, the smallest degree of the Nullstellensatz

certificates

must grow. We have designed a large-scale sparse linear algebra heuristic

to determine the smallest degree Nullstellensatz certificate, and we have

implementated this heuristic in terms of the graph coloring problem and

display our experimental results.

Joint work with J. De Loera, J. Lee, and S. Onn.**Computation of Rankings on Partial Derivatives**

Oleg Golubitsky (Queen's University)

Rankings on partial derivatives generalize admissible term orders and play a similar role:

decomposition algorithms for differential algebraic varieties require introduction

of a ranking. We propose an algorithm that, given a finite set of differential polynomials

with selected leading derivatives, determines whether this selection is consistent with a

ranking and, if so, constructs such a ranking. Computation of a universal decomposition of a

radical differential ideal, i.e., the one that is valid for any ranking, and the differential

generalization of the Groebner walk method rely on the solution of this problem.**Smooth and Algebraic Invariants of a Group Action**

Irina Kogan (North Carolina State University)

We provide an algebraic formulation of the moving frame method for

constructing local smooth invariants on a manifold under an action of a

Lie group. This formulation gives rise to algorithms

for constructing rational and replacement invariants. The latter are

algebraic over the field of rational invariants and play a role analogous

to Cartan's normalized invariants in the smooth theory. The algebraic

algorithms can be used for computing fundamental sets of differential

invariants. This is a joint work with Evelyne Hubert, INRIA, France.**Counting Components Heuristically**

Hans-Christian von Bothmer (Universität Hannover)

Via the Weil-Conjectures one can obtain a lot of geometric information about an algebraic variety X defined over ZZ by counting points over a finite field F_p. Unfortunatedly in many interesting examples it is impossible to count all points because there simply are too many of them. By evaluating the equations of X in a number of random points one can estimate the total number of points with sufficient precision to obtain information about the number of components of X and the codimensions of these components. This method is fast and easily parallelizable, but yields results that are only probably right.**Partial Differential Equations and Real, Finitely Generated, Commutative, and Associative Algebra**

Paul Pedersen (Los Alamos National Laboratory)

Using the exponential function defined on real, finitely

generated,

commutative and associative algebras we describe an algorithm

which

gives a constructive, countable basis for the set of power

series

solutions to any system of linear constant coefficient PDE's.

This

generalizes the fact that functions of a complex variable can

be used

to give a basis for real power series solutions to Laplace's

equation in

2 variables.**Algorithms for Finding Symmetric Gröbner Bases in Infinite Dimensional Rings**

Christopher Hillar (Texas A & M University)

Let K be a field and let R be the polynomial ring in infinitely

many indeterminates over K. Since R is not Noetherian, computation in R,

and in particular, of Gröbner bases, is impossible. However, suppose

that we consider ideals I which are invariant under the infinite symmetric

group G. Then, as an R[G]-module, R is Noetherian and invariant ideals I

have (finite) Gröbner bases (as proved recently by Aschenbrenner and

Hillar). We review this story and describe a new result that gives an

explicit method for computing in R; in particular, solving the membership

problem for invariant ideals.**Computing the Abel map and vector of Riemann constants**

Bernard Deconinck (University of Washington)Matt Patterson (University of Washington)

The Kadomtsev-Petviashvili equation is known to describe approximately the

evolution of surface waves in shallow water. This equation admits families

of multi-phase solutions parameterised by Riemann surfaces. In order to

explicitly calculate these soultions we have created black-box algorithms

to compute the Abel map and the Riemann constant vector(RCV). A Riemann

surface is associated with its Jacobian through the Abel map. The RCV is

the offset between the theta-divisor and the image under the Abel map of

the (g-1)-th symetric power of a Riemann surface of genus g. Using a plane

algebraic curve representation of the Riemann surface, we provide an

algorithm for the numerical computation of the Abel map and the vector of

Riemann constants. Since our plane algebraic curves are of arbitrary degree

and may have arbitrary singularities, the Abel map and RCV of any connected

compact Riemann surface may be obtained in this way.**Change of Order for Regular Chains in Positive Dimension**

Eric Schost (École Polytechnique)

Joint work with Xavier Dahan, Xin Jin, and Marc Moreno Maza.

We discuss changing the variable ordering for a regular chain in

positive dimension. This quite general question has applications going

from implicitization problems to the symbolic resolution of some

systems of differential algebraic equations.

We propose a modular method, reducing the problem to dimension zero

and using Newton-Hensel lifting techniques. The problems raised by the

choice of the specialization points, the lack of the (crucial)

information of what are the free and algebraic variables for the new

ordering, and the efficiency regarding the other methods are

discussed. Strong hypotheses (but not unusual) for the initial regular

chain are required. Change of ordering in dimension zero is taken as

a subroutine.**Degenerating Ideals to Toric Ideals: A Method Used in the Solution of a Problem from Classical Invariant Theory**

Benjamin Howard (University of Minnesota, Twin Cities)

By weighting monomials appropriately it may be possible to

assign a filtration to a ring so that the associated graded ring is toric.

If this toric

variety is sufficiently simple, one may be able to find the relations

among the

generators of the toric ideal. Then by lifting these

toric relations to the ideal of the original ring, one obtains generators

of the

original ideal. This method was applied to find a finite generating

set of relations among the PGL(2) invariants of n-tuples of points on the

projective line. This is joint work with John Millson, Andrew Snowden,

and Ravi Vakil.**Bounds and Algebraic Algorithms for Ordinary Differential Characteristic Sets**

Oleg Golubitsky (Queen's University)

Joint work with Marina Kondratieva, Marc Moreno Maza, and Alexey Ovchinnikov.

The Rosenfeld-Groebner algorithm computes a regular decomposition of a radical differential

ideal and thus is a key tool that allows to study algorithmic properties

of differential algebraic varieties. We prove a bound on the orders of derivatives occurring

in the intermediate differential polynomials computed by this algorithm in

the ordinary case. We also reduce the problem of conversion of a characteristic decomposition

of a radical differential ideal from one ranking to another to a purely algebraic problem.**An Ideal Separating Extension of Affine Space**

Paul Pedersen (Los Alamos National Laboratory)

In affine space the set of solutions to a system of polynomial

equations

does not uniquely determine the system. We extend affine space

so that

the set of solutions (in the extension) to a system of

equations

uniquely determines the system.**Irreducible Decomposition of Monomial Ideals and Upper Bound on Number of Irreducible Components**

Mingfu Zhu (Clemson University)

We give three algorithms for finding the irreducible decomposition of

monomial ideals. The first one is based on the duality between the

intersection and sum operations of monomial ideals. The second one is

based on the projection and the staircase structure of monomial ideals.

The third one is based on a simple enumeration algorithm to traverse

all the facets of the Scarf complex associated with a monomial ideal.

Finally, by using The splitting algorithm and the properties of

the staircase structure, we give a sharper upper bound

on the number of irreducible components . Joint work with Shuhong Gao.