Web: http://www.ima.umn.edu | Email: ima-staff@ima.umn.edu | Telephone: (612) 624-6066 | Fax: (612) 626-7370

### September 2006

2006-2007 Program

### Applications of Algebraic Geometry

See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.

News and Notes

IMA 2006-2007 Thematic year on Applications of Algebraic Geometry begins

Algebraic geometry has a long and distinguished presence in the history of mathematics that produced both powerful and elegant theorems. In recent years new algorithms have been developed and several old and new methods from algebraic geometry have led to significant and unexpected advances in several diverse areas of application. Motivated by these exciting developments, the year in algebraic geometry and its applications aims to bring together mathematicians, computer scientists, economists, statisticians and engineers from various disciplines in order to enhance interactions, generate new applications and motivate further progress. In the first quarter, the two workshops cover algorithms and software with a particular eye towards applications. In the second and third quarter, the workshops cover applications in optimization, control, statistics, economics and bioinformatics, coding, complexity, communications and computational geometry.

Cheri Shakiban Joins IMA as Associate Director

Professor Cheri Shakiban has joined the Institute for Mathematics and its Applications at the University of Minnesota as associate director for a two-year term. Dr. Shakiban succeeds Debra Lewis, who has completed a two-year term of service at the IMA and returning to the University of California, Santa Cruz, where she is professor of mathematics. A thanks and good-bye to Debra! Cheri Shakiban is a professor of mathematics at the University of St. Thomas in St. Paul, Minnesota, where she served as department chair from 1996 through 2004. Her recent research is mostly in the area of computer vision, in which she studies the detection of symmetries, visual tracking, and the reconstruction of occlusions in space curves, with applications to the description of supercoiled DNA molecules. At St. Thomas she has been very active with the support and mentoring of undergraduate research.

Michigan Tech joins the IMA

Michigan Tech has joined the IMA as a Participating Institution. MTU's representative on the Participating Institutions Council is Mark Gockenbach, interim chair of the Mathematical Sciences Department.

IMA Events

### Algebraic Geometric Methods in Engineering

#### September 15-16, 2006

Organizers: Sanjay Lall (Stanford University), Pablo A. Parrilo (Massachusetts Institute of Technology), Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA))

### Algorithms in Algebraic Geometry

#### September 18-22, 2006

Organizers: Alicia Dickenstein (University of Buenos Aires), Frank-Olaf Schreyer (Universität des Saarlandes), Andrew Sommese (University of Notre Dame)
Schedule

## Monday, September 4

 All Day Labor Day —IMA closed.

## Wednesday, September 6

 10:45a-11:45a Start of the Year Reception for IMA visitors Lind Hall 400 11:15a-12:15p Start of the Year Orientation for IMA visitors Lind Hall 409

## Thursday, September 7

 10:30a-11:00a Coffee Break Lind Hall 400 11:00a-12:00p Postdoc Show and Tell EE/CS 3-180 12:15p-1:30p Postdoc Lunch and Posters (RSVP to don@ima.umn.edu until Sep 5) Lind Hall 400 1:30p-2:30p Postdoc Show and Tell (continued) EE/CS 3-180

## Friday, September 8

 11:15a-12:15p Computer orientation for PostDocs and Longterm visitors Lind Hall 409

## Wednesday, September 13

 11:15a-12:15p Solving polynomial systems by homotopy continuation Andrew Sommese (University of Notre Dame) Lind Hall 409 AGS

## Thursday, September 14

 11:15a-12:15p Weekly Tutorial- Real Algebraic Geometry Kenneth Driessel (Iowa State University) Lind Hall 409 RAG

## Friday, September 15

 8:15a-8:45a Coffee and registration EE/CS 3-176 T9.15-16.06 8:45a-9:00a Welcome and opening remarks Douglas N. Arnold (University of Minnesota Twin Cities) EE/CS 3-180 T9.15-16.06 9:00a-9:50a Control Theory and Algebraic Geometry Sanjay Lall (Stanford University) EE/CS 3-180 T9.15-16.06 10:00a-10:30a Break EE/CS 3-176 T9.15-16.06 10:30a-11:20a Some certified methods for Real Solving - applications in robotics Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA)) EE/CS 3-180 T9.15-16.06 11:30a-1:30p Lunch T9.15-16.06 1:30p-2:20p Control Theory and Algebraic Geometry (continued) Sanjay Lall (Stanford University) EE/CS 3-180 T9.15-16.06 2:30p-3:00p Break EE/CS 3-176 T9.15-16.06 3:00p-3:50p Some certified methods for Real Solving - applications in robotics (continued) Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA)) EE/CS 3-180 T9.15-16.06 4:00p-4:30p Second Chances EE/CS 3-180 T9.15-16.06

## Saturday, September 16

 8:50a-9:00a Coffee EE/CS 3-176 T9.15-16.06 9:00a-9:50a Mechanisms and Robot Kinematics: Algebraic Foundations Charles W. Wampler (General Motors Corporation) EE/CS 3-180 T9.15-16.06 10:00a-10:30a Break EE/CS 3-176 T9.15-16.06 10:30a-11:20a Solution of Integral and Differential Equations using Algebraic Splines Chandrajit L. Bajaj (University of Texas) EE/CS 3-180 T9.15-16.06 11:30a-1:30p Lunch T9.15-16.06 1:30p-2:20p Mechanisms and Robot Kinematics: Numerical Algebraic Geometry Charles W. Wampler (General Motors Corporation) EE/CS 3-180 T9.15-16.06 2:30p-3:00p Break EE/CS 3-176 T9.15-16.06 3:00p-3:50p Solution of Integral and Differential Equations using Algebraic Splines Chandrajit L. Bajaj (University of Texas) EE/CS 3-180 T9.15-16.06 4:00p-4:30p Second Chances EE/CS 3-180 T9.15-16.06

## Monday, September 18

 8:30a-9:15a Registration and coffee EE/CS 3-176 W9.18-22.06 9:15a-9:30a Welcome to the IMA Douglas N. Arnold (University of Minnesota Twin Cities) EE/CS 3-180 W9.18-22.06 9:30a-10:20a Generalizing the cross-ratio: the moduli space of n points on the projective line is cut out by simple quadrics if n is not six Ravi Vakil (Stanford University) EE/CS 3-180 W9.18-22.06 10:20a-10:50a Coffee EE/CS 3-176 W9.18-22.06 10:50a-11:40a Factorization of Sparse Polynomials Teresa Krick (University of Buenos Aires) EE/CS 3-180 W9.18-22.06 11:40a-1:40p Lunch W9.18-22.06 1:40p-2:30p Counting Rational Points on Varieties over Finite Fields Daqing Wan (University of California) EE/CS 3-180 W9.18-22.06 2:30p-3:00p Coffee EE/CS 3-176 W9.18-22.06 3:00p-3:50p Maple's Algebraic Curves Package Mark van Hoeij (Florida State University) EE/CS 3-180 W9.18-22.06 4:00p-4:30p Second Chances, a discussion period to revisit workshop topics and issues and look towards future directions. EE/CS 3-180 W9.18-22.06 4:30p-6:00p Reception and Poster Session Lind Hall 400 W9.18-22.06 Computing the Abel map and vector of Riemann constants Bernard Deconinck (University of Washington) Matt Patterson (University of Washington) Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field Jintai Ding (University of Cincinnati) Computation of rankings on partial derivatives Oleg Golubitsky (Queen's University) Degenerating ideals to toric ideals: a method used in the solution of a problem from classical invariant theory Benjamin J. Howard (University of Minnesota Twin Cities) Approximate radicals for clusters: an approach based on Gaussian elimination or SVD Itnuit Janovitz-Freireich (North Carolina State University) Smooth and Algebraic Invariants of a Group Action Irina Kogan (North Carolina State University) Representing NP-Complete problems with polynomials ideals: An exploration of Computational Complexity based on Grobner bases and Hilbert's Nullstellensatz Susan Margulies (University of California) Numerical Campedelli surfaces with algebraic fundamental group of order 9 Margarida Mendes Lopes (Universidade Técnica de Lisboa) Change of order for regular chains in positive dimension Eric Schost (École Polytechnique) Computing holes in semi-groups Ruriko Yoshida (University of Kentucky) Irreducible Decomposition of Monomial Ideals and Upper Bound on Number of Irreducible Components Mingfu Zhu (Clemson University) Counting Components Heuristically Hans-Christian von Bothmer (Universität Hannover)

## Tuesday, September 19

 9:00a-9:30a Coffee EE/CS 3-176 W9.18-22.06 9:30a-10:20a Polar and dual varieties of real curves and surfaces Ragni Piene (University of Oslo) EE/CS 3-180 W9.18-22.06 10:20a-10:50a Coffee EE/CS 3-176 W9.18-22.06 10:50a-11:40a Intersection and Self-intersection of surfaces by means of Bezoutian matrices Laurent Buse (Institut National de Recherche en Informatique Automatique (INRIA)) EE/CS 3-180 W9.18-22.06 11:40a-1:40p Lunch W9.18-22.06 1:40p-2:30p Projections methods for the topology of algebraic curves and surfaces Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) EE/CS 3-180 W9.18-22.06 2:30p-3:00p Coffee EE/CS 3-176 W9.18-22.06 3:00p-3:50p Applications of monomial ideals and computational algebra in the reverse engineering of biological networks. Michael E. Stillman (Cornell University) EE/CS 3-180 W9.18-22.06 3:30p-4:30p Junior Colloquium: Peter D. Lax (Ordway Visitor), The Change of Variables Formula for Multiple Integrals Vincent 16 4:00p-4:30p Second Chances, a discussion period to revisit workshop topics and issues and look towards future directions. EE/CS 3-180 W9.18-22.06 4:30p-4:40p Group picture W9.18-22.06

## Wednesday, September 20

 9:00a-9:30a Coffee EE/CS 3-176 W9.18-22.06 9:30a-10:20a Finding all real solutions contained in a complex algebraic curve Charles W. Wampler (General Motors Corporation) EE/CS 3-180 W9.18-22.06 10:20a-10:50a Coffee EE/CS 3-176 W9.18-22.06 10:50a-11:40a On the Effectiveness of Number Theory in Algebraic Geometry J. Maurice Rojas (Texas A & M University) EE/CS 3-180 W9.18-22.06 11:40a-1:40p Lunch W9.18-22.06 1:40p-2:30p Tools for extracting information from numerically approximated varieties and schemes Chris Peterson (Colorado State University) EE/CS 3-180 W9.18-22.06 2:30p-3:00p Coffee EE/CS 3-176 W9.18-22.06 3:00p-3:50p The numerical computation of the multiplicity of a component of an algebraic set Daniel J. Bates (University of Minnesota Twin Cities) EE/CS 3-180 W9.18-22.06 4:00p-4:30p Second Chances, a discussion period to revisit workshop topics and issues and look towards future directions. EE/CS 3-180

## Thursday, September 21

 9:00a-9:30a Coffee EE/CS 3-176 W9.18-22.06 9:30a-10:20a New Fewnomial Upper Bounds from Gale Dual Polynomial Systems Frank Sottile (Texas A & M University) EE/CS 3-180 W9.18-22.06 10:20a-10:50a Coffee EE/CS 3-176 W9.18-22.06 10:50a-11:40a Grobner basis structure and decomposition of polynomial systems Shuhong Gao (Clemson University) EE/CS 3-180 W9.18-22.06 11:40a-1:40p Lunch W9.18-22.06 1:40p-2:30p On the Complexity of Groebner Basis Computation for Regular and Semi-Regular Systems Bruno Salvy (Institut National de Recherche en Informatique Automatique (INRIA)) EE/CS 3-180 W9.18-22.06 2:30p-3:00p Coffee EE/CS 3-176 W9.18-22.06 3:00p-3:50p Mixed Volume Computation Tien-Yien Li (Michigan State University) EE/CS 3-180 W9.18-22.06 3:30p-4:30p Colloquium: Peter D. Lax (Ordway visitor), Overview of the Zero Dispersion Limit Vincent 16 4:00p-4:30p Second Chances, a discussion period to revisit workshop topics and issues and look towards future directions. EE/CS 3-180 W9.18-22.06 6:00p-9:00p Workshop Dinner Kikugawa at River Place W9.18-22.06

## Friday, September 22

 9:00a-9:30a Coffee EE/CS 3-176 W9.18-22.06 9:30a-10:20a The Newton Polytope of the Implicit Equation Bernd Sturmfels (University of California) EE/CS 3-180 W9.18-22.06 10:20a-10:50a Coffee EE/CS 3-176 W9.18-22.06 10:50a-11:40a Algorithms for Invariant Rings of Algebraic Groups Harm Derksen (University of Michigan) EE/CS 3-180 W9.18-22.06 11:50a-12:20p Second Chances, a discussion period to revisit workshop topics and issues and look towards future directions. EE/CS 3-180 W9.18-22.06 12:20p-12:30p Closing Discussion EE/CS 3-180 W9.18-22.06

## Monday, September 25

 9:30a-10:30a Semigraphoids, Permutohedra, and Mice Bernd Sturmfels (University of California) Lind Hall 305 AGS 11:15a-12:15p Asymptotic Ideal Theory and Parametrized Rational Varieties David Eisenbud (Mathematical Sciences Research Institute) Lind Hall 305 AGS

## Tuesday, September 26

 11:15a-12:15p Applied Math Seminar: Peter D. Lax (Ordway visitor), Positive schemes for solving hyperbolic equations Vincent 1

## Wednesday, September 27

 11:15a-12:15p Approximating singular solutions of polynomial systems Anton Leykin (University of Minnesota Twin Cities) Lind Hall 409 AGS

## Friday, September 29

 1:25p-2:25p Fiber products and exceptional sets Charles W. Wampler (General Motors Corporation) Room 6 Vincent Hall IPS
Abstracts
 Colloquium: Peter D. Lax (Ordway visitor), Overview of the Zero Dispersion Limit Abstract: Many physical theories contain small parameters;thus Schroedinger's equation contains Planck's constant h,the Navier-Stokes equation the reciprocal of the Reynolds number R. The limits h and 1/R tending to zero are of great interest. This talk is about the limiting behavior of solutions of the Korteweg-DeVries equation when the coefficient of dispersion tends to zero. Chandrajit L. Bajaj (University of Texas) Solution of Integral and Differential Equations using Algebraic Splines Abstract: This two part tutorial shall introduce you to algorithmic algebraic geometry methods of manipulating algebraic (polynomial) splines necessary for the solution of multivariate integral and partial differential equations emanating from science and engineering applications. In the first part, we shall discuss well known (classical) algorithms for modeling the structure and energetics of physical domains (molecules to airplanes to oil fields), at multiple scales, with implicit algebraic splines (A-patches), and their rational parametric splines (NURBS) approximations. Algebraic geometry methods include computing global and local parameterizations using Newton factorization and Hensel lifting, computation of adjoints by interpolating through singularities, and low degree curve and surface intersections via Resultants and/or Groebner Basis calculations. The second part shall focus on more current research and attempts at using algebraic geometry methods for faster and more accurate calculations of multivariate definite integrals of algebraic functions arising from the solution of polarization energetics and forces (Generalized Born, Poisson Boltzmann) and Green function solutions of two-phase Stokesian flows. These algebraic geometry methods include the use of ideal theory and solutions of polynomial systems of equations for more accurate cubature formulas and their faster evaluation. Daniel J. Bates (University of Minnesota Twin Cities) The numerical computation of the multiplicity of a component of an algebraic set Abstract: The solution set of a polynomial system decomposes into a union of irreducible components. The set of polynomials imposes on each component a positive integer known as the multiplicity of the component. This number is of interest not only because of its meaning in applications but also because a number of numerical methods have difficulty in problems where the multiplicity of a component is greater than one. In this talk, I will discuss a numerical algorithm for determining the multiplicity of a component of an algebraic set. This is joint work with Chris Peterson and Andrew Sommese. Laurent Buse (Institut National de Recherche en Informatique Automatique (INRIA)) Intersection and Self-intersection of surfaces by means of Bezoutian matrices Abstract: The computation of the intersection and self-intersection loci of parameterized space algebraic surfaces is an important task in Computer Aided Geometric Design. In this talk, we will show that these loci can be represented by particular projections corresponding to certain resultants which can be exactly computed as the determinant of associated Bezoutian-like matrices. This is joint work with M. Elkadi and A. Galligo from the University of Nice. Bernard Deconinck (University of Washington), Matt Patterson (University of Washington) Computing the Abel map and vector of Riemann constants Abstract: 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. Harm Derksen (University of Michigan) Algorithms for Invariant Rings of Algebraic Groups Abstract: Joint work with Gregor Kemper. I will discuss algorithms for finding generators of rings of invariants, with emphasis on reductive groups in positive characteristic and non-reductive groups. Jintai Ding (University of Cincinnati) Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field Abstract: 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. Kenneth Driessel (Iowa State University) Weekly Tutorial- Real Algebraic Geometry Abstract: Dr. Ken Driessel will offer weekly (except for Workshop weeks) tutorial sessions. More details will come. Mark your calendars for now. David Eisenbud (Mathematical Sciences Research Institute) Asymptotic Ideal Theory and Parametrized Rational Varieties Abstract: If I is a homogeneous ideal in a polyonomial ring over a field, then in some ways high powers of I are simpler than I itself. This fact is implicitly used whenever one blows up a subvariety of a variety, for example in the process of resolution of singularities. The attendant phenomena appear in commutative algebra in the study of the Rees algebra of a variety. I will explain a new point of view that connects, for example, the parametrization of a rational curve to the singularities of that curve without passing through the "implicitization" step of finding the equations of the image curve. The work I will describe is joint with Joe Harris and Craig Huneke. Shuhong Gao (Clemson University) Grobner basis structure and decomposition of polynomial systems Abstract: A Grobner basis for an ideal under an elimination order reflects much of the geometric structure of the variety defined by the ideal. We discuss how this relationship can be used in decomposing polynomial systems (with or without parameters) and in primary decomposition of ideals. As an application, we show how this technique can be used in designing deterministic algorithms for factoring univariate polynomials over finite fields, which aims to reduce the factoring problem to a combinatorial one. The talk is based on joint work with Genhua Guan, Raymond Heindl, Jand-Woo Park, Virginia Rodrigues, and Jeff Stroomer. Oleg Golubitsky (Queen's University) Computation of rankings on partial derivatives Abstract: 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. Benjamin J. Howard (University of Minnesota Twin Cities) Degenerating ideals to toric ideals: a method used in the solution of a problem from classical invariant theory Abstract: 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. Itnuit Janovitz-Freireich (North Carolina State University) Approximate radicals for clusters: an approach based on Gaussian elimination or SVD Abstract: 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. Irina Kogan (North Carolina State University) Smooth and Algebraic Invariants of a Group Action Abstract: 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. Teresa Krick (University of Buenos Aires) Factorization of Sparse Polynomials Abstract: In this talk I will discuss algorithms for factoring polynomials over number fields to reach recent results on sparse polynomials, where the complexity of the algorithm takes into account the fact that the polynomial may have many zero coefficients. For simplicity I'll focus on rational polynomials in one or two variables. The talk will review results by F. Cucker, P. Koiran and S. Smale, 1999, H.J. Lenstra (Jr.), 1999, E. Kaltofen and P. Koiran, 2005 and 2006, and a joint work with M. Avendaño and M. Sombra, 2006. Sanjay Lall (Stanford University) Control Theory and Algebraic Geometry Abstract: This talk will discuss how many problems in control theory may be formulated as problems of algebraic geometry. Topics covered include realization theory, homotopy methods for pole placement, construction of Schur functions, stabilization via coprime factorization, systems over rings, controllability, and multidimensional systems. We also discuss more recent research in the area of decentralized control. Anton Leykin (University of Minnesota Twin Cities) Approximating singular solutions of polynomial systems Abstract: n the assumption of regularity, the existing tools of numerical algebraic geometry provide an effective way to deal with solution sets of systems of polynomials both 0- and positive-dimensional. Should a solution be singular, Newton's method involved in tracking the corresponding homotopy continuation path loses its quadratic convergence. This talk concerns a symbolic-numerical method called deflation that restores this convergence by considering an augmented system in more variables. Time permitting, we will discuss the higher-order deflation related to the topic of computation of the multiplicities of singular solution components. Tien-Yien Li (Michigan State University) Mixed Volume Computation Abstract: Most recent algorithms for calculating the mixed volume of the support A = (A1, ... , An ) of a polynomial system P(x) = ( p1(x), ... , pn(x)) in Cn by first finding all the fine mixed cells in a fine mixed subdivision of A followed by adding the volumes of all those cells will be presented in this talk. The problem of finding all the fine mixed cells, which plays a crucial role when the polyhedral homotopy method is employed to find all the isolated zeros of P(x), is dealt with by solving a series of Phase I problems in Linear Programming. Susan Margulies (University of California) Representing NP-Complete problems with polynomials ideals: An exploration of Computational Complexity based on Grobner bases and Hilbert's Nullstellensatz Abstract: 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. Margarida Mendes Lopes (Universidade Técnica de Lisboa) Numerical Campedelli surfaces with algebraic fundamental group of order 9 Abstract: Joint work with Rita Pardini. The (algebraic) fundamental group of minimal regular surfaces S of general type satisfying c_1^2<1/3 c_2 is now well understood. If it is infinite then the surface has a genus 3 hyperelliptic fibration with at least 4 double fibres. If the algebraic fundamental group is finite then its order is at most 9. Furthermore if the fundamental group has order 9 the surface S is necessarily a Campedelli surface,i.e. a surface with c_1^2=2 and vanishing geometric genus. This poster will present the main ideas of the proof of the bound on the order of finite fundamental groups for such surfaces and also the complete classification of Campedelli surfaces with group of order 9. Some previously unknown examples are found and a very interesting feature is that two of these families provide the first known instance of surfaces with c_1^2>1 having base points for the bicanonical system. Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) Projections methods for the topology of algebraic curves and surfaces Abstract: We described algorithms for computing the topology of real algebraic implicit curves and surfaces in dimension 3, based on projections techniques, starting with the algorithm for implicit planar curves. Then we consider curves in dimension 3. Next we describe an algorithm for computing the topology of a general real algebraic surface S. The approach is based on tools from stratification theory and the construction of an explicit Whitney stratification of S. We show how these methods can be turned into effective algorithms, using resultant ans subresultant computations and discussed the problem of iterated resultants and discriminants, for which we give some explicit formula. Chris Peterson (Colorado State University) Tools for extracting information from numerically approximated varieties and schemes Abstract: There are natural situations where one is led to consider numeric approximations of varieties, schemes, sheaves, ideals, modules, etc. For instance, given a homogeneous ideal one might be able to determine a reduced primary decomposition via numerical methods (such as homotopy continuation) whereas symbolic methods might be too slow or not even apply. This provides motivation to develop a set of tools to handle and manipulate numerically approximated varieties and schemes. In this talk, I will discuss some tools of use for these objects. This is joint work with Dan Bates and Andrew Sommese. Ragni Piene (University of Oslo) Polar and dual varieties of real curves and surfaces Abstract: The theory of polar varieties have been used by Bank et al. and Safey El Din et al. to give algorithms for finding a point on each connected component of a smooth, complete intersection real variety. In this talk, based on ongoing joint work with Heidi Mork, we shall consider possibly singular varieties and study the polar varieties and their relation to the dual variety and to the Gauss map. In particular, we shall look at the case of curves and surfaces. J. Maurice Rojas (Texas A & M University) On the Effectiveness of Number Theory in Algebraic Geometry Abstract: One of the most basic notions in polynomial system solving is feasibility: does your system of equations have any roots? We will explore the algorithmic complexity of this problem, focussing on sparse polynomial systems over the real numbers and complex numbers. Over the complex numbers, we will see algorithms completely different from homotopy, resultants, and Grobner bases; and how the Generalized Riemann Hypothesis enters our setting. In particular, we show how earlier methods (of Grigoriev, Karpinski, Odlyzko, and Koiran), depending on unproven number-theoretic hypotheses, can be made unconditional in certain cases. Over the real numbers, we will determine the threshold between polynomial-time and NP-hardness, as a function of the number of variables and monomial terms. In particular, we will give polynomial-time algorithms where only exponential-time algorithms were known before, and we will see how Diophantine approximation enters in an unexpected way. Along the way, we will see how finite fields and p-adic fields are also related to our main focus. Bruno Salvy (Institut National de Recherche en Informatique Automatique (INRIA)) On the Complexity of Groebner Basis Computation for Regular and Semi-Regular Systems Abstract: We study the complexity of Groebner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We bound precisely the exponent of the complexity of Faugère F5 algorithm in this case. This complexity is related to the index of regularity of the ideal. For regular systems, this index is well- known. We define a class of overdetermined systems called semi- regular systems for which we derive sharp asymptotic estimates of the index of regularity. These systems are conjectured to be generic in a precise sense. This is joint work with Magali Bardet and Jean-Charles Faugère. Eric Schost (École Polytechnique) Change of order for regular chains in positive dimension Abstract: 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. Andrew Sommese (University of Notre Dame) Solving polynomial systems by homotopy continuation Abstract: We will give a brief introduction to pathtracking and how it is used to find the solutions of a polynomial system. We will discuss isolated solutions first and, as an extended example of the solution of a nontrivial system, discuss the solution by Charles Wampler and Alexander Morgan (both of GM R & D) and myself of the nine-point path synthesis problem for planar four-bars. As time permits, we will discuss the numerical irreducible decomposition developed by Verschelde, Wampler, and myself. Frank Sottile (Texas A & M University) New Fewnomial Upper Bounds from Gale Dual Polynomial Systems Abstract: In 1980, Askold Khovanskii established his fewnomial bound for the number of real solutions to a system of polynomials, thereby showing that the complexity of real solutions to a polynomial system depends upon the number of monomials and not the degree. This fundamental finiteness result in real algebraic geometry was proven by induction on the number of monomials and the bound is unrealistically large. I will report on joint work with Frederic Bihan on a new fewnomial bound which is substantially lower than Khovanskii's bound. This bound is obtained by first reducing a given system to a Gale system, which comes from the Gale dual to the exponent vectors in the original system, and then bounding the number of solutions to a Gale system. Like Khovanskii's bound, this bound is the product of an exponential function and a polynomial in the dimension, with the exponents in both terms depending upon the number of monomials. In our bound, the exponents are smaller than in Khovanskii's. Michael E. Stillman (Cornell University) Applications of monomial ideals and computational algebra in the reverse engineering of biological networks. Abstract: he reverse engineering of biological networks is an important and interesting problem. Two examples of such networks are gene regulatory networks, and the relationship of voxels in the brain. We describe a method for determining possible "wiring diagrams" for such networks. The method is based on computational algebra, and a key part of the method uses computations involving monomial ideals in a polynomial ring. To illustrate the algorithms, we apply the method to data coming from fMRI scans of the brain. This talk represents joint work (on the arXiv at q-bio.QM/0605032) with Abdul Jarrah, Reinhard Laubenbacher, and Brandy Stigler. The analysis of the brain data was performed by Paola Vera. Bernd Sturmfels (University of California) Semigraphoids, Permutohedra, and Mice Abstract: Semigraphoids are combinatorial structures that arise in statistical learning theory. They are equivalent to convex rank tests and to polyhedral fans that coarsen the reflection arrangement of the symmetric group. This lecture gives an introduction to this theory. It centers around our recent answers to questions raised by Matus, Studeny, Postnikov, Reiner and Williams. This represents joint work with R.Hemmecke, J.Morton, L.Pachter, A.Shiu and O. Wienand. The mice are in the title because everything started with the analysis of microarray data in molecular biology. Reading: Milan Studeny: Probabilistic Conditional Independence Structures, Springer Series in Information Science and Statistics, 2005. Ravi Vakil (Stanford University) Generalizing the cross-ratio: the moduli space of n points on the projective line is cut out by simple quadrics if n is not six Abstract: The cross-ratio is a classical gadget that let's you see if two sets of four points on the projective line are projectively equivalent — it is the "moduli space of four points on the projective line." The generalization of this to an arbitrary number of points leads to the notion of the moduli space of n points on the projective line, which is a projective variety, one of the most classical examples of a Geometric Invariant Theory quotient. It also may be interpreted as the space of all polygons in 3-space. We show that this space is actually cut out by quadrics, of a particularly simple sort. This talk is intended for a broad audience. (This is joint work with B. Howard, J. Millson, and A. Snowden, and deals with preprint math.AG/0607372.) Charles W. Wampler (General Motors Corporation) Finding all real solutions contained in a complex algebraic curve Abstract: Using the methods of numerical algebraic geometry, one can compute a numerical irreducible decomposition of the solution set of polynomial systems. This decomposition describes the enitre solution set and its breakup into irreducible pieces over complex Euclidean space. However, in engineering or science, it is common that only the real solutions are of interest. A single complex component may contain multiple real components, some possibly having lower dimension in the reals than the dimension of the complex component that contains them. We present an algorithm for finding all real solutions inside the pure-one-dimensional complex solution set of a polynomial system. The algorithm finds a numerical approximation to all isolated real solutions and a description of all real curves in a Morse-like representation consisting of vertices with edges connecting them. The work presented in this talk has been done in collaboration with Ye Lu, Daniel Bates, and Andrew Sommese. Daqing Wan (University of California) Counting Rational Points on Varieties over Finite Fields Abstract: In this lecture, we discuss various results on both complexity and algorithms for counting the number of rational points on a hypersurface over a finite field, with am emphasis on p-adic methods. Ruriko Yoshida (University of Kentucky) Computing holes in semi-groups Abstract: 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 \$h\in 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. Mingfu Zhu (Clemson University) Irreducible Decomposition of Monomial Ideals and Upper Bound on Number of Irreducible Components Abstract: 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. Mark van Hoeij (Florida State University) Maple's Algebraic Curves Package Abstract: Maple has a number of algorithms for algebraic curves. Algebraic algorithms such as genus, holomorphic differentials, integral basis, parametrization, normal forms for (hyper)-elliptic curves, as well as numeric algorithms such as monodromy and periodmatrix. How these algorithms work is the topic of this talk. Possible future improvements will be discussed as well. Hans-Christian von Bothmer (Universität Hannover) Counting Components Heuristically Abstract: 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."
Visitors in Residence