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

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:

https://aco.gatech.edu/sites/default/files/documents/2021/dissertation-t...

Summary of the thesis is below.

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.