Public API

interval_classic_newton(sys::Vector{<:Union{AbstractAlgebra.Generic.MPoly, QQMPolyRingElem, ZZMPolyRingElem}}, 
                       initial_point::Vector{U}, 
                       input_precision::Int64=63, 
                       work_precision::Int64=63, 
                       target_precision::Int64=2, 
                       output_precision::Int64=2, 
                       max_nb_loops::Int64=10; 
                       verbose::Cint=Cint(1), flags::Integer=0) where {U<:Union{BigFloat,BigInterval}, T}

Performs the classical interval Newton method for solving a system of equations using AbstractAlgebra or Nemo polynomials.

Description

This function implements the classical interval Newton method through the following steps:

1. Input Processing:

   • Converts the polynomial system to a C-object with interval coefficients at specified input precision
   • Copies the initial point to C while preserving its original precision (BigFloat or BigInterval)

2. Solution Process:

   • Performs the Kantorovich test to verify conditions for solution existence and uniqueness
   • Executes the interval Newton method with the specified working precision
   • Iteratively refines the solution until target precision is reached or max iterations exceeded

3. Output:

   • Returns a tuple containing:
     • Status code indicating success or failure
     • Solution intervals rounded to output precision
     • Kantorovich test constants

Arguments

• sys::Vector: A vector of polynomials from AbstractAlgebra or Nemo representing the system of equations
• initial_point::Vector{U}: Starting point for the Newton method, where U is either BigFloat or BigInterval
• input_precision::Int64: Precision (in bits) for input polynomial coefficients. Default is 63
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision (interval length of 2^(-target_precision)). Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• verbose::Cint: Verbosity level for logging. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Tuple (status, solution, constants) where:

• status::Int: Result code (0: singular Jacobian, 1: solution found, 2: max precision reached, 3: max iterations reached)
• solution::Vector{BigInterval}: Computed solution intervals
• constants::Tuple: Kantorovich test constants

interval_classic_newton(f::Union{AbstractAlgebra.Generic.MPoly, QQMPolyRingElem, ZZMPolyRingElem},
                       initial_point::U,
                       input_precision::Int64=63,
                       work_precision::Int64=63,
                       target_precision::Int64=2,
                       output_precision::Int64=2,
                       max_nb_loops::Int64=10;
                       verbose::Cint=Cint(1), flags::Integer=0) where {U<:Union{BigFloat,BigInterval},T}

Single equation version of interval Newton method for AbstractAlgebra or Nemo polynomials.

Arguments

• f: A single polynomial from AbstractAlgebra or Nemo
• initial_point::U: Starting point (BigFloat or BigInterval)
• Other arguments as above

Returns

Same as above, but for a single equation

interval_classic_newton(sys::Vector{DynamicPolynomials.Polynomial{T, U, BigInterval}},
                       initial_point::Vector{V},
                       work_precision::Int64=63,
                       target_precision::Int64=2,
                       output_precision::Int64=2,
                       max_nb_loops::Int64=10;
                       verbose::Cint=Cint(1), flags::Integer=0) where {V<:Union{BigFloat,BigInterval}, T, U}

Performs the classical interval Newton method for a system of DynamicPolynomials.

Description

This function implements the same classical interval Newton method as above, with one key difference:

• The system is already in interval form (DynamicPolynomials with BigInterval coefficients)
• No input precision parameter is needed as the system is copied with the maximum precision of its coefficients

Arguments

• sys::Vector: A vector of DynamicPolynomials with BigInterval coefficients
• initial_point::Vector{V}: Starting point (BigFloat or BigInterval)
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision. Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• verbose::Cint: Verbosity level. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Same as above

interval_classic_newton(f::DynamicPolynomials.Polynomial{T, U, BigInterval},
                       initial_point::V,
                       work_precision::Int64=63,
                       target_precision::Int64=2,
                       output_precision::Int64=2,
                       max_nb_loops::Int64=10;
                       verbose::Cint=Cint(1), flags::Integer=0) where {V<:Union{BigFloat,BigInterval}, T, U}

Single equation version of interval Newton method for DynamicPolynomials.

Arguments

• f: A single DynamicPolynomial with BigInterval coefficients
• initial_point::V: Starting point (BigFloat or BigInterval)
• Other arguments as above

Returns

Same as above, but for a single equation

interval_classic_newton(sys_ptr::Ptr{Cvoid},
                       initial_point::Vector{T},
                       work_precision::Int64=63,
                       target_precision::Int64=2,
                       output_precision::Int64=2,
                       max_nb_loops::Int64=10;
                       verbose::Cint=Cint(1), flags::Integer=0) where {T<:Union{BigFloat,BigInterval}}

Low-level version of the classical interval Newton method that works directly with C pointers.

Arguments

• sys_ptr::Ptr{Cvoid}: A C pointer to the polynomial system (typically obtained from sys_get_C_ptr)
• initial_point::Vector{T}: Starting point (BigFloat or BigInterval)
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision. Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• verbose::Cint: Verbosity level. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Tuple (status, solution, constants) where:

• status::Int: Result code (0: singular Jacobian, 1: solution found, 2: max precision reached, 3: max iterations reached)
• solution::Vector{BigInterval}: Computed solution intervals
• constants::Tuple: Kantorovich test constants

Notes

• This is an internal function that should typically be called through the higher-level interfaces
• The system pointer must be properly initialized using sys_get_C_ptr

Examples

# Using AbstractAlgebra
using AbstractAlgebra
R, (x,y) = polynomial_ring(QQ, ["x", "y"])
f = x^2 + y^2 - 1
g = x - y
sys = [f, g]
initial = [BigFloat(0.5), BigFloat(0.5)]
status, sol, consts = LACE.interval_classic_newton(sys, initial)

# Using DynamicPolynomials
using DynamicPolynomials, MPFI
@polyvar x y
f = BigInterval(1)*x^2 + BigInterval(1)*y^2 - BigInterval(1.0, 1.1)
g = x - y
sys = [f, g]
initial = [BigInterval(0.5), BigInterval(0.5)]
status, sol, consts = LACE.interval_classic_newton(sys, initial)

interval_newton(sys::Vector{<:Union{AbstractAlgebra.Generic.MPoly, QQMPolyRingElem, ZZMPolyRingElem}}, 
                initial_point::Vector{W}, 
                input_precision::Int64=63, 
                work_precision::Int64=63, 
                target_precision::Int64=2, 
                output_precision::Int64=2, 
                max_nb_loops::Int64=10;
                refine::Int32=Int32(1), 
                verbose::Cint=Cint(1), flags::Integer=0) where {W<:Union{BigFloat,BigInterval}, T}

Performs the interval Newton method for solving a system of equations using AbstractAlgebra or Nemo polynomials. The refinement strategy (controlled by refine) affects how the method handles successive iterations:

• With refine=1, the method always takes intersections, which is appropriate when the initial interval is known to contain the solution
• With refine=0, the method uses a heuristic approach that only performs intersection when the new solution interval contains the center of the previous interval.

Description

This function implements the standard interval Newton method through the following steps:

1. Input Processing:

   • Converts the polynomial system to a C-object with interval coefficients at specified input precision
   • Copies the initial point to C while preserving its original precision (BigFloat or BigInterval)

2. Solution Process:

   • Performs the Kantorovich test to verify conditions for solution existence and uniqueness
   • Executes the interval Newton method with intersection operations between iterations
   • Iteratively refines the solution until target precision is reached or max iterations exceeded

3. Output:

   • Returns a tuple containing:
     • Status code indicating success or failure
     • Solution intervals rounded to output precision
     • Kantorovich test constants

Arguments

• sys::Vector: A vector of polynomials from AbstractAlgebra or Nemo representing the system of equations
• initial_point::Vector{W}: Starting point for the Newton method, where W is either BigFloat or BigInterval
• input_precision::Int64: Precision (in bits) for input polynomial coefficients. Default is 63
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision (interval length of 2^(-target_precision)). Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• refine::Int32: Flag to control refinement behavior. Default is 1
• verbose::Cint: Verbosity level for logging. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Tuple (status, solution, constants) where:

• status::Int: Result code (0: singular Jacobian, 1: solution found, 2: max precision reached, 3: max iterations reached)
• solution::Vector{BigInterval}: Computed solution intervals
• constants::Tuple: Kantorovich test constants

interval_newton(f::Union{AbstractAlgebra.Generic.MPoly, QQMPolyRingElem, ZZMPolyRingElem},
                initial_point::W,
                input_precision::Int64=63,
                work_precision::Int64=63,
                target_precision::Int64=2,
                output_precision::Int64=2,
                max_nb_loops::Int64=10;
                refine::Int32=Int32(1),
                verbose::Cint=Cint(1), flags::Integer=0) where {W<:Union{BigFloat,BigInterval},T}

Single equation version of interval Newton method for AbstractAlgebra or Nemo polynomials.

Arguments

• f: A single polynomial from AbstractAlgebra or Nemo
• initial_point::W: Starting point (BigFloat or BigInterval)
• Other arguments as above

Returns

Same as above, but for a single equation

interval_newton(sys::Vector{DynamicPolynomials.Polynomial{T, U, BigInterval}},
                initial_point::Vector{V},
                work_precision::Int64=63,
                target_precision::Int64=2,
                output_precision::Int64=2,
                max_nb_loops::Int64=10;
                refine::Int32=Int32(1),
                verbose::Cint=Cint(1), flags::Integer=0) where {V<:Union{BigFloat,BigInterval}, T, U}

Performs the standard interval Newton method for a system of DynamicPolynomials.

Description

This function implements the same standard interval Newton method as above, with one key difference:

• The system is already in interval form (DynamicPolynomials with BigInterval coefficients)
• No input precision parameter is needed as the system is copied with the maximum precision of its coefficients

Arguments

• sys::Vector: A vector of DynamicPolynomials with BigInterval coefficients
• initial_point::Vector{V}: Starting point (BigFloat or BigInterval)
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision. Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• refine::Int32: Flag to control refinement behavior. Default is 1
• verbose::Cint: Verbosity level. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Same as above

interval_newton(f::DynamicPolynomials.Polynomial{T, U, BigInterval},
                initial_point::V,
                work_precision::Int64=63,
                target_precision::Int64=2,
                output_precision::Int64=2,
                max_nb_loops::Int64=10;
                refine::Int32=Int32(1),
                verbose::Cint=Cint(1), flags::Integer=0) where {V<:Union{BigFloat,BigInterval}, T, U}

Single equation version of interval Newton method for DynamicPolynomials.

Arguments

• f: A single DynamicPolynomial with BigInterval coefficients
• initial_point::V: Starting point (BigFloat or BigInterval)
• Other arguments as above

Returns

Same as above, but for a single equation

interval_newton(sys_ptr::Ptr{Cvoid},
                initial_point::Vector{T},
                work_precision::Int64=63,
                target_precision::Int64=2,
                output_precision::Int64=2,
                max_nb_loops::Int64=10,
                refine::Int32=Int32(1);
                verbose::Cint=Cint(1), flags::Integer=0) where {T<:Union{BigFloat,BigInterval}}

Low-level version of the standard interval Newton method that works directly with C pointers.

Arguments

• sys_ptr::Ptr{Cvoid}: A C pointer to the polynomial system (typically obtained from sys_get_C_ptr)
• initial_point::Vector{T}: Starting point (BigFloat or BigInterval)
• work_precision::Int64: Precision for intermediate calculations. Default is 63
• target_precision::Int64: Desired solution precision. Default is 2
• output_precision::Int64: Precision for rounding final result. Default is 2
• max_nb_loops::Int64: Maximum number of iterations. Default is 10
• refine::Int32: Flag to control refinement behavior. Default is 1
• verbose::Cint: Verbosity level. Default is 1
• flags::Integer: Strategies of the Kantorovich test, a sum of KANTO_HESSIAN, KANTO_PRECOND, KANTO_SCHULZ; 0 is the classical test. Default is 0

Returns

Tuple (status, solution, constants) where:

• status::Int: Result code (0: singular Jacobian, 1: solution found, 2: max precision reached, 3: max iterations reached)
• solution::Vector{BigInterval}: Computed solution intervals
• constants::Tuple: Kantorovich test constants

Notes

• This is an internal function that should typically be called through the higher-level interfaces
• The system pointer must be properly initialized using sys_get_C_ptr

Examples

# Using AbstractAlgebra
using AbstractAlgebra
R, (x,y) = polynomial_ring(QQ, ["x", "y"])
f = x^2 + y^2 - 1
g = x - y
sys = [f, g]
initial = [BigFloat(0.5), BigFloat(0.5)]
status, sol, consts = LACE.interval_newton(sys, initial)

# Using DynamicPolynomials
using DynamicPolynomials, MPFI
@polyvar x y
f = BigInterval(1)*x^2 + BigInterval(1)*y^2 - BigInterval(1.0, 1.1)
g = x - y
sys = [f, g]
initial = [BigInterval(0.5), BigInterval(0.5)]
status, sol, consts = LACE.interval_newton(sys, initial)

kantorovich_test(sys::Union{Vector{AbstractAlgebra.Generic.MPoly{T}}, Vector{DynamicPolynomials.Polynomial{T, U, V}}},
                 initial_point::Vector{W},
                 work_precision::Int64=63,
                 output_precision::Int64=2;
                 verb::Cint=1) where {W<:Union{BigFloat, BigInterval}, T, U, V} -> Vector{BigInterval}

The constants of the Kantorovich test of the polynomial system sys at initial_point (BigFloat or BigInterval entries), which certifies the existence and uniqueness of a root in a ball around that point: [2B0, C], the radius 2B0 of the ball and the constant C (certified when C <= 1), with output_precision bits. work_precision is the precision (bits) of the computation, verb the verbosity. A wrapper for LACE.kantorovich_test, which also takes the keyword flags.

kantorovich_test(f::Union{AbstractAlgebra.Generic.MPoly{T}, DynamicPolynomials.Polynomial{T, U, V}},
                 initial_point::W,
                 work_precision::Int64=63,
                 output_precision::Int64=2;
                 verb::Cint=1) where {W<:Union{BigFloat, BigInterval}, T, U, V} -> Vector{BigInterval}

The same for the single polynomial f at the point initial_point.

evaluate(f::Union{DynamicPolynomials.Polynomial{T, U, V}, AbstractAlgebra.Generic.MPoly{T}},
         eval_point::Union{BigFloat, BigInterval};
         precision::Integer=Int64(24)) where {T, U, V} -> BigInterval

An enclosure of the univariate polynomial f (DynamicPolynomials.Polynomial or AbstractAlgebra.Generic.MPoly in one variable) at eval_point, a BigFloat or a BigInterval, computed and returned with precision bits. A wrapper for LACE.pol_uni_eval.

evaluate(sys::Union{Vector{AbstractAlgebra.Generic.MPoly{T}}, Vector{DynamicPolynomials.Polynomial{T, U, V}}},
         eval_point::Vector{W};
         precision::Integer=Int64(24)) where {W<:Union{BigFloat, BigInterval}, T, U, V} -> Vector{BigInterval}

Enclosures of the multivariate polynomials sys (AbstractAlgebra.Generic.MPoly or DynamicPolynomials.Polynomial) at the point eval_point (BigFloat or BigInterval coordinates, one per variable), one per polynomial, computed and returned with precision bits. A wrapper for LACE.sys_eval.

zdim_parameterization(sys; get_separating_element = false, multiplicities = false, verbose = true, kwargs...)

The Rational Univariate Representation of a zero-dimensional system sys (over Q, Z or GF(p)): the eliminant f(T), then one numerator per variable, x_k = g_k(T) / f'(T) at the roots of f, all as coefficient vectors from the constant term; with get_separating_element = true, the pair (rur, sep), sep the separating linear form.

With multiplicities = true the multiplicities of the solutions are computed as well and the result is (rur, mult), or (rur, sep, mult): mult is a vector of pairs j => h_j, h_j the monic polynomial whose roots are the values of the separating form at the solutions of multiplicity j; the RUR itself does not change. Both implementations take this keyword.

Computed by LACE.jl or by RationalUnivariateRepresentation.jl according to rur_backend(); the keywords are passed on (see LACE.zdim_parameterization and RationalUnivariateRepresentation.zdim_parameterization).

rur_backend() -> Symbol

The implementation zdim_parameterization calls: :lace, LACE.jl (the default), or :julia, RationalUnivariateRepresentation.jl.

rur_backend!(b::Symbol) -> Symbol

Choose the implementation of zdim_parameterization:

• :lace (the default): LACE.jl, everything in its C library, the Groebner bases included; LACE.gb_backend!(:groebner) makes it take its Groebner bases from Groebner.jl;
• :julia: RationalUnivariateRepresentation.jl, written in Julia.

The environment variable PACE_RUR (lace or julia), read when PACE is loaded, does the same.

discriminant_variety(sys, vars, params; kwargs...) -> Vector{Vector}

A discriminant variety of the system sys of K[params][vars], generically zero-dimensional in vars (K the rationals or a prime field): the elimination ideal <sys, det(Jacobian w.r.t. vars)> ∩ K[params] and, for each variable of vars, the leading coefficients of the elements of a Groebner basis for DRL(vars) > DRL(params) whose leading monomial in vars is a pure power of that variable; the constant components removed, the components given by one polynomial split into irreducible factors. An error is raised if sys is not generically zero-dimensional in vars.

With dv_backend() == :lace, the ideals at infinity are computed by LACE.w_infty, the elimination ideal of the system and the Jacobian determinant by LACE.elim, and the components by DiscriminantVariety.postprocess; with :julia, DiscriminantVariety.jl computes everything. The keywords are passed on (threads for LACE.jl, batch for DiscriminantVariety.jl).

eliminate(sys, vars; kwargs...) -> Vector

The reduced Groebner basis of the elimination ideal <sys> ∩ K[params], the parameters being the other variables of the ring. Computed by LACE.jl (LACE.elim, primitive integer polynomials) or by DiscriminantVariety.jl according to dv_backend(); the keywords are passed on.

dv_backend() -> Symbol

The implementation discriminant_variety and eliminate call over the rationals: :lace (the default), the elimination ideals and ideals at infinity of LACE.jl, or :julia, DiscriminantVariety.jl.

dv_backend!(b::Symbol) -> Symbol

Choose the implementation of discriminant_variety and eliminate over the rationals:

• :lace (the default): the elimination ideals (LACE.elim) and the ideals at infinity (LACE.w_infty) computed in the C library of LACE.jl, the discriminant variety assembled from them by PACE.jl, its components given by DiscriminantVariety.postprocess;
• :julia: DiscriminantVariety.jl alone, written in Julia.

Over a prime field, DiscriminantVariety.jl computes them in both cases. The environment variable PACE_DV (lace or julia), read when PACE is loaded, does the same.

isolate(f::Vector; output_precision = 2, constraints = [], constraint_values = false,
        ensure_derivative_nonzero = false, search_interval = nothing)
isolate(sys::Vector{<:MPolyRingElem}, vars::Vector{Symbol}; output_precision = 2)
isolate(rur::Vector{Vector{Rational{BigInt}}}, sep; output_precision = 2)
isolate(ext::Vector{BigInt}, den::Vector{BigInt}, nums::Vector{Vector{BigInt}}, sep; output_precision = 2)

Isolates the real roots of a univariate polynomial (integer or rational coefficients, from the constant term), of a zero-dimensional polynomial system over Q, or of a rational parameterization (in the format of zdim_parameterization, or as integer eliminant / denominator / numerators). A wrapper for LACE.rs_isolate.

Every solution is a vector of BigInterval boxes of output_precision significant bits, one per coordinate (a single one for a univariate polynomial). For a univariate polynomial, constraints are polynomials whose sign is made constant on every box (constraint_values = true also returns their enclosures), ensure_derivative_nonzero adds the derivative to them (rational coefficients only), and search_interval = (l, r) restricts the isolation to [l, r]. threads (0 by default: the library's default, one per performance core) sets the number of workers. A failure raises an exception.

See also

LACE.rs_isolate, LACE.real_solutions

tci_points(icurve, vars::Vector{Symbol}, ym, yM, xm, xM, nb::Integer, prec::Integer; verbose = 0, threads = 0)

Points of the plane curve icurve(vars[1], vars[2]) = 0 (a bivariate polynomial with integer or rational coefficients) in the box where vars[1] lies in [ym, yM] and vars[2] in [xm, xM]: for nb values of each variable across the box, the roots in the other variable, refined to the size of a pixel. Returns (a, o), the coordinates of the points along vars[1] and along vars[2]. prec is accepted and ignored. A wrapper for LACE.rs_tci_points.

isolate_complex_roots_sqrfree_poly(args...; kwargs...)

A wrapper function for PWPoly.isolate_roots that isolates the complex roots of a square-free polynomial with integer coefficients.

See also

PACE.PWPoly.isolate_roots

isolate_complex_roots_complex_sqrfree_poly(args...; kwargs...)

A wrapper function for PWPoly.isolate_roots_complex that isolates the complex roots of a square-free polynomial with complex integer coefficients.

See also

PACE.PWPoly.isolate_roots_complex

approximate_roots(args...; kwargs...)

A wrapper function for PWPoly.approximate_roots that approximates the complex roots of a polynomial with integer coefficients (not necessarily square-free).

See also

PACE.PWPoly.approximate_roots

approximate_roots_complex_poly(args...; kwargs...)

A wrapper function for PWPoly.approximate_roots_complex that approximates the complex roots of a polynomial with complex integer coefficients (not necessarily square-free).

See also

PACE.PWPoly.approximate_roots_complex

refine_complex_roots(args...; kwargs...)

A wrapper function for PWPoly.refine_roots that refines roots of a real polynomial in a bounded domain with known root count.

See also

PACE.PWPoly.refine_roots

refine_complex_roots_complex_poly(args...; kwargs...)

A wrapper function for PWPoly.refine_roots_complex that refines roots of a complex polynomial in a bounded domain with known root count.

See also

PACE.PWPoly.refine_roots_complex

evaluate_at_complex_points(args...; kwargs...)

A wrapper function for PWPoly.evaluate_polynomial that evaluates a polynomial with rational or integer coefficients at complex points.

See also

PACE.PWPoly.evaluate_polynomial

evaluate_at_complex_points_complex_poly(args...; kwargs...)

A wrapper function for PWPoly.evaluate_polynomial_complex that evaluates a polynomial with complex rational or integer coefficients at complex points.

See also

PACE.PWPoly.evaluate_polynomial_complex

curve_topology(C; verbose::Bool = false) -> CurveTopology.Topology

The certified topology of the real plane curve C(x, y) = 0: a graph isotopic to the curve, its critical points and the branches at each of them, its vertical lines. C is a polynomial in two variables with integer or rational coefficients (AbstractAlgebra, Nemo or DynamicPolynomials, the first variable being x), or a string in x and y such as "(x^2+y^2)^2 - 2*(x^2-y^2)". verbose prints the steps of the computation with their times. A wrapper for CurveTopology.topology.

curve_complement(T::CurveTopology.Topology) -> Vector{CurveTopology.ComplementComponent}

The connected components of the complement of the curve of T in the plane, each with a rational sample point, the sign of the polynomial there, whether it is bounded, its boundary and its neighbours. A wrapper for CurveTopology.complement.

curve_drawing(T::CurveTopology.Topology; window = nothing, pixels = (800, 800),
              verbose) -> CurveTopology.Drawing

A certified drawing of the curve of T in the window (xmin, xmax, ymin, ymax) (by default, a window holding the critical points) for an image of pixels = (W, H) pixels; verbose defaults to that of the last curve_topology call. A wrapper for CurveTopology.drawing.

write_curve_svg(path, T::CurveTopology.Topology, D::CurveTopology.Drawing,
                K = curve_complement(T); title) -> path

Writes the drawing D of the curve of T as an SVG file, the components of the complement K filled with one colour each; title defaults to the polynomial. A wrapper for CurveTopology.write_svg.

compute_system_solutions_from_rur(sys::Vector, 
                                target_precision::Int64=8;
                                verbose::Bool=false,
                                parallel::Bool=false,
                                refine::Cint=Cint(1))

Compute the solutions of a polynomial system using Rational Univariate Representation (RUR). The function first computes the RUR, then isolates the roots of the first polynomial, and finally finds the complete system solutions by evaluating the remaining RUR polynomials.

Arguments

• sys::Vector: A vector of polynomials representing the system of equations
• target_precision::Int64: The target precision in bits for the mantissa of the solutions (default: 8)
• verbose::Bool: Whether to print progress information during computation (default: false)
• parallel::Bool: Whether to use parallel computation when possible (default: false)
• refine::Cint: Controls the refinement strategy (default: 1)
  • 1: Perform refinement using interval Newton method
  • 0: No refinement

Returns

A vector of solutions to the polynomial system, where each solution is represented by intervals.

Notes

The computation follows these steps:

1. Computes the RUR and separating element with zdim_parameterization (see rur_backend!)
2. Isolates the roots of the first RUR polynomial using LACE.jl
3. Evaluates the remaining RUR polynomials using LACE.jl to obtain the complete system solutions

compute_system_solutions_from_rur(rur::Vector{Vector{Rational{BigInt}}}, 
                                sep::Vector{Int64},
                                target_precision::Int64=8;
                                verbose::Bool=false,
                                parallel::Bool=false,
                                refine::Cint=Cint(1))

Compute the solutions of a polynomial system using a pre-computed Rational Univariate Representation (RUR). The function takes the RUR and separating element as input, computes the roots of the first RUR polynomial, and then finds the complete system solutions by evaluating the remaining RUR polynomials.

Arguments

• rur::Vector{Vector{Rational{BigInt}}}: The pre-computed RUR polynomials
• sep::Vector{Int64}: The pre-computed separating element
• target_precision::Int64: The target precision in bits for the mantissa of the solutions (default: 8)
• verbose::Bool: Whether to print progress information during computation (default: false)
• parallel::Bool: Whether to use parallel computation when possible (default: false)
• refine::Cint: Controls the refinement strategy (default: 1)
  • 1: Perform refinement using interval Newton method
  • 0: No refinement

Returns

A vector of solutions to the polynomial system, where each solution is represented by intervals.

Notes

This variant skips the RUR computation step and proceeds directly to:

1. Isolating the roots of the first RUR polynomial using LACE.jl
2. Evaluating the remaining RUR polynomials using LACE.jl to obtain the complete system solutions

solve_system_in_extension_field(sys1, sys2, work_precision; rat_precision = work_precision,
                                max_iters = 10, parallel = false, all_sols1 = false,
                                all_sols2 = false, certify = true)

Solves sys1 (in the variables of its ring), then sys2 (in the variables of its ring, those of sys1 last) above each solution of sys1: sys2 is solved by a RUR at rational approximations (rat_precision bits) of the solutions of sys1, then, when certify, each Hurwitz stable solution is certified by interval Newton (Kantorovich test first) on sys2 specialised at the interval solutions of sys1.

With all_sols1 = false only the solution of sys1 with the largest last coordinate is kept; with all_sols2 = false the result is the Hurwitz stable solution with the smallest first coordinate gamma^2, returned as [[[gamma, ...]]]. Returns (sols1, sols2).

solve_pos_dim_system_in_extension_field(sys1, sys2_e, e_val, work_precision; kwargs...)

solve_system_in_extension_field for a system sys2_e whose first equation involves a parameter, the second variable of its ring: the approximate solutions are computed with the parameter set to e_val, the certification with the parameter set to 0. Same keywords and result.

partial_CAD(polynomials::Vector) -> Vector

Sample points with rational coordinates of the cells of a partial Cylindrical Algebraic Decomposition (CAD) adapted to the multivariate Nemo polynomials polynomials (rational coefficients): the projection keeps the leading and trailing coefficients, the discriminants and the pairwise resultants with respect to the last variable, down to one variable; the lifting takes one rational point in each gap between the isolated roots (and one beyond each end). Each point is a vector of coordinates in the order of the variables.

Example

_, (x, y) = Nemo.polynomial_ring(Nemo.QQ, ["x", "y"])

# Define a system of polynomials
f1 = x - 3
f2 = x^2 + y^2 - 2
polys = [f1, f2]

# Get sample points from the CAD cells
sample_points = partial_CAD(polys)

isolate_non_overlapping(sres0_sqrfree, all_factors; starting_precision::Int32 = Int32(2))
    -> (sres0_roots, roots, idx)

The real roots of the square-free univariate polynomial sres0_sqrfree and of the polynomials all_factors (Nemo, rational coefficients), isolated by isolate with an output precision increased by one bit from starting_precision until no box of a root of sres0_sqrfree meets a box of a root of a factor. sres0_roots are the boxes of sres0_sqrfree, roots those of the factors all_factors[idx], the ones isolated at the last precision.

isolate_non_overlapping(all_factors) -> Vector{BigInterval}

The real roots of the non-constant polynomials all_factors (Nemo, rational coefficients), as pairwise disjoint closed boxes sorted by their left bound: the roots of the square-free part of their product, isolated by LACE. starting_precision is accepted and ignored.

rationals_in_between(sep::BigFloat, intervals::Vector) -> Vector

Sample points around and between sorted disjoint intervals: lo_1 - sep, then for each gap [hi_i, lo_(i+1)] its midpoint (as a Rational{BigInt}), then hi_n + sep; [sep] when intervals is empty. The intervals are BigIntervals, or, for the second method, [[lo, hi]] vectors of BigFloat.

subresultants(p, q) -> Vector

The subresultant sequence of the univariate polynomials p and q (same parent), by Ducos' algorithm: [p, q, S..., r], p and q ordered by decreasing degree, then the subresultants the algorithm computes, by decreasing degree, and last r, the resultant of p and q as a constant polynomial (zero when they have a common factor). [p, q] when the one of lower degree is a constant; [0] when one of them is zero.

signed_subresultants(p, q) -> Vector

The nonzero signed subresultants of p and p' q (p' the derivative of p), whose sign variations give the Tarski query of q on the real roots of p: [p, p' q, ...], the further terms being those of subresultants(p, p' q), the term of index j multiplied by (-1)^((v-j)(v-j+1)/2), v = deg(p' q).

subresultant_coefs(p, q) -> Vector

The leading coefficients of subresultants(p, q).

signed_subresultant_coefs(p, q) -> Vector

The leading coefficients of signed_subresultants(p, q).

sign_variation(seq, seq_signs, seq_not_factored, params...) -> Int

V(-∞) - V(+∞), where V(±∞) is the number of sign variations (zeros skipped) at ±∞ of a sequence of univariate polynomials whose leading coefficients depend on parameters; for a Sturm or signed subresultant sequence it counts real roots. The i-th polynomial is seq_not_factored[i] (its degree gives the sign at ±∞), its leading coefficient is given factored, seq[i] the list of pairs (factor, multiplicity) and seq_signs[i] the sign of the remaining unit. The factors are evaluated at params... (rationals, or BigIntervals: a factor whose sign is not constant on the box counts as zero); without params they are constants.

lienard_chipart(p) -> (coefs, sres)

The two sequences whose signs the Liénard-Chipart criterion examines for the univariate polynomial p: coefs the coefficients of p (constant term first) and sres the principal signed subresultant coefficients signed_subresultant_coefs(x G, F) when deg p is odd, signed_subresultant_coefs(F, G) otherwise, where p(x) = F(x^2) + x G(x^2) (F, G in the ring of p).

hurwitz_stable(H::Matrix, sign_lc::Int) -> Int

Routh-Hurwitz criterion on the Hurwitz matrix H of a polynomial whose leading coefficient has sign sign_lc ($\pm 1$): the polynomial is stable when every leading principal minor $\Delta_k$, multiplied by sign_lc when $k$ is odd, is positive. Returns 1 (stable), -1 (some $\Delta_k$ has the wrong sign: unstable) or 0 (no wrong sign but some $\Delta_k = 0$: a root on the imaginary axis or a pair of roots symmetric about the origin; not stable).

hurwitz_stable(coefs::Vector{T}) -> Int

Hurwitz stability of the polynomial of coefficients coefs, highest degree first: 1 when every root has a negative real part, -1 when some root has a positive real part, 0 when some leading principal minor of the Hurwitz matrix vanishes (not stable). Exact for integer and rational coefficients.

hurwitz_stable([1, 3, 3, 1])      # (s + 1)^3: 1
hurwitz_stable([-1, -3, -3, -1])  # -(s + 1)^3: 1
hurwitz_stable([1, 1, -1, -1])    # (s - 1)(s + 1)^2: -1
hurwitz_stable([1, 0, 1])         # s^2 + 1: 0

hurwitz_stable(coefs::Vector{BigInterval}) -> Bool

Kharitonov's theorem: the interval polynomial of coefficients coefs (highest degree first) is Hurwitz stable for every choice of its coefficients in their intervals if and only if its four Kharitonov polynomials are. From the constant term upwards, with l and r the left and right ends of each coefficient, they follow the patterns l l r r, l r r l, r l l r and r r l l, repeated every four powers.

hurwitz_stable_routh(coefs::Vector{BigInterval}) -> Bool

The Routh-Hurwitz criterion applied directly to the interval coefficients coefs (highest degree first), in interval arithmetic: true only when every minor is certified with the right sign.

hurwitz_matrix(coefs::Vector{T}) -> Matrix{T}

The $n \times n$ Hurwitz matrix of the polynomial of degree $n$ whose coefficients coefs are given highest degree first (coefs[1] is the leading coefficient): H[d+1, k+1] = coefs[2d - k + 2], zero outside the vector. It is the transpose of the usual layout, which leaves its leading principal minors unchanged.

leading_principal_minors(M) -> Vector

The leading principal minors $\Delta_1, \dots, \Delta_n$ of the square matrix M. Over the integers and the rationals they are the pivots of a fraction-free (Bareiss) elimination without row exchange, $O(n^3)$ exact operations; a zero pivot, or any other coefficient type, falls back to one determinant per minor.

min_hurwitz_solution(sols) -> Int

The index of the solution s of sols with the smallest first coordinate among those whose other coordinates s[2:end] are, with a leading 1, the coefficients (constant term last) of a Hurwitz stable polynomial; 0 when there is none.