Efficient Algorithms for Geometric Invariant Theory (SIAM-AG 2019)

Mini-Symposium MS125 at the SIAM Conference on Applied Algebraic Geometry 2019, July 12, 2019. Room F-107 @ Unitobler, Bern.

Invited Speakers: Harm Derksen, Cole Franks, Ankit Garg, Gábor Ivanyos

Organizers: Peter Bürgisser, Michael Walter

Overview

Recently, motivated by the polynomial identity testing problem from computer science, and by questions arising in quantum information theory, efficient numerical algorithms for solving the null cone problem from geometric invariant theory have been proposed. The goal of the minisymposium is to review this progress and to report on recent advances.

Schedule

Abstracts

Algorithms for the separation of orbits of matrices (Harm Derksen, University of Michigan)

We consider two group actions on the set of m-tuples of n by n matrices, namely the simultaneous conjugation action of GL(n) and the left-right action of SL(n) x SL(n). An invariant can separate two orbits of m-tuples if and only if the closures of these orbits are disjoint. In both cases we present a polynomial time algorithm that decides whether the orbit closures of two m-tuples intersect. This is joint work with Visu Makam.

Analytic algorithms for the null cone problem (Ankit Garg, Microsoft India)

Null cone is a fundamental object in invariant theory. It is the variety defined by all the homogeneous invariant polynomials for a particular group action. This talk will be focused on the computational complexity of testing membership in the null cone. From a purely algebraic point of view, this problem seems hard, since except in a few cases, one does not have any nice description of the invariant polynomials. However, we will see that there is a good reason to believe that analytic methods can provide provably efficient algorithms for the null cone and we will discuss several examples where this has already been achieved, the most notable being bipartite matching, linear programming, non-commutative rank etc. The analytic approach goes via the Kempf-Ness criterion and connects to the exciting area of geodesically convex optimization.

Non-commutative rank of linear matrices, related structures and applications (Gabor Ivanyos, Hungarian Academy of Sciences)

The non-commutative rank of a matrix with homogeneous linear entries is the rank when we consider the variables as elements of the appropriate free division algebra. This is the same as the maximum size of a square sub-matrix such that the tuple of coefficient matrices is not in the null-cone of the polynomial invariants for the left-right action of the suitable special linear group. There is a “dual” characterization in terms of large common rectangular zero blocks (after appropriate changes of bases).We will outline a deterministic polynomial time algorithm for computing the non-commutative rank in a two-fold constructive way. Firstly, it computes a polynomial invariant for an appropriate sub-matrix together with a non-vanishing substitution of values from a division algebra of relatively small dimension (actually, even from a matrix algebra) into the variables. Then, in the non-full rank case, common zero blocks with matching parameters are revealed. We will also discuss related common “echelon forms” for the coefficient matrices and some applications. The algorithm for finding the large zero blocks works along certain flags of subspaces that further “echelonize” the coefficient matrices. These flags are analogous to the alternating forests in algorithms for finding maximum matchings in bipartite graphs. Interestingly, their behavior explain certain special cases when the non-commutative rank coincide with or approximates the usual, “commutative” one (i.e., with the rank when the variables are considered as elements of a commutative field). Some of these special cases will be discussed as well.
The talk is based on joint works with Youming Qiao and K. V. Subrahmanyam.

Analytic algorithms for the moment polytope (Cole Franks, Rutgers University)

Moment polytopes are convex bodies associated to certain group actions on manifolds. When the manifold is a projective variety invariant under the action of a reductive Lie group, it is known that the moment polytope encodes asymptotic information about the irreducible representations of the group occurring in the coordinate ring of the variety. This talk concerns the computational complexity of deciding moment polytope membership. Existing methods include enumerating the (potentially exponentially many) facets and evaluating highest weight polynomials (of potentially exponential degree), but we will discuss analytic algorithms that do not seem to face the same hurdles. These analytic algorithms are also notable for their simplicity and their ability to compute preimages under the moment map, a problem of practical interest. We will discuss how alternating minimization, one of the simplest approaches in optimization, leads to analytic algorithms for Horn’s problem and the quantum marginal problem. Among the conceptual tools in the analysis of these algorithms are “reductions” to the null cone problem and lower bounds for Kempf-Ness functions via representation theory.

Additional Material

• Slides and recordings from the Workshop on Optimization, Complexity and Invariant Theory organized by Avi Wigderson at the IAS (June 4-8, 2018).

• Slides from the Tutorial & Workshop on Scaling Algorithms and Applications at FOCS 2019.