FoCM 2014 conference

Session C1 - Computational Algebraic Geometry

Organizers: Carlos D’Andrea (University of Barcelona, Spain) - Gregory Smith (Queen’s University, Canada) - Agnes Szanto (North Carolina State University, USA)

Workshop website

View session abstracts PDF



December 20, 18:00 ~ 18:20 - Room B11

Degree Bounds in Rational Sums of Squares Representations on Curves

Greg Blekherman

Georgia Tech, USA   -

Let $X$ be a curve with dense real points. It is well-known that any polynomial $p$ nonnegative on $X$ can be written as a sum of squares of rational functions in the coordinate ring of $X$. I will present new degree bounds for these rational sums of squares representations, which depend on the Hilbert series of $X$ only. The bound can be shown to be tight in many instances. It is an open question whether the bound is tight for any curve $X$ with dense real points.

Joint work with Greg Smith (Queens University) and Mauricio Velasco (Universidad de los Andes).

View abstract PDF

December 20, 15:35 ~ 16:25 - Room B11

From chemical reaction networks to Descartes' rule of signs

Alicia Dickenstein

Universidad de Buenos Aires, Argentina   -

In the context of chemical reaction networks with mass-action and other rational kinetics, a major question is to preclude or to guarantee multiple positive steady states. I will explain this motivation and I will present necessary and sufficient conditions in terms of sign vectors for the injectivity of families of polynomials maps with arbitrary real exponents defined on the positive orthant. These conditions extend existing injectivity conditions expressed in terms of Jacobian matrices and determinants, obtained by several authors. In the context of real algebraic geometry, this approach can be seen as the first partial multivariate generalization of the classical Descartes' rule, which bounds the number of positive real roots of a univariate real polynomial in terms of the number of sign variations of its coefficients. This is joint work with Stefan M\"uller, Elisenda Feliu, Georg Regensburger, Anne Shiu and Carsten Conradi. I will also present some further advances in this multivariate generalization obtained in collaboration with Fr\'ed\'eric Bihan.

View abstract PDF

December 20, 17:00 ~ 17:20 - Room B11

Newton homotopies and certification

Jonathan Hauenstein

University of Notre Dame, USA   -

A homotopy in which only the constant terms change is called a Newton homotopy. Such homotopies are used in moving robots, solving PDEs, and performing monodromy loops. This talk will introduce computations involving Newton homotopies, methods for a priori and a posteriori path tracking for Newton homotopies, and complexity results.

Joint work with Ian Haywood (North Carolina State University, USA) and Alan Liddell (University of Notre Dame, USA).

View abstract PDF

December 19, 18:00 ~ 18:20 - Room B12

Computing global vector fields on varieties with torus actions

Nathan Ilten

Simon Fraser University, Canada   -

The space of global vector fields is an important invariant of an algebraic variety. In this talk, I will discuss an approach to computing this space for smooth varieties endowed with the effective action of an algebraic torus. Indeed, for such varieties, the space of global vector fields can be described in terms of global vector fields on a suitable quotient. For the special case of rational varieties with a complexity-one torus action, these computations become quite explicit.

This approach relies upon general machinery for describing equivariant vector bundles on varieties with torus action.

Joint work with Hendrik Suess (University of Edinburgh).

View abstract PDF

December 18, 18:30 ~ 18:50 - Room B12

Plethysm and lattice point counting

Thomas Kahle

Otto-von-Guericke Universität Magdeburg, Germany   -

We show that the coefficient of the Schur functor $S^\lambda$ in the decomposition of the plethysm $S^\mu(S^k)$ into irreducibles is the solution to a lattice point counting problem. Consequently, for each fixed $\mu$, the solution to this problem is a piecewise quasi-polynomial in $(\lambda,k)$. We show how to use computer algebra to determine this function explicitly when $\mu$ is a partition of 4 or 5. We also discuss asymptotics of the resulting piecewise quasi-polynomials.

Joint work with Mateusz Michalek (Simons Institute, UC Berkeley).

View abstract PDF

December 19, 16:00 ~ 16:20 - Room B12

A numerical algorithm for zero counting

Teresa Krick

Universidad de Buenos Aires & CONICET, Argentina   -

The purpose of this talk is to honor and remember our dear friend Mario Wschebor.

Together with Mario, Felipe Cucker and Gregorio Malajovich, we produce and analyze a numerical (iterative) algorithm for computing the exact number of real projective zeros of a system of $n$ real homogeneous polynomial equations in $n + 1$ variables. We first show that the number of iterations, and the cost of each iteration, depends on a condition number of the system, in addition to other usual parameters. The algorithm can be implemented with finite precision as long as the round-off unit satisfies some bound depending on the same parameters. Then we show that the condition number that we introduced satisfies an Eckard-Young theorem, as it represents the inverse of the distance of the input system to the ill-posed systems. We derive from this smoothed analysis bounds for it, applying general results obtained by Bürgisser, Cucker and Lotz. Finally, we use specific probability techniques as a Rice theorem to obtain more precise bounds for the tail and the expected value of the condition number, considered as a random variable when imposing a probability measure on the space of polynomial systems.

Joint work with Felipe Cucker (City University of Hong Kong), Gregorio Malajovich (Universidade Federal do Rio de Janeiro) and Mario Wschebor (Universidad de la República del Uruguay).

View abstract PDF

December 19, 15:00 ~ 15:20 - Room B12

Schubert varieties and distances between subspaces of different dimensions

Lek-Heng Lim

University of Chicago, USA   -

We resolve two fundamental problems regarding subspace distances that have arisen considerably often in applications: How could one define a notion of distance between (i) two linear subspaces of different dimensions, or (ii) two affine subspaces of the same dimension, in a way that generalizes the usual Grassmann distance between equidimensional linear subspaces? We show that (i) is the distance of a point to a Schubert variety, and (ii) is the distance within the Grassmannian of affine subspaces. In our context, a Schubert variety and the Grassmannian of affine subspaces are both regarded as subsets of the usual Grassmannian of linear subspaces. Combining (i) and (ii) yields a notion of distance between (iii) two affine subspaces of different dimensions. Aside from reducing to the usual Grassmann distance when the subspaces in (i) are equidimensional or when the affine subspaces in (ii) are linear subspaces, these distances are intrinsic and do not depend on any embedding of the Grassmannian into a larger ambient space. Furthermore, they can all be written down as concrete expressions involving principal angles, and are efficiently computable in numerically stable ways. We show that our results are largely independent of the Grassmann distance --- if desired, it may be substituted by any other common distances between subspaces. Central to our approach to these problems is a concrete algebraic geometric view of the Grassmannian that parallels the differential geometric perspective that is now well-established in applied and computational mathematics. A secondary goal of this article is to demonstrate that the basic algebraic geometry of Grassmannian can be just as accessible and useful to practitioners.

Joint work with Ke Ye (University of Chicago).

View abstract PDF

December 18, 16:00 ~ 16:20 - Room B12

Cellular Binomial Ideals

Laura Matusevich

Texas A&M University, USA   -

Without any restrictions on the base field, we compute the hull and provide an unmixed decomposition of a cellular binomial ideal. The latter had already been proved by Eisenbud and Sturmfels in characteristic zero, and conjectured to also hold in positive characteristic. Over an algebraically closed field, we further obtain an explicit (but not necessarily minimal) primary decomposition of such an ideal.

The binomial primary decomposition algorithms developed by Eisenbud and Sturmfels, and improved by Ojeda and Piedra, and Kahle, perform a cellular decomposition as a first step. We believe that our results provide further improvements to these algorithms, paving the way for the implementation of binomial primary decomposition over finite fields.

Joint work with Zekiye Sahin Eser (Texas A&M University, USA).

View abstract PDF

December 20, 17:30 ~ 17:50 - Room B11

Computing with noncommutative algebras in Macaulay2

Frank Moore

Wake Forest University, USA   -

NCAlgebra is a new package for Macaulay2 which provides tools for working with noncommutative graded rings and matrices over such rings. In this presentation, we give an overview of the package’s primary methods, including those which compute noncommutative Gr\"obner bases, Hilbert series, central and normal elements, and kernels of matrices. We will also give examples of calculations that been made possible with this package.

Joint work with Andy Conner (St. Mary's University, Moraga, CA, USA).

View abstract PDF

December 19, 15:30 ~ 15:50 - Room B12

Algorithmic and Geometric Aspects of Sparse Decomposition

Bernard Mourrain

Inria, France   -

Several problems in signal processing, tensor decomposition, sparse interpolation, polynomial optimization, etc reduce to the reconstruction of sum of exponential functions from truncated moment sequences. Prony proposed in 1795 a method to solve this problem for functions of one variable, when enough moments are known. We describe a generalization in several variables and a new algorithm to compute the decomposition of series as sums of exponential functions. An ingredient of the approach is a flat extension property, which is related to the commutation property of multiplication operators modulo a zero-dimensional ideal. We analyze this problem from a geometric point of view, describe its connection with the Hilbert scheme of points and present some applications to reconstruction and approximation problems.

View abstract PDF

December 18, 17:30 ~ 17:50 - Room B12

Effective computations on Grassmann, Flag, and Stiefel varieties with applications

Chris Peterson

Colorado State University, USA   -

Consider a sequence of images of a fixed object collected under a continuous variation of state (varying illumination, frequency, pose, etc). In pixel space, the collection of images can be intuitively viewed as lying on a manifold. Noise, quantization, and background clutter significantly degrade this model. What one actually sees is a data cloud clustered near the manifold. The Grassmann, flag, and Stiefel varieties have proven to be effective settings for extracting information about the underlying manifold and for comparing the appearance of different objects imaged under the same variations of state. In this setting one is led to consider problems such as "how can you average a collection of subspaces?" and "what if the subspaces are of differing dimensions?" and "what point on a given Schubert variety lies closest to a given point on a Grassmann manifold?". In this talk, we will give an overview of some of the theory and computational techniques that have allowed for solutions to these and related problems.

Joint work with Michael Kirby (Colorado State University, math), Bruce Draper (Colorado State University, computer science), Tim Marrinan (Colorado State University) and Justin Marks (Bowdoin College).

View abstract PDF

December 19, 17:00 ~ 17:20 - Room B12

Probabilistic method for toric ideals

Sonja Petrovic

Illinois Institute of Technology, USA   -

In this talk we will discuss a probabilistic algorithm that can be used to obtain a generating set of a toric ideal. Apart from being of interest in computational algebra, the problem has applications in statistics, where toric ideal generators form Markov bases for statistical models.

Joint work with Jesús A. De Loera (University of California, Davis) and Despina Stasi (Illinois Institute of Technology).

View abstract PDF

December 18, 14:35 ~ 15:25 - Room B12

Cactus varieties of cubic forms

Kristian Ranestad

University of Oslo, Norway   -

The rank of a symmetric form is the length of its shortest decomposition as a sum of pure powers of linear forms, i.e. the shortest smooth apolar scheme. The cactus rank of the form is the the length of the shortest apolar scheme. The $a$-th cactus variety of cubic forms $C_{a,n}$ is the closure of the family of cubic forms of cactus rank $a$ in the projective space of cubic forms in $n+1$ variables. I shall report on recent work with Bernardi, Jelisiejew and Marques giving the dimension and a geometric characterization of the general member of $C_{a,n}$ when $1\leq a\leq 2n+2$.​

Joint work with Alessandra Bernardi (Universita de Bologna, Italy), Joachim Jelisiejew (University of Warsaw, Poland) and Pedro Macias Marques (Universidade de Evora, Portugal).

View abstract PDF

December 18, 18:00 ~ 18:20 - Room B12

Generalized barycentric coordinates and algebraic geometry

Hal Schenck

University of Illinois, USA   -

Let $P_d$ be a convex polygon with $d$ vertices. The associated Wachspress surface $W_d$ is a fundamental object in approximation theory, defined as the image of the rational map $w_d$ from ${\mathbb P}^2$ to ${\mathbb P}^{d-1}$, determined by the Wachspress barycentric coordinates for $P_d$. We show $w_d$ is a regular map on a blowup $X_d$ of ${\mathbb P}^2$, and if $d>4$ is given by a very ample divisor on $X_d$, so has a smooth image $W_d$. We determine generators for the ideal of $W_d$, and prove that in graded lex order, the initial ideal of $I(W_d)$ is given by a Stanley-Reisner ideal. As a consequence, we show that the associated surface is arithmetically Cohen-Macaulay, of Castelnuovo-Mumford regularity two, and determine all the graded betti numbers of $I(W_d)$.

Joint work with Corey Irving (Santa Clara University, USA).

View abstract PDF

December 19, 14:30 ~ 14:50 - Room B12

Partitioning on varieties and point-hypersurface incidences

Martin Sombra

ICREA and University of Barcelona, Spain   -

I will describe a new polynomial partitioning result applicable to finite sets of points in a variety of codimension at most 2. It generalizes the Guth-Katz polynomial partitioning theorem as well later generalizations of this result to sets of points in hypersurfaces.

This result opens up the possibility of proving new incidence bounds in higher dimensions, and we apply it to the problem of bounding incidences between points and hypersurfaces in 4-dimensional real space.

Joint work with Saugata Basu (Purdue University, USA).

View abstract PDF

December 18, 17:00 ~ 17:20 - Room B12

Applications of computational algebraic geometry to vacuum moduli spaces of supersymmetric models in physics

Michael Stillman

Cornell University, USA   -

Given a supersymmetric potential function, such as one for the MSSM (minimal super-symmetric extension of the standard model of particle physics), there is a naturally associated affine algebraic variety, which is (essentially) the moduli space of possible vacua of the theory. In this talk we describe the structure of some of these moduli spaces, including the Electro-weak sector of the MSSM, which were obtained with the help of computational algebraic geometry and Macaulay2. We consider theories where one allows for more than 3 generations of particles. Since nature seems to have chosen 3 generations, theories for which this number of generations is forced would be ideal. Although it does not appear that 3 generations is forced here, we see how the geometry varies with different numbers of generations of particles.

We will assume no knowledge of physics during this talk. We will briefly describe the physics needed, and then we will describe the algebraic geometric and computational methods and results which allow the structure to become apparent.

This talk is based on the preprint

Joint work with Yang-Hui He (Oxford and City University London, UK), Vishnu Jejjala (University of the Witwatersrand, Johannesburg, South Africa), Cyril Matti (City University, London, UK) and Brent Nelson (Northeastern University, USA).

View abstract PDF

December 20, 14:30 ~ 14:50 - Room B11

The Maximum Likelihood Threshold of a Graph

Seth Sullivant

North Carolina State University, USA   -

The maximum likelihood threshold of a graph is the smallest number of data points that guarantees that maximum likelihood estimates exist almost surely in the Gaussian graphical model associated to the graph. We show that this graph parameter is connected to the theory of combinatorial rigidity. In particular, if the edge set of a graph $G$ is an independent set in the $n-1$-dimensional generic rigidity matroid, then the maximum likelihood threshold of $G$ is less than or equal to $n$. This connection allows us to prove many results about the maximum likelihood threshold.

Joint work with Elizabeth Gross (San Jose State University).

View abstract PDF

December 19, 17:30 ~ 17:50 - Room B12

Dual toric codes and polytopes of degree one

Mauricio Velasco

Universidad de los Andes, Colombia   -

A construction due to Hansen associates a linear code over a finite field $\mathbb{F}_q$ to the projective toric variety $X(P)$ specified by a lattice polytope $P$. The toric code $V$ is the subspace of $\mathbb{F}_q^t$ constructed by evaluating the polynomials spanned by the lattice points of $P$ at the $t$ points of the torus in $X(P)$ defined over $\mathbb{F}_q$. The dual toric code is its dual subspace $V^*$ consisting of all linear functionals in $(\mathbb{F}_q^t)^*$ which vanish identically on $V$.

In this talk we will show that some statistical features of the code $V^*$ are controlled by the geometry of the toric variety $X(P)$. This correspondence allows us to distinguish extremal dual toric codes and to classify them using the classification of polytopes of degree one due to Batyrev and Nill.

Joint work with Valerie Gauthier (Universidad del Rosario, Colombia).

View abstract PDF

December 18, 15:30 ~ 15:50 - Room B12

An algebraic approach to phase retrieval

Cynthia Vinzant

North Carolina State University, USA   -

The problem of phase retrieval is to reconstruct a signal from certain magnitude measurements. This problem is closely related to low-rank matrix completion and has many imaging-related applications: microscopy, optics, and diffraction imaging, among others. In purely mathematical terms, phase retrieval means recovering a complex vector from the modulus of its inner product with certain measurement vectors. One can ask how many measurements are necessary for this recovery to be possible. I’ll discuss recent progress made on this problem by translating it into algebraic language and talk about my adventures as an algebraist in frame theory.

Joint work with Aldo Conca (University of Genova, Italy), Dan Edidin (University of Missouri, USA) and Milena Hering (University of Edinburgh, UK).

View abstract PDF

December 20, 15:00 ~ 15:20 - Room B11

Computing tropical curves via homotopy continuation

Josephine Yu

Georgia Tech, United States of America   -

We develop a method for computing tropical curves using numerical algebraic geometry. Our method guesses rays in tropical curves by sampling points in amoebas, and we develop numerical procedures to check whether a point is in the tropical variety without having to compute any Groebner bases. We also give an implementation of our methods. As an application, we use this technique to compute Newton polygons of $A$-polynomials of knots.

Joint work with Anders Jensen (Aarhus University) and Anton Leykin (Georgia Tech).

View abstract PDF



Cox rings of some big rational surfaces



Smooth rational surfaces with big anticanonical class are known to have finitely generated Cox ring, but an explicit set of generators and their relations is not known. For a family of these surfaces, obtained as blow-ups of $\mathbb{P}^2$ at special point configurations, we prove that the Cox ring is generated by sections supported on negative curves. For some of these configurations we have a conjectural description of the relations. We believe they are generated by quadrics, and for a given degree we can decide computationally whether there are or there are not new relations in this degree. Some of our results, for both generators and relations, are computer-assisted proofs using Macaulay2. These results are joint work with Mauricio Velasco.


View abstract PDF

Sampling Zeros, Model Zeros, and Maximum Likelihood Degrees

Elizabeth Gross

San Jose State University, USA   -

Given a statistical model, the maximum likelihood degree is the number of complex solutions to the likelihood equations for generic data, or equivalently, the degree of the likelihood locus. In this poster, we consider discrete algebraic statistical models and explore the solutions to the likelihood equations when the data are no longer generic, but instead contain zeros. In this case, with the help of numerical algebraic geometry, we see that the solutions partition into two clusters, solutions to the likelihood equations for sampling zeros and solutions that lie on the coordinate hyperplanes. Using this fact, we show how the problem of finding critical points to the likelihood function can be partitioned into smaller and computationally easier problems involving sampling and model zeros.

Joint work with Jose Rodriguez (University of Notre Dame).

View abstract PDF

Algebraic geometry of tree tensor network states

Sara Jamshidi

Pennsylvania State University, USA   -

Tree tensor networks have been used to model the ground states of Hamiltonians in condensed matter physics and quantum chemistry. Exactly which quantum states can be represented by a tree tensor network with a given topology and given restrictions on the parameter tensors? When the restrictions are algebraic, the set of states is a projective algebraic variety. We describe those varieties, using techniques originally developed for phylogenetics.

Joint work with Jason Morton (Pennsylvania State University, USA).

View abstract PDF

Multiplicities of Classical Varieties

Jack Jeffries

University of Utah, United States   -

The $j$-multiplicity plays an important role in the intersection theory of Stückrad-Vogel cycles, while recent developments confirm the connections between the $\epsilon$-multiplicity and equisingularity theory. We establish, under some constraints, a relationship between the $j$-multiplicity of an ideal and the degree of its fiber cone. As a consequence, we are able to compute the $j$-multiplicity of all the ideals defining rational normal scrolls. By using the standard monomial theory, we can also compute the $j$- and $\epsilon$-multiplicity of ideals defining determinantal varieties: The found quantities are integrals which, quite surprisingly, are central in random matrix theory. This is joint work with Jonathan Montaño and Matteo Varbaro.

Joint work with Jonathan Montaño (Purdue University, USA) and Matteo Varbaro (University of Genoa, Italy).

View abstract PDF