Campuses:

<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.