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.

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.

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.

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.

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.

A Gröbner 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.

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.

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.

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.

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.

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.

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.

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.

Most recent algorithms for calculating the mixed volume of the support A = (A_{1, ... ,} A_n ) of a polynomial system P(x) = ( p₁(x), ... , p_n(x)) in Cⁿ 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.

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.

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.

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.

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.

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.

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.

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.

We study the complexity of Gröbner 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.

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.

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.

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.

We apply tropical geometry to study the image of a map defined by Laurent polynomials with generic coefficients. If this image is a hypersurface then our approach gives a construction of its Newton polytope. This is joint work with Jenia Tevelev and Josephine Yu http://front.math.ucdavis.edu/math.CO/0607368.

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

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.

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.

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.

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.

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.

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