fanroots 0.1.0

Root-finding and optimization on polyhedral fans

fanroots

Original author: Nate MacFadden, Liam McAllister Group, Cornell

Contributors: —

Root-finding and optimization for vector-valued functions defined piecewise over the secondary fan of a point or vector configuration. Designed for Kähler moduli stabilization (KMS) in string compactifications, where it delivers order-of-magnitude speedups over prior methods (i.e., those in arXiv:2406.13751).

The Problem

Given a vector/point configuration with $N$ elements, the secondary fan partitions $\mathbb{R}^N$ (or, for vector configurations, a convex subregion of this space) into convex 'secondary' cones. Call $\mathbb{R}^N$ 'height space'. This software is designed for continuous, differentiable functions whose analytic form may vary chamber-by-chamber. One example is K"ahler moduli stabilization, which depends on the intersection numbers of the toric variety associated to each triangulation. These numbers change discretely as one crosses walls of the secondary fan, but the function remains smooth.

The major complication in practice is the moderate-to-high dimension $\mathbb{R}^N$ ($N\approx 200$) as well as the large number of chambers (depending roughly exponentially on N - see arXiv:2008.01730, arXiv:2309.10855, and arXiv:2602.16909). At $N$ of interest, there are far too many chambers to enumerate, so operations are instead taken locally.

Algorithm

fanroots solves this by moving through the fan adaptively:

• Large steps (JumpStep): jump directly to target heights, recomputing the triangulation from scratch. Effective when the function varies slowly chamber-by-chamber, as is typical for finding locations in Kähler moduli space where the divisors take certain volumes.
• Small steps (FlopStep): walk along the step direction via CYTools' flip_linear — a wrapper of regfans' flip routines that additionally tracks intersection numbers — flipping through chamber walls one at a time. Efficient for fine-grained convergence once near a solution.

A schedule can mix both strategies dynamically based on step size. Step proposals include Newton's method, Gauss-Newton, gradient descent, and Levenberg-Marquardt. Step sizes are tuned via backtracking line search, ternary search, or 'shrinking'.

For functions depending on the intersection numbers, performance is further boosted by a recently developed fast intersection number kernel in CYTools, since computation of the intersection numbers typically becomes the bottleneck for such cases.

Installation

pip install -e .

Requires CYTools, whose cytools.vector_config module supplies the VectorConfiguration/Fan types fanroots operates on. These wrap regfans' flip/flop routines, adding toric capabilities.

Usage

This operates via an optimization class FanRoots:

from fanroots import FanRoots

optimizer = FanRoots(
    vc=my_vector_configuration,
    fct=fct,
    jac=jac,
    step_proposal="newton",       # "newton", "gauss_newton", "grad", "lma"
    step_size_optimizer="shrink", # "shrink", "bls", "ternary", "naive"
    step_taking_method="jump",    # "jump", "flop"
    tolerance=1e-6,
)
optimizer.optimize()

Key arguments (see help(FanRoots) for the full list):

Argument	Options	Description
step_proposal	"newton", "gauss_newton", "grad", "lma"	Step direction method
step_size_optimizer	"shrink", "bls", "ternary", "naive"	Step size tuning
step_taking_method	"jump", "flop"	How to move through the fan; overridden by step_taking_schedule for mixed strategies
learning_rate	float	Scales the proposed step before size optimization
tolerance	float	Halt when |fct(h)|_2 < tolerance
min_step_size	float	Halt if step shrinks below this
verbosity	int	Controls diagnostic output

See the VolumeFinder class in fanroots/applications/volume_finder.py for a complete example finding Kähler parameters that realize prescribed divisor volumes.