Session II.6 - Computational Algebraic Geometry
Talks
Thursday, June 15, 14:00 ~ 14:30
Deriving equations for equivariant phylogenetic varieties
Marta Casanellas
Universitat Politècnica de Catalunya, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
Phylogenetics studies the evolutionary relationships among species using their molecular sequences. These relationships are represented on a phylogenetic tree or network. Modeling nucleotide or amino acid substitution along a phylogenetic tree is one of the most common approaches in phylogenetic reconstruction. One can use a general Markov model or one of its submodels given by certain substitution symmetries. If these symmetries are governed by the action of a permutation group G on the rows and columns of a transition matrix, we speak of G-equivariant models. A Markov process on a phylogenetic tree or network parametrizes a dense subset of an algebraic variety, the so-called phylogenetic variety.
During the last decade algebraic geometry has been used in phylogenetics for phylogenetic reconstruction and to establish the identifiability of parameters of complex evolutionary models (and thus guarantee model consistency). Since G-equivariant models have fewer parameters than a general Markov model, their phylogenetic varieties are defined by more equations and these are usually hard to find. We will see that we can easily derive equations for G-equivariant models from the equations of a phylogenetic variety evolving under a general Markov model. As a consequence, we will discuss the identifiability of networks evolving under G-equivariant models.
Joint work with Jesús Fernández-Sánchez (Universitat Politècnica de Catalunya, Spain).
Thursday, June 15, 14:30 ~ 15:00
Rational partition models under iterative proportional scaling
Jane Ivy Coons
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
The classical iterative proportional scaling algorithm, or IPS, numerically computes the maximum likelihood estimate of a given vector of counts for a log-linear partition model. We investigate the conditions under which IPS produces the exact maximum likelihood estimate, or MLE, in finitely many steps. Since IPS produces a rational function at each step, a necessary condition is that the model must have rational maximum likelihood estimator. However, the convergence is highly parametrization-dependent; indeed, one parametrization of a model may exhibit exact convergence in finitely many steps while another does not. We introduce the generalized running intersection property, which guarantees exact convergence of IPS. As the name suggests, this strictly generalizes the well-known running intersection property for hierarchical models. This generalized running intersection property can be understood in terms of the toric geometry of the log-linear model, and models that satisfy this property can be obtained by performing repeated toric fiber products of linear ideals. We also draw connections between models that satisfy the generalized running intersection property and balanced, stratified staged trees.
Joint work with Carlotta Langer (Hamburg University of Technology, Hamburg, Germany) and Michael Ruddy (Qventus).
Thursday, June 15, 15:00 ~ 15:30
Sparse Factorizations of Real Polynomials & Linear Convolutional Neural Networks
Kathlén Kohn
KTH Royal Institute of Technology, Sweden - This email address is being protected from spambots. You need JavaScript enabled to view it.
This talk will explain that Convolutional Neural Networks without activation parametrize semialgebraic sets of real homogeneous polynomials that admit a certain space factorization. We will investigate how the geometry of these semialgebraic sets (e.g., its singularities and relative boundary) changes with the network architecture. Moreover, we will start to explore how these geometric properties affect the optimization of a loss function for given training data.
Joint work with Guido Montúfar (MPI MiS Leipzig / UCLA), Vahid Shahverdi (KTH) and Matthew Trager (Amazon).
Thursday, June 15, 15:30 ~ 16:00
3D genome reconstruction from partially phased Hi-C data
Kaie Kubjas
Aalto University, Finland - This email address is being protected from spambots. You need JavaScript enabled to view it.
The three-dimensional (3D) genome structure plays an important role in gene regulation. One of the main approaches to infer the 3D genome structure is from contact matrices that record interactions between different regions (loci) of the genome. In the case of diploid organisms the contact data is often unphased, which means that one cannot differentiate between contacts for homologous chromosomes. This talk is about partially-phased population contact data. Partially-phased contact data means that for some loci one can assign contacts to a maternal or paternal homolog. We study the identifiability of 3D genome reconstruction from partially phased contact data. Moreover, we suggest a reconstruction method built on semidefinite programming and homotopy continuation.
Joint work with Diego Cifuentes (Georgia Institute of Technology), Jan Draisma (University of Bern), Oskar Henriksson (University of Copenhagen) and Annachiara Korchmaros (University of Leipzig).
Thursday, June 15, 16:30 ~ 17:00
Real Hyperplane Sections and Linear Series on Algebraic Curves
Daniel Plaumann
TU Dortmund University, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Given a real algebraic curve in projective space, we study the computational problem of deciding whether there exists a hyperplane meeting the curve in real points only. This translates into a particular type of parametrized real root counting problem. More generally, given any divisor on such a curve, we may ask whether the corresponding linear series contains an effective divisor with real support. We will focus on examples and indicate a few general results.
Joint work with Huu Phuoc Le (LIP6, Paris) and Dimitri Manevich (TU Dortmund).
Thursday, June 15, 17:00 ~ 17:30
Hyperplane sections of polytopes
Chiara Meroni
MPI Leipzig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We obtain a parametric, semialgebraic description of properties of the hyperplane sections of a polytope. Using this structure, we provide algorithms for the optimization of several combinatorial and metric properties over all hyperplane slices of a polytope. We report on their computational complexity, and explore some connections to constructions and problems in combinatorics and convex geometry.
Joint work with Marie-Charlotte Brandenburg (Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany) and Jesús A. De Loera (University of California, Davis, USA).
Thursday, June 15, 17:30 ~ 18:00
Recent progress on Gröbner bases computations
Mohab Safey El Din
Sorbonne University, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Recent progress on Gröbner bases computations
Gröbner bases theory and algorithms provide versatile tools for polynomial system solving. Modern algorithms are based on advanced reductions to linear algebra, relying on constructions from commutative algebra.
In this talk, we present new methods for ideal theoretic operations such as saturation and change of ordering in order to make effective algebraic operations such as set difference and projection in algebraic geometry. These methods are based on pushing further the aforementioned linear algebra reductions and the use of module theory.
Joint work with J. Berthomieu (Sorbonne Univ.), C. Eder (TU Kaiserslautern) and V. Neiger (Sorbonne Univ.).
Thursday, June 15, 18:00 ~ 18:30
Adjoints of Polypols
Rainer Sinn
Universität Leipzig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We discuss real curves which are adjoint (that is determined by) polypols introduced by Emil Wachspress. The simplest example of a polypol is a convex polygon in the plane. In this case, the adjoint curve has a fixed degree given by the number of vertices of the polygon and passes through all vertices of the line arrangement given by the edges that are not vertices of the polygon itself. More generally, polypols allow for nonlinear boundary components. We will mostly focus on recent works on polygons and may see some open questions in general.
Joint work with Kathlén Kohn (KTH Stockholm, Sweden), Ragni Piene (University of Oslo, Norway), Kristian Ranestad (University of Oslo, Norway), Felix Rydell (KTH Stockholm, Sweden), Boris Shapiro (Stockholm University, Sweden), Miruna-Stefana Sorea (SISSA Trieste, Italy), Simon Telen (CWI Amsterdam, Netherlands);, and Daniele Agostini (University of Tübingen, Germany), Daniel Plaumann (TU Dortmund, Germany) and Jannik Wesner (TU Dortmund, Germany).
Friday, June 16, 15:00 ~ 15:30
Preserving and Exploiting Symmetry in Multivariate interpolation
Evelyne Hubert
Inria Côte d'Azur, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Interpolation is a prime tool in algebraic computation while symmetry is a qualitative feature that can be more relevant to a mathematical model than the numerical accuracy of the parameters. We shall show how to exactly preserve symmetry in multivariate interpolation while exploiting it to alleviate the computational cost. We revisit minimal degree and least interpolation with symmetry adapted bases, rather than monomial bases.
An interpolation problem is defined by a set of linear forms on the polynomial ring and values to be achieved by an interpolant. For Lagrange interpolation the linear forms consist of evaluations at some nodes, while Hermite interpolation also considers the values of successive derivatives. Both are examples of ideal interpolation in that the kernels of the linear forms intersect into an ideal.
For a space of linear forms invariant under a group action, we construct bases of invariant interpolation spaces in blocks, capturing the inherent redundancy in the computations. With the so constructed symmetry adapted interpolation bases, the uniquely defined interpolant automatically preserves any equivariance the interpolation problem might have. Even with no equivariance, the computational cost to obtain the interpolant is alleviated thanks to the smaller size of the matrices to be inverted.
For an ideal interpolation problem with symmetry, we address the simultaneous computation of a symmetry adapted basis of the least interpolation space and the symmetry adapted H-basis of the ideal. Beside its manifest presence in the output, symmetry is exploited computationally at all stages of the algorithm. For an ideal invariant, under a group action, defined by a Groebner basis, the algorithm allows to obtain a symmetry adapted basis of the quotient and of the generators. We shall also note how it applies surprisingly but straightforwardly to compute fundamental invariants and equivariants of a reflection group.
Journal of Symbolic Computation 107 (2021) https://doi.org/10.1016/j.jsc.2021.01.004
Journal of Symbolic Computation 115 (2023) https://doi.org/10.1016/j.jsc.2022.08.014
Joint work with Erick Rodriguez Bazan (Inria Côte d'Azur).
Friday, June 16, 15:30 ~ 16:00
Robust extraneous components of Canny's resultant
Gleb Pogudin
Ecole Polytechnique, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Resultants are one of the oldest tools in computational algebraic geometry and can be used to compute a projection of an algebraic variety, that is, of a solution set of a system of polynomial equations. If this solution set has components of different dimensions, a resultant may be identically zero thus giving no interesting information. John Canny in 1990 proposed a workaround based on symbolic perturbation of the equations which was, in particular, used by Agnes Szanto in her algorithm for computing a triangular set representation of an algebraic variety. Because of being based on perturbations, Canny's approach may introduce extraneous components into the computed projection. Interestingly, some of them turn out to be very robust to the change of perturbation and thus hard to eliminate. We will discuss examples of some components and explain how they can be related to the invariants of the original algebraic variety.
Friday, June 16, 16:30 ~ 17:00
Certification of approximate singularities with a view to the punctual Hilbert scheme
Bernard Mourrain
Inria @ Université Côte d'Azur, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Computing singular solutions of polynomial systems $f =(f_{1}, \ldots, f_{N})\in \mathbb{C}[x_{1}\ldots, x_{n}]^{N}$ is a challenging question from a practical numerical point of view.
To address this problem and solve more efficiently non-linear equations with isolated singular solutions, one can analyse the multiplicity structure or inverse system and then exploit the properties of this structure to develop efficient algorithms. This leads to the conceptualisation of families of multiplicity structures of a given length as an algebraic variety, and to the study of the so-called punctual Hilbert schemes.
In this presentation we take this approach. We first recall algorithms to compute the inverse system of an isolated singular point. We localise our study to the algebraic variety $\mathrm{Hilb}_{B}$ of inverse systems, which admits a given dual (monomial) basis $B$. We present some algebraic and geometric properties of this variety, which relies on the algorithmic construction of its points. Using deformations on the punctual Hilbert scheme, we describe a method to certify that an approximate numerical solution of $f$ is close to an isolated singular point of a nearby polynomial system with a prescribed multiplicity structure. It involves Newton iterations applied to an extended deflated system that locally converges, under regularity conditions, to a small deformation of $f$ such that this deformed system has an exact singular solution. The iteration simultaneously converges to the coordinates of the singular solution and the coefficients of the inverse system that describes the multiplicity structure at the singular solution. We use $\alpha$-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the distance to the singular point.
This is based on joint works with Agnes Szanto, to whom this presentation is dedicated.
Friday, June 16, 17:00 ~ 17:30
Subresultants and the Shape Lemma
Carlos D'Andrea
Universitat de Barcelona, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
In nice cases, a zero-dimensional complete intersection ideal over a field has a Shape Lemma. There are also cases where the ideal is generated by the resultant and first subresultant polynomials of the generators. This situation has been explored by Agnes Szanto in some earlier papers in her academic career. We will review them and explore the relation between these representations, and also study when the resultant generates the elimination ideal.
Joint work with David Cox (Amherst College, USA).
Friday, June 16, 17:30 ~ 18:30
Towards Agnes' symmetric Hermite interpolation
Teresa Krick
University of Buenos Aires & CONICET, Argentina - This email address is being protected from spambots. You need JavaScript enabled to view it.
I will describe an ongoing project started some years ago with Agnes, after she accidentally rediscovered Lagrange interpolation for multivariate symmetric polynomials when working together on univariate subresultants. I will present some of the preliminary results obtained towards the extension of this theory to symmetric Hermite interpolation, which corresponds to the case when there are nodes coalescences.
Joint work with Agnes Szanto.
Saturday, June 17, 14:00 ~ 14:30
Symmetric SAGE and SONC forms and exactness of relaxations
Thorsten Theobald
Goethe University Frankfurt, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
The cones of sums of arithmetic-geometric exponentials (SAGE cone) and sums of nonnegative circuit polynomials (SONC) provide non-negativity certificates and relaxations for signomials and polynomials, enriching the computational techniques based on sums of squares. In this talk we discuss techniques to exploit and to analyze these cone in the presence of symmetries under the linear action of a finite group. Based on a symmetry-adapted representation, we present a class of signomials (respectively polynomials) where the SAGE-relaxation (respectively SONC-relaxation) is exact.
Joint work with Philippe Moustrou (Univ. Toulouse, France), Cordian Riener (UiT The Arctic University of Norway) and Hugues Verdure (UiT The Arctic University of Norway).
Saturday, June 17, 14:30 ~ 15:00
The SONC Cone: Primal and Dual Perspectives
Timo de Wolff
TU Braunschweig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Solving polynomial optimization problems requires to certify nonnegativity of multivariate, real polynomials. A classical way to do this are sums of squares (SOS). An alternative way are sums of nonnegative circuit polynomials (SONC), which I introduced joint with Iliman in 2014 building on work by Reznick. For a fixed support, SONCs form a convex cone, which has the same dimension as the corresponding nonnegativity cone. Moreover, motivated from a dualization process, one can obtain a particular (strict but full-dimensional) subcone of the SONC cone - the DSONC cone - leading to certificates which have, despite being weaker than SONC, the benefit to be obtainable via linear programming. In this talk I will speak about the SONC cone and its DSONC subcone. It is based on ArXiv 2204.03918.
Joint work with Janin Heuer (TU Braunschweig).
Saturday, June 17, 15:00 ~ 15:30
Minimization of analytic functions over compact domains
Georgy Scholten
Sorbonne Université, LIP6, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this talk, we propose a new method to minimize analytic functions over compact domains through the use of polynomial approximations. This is in essence an effective application of the Stone-Weierstrass Theorem, as we seek to construct a polynomial approximant of $f$ over a compact domain satisfying an arbitrary set precision. The polynomial approximation allows us to compute all critical points of the approximant exactly, using methods from computer algebra. Our Main Theorem provides conditions of probabilistic nature on the local minima of the objective function and on the accuracy of the polynomial approximation sufficient to guarantee that all local minima located in the interior of the compact domain are captured by the critical points of the polynomial. We provide an implementation of a probabilistic method to construct a polynomial least squares approximant of low degree, compute its critical points and initialize local minimization methods on the objective function $f$ at these points, in order to recover the totality of its local minima .
Joint work with Mohab Safey El Din (Sorbonne Université, LIP6) and Emmanuel Trélat (Sorbonne Université, LJLL).
Saturday, June 17, 15:30 ~ 16:00
The spark randomizer: a probabilistic algorithm for computing Gröbner bases
Sonja Petrović
Illinois Institute of Technology, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
We place the problem of computing a Gr\"obner basis of a polynomial ideal within the violator space framework in order to use Clarkson's fast sampling algorithm from geometric optimization. The framework requires three ingredients, some of which we provide theoretically, and the missing ones we provide as outputs of a machine learning algorithm. We demonstrate how this blended randomization-and-learning approach can work for symbolic computation.
Joint work with Shahrzad Jamshidi (Lake Forest College, United States) and Despina Stasi (Illinois Institute of Technology, United States).
Saturday, June 17, 16:30 ~ 17:00
Efficient algorithms for Riemann—Roch spaces
Grégoire Lecerf
CNRS & École polytechnique, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Riemann—Roch spaces are a cornerstone of modern applications of algebra to various areas of computer science: error correcting codes, secret sharing, multi-party computations, zero-knowledge proofs, resilience in distributed storage systems, interactive oracle proofs... Best performances are achieved for specific families of spaces known to be difficult to compute.
We will present a new probabilistic algorithm of Las Vegas type that computes Riemann—Roch spaces of plane projective curves in expected sub-quadratic time whenever the characteristic is zero or positive but sufficiently large. The method relies on the Brill—Noether theory and recent fast algorithms for Puiseux series and structured polynomial matrices. In case of curves with only ordinary singularities, we will present a faster variant that even supports any characteristic.
Saturday, June 17, 17:00 ~ 17:30
An Invitation to Tropical Alexandrov Curvature
Carlos Améndola
TU Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Alexandrov curvature, a generalization of classical Riemannian sectional curvature, is determined by comparison of triangles in an arbitrary metric space to corresponding triangles in Euclidean space. We study Alexandrov curvature in the tropical projective torus with respect to the tropical metric, which has been useful in various statistical analyses, particularly in phylogenomics. We find that positive, negative, zero, and undefined Alexandrov curvature can exist concurrently in the tropical setting, and that there is a tight connection between triangle combinatorial type and curvature. Our results are aided by computational experiments, and shed light on the intricate geometry of the tropical projective torus.
Joint work with Anthea Monod (Imperial College London).
Saturday, June 17, 17:30 ~ 18:00
Duality and blow-up algebras
Yairon Cid Ruiz
KU Leuven, Belgium - This email address is being protected from spambots. You need JavaScript enabled to view it.
We provide a generalization of Jouanolou duality that is applicable to a plethora of situations. The environment where this generalized duality takes place is a new class of rings, that we introduce and call weakly Gorenstein. As a main consequence, we obtain a new general framework to investigate blowup algebras. We use our results to study and determine the defining equations of the Rees algebra of certain families of ideals.
Joint work with Claudia Polini (University of Notre Dame) and Bernd Ulrich (Purdue University).
Saturday, June 17, 18:00 ~ 18:30
Rigidity of Hypergraphs under Algebraic Constraints
Fatemeh Mohammadi
KU Leuven, Belgium - This email address is being protected from spambots. You need JavaScript enabled to view it.
I will talk about the connection between graph rigidity theory and tensor completions. Graph rigidity theory studies the rigidity or flexibility of bar-joint linkages in Euclidean space. In other words, rigidity theory of bar and joint frameworks studies uniqueness of point configurations given some of the pairwise distances. Replacing the distance measurement with a general polynomial function, the rigidity of frameworks relates to the unique identifiability of certain tensor completions. In this talk I will present algebraic and geometric problems emerged through such a formulation, and the connection to the classical secant varieties.
Joint work with James Cruickshank (National University of Ireland Galway, Ireland), Anthony Nixon (Lancaster University, UK) and Shin-ichi Tanigawa (Tokyo University, Japan).
Posters
On the strongly robust property of toric ideals
Dimitra Kosta
University of Edinburgh, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
To every toric ideal one can associate an oriented matroid structure, consisting of a graph and another toric ideal, called bouquet ideal. The connected components of this graph are called bouquets. Bouquets are of three types; free, mixed and non mixed. We prove that the cardinality of the following sets - the set of indispensable elements, minimal Markov bases, the Universal Markov basis and the Universal Gröbner basis of a toric ideal - depends only on the type of the bouquets and the bouquet ideal. These results enable us to introduce the strongly robustness simplicial complex and show that it determines the strongly robustness property. For codimension 2 toric ideals, we study the strongly robustness simplicial complex and prove that robustness implies strongly robustness.
Joint work with Apostolos Thoma, University of Ioannina, Greece and Marius Vladoiu, University of Bucharest, Romania.
Statistical Models with Toric Structure
Aida Maraj
University of Michigan, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Staged tree models are discrete statistical models encoding relationships between events in a directed rooted tree with colored vertices. In algebro-geometric terms, the model consists of points inside a toric variety whose design matrix is determined by the root to leaf paths in the tree. For certain trees, called balanced, Duarte and Görgen proved that the model is in fact the intersection of this toric variety and the probability simplex. The toric structure gives the model a straightforward description, and has computational advantages; it provides a Gröbner basis of binomial quadratics completely determined by the paths in the tree. In this poster we (1) show that the class of staged tree models with toric structure extends far outside of the balanced case, if we allow a linear change of coordinates, and (2) discuss staged tree models for which such a change of coordinates is not possible. Part (1) is based on work with Christiane Görgen and Lisa Nicklasson and part (2) is work with Arpan Pal.
Multilinear Hyperquiver Representations
Tommi Muller
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
We count singular vector tuples of a system of tensors. We do so by studying the generalisation of quivers to directed hypergraphs. Assigning vector spaces to its nodes and multilinear maps to the its hyperedges gives a hyperquiver representation. Hyperquiver representations generalise quiver representations (where all hyperedges are edges) and tensors (where there is only one multilinear map). The singular vectors of a hyperquiver representation are a compatible assignment of vectors to the nodes. We compute the dimension and degree of the the variety of singular vectors of a hyperquiver representation. Our formula specialises to the result of Friedland and Ottaviani to count the singular vector tuples of a generic tensor, as well as to the formula of Cartwright and Sturmfels to count the eigenvectors of a generic tensor.
Joint work with Vidit Nanda (University of Oxford, United Kingdom) and Anna Seigal (Harvard University, United States).
Dynamics of root-finding methods
Bernhard Reinke
University of Liverpool, UK - This email address is being protected from spambots. You need JavaScript enabled to view it.
We give an overview of root-finding methods of univariate polynomials and their interpretation as complex dynamical systems. The main focus is the Weierstrass/Durand–Kerner method and its similarities and differences to the Newton and the Ehrlich–Aberth methods.
In particular, we show how to use methods from computational algebraic geometry to investigate (and/or establish) the existence of attracting periodic cycles, as well as diverging orbits, and present explicit examples of both phenomena for the Weierstrass method.
Bernhard Reinke. Diverging orbits for the Ehrlich–Aberth and the Weierstrass root finders. Proc. Amer. Math. Soc. 150 (2022), 1287–1300 https ://doi.org/10.1090/proc/15715
Bernhard Reinke, Dierk Schleicher, and Michael Stoll. The Weierstrass–Durand–Kerner root finder is not generally convergent. Math. Comp. 92 (2023), 839–866 https ://doi.org/10.1090/mcom/3783
Joint work with Dierk Schleicher (Aix-Marseille Université, France) and Michael Stoll (Universität Bayreuth, Germany).