September 18 - 22, 2006
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_{1}(x), ... , p_{n}(x)) in
C^{n} 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.
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.
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.
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.)
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."
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.