### Applications of monodromy in solving polynomial systems

- Series
- Dissertation Defense
- Time
- Wednesday, June 16, 2021 - 12:00 for 1.5 hours (actually 80 minutes)
- Location
- ONLINE
- Speaker
- Timothy Duff – GA Tech – tduff3@gatech.edu

Final doctoral examination and defense of dissertation of Timothy Duff, June 16, 2021

Date: June 16, 2021, 12:00pm EST

Bluejeans Link is https://bluejeans.com/151393219/

Title: Applications of monodromy in solving polynomial systems

Advisor: Dr. Anton Leykin, School of Mathematics, Georgia Institute of Technology

Committee:

Dr. Matthew Baker, School of Mathematics, Georgia Institute of Technology

Dr. Gregory Blekherman, School of Mathematics, Georgia Institute of Technology

Dr. Richard Peng, School of Computer Science, Georgia Institute of Technology

Dr. Rekha Thomas, Department of Mathematics, University of Washington

Dr. Josephine Yu, School of Mathematics, Georgia Institute of Technology

Reader: Dr. Rekha Thomas, Department of Mathematics, University of Washington

---------------------------------------------------------------------------------------------------------

The thesis is available here:

fhttps://timduff35.github.io/timduff35/thesis.pdf

Summary:

Polynomial systems of equations that occur in applications frequently have a special structure. Part of that structure can be captured by an associated Galois/monodromy group. This makes numerical homotopy continuation methods that exploit this monodromy action an attractive choice for solving these systems; by contrast, other symbolic-numeric techniques do not generally see this structure. Naturally, there are trade-offs when monodromy is chosen over other methods. Nevertheless, there is a growing literature demonstrating that the trade can be worthwhile in practice.

In this thesis, we consider a framework for efficient monodromy computation which rivals the state-of-the-art in homotopy continuation methods. We show how its implementation in the package MonodromySolver can be used to efficiently solve challenging systems of polynomial equations. Among many applications, we apply monodromy to computer vision---specifically, the study and classification of minimal problems used in RANSAC-based 3D reconstruction pipelines. As a byproduct of numerically computing their Galois/monodromy groups, we observe that several of these problems have a decomposition into algebraic subproblems. Although precise knowledge of such a decomposition is hard to obtain in general, we determine it in some novel cases.