Main navigation | Main content
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.
September 25, 2006, 9:30 - 10:30 am, Lind Hall 305Semigraphoids, 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.
September 25, 2006, 11:15 am-12:15 pm, Lind Hall 305Assymptotic 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
September 27, 2006, 11:15 am-12:15 pm, Lind Hall 305Approximating singular solutions of polynomial systems
Abstract: In 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.
October 4, 2006, 11:15 am-12:15 pm, Lind Hall 409An experimental approach to numerical Godeaux surfaces
Abstract: A (numerical) Godeaux surface is a minimal surface X of general type with K_2=1 and p_g=0, hence also q=0 and H_1(X,Q)=0. So in some sense these are the surfaces of general type with smallest possible invariants. Godeaux constructed a family of such surfaces as quotients of a quintic hypersurface by a fixed point free action of Z_5. By the work of Miyaoka it is known that the torsion group T=H_1(X,Z) is a cyclic group of order at most 5. The surfaces with T=Z_d for d=3,4,5 have a moduli space which consists of one 8 dimensional component by work of Reid and Miyaoka. For T=Z_2 or T=0 much less is known. Existence of such surfaces was proved by Rebecca Barlow, by a complicated quotient construction. Traditionally there are two approaches to construct numerical Godeaux surfaces: Either by a Godeaux approach as a quotient of a simpler surface by a possibly non free group action, or by a Campedelli approach as a double plane branched along a curve with a specific configuration of singularities. In this talk I present a third approach based on homological algebra and computer algebra.
ndcourse@ima.umn.edu October 11, 2006, 11:15 am-12:15 pm, Lind Hall 305Examples of exact results from inexact methods
Abstract: In this talk, some examples will be presented that illustrate how exact equations can often be recovered from numerically approximated generic points on a variety.
October 18, 2006, 11:15 am-12:15 pm, Lind Hall 409A numerical approach toward approximate algebraic
computation
Abstract: From the perspective of numerical analysts, algebraic problems are frequently ill-posed as characterized by Hardamard, where a tiny perturbation in the problem data or roundoff can completely alter the solution structure. Such problems include matrix rank/kernel, singular root-finding, greatest common divisors, irreducible factorization, dual basis of a polynomial ideal, Jordan Canonical Form, etc, and arise in applications as simple as solving linear systems. Due to unbounded sensitivity, ill-posed problems are not suitable for straightforward computation using floating point arithmetic. In this talk we shall discuss the notion of the "approximate solution" to ill-posed algebraic problems and present a strategy for its numerical computation. This approach consists of a three-strike reformulation principle that removes the ill-posedness, and a two-staged computing strategy for finding approximate solutions. Numerical algorithms have been developed and implemented for several basic algebraic problems with remarkable robustness and accuracy.
November 1, 2006, 11:15 am-12:15 pm, Lind Hall 409Equations and degenerations of the moduli space of genus zero stable curves with n marked points
Abstract: Curves are one of the basic objects of algebraic geometry, and so much attention has been paid to the moduli space of all curves of a given genus. This talk will focus on the moduli space of genus zero stable curves with n marked points, which is a compactification of the space M_{0,n} of isomorphism classes of n points on the projective line. After introducing this space, I will describe joint work with Angela Gibney on explicit equations for it, which lets us see degenerations to toric varieties.
November 2, 2006, 10:10-11:00 am, Lind Hall 409Computer assisted mathematics: Tools and tactics for
solving hard problems
Abstract: In this talk I will present several problems that have caught my attention over the past few years. We will go over Mathematica formulations and solutions. Along the way we will meet with a branch-and-bound loop in its natural habitat, some rampaging Gröbner bases, a couple of tamed logic puzzles, and at least a dozen wild beasts.
As the purpose is to illustrate a few of the many ways in which Mathematica can be used to advantage in tackling difficult problems, we will go into a bit of detail in selected examples. Do not let this deter you; there will be no exam, and it is the methods, not the problems, that are of importance. The examples are culled from problems I have seen on Usenet groups (primarily MathGroup), in articles, or have been asked in person.
November 8, 2006, 11:15 am-12:15 pm, Lind Hall 409Excess intersection theory and homotopy continuation methods
Abstract: I will recall first basic techniques and results in (excess) intersection theory in algebraic geometry and then discuss their implications and also applications toward a numerical approach to primary decomposition for ideals in polynomial rings.
November 13, 2006, 11:15 am-12:15 pm, Lind Hall 409Complexity measures
Abstract: It is well-known that on the one hand the costs for computing a Gröbner basis can be prohibitively high in the worst case, but on the other hand computations can often be carried out successfully in practice. As an attempt to explain this discrepancy, several invariants that measure the size or the complexity of an ideal or a module have been introduced. The most prominent one is the Castelnuovo-Mumford regularity, but there are also extended degrees introduced by Vasconcelos and, more recently, the extended regularity jointly proposed with Chardin. The latter two notions are defined axiomatically. In the talk we will discuss the three concepts and their relations as well as some known results and open problems.
November 15, 2006, 11:15 am-12:15 pm, Lind Hall 409Tropical celestial mechanics
Abstract: Some interesting problems in mechanics can be reduced to solving systems of algebraic equations. A good example is finding relative equilibria of the gravitational n-body problem. These are special configurations of the n point masses which can rotate rigidly such that the outward centrifugal forces exactly cancel the gravitational attractions. The algebraic equations are complicated enough that it is a long-standing open problem even to show that the number of solutions is finite. I will describe a solution to this question for n=4 which makes use of some ideas from what is now called tropical algebraic geometry – Puiseux series solutions, initial ideals, etc. The problem is open for larger n.
November 15, 2006, 2:15 pm-3:15 pm, Lind Hall 409On approximate triangular decompositions in dimension zero
Abstract: Triangular decompositions for systems of polynomial equations with n variables, with exact coefficients are well-developed theoretically and in terms of implemented algorithms in computer algebra systems. However there is much less research about triangular decompositions for systems with approximate coefficients. In this talk we will discuss the zero-dimensional case, of systems having finitely many roots. Our methods depend on having approximations for all the roots, and these are provided by the homotopy continuation methods of Sommese, Verschelde and Wampler. We introduce approximate equiprojectable decompositions for such systems, which represent a generalization of the recently developed analogous concept for exact systems. We demonstrate experimentally the favourable computational features of this new approach, and give a statistical analysis of its error. Our paper is available at http://publish.uwo.ca/~wwu26/
November 20, 2006, 11:15 am-12:15 pm, Lind Hall 409
Computations in classical invariant theory of binary
forms
Abstract: Recent years have witnessed a reflourishing of interest in classical invariant theory, both as a mathematical subject and in applications. The applications have required a revival of the computational approach, a task that is now improved by the current availability of symbolic manipulation computer softwares. In this talk, we will review the basic concepts of invariants and covariants of binary forms, and discuss some elementary examples. We will then use the symbolic method of Aronhold, and algebrochemical methods of Clifford and Sylvester for computations and present some applications to syzygies and transvectants of covariants.
November 29, 2006, 11:15 am-12:15 pm, Lind Hall 409Tropical discriminants
Abstract: The theory of A-discriminants is a far going generalization of the discriminant of a univariate polynomial, proposed in the late 80's by Gel'fand, Kapranov and Zelevinsky, who also described many of their combinatorial properties. We present a new approach to this theory using tropical geometry.
We tropicalize the Horn-Kapranov uniformization, which allows us to determine invariants of A-discriminants, even if the actual equations are too hard to be computed.
Joint work with
December 6, 2006, 11:15 am-12:15 pm, Lind Hall 409Gröbner walks and Scarf homotopies
Abstract: We give a light introduction to Gröbner basis conversion and outline emerging insights on the connection to a classical algorithm by Scarf in optimization.
December 13, 2006, 11:15 am-12:15 pm, Lind Hall 409Some algorithmic aspects of local cohomology
Abstract: One application of local cohomology is that it provides a lower bound on the number of defining equations of algebraic varieties. To be useful for this application, local cohomology must be efficiently computable. We will discuss some computability issues and resulting lower bounds for the number of defining equations of some interesting varieties.
January 10, 2007, 11:15 am-12:15 pm, Lind Hall 409Algorithms in algebraic analysis
Abstract: In the first part of this talk I will give an introduction to the algorithmic theory of D-modules. This would include the description of the properties of the rings of differential operators, in particular, the ones that allow for computation of Gröbner bases.
The second part will show the applications of D-modules to the computation of local cohomology of a polynomial ring at a given ideal. The nonvanishing of the local cohomology module of a certain degree may answer the question about the minimal number of generators for the ideal.
The presentation is going to be accompanied by the demonstration of the relevant computations in the D-modules for Macaulay 2 package. January 24, 2007, 11:15 am-12:15 pm, Lind Hall 409Moments of positivity
Abstract: The seminar will offer an unifying overview of the theory of positive functionals, the spectral theorem, moment problems and polynomial optimization. We will treat only the commutative case, in the following order:
SDP and LP-relaxations in polynomial optimization: The power of real algebraic geometry
Summary: In this seminar we consider the general polynomial optimization problem: that is, finding the GLOBAL minimum of a polynomial over a compact basic semi-algebraic set, a NP-hard problem. We will describe how powerfull representation results in real algebraic geometry are exploited to build up a hierarchy of linear or semidefinite programming (LP or SDP) relaxations, whose monotone sequence of optimal values converges to the desired value. A comparison with the usual Kuhn-Tucker local optimality conditions is also discussed.
February 7, 2007, 11:15 am-12:15 pm, EE/Sci 3-180 [Note room change]
An introduction to algebraic statistics
Talks
(A/V)
Abstract: This will be a gentle introduction to the applications of algebraic geometry to statistics. The main goal of the talk is to present statistical models, i.e. sets of probability distributions (defined parametrically most of the time), as algebraic varieties. I will give examples where defining equations of such statistical model varieties have been successfully computed: various graphical models and models for DNA sequence evolution. I will also talk about the algebraic degree of maximum likelihood estimation with old and new examples.
February 14, 2007, 11:15 am-12:15 pm, Lind Hall 229
Statistical formulation of issues associated with multi-way
contingency tables and the links to algebraic geometry
Talks(A/V)
Abstract: Many statistical problems arising in the context of multi-dimensional tables of non-negative counts (known as contingency tables) have natural representations in algebraic and polyhedral geometry. I will introduce some of these problems in the context of actual examples of large sparse tables and talk about how we have treated them and why. For example, our work on bounds for contingency table entries has been motivated by problems arising in the context of the protection of confidential statistical data results on decompositions related to graphical model representations have explicit algebraic geometry formulations. Similarly, results on the existence of maximum likelihood estimates for log-linear models are tied to polyhedral representations. It turns out that there are close linkages that I will describe.
February 21, 2007, 11:15 am-12:15 pm, EE/CSci 3-180Rational and algebraic invariants of a group
action
Abstract: We consider a rational group action on the affine space and propose a construction of a finite set of rational invariants and a simple algorithm to rewrite any rational invariant in terms of those generators.
The construction can be extended to provide algebraic foundations to Cartan's moving frame method, as revised in [Fels & Olver 1999].
This is joint work with Irina Kogan, North Carolina State University.
February 28, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Moving frames in classical invariant theory and computer
vision
Talks(A/V)
Abstract: Classical invariant theory was inspired by the basic problems of equivalence and symmetry of polynomials (or forms) under the projective group. In this talk, I will explain how a powerful new approach to the Cartan method of moving frames can be applied to classify algebraic and differential invariants for very general group actions, leading, among many other applications, to new solutions to the equivalence and symmetry problems arising in both invariant theory, differential geometry, and object recognition in computer vision.
March 14, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Counting monomials
Talks(A/V)
Abstract: The contents of this elementary talk grew out of my need to explain to non-mathematicians what I do for a living.
I will pose (and solve) two old chessboard enumeration problems and a new problem. We will solve these by counting certain monomials, and this will naturally lead us to the notion of Hilbert functions. With these examples in mind, we will try and understand the simplest of monomial ideals, namely, edge ideals, and discover that these are not simple at all! On the way we will discover a new numerical invariant of forests.
March 21, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Symmetries in SDP-based relaxations for
constrained polynomial optimization
Talks(A/V)
Abstract: We consider the issue of exploiting symmetries in the hierarchy of semidefinite programming relaxations recently introduced in polynomial optimization. After providing the necessary background we focus on problems where either the symmetric or the cyclic group is acting on the variables and extend the representation-theoretical methods of Gatermann and Parrilo to constrained polynomial optimization problems. Moreover, we also propose methods to efficiently compute lower and upper bounds for the subclass of problems where the objective function and the constraints are described in terms of power sums.
(Joint work with L. Jansson, J.B. Lasserre and C. Riener)
March 28, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Algebraic geometry of Gaussian Bayesian networks
Talks(A/V)
Abstract: Conditional independence models for Gaussian random variables are algebraic varieties in the cone of positive definite matrices. We explore the geometry of these varieties in the case of Bayesian networks, with a view towards generalizing the recursive factorization theorem. When some of the random variables are hidden, non-independence constraints are need to describe the Bayesian networks. These non-independence constraints have potential inferential uses for studying collections of random variables. In the case that the underlying network is a tree, we give a complete description of the defining constraints of the model and show a surprising connection to the Grassmannian.
April 4, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Optimal fewnomial bounds from Gale dual polynomial
systems
Talks(A/V)
Abstract: In 1980, Askold Khovanskii established his fewnomial bound for the number of real solutions to a system of polynomials, showing that the complexity of the set of real solutions to a system of polynomials depends upon the number of monomials and not on the degree. This fundamental finiteness result in real algebraic geometry is believed to be unrealistically large.
I will report on joint work with Frederic Bihan on a new fewnomial bound which is substantially lower than Khovanskii's bound and asymptotically optimal. This bound is obtained by first reducing a given system to a Gale 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.
I will also dicuss a continuation of this work with J Maurice Rojas in which we show that this fewnomial bound is optimal, in an asymptotic sense. We also use it to establish a new and significantly smaller bound for the total Betti number of a fewnomial hypersurface. Conditional independence models for Gaussian random variables are algebraic varieties in the cone of positive definite matrices. We explore the geometry of these varieties in the case of Bayesian networks,
April 11, 2007, 11:15 am-12:15 pm, EE/CSci 3-180
Combinatorial complexity in o-minimal geometry
Talks(A/V)
Abstract: We prove tight bounds on the combinatorial and topological complexity of sets defined in terms of n definable sets belonging to some fixed definable family of sets in an o-minimal structure. This generalizes the combinatorial parts of similar bounds known in the case of semi-algebraic and semi-Pfaffian sets, and as a result vastly increases the applicability of results on combinatorial and topological complexity of arrangements studied in discrete and computational geometry. As a sample application, we extend a Ramsey-type theorem due to Alon et al. originally proved for semi-algebraic sets of fixed description complexity to this more general setting. The talk will be self-contained and I will go over the basic definitions of o-minimality for those who are unfamiliar with the notion.
April 25, 2007, 11:15am-12:15 pm, Lind Hall 229On sparse polynomial systems, mixed volumes and condition numbers
Abstract: pdf
April 26, 2007, 10:15-11:10 am, EE/CSci 3-180Random polynomial systems and balanced metrics on toric varieties
Abstract: Suppose c_{0},...,c_{d} are independent identically distributed real Gaussians with mean 0 and variance 1. Around the 1940s, Kac and Rice proved that the expected number of real roots of the polynomial c_{0} + c_{1} x + ... + c_{d} x^{d}i, then the expected number of real roots is EXACTLY the square root of d. Aside from the cute square root phenomenon, Kostlan also observed that the distribution function of the real roots is constant with respect to the usual metric on the real projective line.
The question of what a "natural" probability measure for general multivariate polynomials then arises. We exhibit two (equivalent) combinatorial constructions that conjecturally yield such a measure. We show how our conjecture is true in certain interesting special cases, thus recovering earlier work of Shub, Smale, and McLennan. We also relate our conjecture to earlier asymptotic results of Shiffman and Zelditch on random sections of holomorphic line bundles.
This talk will deal concretely with polynomials and Newton polytopes, so no background on probability or algebraic geometry is assumed.
May 2, 2007, 11:15am-12:15 pm, Lind Hall 409A homological obstruction to weak order on trees
Abstract: When sorting data on a network of computers, it is natural to ask which data swaps between neighbors constitute progress. In a linear array, the answer is simple, by virtue of the fact that permutations admit pleasant notions of inversions and weak order. I will discuss how the topology of chessboard complexes constrains the extent to which these ideas may carry over to other trees; it turns out that there are homological obstructions telling us that a tree does not admit an inversion function unless each node has at least as much capacity as its degree minus one. On the other hand, we construct an inversion function and weak order for all trees that do meet this capacity requirement, and we prove a connectivity bound conjectured by Babson and Reiner for 'Coxeter-like complexes' along the way.
May 9, 2007, 11:15am-12:15 pm, Lind Hall 409Schubert combinatorics and geometry
Abstract: The topic of Schubert varieties of homogeneous spaces G/P is at the interface between algebraic geometry and combinatorics. I'll describe work on two themes.
The first is Schubert calculus: counting points in intersections of Schubert varieties. A goal has been combinatorial rules for these computations. I'll explain the carton rule which manifests basic symmetries of the numbers for the Grassmannian case; this version also has the advantage of generalizing to (co)minuscule G/P.
The second concerns singularities of Schubert varieties. I'll give a combinatorial framework for understanding invariant of singularities via a notion we call interval pattern avoidance.
The first half of this talk is joint work with Hugh Thomas (U. New Brunswick) while the second half is joint work with Alexander Woo (UC Davis).
May 15, 2007, 1:15-2:15 pm, Lind Hall 305Discriminants, dual varieties and toric geometry
Abstract: Given an algebraic variety, embedded in projective space, the closure of all hyperplanes tangent at some non singular point is called the dual variety. A general embedding has dual variety of co-dimension one (in the dual projective space) and hence defined by an irreducible homogeneous polynomial, called the discriminant. The study of the exceptional embeddings, i.e. the ones having dual variety of lower dimension, is a very classical problem in algebraic geometry, still open for many classes of varieties. I will explain the problem and give the solution for the class of non singular toric varieties.
May 16, 2007, 11:15am-12:15 pm, Lind Hall 409Average volume, curvatures, and Euler characteristic of random real algebraic varieties
Abstract: We determine the expected curvature polynomial of random real projective varieties given as the zero set of independent random polynomials with Gaussian distribution, whose distribution is invariant under the action of the orthogonal group. In particular, the expected Euler characteristic of such random real projective varieties is found. This considerably extends previously known results on the number of roots, the volume, and the Euler characteristic of the solution set of random polynomial equations.
May 23, 2007, 11:15am-12:15 pm, Lind Hall 409
On the Newton polytope of specialized resultants
Abstract: We overview basic notions from sparse, or toric, elimination theory and apply them in order to predict the Newton polytope of the sparse resultant. We consider the case when all but a constant number of resultant parameters are specialized. Of independent interest is the problem of predicting the support of the implicit equation of a parametric curve or surface. We bound this support by a direct approach, based on combinatorial geometry. The talk will point to various open questions.
June 6, 2007, 11:15am-12:15 pm, Lind Hall 302A symbolic approach to sparse elimination
Abstract: Sparse elimination is concerned with systems of polynomial equations in which each equation is given by a polynomial having non-zero coefﬁcients only for those monomials lying in a prescribed set.
We will discuss a new symbolic procedure for solving zero-dimensional sparse polynomial systems by means of deformation techniques. Roughly speaking, a deformation method to solve a zero-dimensional polynomial equation system works as follows: the input system is regarded as a member of a parametric family of zero-dimensional systems. Then, the solutions to a particular parametric instance which is "easy to solve" are computed and, finally, these solutions enable one to recover the solutions of the original system.
The algorithm combines the polyhedral deformation introduced by Huber and Sturmfels with symbolic techniques relying on the Newton-Hensel lifting procedure. Its running time can be estimated mainly in terms of the input length and two invariants related to the combinatorial structure underlying the problem.
June 20, 2007, Lind Hall 305
IMA program on applications of algebraic geometry
(Special seminar as part of the annual
PIC-IAB meeting)
Connect With Us: |