We present a general method based on moving frames for approximating
differential invariants by joint invariants. The examples of the Gauss and
mean curvature of a surface in R3 will be presented.
Back
The Groebner basis has foundational and computational applications
in a variety of statistical problems. Markov Chain Monte Carlo methods,
generating function methods, parameter identifiability, and statistical
sufficiency can make use of the Groebner basis and these applications will be
described with practical examples. Also, some ongoing work on high-dimensional
models with incomplete data will be discussed.
Back
Computing numerical approximations to the roots of a univariate polynomial is a
classic problem from numerical analysis and symbolic algebra. I present a novel
iterative algorithm that combines floating-point linear algebra with extended-
precision arithmetic. Given a current estimate of the roots, the algorithm
constructs a generalization of the companion matrix of the polynomial--actually an
eigenvalue formulation of Lagrange interpolation. The eigenvalues of the matrix,
computed in floating-point with standard numerical methods, form the new estimate
of the roots. Surprisingly, even though the initial eigenvalue computations can
be extraordinarily ill-conditioned, the iteration converges to approximations of
the roots accurate to floating-point precision. The algorithm has been successfully
applied to very difficult polynomials, e.g. the Wilkinson polynomial of degree 600.
In practice, the algorithm appears to be an order of magnitude faster than the
best available alternative.
Back
One of the central problems of classical invariant theory is the
problem of equivalence and symmetry of complex multivariable polynomials
under linear changes of variables. A non-traditional approach to this
problem has been proposed by Peter Olver in his recent book on classical
invariant theory. The main idea is to reformulate the problem as the
problem of equivalence and symmetry of submanifolds, by considering the
graph of a polynomial in m variables as a hypersurface in m+1
dimensional complex space. The solution for the latter problem can be
obtained using a classical tool from differential geometry -- Cartan's
moving frame method. We will discuss two algorithms arising from
this approach: the first one determines the symmetry (or isotropy)
group of a given polynomial, while the second allows to decide whether
two polynomials are equivalent (or belong to the same orbit).
Both algorithms involve Gröbner basis computations, whose complexity
limits our ability to solve specific problems.
Nevertheless, some interesting new results were obtained,
such as classification of the symmetry groups of homogeneous cubics in
three variables, and necessary and sufficient conditions for a three
variable homogeneous polynomial of degree n to be equivalent to
xn+yn+zn.
Back
The design of digital FIR filters is an area of signal processing
where techniques from computational algebraic geometry are currently
being applied. In particular, Selesnick and Burrus have developed
a system of polynomial design equations for filters by imposing a
specified number M of flatness constraints on the passband in the
magnitude response and a second number L of flatness constraints
on the group delay response. In this talk, we will concentrate
on techniques for solving the Selesnick-Burrus equations in the
difficult cases where M is large and L is small relative to M
("Region II" in their terminology) and illustrate how Groebner
bases, eigenvalue methods, and sparse resultants can be brought
to bear.
Back
We introduce the notion of a supernormal configuration of
vectors in Zd, which generalizes both unimodular and normal
configurations. This is motivated by the study of lattice ideals arising
from three dimensional lattices, such as codimension three toric ideals.
Our main result is that when the Gale dual of a configuration is
supernormal, the Gröbner fan of the corresponding toric ideal equals the
secondary fan.
Back
The applications of computational algebraic geometry to the
study of the computational complexity of noncooperative game theory
will be reviewed, with emphasis on the following recent result of Berg
and McLennan. The expected number of Nash equilibria of a two person
game in which both players have N pure strategies has the asymptotic
growth rate 1.3253068N. As N becomes large almost all equilibria
have each player assigning positive probability to approximately
31.5915 percent of her pure strategies. These results are obtained
by applying computational methods of statistical mechanics to a
formula for the mean number of Nash equilibria of a normal form game,
on a particular support, developed by McLennan.
Back
Let k be a commutative ring and let B:=k[X1, . . . , Xn]/I, where I is an ideal generated by monomials Xalpha i and binomials Xbeta j-uj Xgamma j, with each uj in U, the group of units in k. Then B is graded by the monoid S:=Nn/~, where ~ is a monoid congruence determined by the alphai and the pairs (betaj, gammaj). If we change the uj's, we get another S-graded k-algebra that may or may not be isomorphic to B by a graded algebra map. The equivalence types of graded algebras obtained as the uj's vary are classified by a group H2(S, U).
In this talk will define this group carefully, show
connections with Harrison cohomology and with A-graded algebras (as
described in Sturmfels, Gröbner bases and convex polytopes),
and exhibit computer calculations of H2(S, U)
for selected S. The
last suggests a combinatorial puzzle that (as of this writing) is not
solved. All of this machinery was developed in order to make examples of
ordered rings that answer certain questions in real commutative algebra.
I will sketch this application and exhibit a very peculiar ordered ring.
Back
We propose a construction of rank-jumping parameters for a broad
class of toric ideals, which contains the generic non Cohen Macaulay toric
ideals.This gives rise to a question in combinatorial commutative algebra,
namely, to understand this class and characterize it in such a way that
examples are easy to compute.
Back
We talk on efficiently computing sparse resultants of composed polynomials. By the sparse resultant of several sparse polynomials in several variables (one fewer variables than polynomials) we mean an irreducible polynomial in the coefficients of the sparse polynomials that vanishes if they have a common zero (in an appropriate space). By a composed polynomial we mean the polynomial obtained from a given sparse polynomial by replacing each variable by a sparse polynomial.
We report on three results:
We present a new algorithm
for computing the primary decomposition of zero dimensional ideals in
polynomial rings over infinite fields. While the algorithm appears slower, in
practice, than existing algorithms, it has several interesting features. In
particular, if the ideal is given by a Gröbner basis, the algorithm uses
only elementary linear algebra and univariate polynomial factorization over
the base field.
Back
Suppose a multivariate sequence has a rational generating
function, F = G/H. We want to obtain asymptotics for the coefficients
of F. I will give several examples of this, then discuss a general
method of computing the asymptotics, in which the singularities of
the zero set of H play a large role. The chief hurdle in making these
the asymptotic computations effective is finding and classifying the
singularities of H. I will discuss what measure of effectiveness of
computation is attained by current theory and software.
Back
The Membrane Inclusions Curvature Equations describe the minimum energy arrangements of N conical proteins embedded in an idealized cell membrane. We exploit the symmetries of the system to give two reformulations which allow the successful computation of solutions up to N=280 using current Gröbner bases algorithms.
Joint with Jean-Charles Faugere and Milena Hering.
Back
A recent example of Bertrand Haas shows that a pair of real bivariate
polynomial equations (where each equation has at most 3 monomial terms)
can have as many as 5 roots in the positive quadrant. However, until
recently, the best upper bound on the number of roots independent of
the degrees (following from more general results of Khovanski) is 248,832.
We give an elementary proof that 5 is the correct maximum. Our proof also
generalizes to real exponents, systems where one of the equations has more
than 3 terms, and counting connected components.
Back
Convolutional codes can be viewed as submodules of Rn where R is the polynomial ring. Maximum distance separable (MDS) convolutional codes are characterized through the property that the free distance attains the generalized Singleton bound. By now several constructions are known for MDS convolutional codes.
In this talk we will explain some of these constructions. We also will present a new algorithm which is able to decode MDS or near MDS convolutional codes under some very weak assumptions on the error pattern.
Joint work with Roxana Smarandache
Back
In this talk we outline the design equations arising in the
construction of wavelet bases and frames.
We describe several desirable properties wavelets should
have to enhance their utility in signal processing applications,
and how they are represented as design equations.
We then describe our experiences using Groebner bases to solve
the corresponding nonlinear design equations.
In particular, we consider the design of pairs of wavelet bases
where the wavelets form a Hilbert transform pair and
present new solutions obtained using Groebner bases.
Using Groebner bases in practice can be a challenge because of
the high computational and memory requirements. However, our
experiences and results support the utility of GBs in certain
cases. But the effective use of GBs requires a knowledge of how
to apply operations like GB factorization, the FGLM algorithm, etc.
Back
Abstract: The sum of the first k random exponents of a unitarily invariant probability measure on GL(n,C) can be expressed as the integral of the log of the determinant of the matrices over the Grassmannian of k planes in n space. We show that this integral is a lower bound for the integral of the sum of the k largest logs of the absolute values of the eigenvalues of the matrices. A lower bound for the mean Mahler measure of the characteristic polynomials of these matrices follows directly.
Joint work with J.-P. Dedieu
Back
Using cellular resolutions, we give an explicit description of
cohomology on complete toric variety. As an application, we'll discuss
multi-graded Hilbert polynomials and regularity.
Back
Homotopy continuation methods are numerically stable algorithms to compute all isolated solutions of a polynomial system. A recent application of these methods finds generic points on each positive dimensional solution component of the system. Using monodromy we can predict a classification of those generic points along the breakup of components into irreducible ones. Besides an increased efficiency, the new methods improve the numerical conditioning of the multivariate interpolation problem to generate equations for the components. The performance of our new algorithms will be illustrated on some well-known examples in science and engineering: systems of adjacent minors of a general 2-by-n matrix, the cyclic 8- and 9-roots problems, and the Stewart-Gough platform in mechanical systems design.
Joint work with Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler
Back