Krawczyk Test

These lower-level helpers expose the interval Krawczyk tests used by the path tracker, Moore-box refinement, and variety certification routines. The core test goes back to Krawczyk's interval Newton method [Kra69].

`krawczyk_test`

CertifiedHomotopyTracking.krawczyk_test — Function

krawczyk_test(sys::SpecializedHomotopy, x, t, r; rho=0.7)
krawczyk_test(sys::SpecializedHomotopy, x, t, r, A; rho=0.7)

Run a Krawczyk inclusion/contraction test. For a given system and point, returns (passed, k_norm).

source

julia> @variables x y;
julia> CC = AcbField(128);
julia> compiled = compile_system([x^2 + y^2 - 2, x^3 - y], [x, y]);Compiling Static Polynomial System...
Compilation Done.
julia> sys = SpecializedHomotopy(compiled, CC);
julia> x0 = [CC(1.001), CC(0.999)];
julia> t = CC(0);
julia> A = compute_preconditioner(sys, x0, t);
julia> krawczyk_test(sys, x0, t, 1e-2, A)(true, 0.08567188563756645)
julia> krawczyk_test(sys, x0, t, 1e-3, A)(false, 0.999981977045536)

`compute_preconditioner`

CertifiedHomotopyTracking.compute_preconditioner — Function

compute_preconditioner(sys::SpecializedHomotopy, x, t)

Evaluate the Jacobian at the midpoint of (x, t) and return its inverse as the preconditioner used by Krawczyk tests.

source

`refine_moore_box`

CertifiedHomotopyTracking.refine_moore_box — Function

refine_moore_box(sys::SpecializedHomotopy, x, t, r_init, A_init; tau=0.125)
refine_moore_box(variety::AlgebraicVarietySystem, x, normal_radius; kwargs...)

Refine a Moore box until the corresponding Krawczyk test succeeds, or report failure.

The SpecializedHomotopy method is used internally by track_path. The AlgebraicVarietySystem method returns a VarietyBox for certifying local boxes on varieties.

Common variety options:

rank_tol=1e-10: local Jacobian rank threshold.
rho=1/8: Krawczyk threshold.
tau=0.125: initial shrink threshold.
min_radius=0, max_radius=1.0: radius bounds.
growth_factor=2.0, radius_shrink_factor=0.5: radius adjustment factors.
max_iter=20: maximum radius/refinement attempts.

source

julia> refined, radius, A_refined, success = refine_moore_box(sys, x0, t, 1e-4, A);
julia> successtrue
julia> refined2-element Vector{AcbFieldElem}:
 [1.00000099875149831418085849948919584232 +/- 1.63e-40]
 [1.00000000025000018758340810133298666347 +/- 2.05e-39]
julia> radius[0.0256000000000000012267964422107979771681 +/- 1.30e-41]
julia> krawczyk_test(sys, refined, t, radius, A_refined)(true, 0.11000186239834875)

`krawczyk_operator`

CertifiedHomotopyTracking.krawczyk_operator — Function

krawczyk_operator(system, point, r, A)

Compute the legacy polynomial-ring Krawczyk operator for system at point with radius r and preconditioner A.

For current SpecializedHomotopy-based code, prefer krawczyk_test.

source

References

[Kra69]: R. Krawczyk. Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing 4, 187–201 (1969).