Session S34 - Symbolic and Numerical Computation with Polynomials

Friday, July 16, 14:15 ~ 14:45 UTC-3

Efficient algorithms for torus actions by interior-points methods for unconstrained geometric programming

Peter Bürgisser

TU Berlin, Germany   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

There has been recent interest in the complexity of solving fundamental computational problems in invariant theory. These problems arise in the setting of an action of a reductive group on a vector space and capture a diverse set of problems in different areas of computer science, mathematics, and physics. Both algebraic and analytical approaches have been suggested. While no efficient algorithms are known for general groups, polynomial time algorithms were recently found when the acting group is an algebraic torus.

In the talk we focus on analytic solutions for the norm minimization and scaling problems in the case of a torus action. This amounts to unconstrained geometric programming problems. We introduce condition measures for these problems and provide condition-based analyses of interior-point methods for them. This way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing.

See https://arxiv.org/abs/2008.12110

Joint work with Yinan Li (Centrum Wiskunde & Informatica (CWI) and QuSoft), Harold Nieuwboer (Korteweg–de Vries Institute for Mathematics and QuSoft, University of Amsterdam) and Michael Walter (Korteweg–de Vries Institute for Mathematics, Institute for Theoretical Physics, Institute for Language, Logic, and Computation, and QuSoft, University of Amsterdam).

View abstract PDF