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)
Talks
December 20, 18:00 ~ 18:20 - Room B11
Degree Bounds in Rational Sums of Squares Representations on Curves
Greg Blekherman
Georgia Tech, USA - greg@math.gatech.edu
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).
December 20, 15:35 ~ 16:25 - Room B11
From chemical reaction networks to Descartes' rule of signs
Alicia Dickenstein
Universidad de Buenos Aires, Argentina - alidick@dm.uba.ar
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.
December 20, 17:00 ~ 17:20 - Room B11
Newton homotopies and certification
Jonathan Hauenstein
University of Notre Dame, USA - hauenstein@nd.edu
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).
December 19, 18:00 ~ 18:20 - Room B12
Computing global vector fields on varieties with torus actions
Nathan Ilten
Simon Fraser University, Canada - nilten@sfu.ca
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).
December 18, 18:30 ~ 18:50 - Room B12
Plethysm and lattice point counting
Thomas Kahle
Otto-von-Guericke Universität Magdeburg, Germany - thomas.kahle@ovgu.de
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).
December 19, 16:00 ~ 16:20 - Room B12
A numerical algorithm for zero counting
Teresa Krick
Universidad de Buenos Aires & CONICET, Argentina - krick@dm.uba.ar
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).
December 19, 15:00 ~ 15:20 - Room B12
Schubert varieties and distances between subspaces of different dimensions
Lek-Heng Lim
University of Chicago, USA - lekheng@galton.uchicago.edu
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).
December 18, 16:00 ~ 16:20 - Room B12
Cellular Binomial Ideals
Laura Matusevich
Texas A&M University, USA - laura@math.tamu.edu
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).
December 20, 17:30 ~ 17:50 - Room B11
Computing with noncommutative algebras in Macaulay2
Frank Moore
Wake Forest University, USA - moorewf@wfu.edu
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).
December 19, 15:30 ~ 15:50 - Room B12
Algorithmic and Geometric Aspects of Sparse Decomposition
Bernard Mourrain
Inria, France - Bernard.Mourrain@inria.fr
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.
December 18, 17:30 ~ 17:50 - Room B12
Effective computations on Grassmann, Flag, and Stiefel varieties with applications
Chris Peterson
Colorado State University, USA - peterson@math.colostate.edu
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).
December 19, 17:00 ~ 17:20 - Room B12
Probabilistic method for toric ideals
Sonja Petrovic
Illinois Institute of Technology, USA - sonja.petrovic@iit.edu
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).
December 18, 14:35 ~ 15:25 - Room B12
Cactus varieties of cubic forms
Kristian Ranestad
University of Oslo, Norway - ranestad@math.uio.no
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).
December 18, 18:00 ~ 18:20 - Room B12
Generalized barycentric coordinates and algebraic geometry
Hal Schenck
University of Illinois, USA - schenck@math.uiuc.edu
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).
December 19, 14:30 ~ 14:50 - Room B12
Partitioning on varieties and point-hypersurface incidences
Martin Sombra
ICREA and University of Barcelona, Spain - sombra@ub.edu
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).
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 - mike@math.cornell.edu
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 arxiv.org/1408.6841
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).
December 20, 14:30 ~ 14:50 - Room B11
The Maximum Likelihood Threshold of a Graph
Seth Sullivant
North Carolina State University, USA - smsulli2@ncsu.edu
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).
December 19, 17:30 ~ 17:50 - Room B12
Dual toric codes and polytopes of degree one
Mauricio Velasco
Universidad de los Andes, Colombia - mvelasco@uniandes.edu.co
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).
December 18, 15:30 ~ 15:50 - Room B12
An algebraic approach to phase retrieval
Cynthia Vinzant
North Carolina State University, USA - vinzant@umich.edu
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).
December 20, 15:00 ~ 15:20 - Room B11
Computing tropical curves via homotopy continuation
Josephine Yu
Georgia Tech, United States of America - jyu@math.gatech.edu
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).
Posters
Cox rings of some big rational surfaces
JOSE DARIO BASTIDAS OLAYA
UNIVERSIDAD DE LOS ANDES, COLOMBIA - jd.bastidas251@uniandes.edu.co
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.
Joint work with MAURICIO VELASCO (UNIVERSIDAD DE LOS ANDES, COLOMBIA).
Sampling Zeros, Model Zeros, and Maximum Likelihood Degrees
Elizabeth Gross
San Jose State University, USA - elizabeth.gross@sjsu.edu
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).
Algebraic geometry of tree tensor network states
Sara Jamshidi
Pennsylvania State University, USA - jamshidi@math.psu.edu
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).
Multiplicities of Classical Varieties
Jack Jeffries
University of Utah, United States - jeffries@math.utah.edu
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).