🪢 Crossed paths: when two paths become one

Homotopy continuation tracks one path per start point, from a generic start system at \(t=1\) to your target system at \(t=0\). The homotopy carries a random parameter \(\gamma\), and that randomness is load-bearing: it guarantees, with probability 1, that the paths stay separate for all \(0 < t \le 1\). Distinct paths simply do not meet.

So if two distinct paths do arrive at the same point, something has gone wrong. It is not a benign “duplicate” – it is a path crossing: somewhere along the way the numerical tracker took a step coarse enough to jump from one path onto a neighbouring one, and from there the two are indistinguishable. They reach the endgame boundary as the same point, the endgame sends both to the same solution, and you are left with a duplicate where there should have been two answers – a solution silently lost.

This tutorial does three things: provoke a crossing on purpose, see how Bertini 2 detects and fixes it, and – the real point – show why you should never see one with the defaults.

What Bertini does at the endgame boundary

A zero-dim solve has a definite shape: track every path to the endgame boundary (by default \(t = 0.1\)), then run the endgame from there to \(t=0\). In between sits the midpath check. It compares every pair of boundary points and, if two agree to within a relaxed same-point tolerance, flags a crossing. Then EGBoundaryAction() re-tracks the offending paths with tightened settings – a smaller tolerance and a higher-order predictor – and checks again, up to max_num_crossed_path_resolve_attempts times (default 2).

Two distinct paths agreeing to several digits at \(t=0.1\) is a measure-zero coincidence, which is exactly why it is a reliable alarm: under correct tracking it never fires.

Provoking one

The classic way to under-resolve paths is a low-order predictor with a loose tolerance. We use the Euler predictor (order 1) and a loose pre-endgame tolerance on the cyclic-5 system (120 paths, 70 distinct finite solutions). The complete script is crossed_paths.py:

examples/crossed_paths.py
#!/usr/bin/env python
"""Provoke a path crossing on purpose, and watch Bertini 2 detect and re-track it.

Two *distinct* homotopy paths reaching the **same** point at the endgame boundary is a
probability-0 event -- the homotopy's gamma is random, so generic paths never meet.  When it does
happen it is a **path crossing**: a symptom that the tracker under-resolved the paths (most often a
too-low-order predictor or a too-loose tolerance), not a benign duplicate.  The zero-dim solver
checks for this at the endgame boundary and, by default, re-tracks the offending paths with
tightened settings.

To see the machinery work we deliberately break the tracking: the **Euler** predictor (order 1)
with a **loose** pre-endgame tolerance, on the cyclic-5 system.  The fixed seed only makes the bad
behaviour reproducible -- it is NOT the fix.  The fix is the solver's re-tracking (and, in normal
use, the better default predictor / a tighter tolerance).

Run it::

    python crossed_paths.py            # uses a seed known to cross on the author's machine
    python crossed_paths.py --seed 7   # try another seed

Which seed crosses depends on platform numerics; if the chosen one does not cross, the script says
so and suggests trying another.
"""

import argparse
import numpy as np

import bertini as pb

CYCLIC_N = 5
KNOWN_FINITE = 70            # distinct finite solutions of cyclic-5
OK = int(pb.SuccessCode.Success)


def cyclic_system(n):
    """The cyclic-n system: the n-1 cyclic sums of products, plus (prod - 1)."""
    x = [pb.Variable('x{}'.format(i)) for i in range(n)]
    w = x + x
    sys = pb.System()
    for length in range(1, n):
        sys.add_function(np.sum([np.prod(w[start:start + length]) for start in range(n)]))
    sys.add_function(np.prod(x) - 1)
    sys.add_variable_group(pb.VariableGroup(x))
    return sys


def solve(seed, resolve_attempts, tol=1e-4):
    """Solve cyclic-5 with the Euler predictor + a loose tolerance at a fixed seed.

    ``resolve_attempts`` is how many times the solver may re-track crossed paths at the endgame
    boundary; 0 means "detect and report only".  Returns (report, distinct_finite_count).
    """
    pb.random.set_random_seed(seed)
    solver = pb.ZeroDimSolver(cyclic_system(CYCLIC_N), endgame='cauchy', mptype='double', startsystem='binomial')

    # The deliberate culprit: a first-order predictor.
    solver.get_tracker().predictor(pb.Predictor.Euler)

    tols = solver.get_config(pb.nag_algorithm.TolerancesConfig)
    tols.newton_before_endgame = tol
    tols.newton_during_endgame = tol / 10
    solver.set_config(tols)

    zd = solver.get_config(pb.nag_algorithm.ZeroDimConfig)
    zd.max_num_crossed_path_resolve_attempts = resolve_attempts
    solver.set_config(zd)

    solver.solve()

    report = solver.endgame_boundary_metadata()
    finite = [m for m in solver.solution_metadata()
              if int(m.endgame_success_code) == OK and m.is_finite]
    distinct = round(sum(1.0 / m.multiplicity for m in finite))
    return report, distinct


def main():
    parser = argparse.ArgumentParser(description=__doc__,
                                     formatter_class=argparse.RawDescriptionHelpFormatter)
    parser.add_argument('--seed', type=int, default=3,
                        help='RNG seed (default 3; chosen to cross on the author\'s machine)')
    args = parser.parse_args()

    # First, turn OFF re-tracking, so we can see the damage a crossing does on its own.
    report, distinct = solve(args.seed, resolve_attempts=0)
    print('Euler + loose tolerance, re-tracking DISABLED (max_num_crossed_path_resolve_attempts=0):')
    print('  crossings detected : {}'.format(report.num_crossings_detected))
    print('  crossed path indices: {}'.format(list(report.crossed_path_indices)))
    print('  midpath check passed: {}'.format(report.passed))
    print('  distinct finite solutions: {} / {}'.format(distinct, KNOWN_FINITE))

    if report.num_crossings_detected == 0:
        print('\nNo crossing was provoked at seed {} on this machine.  Try another --seed.'.format(args.seed))
        return

    print('\n  --> the crossed paths merged into one, so a true solution was lost'
          if distinct < KNOWN_FINITE else
          '\n  --> a crossing was detected (the endpoints happened to still be recoverable)')

    # Now the default behaviour: re-track the crossed paths with tightened settings.
    report, distinct = solve(args.seed, resolve_attempts=2)
    print('\nSame solve, re-tracking ENABLED (the default):')
    print('  crossings detected : {}'.format(report.num_crossings_detected))
    print('  re-track attempts  : {}'.format(report.num_resolve_attempts))
    print('  midpath check passed: {}'.format(report.passed))
    print('  distinct finite solutions: {} / {}'.format(distinct, KNOWN_FINITE))

    assert distinct == KNOWN_FINITE, \
        'expected the re-track to recover all {} solutions'.format(KNOWN_FINITE)
    print('\n  --> the crossing was resolved and the lost solution recovered.')
    print('      The real lesson: use a higher-order predictor (the default RKF45) or a tighter')
    print('      tolerance, and the crossing never happens in the first place.')


if __name__ == '__main__':
    main()

The key knobs are three lines on the solver:

solver.get_tracker().predictor(pb.Predictor.Euler)   # order-1 predictor: the culprit

tols = solver.get_config(pb.nag_algorithm.TolerancesConfig)
tols.newton_before_endgame = 1e-4                              # loose tracking before the endgame
solver.set_config(tols)

zd = solver.get_config(pb.nag_algorithm.ZeroDimConfig)
zd.max_num_crossed_path_resolve_attempts = 0                  # 0 = detect & report, do NOT re-track
solver.set_config(zd)

Note

The fixed seed only makes the bad behaviour reproducible so we can talk about it. Pinning a seed is never the fix for a flaky solve – the fixes are tolerance, precision, and predictor. See 🚀 Solving at scale: many cores, many machines.

Seeing the damage, then the repair

Run with re-tracking disabled first, so the crossing stands uncorrected:

Euler + loose tolerance, re-tracking DISABLED (max_num_crossed_path_resolve_attempts=0):
  crossings detected : 2
  crossed path indices: [16, 58]
  midpath check passed: False
  distinct finite solutions: 69 / 70

  --> the crossed paths merged into one, so a true solution was lost

Paths 16 and 58 jumped onto each other. The solver tells you this – the report from endgame_boundary_metadata() carries passed = False and the offending indices – but with re-tracking off it does nothing about it, and the distinct finite count comes up one short: 69 instead of 70.

Now the default behaviour, re-tracking enabled:

Same solve, re-tracking ENABLED (the default):
  crossings detected : 2
  re-track attempts  : 1
  midpath check passed: True
  distinct finite solutions: 70 / 70

  --> the crossing was resolved and the lost solution recovered.

One re-track attempt – tighter tolerance, and Euler bumped up to the default RKF45 – pulls the two paths back apart, and the missing solution reappears. 70 of 70.

Reading the report

Every solve exposes what the midpath check found, via endgame_boundary_metadata():

report = solver.endgame_boundary_metadata()
report.passed                  # did the check ultimately pass (no crossings left)?
report.num_crossings_detected  # how many crossed paths were found on the first check
report.num_resolve_attempts    # how many re-track attempts were performed
report.crossed_path_indices    # which paths were involved

Use it as a correctness gate in your own scripts: if report.passed is False after a solve, some crossings were left unresolved and the affected solutions may be wrong – re-solve with a better predictor or a tighter tolerance.

What to actually do about crossings

  • Prefer prevention. The defaults exist precisely so this never happens: the default predictor is RKF45 (order 4 with an embedded error estimate), not Euler. Swap the one Euler line out – or just don’t put it in – and the crossing disappears at the source. A modestly tighter newton_before_endgame does the same.

  • Let the solver self-correct. With max_num_crossed_path_resolve_attempts > 0 (the default is 2) the re-track usually fixes a stray crossing for you, as above.

  • Decide what “give up” means. Set max_num_crossed_path_resolve_attempts = 0 to detect and report only – the solve keeps tracking the crossed paths through the endgame (you never get fewer answers than you would without the check), but it does not spend time re-tracking; you read report.passed and decide. This is the conservative choice when you would rather re-solve the whole system with better settings than retry individual paths.

The honest summary: a crossing is a signal you tracked too coarsely. Bertini 2 will catch it and, within a bounded number of attempts, usually fix it – but the best solve is the one where the predictor and tolerance are good enough that the alarm never sounds.