Back to search

Georgia Institute of Technology

Applications of monodromy in solving polynomial systems

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Duff, Timothy
Advisor dc:contributor.advisor
  • Leykin, Anton
Committee members dc:contributor.committeemember
  • Thomas, Rekha
  • Yu, Josephine
  • Baker, Matthew
  • Blekherman, Gregory
  • Peng, Richard

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/65027

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Duff, Timothy. Applications of monodromy in solving polynomial systems. Doctoral thesis, Georgia Institute of Technology, 2021. http://hdl.handle.net/1853/65027