A primal-dual formulation for certifiable computations in Schubert calculus (Q330099): Difference between revisions

Numerical algebraic geometry provides fast, efficient methods to approximate all solutions to a system of polynomial equations. When the system is square in which the number of equations is equal to the number of variables, Smale's \(\alpha\)-theory gives methods to certify that these approximate solutions correspond to actual solutions. This is implemented in software which can be used to prove that all solutions have been found and to certifiably count the number of real solutions. The Schubert calculus of enumerative geometry has come to mean all problems of determining the linear subspaces of a vector space which have specified positions with respect to other, fixed but general subspaces. Originating in work of \textit{H. Schubert} [Math. Ann. 26, 26--51 (1885; JFM 17.0668.01); Mitt. Math. Ges. Hamb. 1, 134--155 (1886; JFM 18.0631.01)], it has long been an active subject, undergoing significant recent development. As a rich and well-understood class of geometric problems, the Schubert calculus is a laboratory for the systematic study of new phenomena in enumerative geometry, particularly as Schubert problems are readily formulated and studied on a computer. There are two traditional formulations of Schubert problems, one in global Plücker coordinates and one in the local coordinates of a Schubert cell. The first involves quadratic Plücker equations and linear equations, while the second uses no Plücker equations, and the linear equations are replaced by minors of matrices. Both formulations typically involve far more equations than variables. The second method was used to provide evidence for the Shapiro conjecture and discover its generalizations through the systematic study of many billions of instances of several thousand Schubert problems. Traditional formulations of Schubert problems typically lead to overdetermined systems (more equations than variables), so algorithms based on \(\alpha\)-theory cannot be used to certify traditional numerical computation in Schubert calculus. In this paper the authors present a novel formulation of any Schubert problem in primal-dual coordinates as a square system of bilinear equations. This will enable certification based on \(\alpha\)-theory, both a posteri certification of approximate solutions and certified path-tracking. The set of all \(\ell\)-dimensional linear subspaces (\(\ell\)-planes) in a vector space \(V\) having specified position with respect to a fixed subspace forms a Schubert subvariety of the Grassmannian. A Schubert problem is formulated as the intersection of a collection of Schubert varieties in a Grassmannian which are in general position. A natural extension is to consider a Schubert problem to be given by intersecting a collection of Schubert subvarieties in general position in a flag manifold. They give a square primaldual formulation of any Schubert problem on any flag manifold. The main ideas are well illustrated for the Grassmannian. In Sect. \(2\) they describe Schubert varieties in the Grassmannian and give a traditional formulation of a Schubert problem as an overdetermined system of determinantal equations in local coordinates for the Grassmannian. We introduce our primal-dual reformulation in Sect. \(3\), where they use duality to recast Schubert problems as a square system of bilinear equations in a larger space.We improve this, using a hybrid approach and more sophisticated local coordinates to our primal-dual formulation in Sect. \(4\). Finally, in Sect. \(5\) they explain how this extends to all Schubert problems in a flag manifold.