Building your own fast solver
Homotopy Continuation Tutorial

Ricardo Fabbri

Rio de Janeiro State University

Author of MiNuS github.com/rfabbri/minus

Building your own fast solver
MiNuS fast continuation solver framework
1. Build a Macaulay basic prototype

macaulay2.com

2. Add Macaulay pro features
3. Build a C++ fast solver step-by-stepgithub.com/rfabbri/minus

1. Design of fast template system
2. Design of fast executable
4. Benchmark

Generic prototype

Optimized C++SolverBuilding a Macaulay prototype
MiNuS fast continuation solver framework• Macaulay is a powerful, modern scripting language• Focuses on symbolic computation• Runs Homotopy Continuation• Generic C++ under the hood
• Code-matched with optimized MiNuS C++ framework• Origin of fastest most reliable solver for hard problems

Generic prototype• Used by key Algebraic-geometry researchers• Able to help build fast solvers that no one else hasmacaulay2.com

github.com/rfabbri/minus

Building a C++ fast solver
MiNuS fast continuation solver framework• MiNuS is a template system that helps build and debug your fast solver• Allows to test diferent formulations, problems, and implementations• Leverages the fact that the core algorithm is just predictor-corrector• Born out of intense semester program at ICERM• Bertini and Macaulay team on large unsolved problem• Solver with Macaulay 60s —> MiNuS in 400ms

Optimized C++
Solver

Trifocal Relative Pose from Lines at Points, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, CVPR 2020 and PAMI 2022
Ricardo Fabbri, Timothy Duff, Hongyi Fan, Margaret Regan, David de Pinho (my former MSc. Student), Elias Tsigaridas, Charles Wampler, Jonathan Hauenstein, Peter Giblin, Benjamin Kimia, Anton Leykin and Tomas Pajdla (pdf | code | datasets | bib)github.com/rfabbri/minus

Building a C++ fast solver
MiNuS fast continuation solver framework
Main idea of MiNuS: Progressive specialization• Key to good Numerical algorithms is knowledge to specialize algorithms• HC is too generic• Start system, Randomization, Predictor-corrector, evaluator code are generic• Pretraining Analogy• Existing numerical algorithms are pretrained on the space of all problems,• “Dataset” is very unbalanced towards o ine problems• Realtime scenarios underrepresented

Optimized C++
Solver• Fine-tuning the HC model to your problem is key
ffl

github.com/rfabbri/minus

Building a C++ fast solver
MiNuS fast continuation solver framework

Trifocal
Pose
Estimation
Using CurveDi↵erential
Geometr
15
Chapter 14. Chapter
Trifocal 14.
Relative
PoseRelative
Estimation
UsingCurve Di↵erential
Geometry
150

chicago14a=?
Remark
14.6.2.
Noteinthat
whereasini (14.6.3)
the T i canbeindependently
Remark 14.6.2.
Note that
whereas(14.6.3)
the T
can independently
multiplied by be multiplied barbitrarynon-zeroinrealnumbers(14.6.4)
this isnotcantheonlycase:bethey
can only be multiplie
arbitrary non-zeroreal numbers(14.6.4)
this inis not
the case:they
multipliedby thesame real number.
by the same realnumber.

trifocal 14x14 formulation a

far equations
we have nineequations
and andthe their
unknowns
So far we haveSonine
and theunknowns
countsandare their counts are
6

Vi6R, T = ? 6R, T6

ViR, T

linecircle2a6

R, T = ? 6

Trifocal relative pose from SIFT features
Proposed
Fabbri
ECCV2012
The other nineequations,
to make
18 unknowns
and18equations,
fromTheother nineequations,
to in
make
18 unknowns
andare18obtained
equations,are obtained fro
SolvedFabbri,Duff, etal
PAMI2022
the fact that theVi theprojectto certain
known
inthe
three
imageplanes.
Thethevectors
fact thatvectors
Vi byprojectto vectors
certainknown
vectors
in thethree
image planes. Th
Algebraicof nonlinearity
312
lengths of thelengths
Vi and ofof thetheirViprojections
aredegreeirrelevant.
Noteirrelevant.
that wealreadyknowwethealready know thandof theirprojectionsareNotethat
12
image of the tangent
line
in
directionofthevector
Vpassesthroughoror
so it oris 1 or 2 so it
iof the vector V passesiii
imageofthetangent
line
indirection
through
Model problemsii
iiline-circle 14x14 formulation aonly the directions which matter. The nine remaining equations are github.com/rfabbri/minus

Building a C++ fast solver
MiNuS fast continuation solver framework

chicago14a
trifocal 14x14 formulation alinecircle2aline-circle 14x14 formulation a(x 2 + y 2) + b * x + c = 0d*x + e*y + f = 0
Recal Tim Duff’s talkModel problems

github.com/rfabbri/minus

Building a Macaulay prototype
Hands-on• git clone minus• scripts are in minus/tutorial• equations, start, end• running• shell: m2• m2:
macaulay2.com

Generic prototype

load(“script”)

github.com/rfabbri/minus

Building a Macaulay prototype
Hands-on• Evaluators to C++

HxH.cxx and Hxt.cxx
macaulay2.com

github.com/rfabbri/minus

Building a Macaulay prototype
Hands-on• Evaluators to C++

HxH.cxx and Hxt.cxx
macaulay2.com

github.com/rfabbri/minus

— End or part 2 —