# GPU-Based Homotopy Continuation for Minimal Problems in Computer Vision

arXiv: https://arxiv.org/abs/2112.03444 · HTML: https://mlsanity.com/paper/2112.03444/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 103 references that are in the map.
- First posted on arXiv 7 Dec 2021.

## Builds on (most cited first, 9 of 9)

- [cuDNN: Efficient Primitives for Deep Learning](https://mlsanity.com/paper/1410.0759/) (2014)
- [Dissecting the NVIDIA Volta GPU Architecture via Microbenchmarking](https://mlsanity.com/paper/1804.06826/) (2018)
- [Beyond Gr"obner Bases: Basis Selection for Minimal Solvers](https://mlsanity.com/paper/1803.04360/) (2018)
- [PLMP -- Point-Line Minimal Problems in Complete Multi-View Visibility](https://mlsanity.com/paper/1903.10008/) (2019)
- [A clever elimination strategy for efficient minimal solvers](https://mlsanity.com/paper/1703.05289/) (2017)
- [PL1P -- Point-line Minimal Problems under Partial Visibility in Three Views](https://mlsanity.com/paper/2003.05015/) (2020)
- [Minimal Problems for the Calibrated Trifocal Variety](https://mlsanity.com/paper/1611.05947/) (2016)
- [Radially-Distorted Conjugate Translations](https://mlsanity.com/paper/1711.11339/) (2017)
- [GAPS: Generator for Automatic Polynomial Solvers](https://mlsanity.com/paper/2004.11765/) (2020)

## Built on by (most cited first, 8 of 8)

- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [Trifocal Tensor and Relative Pose Estimation with Known Vertical Direction](https://mlsanity.com/paper/2512.19110/) (2025)
- [Practical solutions to the relative pose of three calibrated cameras](https://mlsanity.com/paper/2303.16078/) (2023)
- [Condition numbers in multiview geometry, instability in relative pose estimation, and RANSAC](https://mlsanity.com/paper/2310.02719/) (2023)
- [Simulator HC: Regression-based Online Simulation of Starting Problem-Solution Pairs for Homotopy Continuation in Geometric Vision](https://mlsanity.com/paper/2411.03745/) (2024)
- [Three-view Focal Length Recovery From Homographies](https://mlsanity.com/paper/2501.07499/) (2025)
- [Towards Fair and Robust Face Parsing for Generative AI: A Multi-Objective Approach](https://mlsanity.com/paper/2502.04391/) (2025)
- [Numerically Computing Galois Groups of Minimal Problems](https://mlsanity.com/paper/2507.10407/) (2025)

## Abstract (arXiv)

Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 26 times on polynomial benchmarks. We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.