LACE for Maple

The Maple package LACE computes, with certified results:

the real roots of univariate polynomials, isolated in intervals, with constraints or through a parameterization;
the Rational Univariate Representation (RUR) and the real solutions of zero-dimensional polynomial systems;
the resultant, the decomposition and the RUR of bivariate systems.

Its functions are exported by the module LACE, which is also available under the names RealSolving and RS4, so that code written for those packages runs unchanged. Maple’s own fgbrs package, used by RootFinding, is left untouched.

Installation

Download the archive LACE-Maple2026-Darwin_arm64.tar.gz, for Maple 2026 on macOS 12 or later, Apple silicon; other platforms and versions of Maple are not available yet. It holds a directory LACE with README.md and lib/ (LACE.mla, the Maple code and its help pages LACE.help, and liblace_mpl.so, the compiled library). It needs nothing but Maple: the arithmetic libraries GMP, MPFR and MPFI (LGPL) are included.

Quit Maple, then install the package as a Maple toolbox, in a terminal, from the directory that holds the archive:

mkdir -p ~/maple/toolbox/2026
tar -C ~/maple/toolbox/2026 -xzf LACE-Maple2026-Darwin_arm64.tar.gz
xattr -cr ~/maple/toolbox/2026/LACE

xattr removes the quarantine that macOS puts on files received from the Internet or by AirDrop; without it, Maple may be refused the library. Maple adds ~/maple/toolbox/2026/LACE/lib to libname, and reads the help pages, when it starts: start Maple and check:

LACE:-library();     # the file .../maple/toolbox/2026/LACE/lib/liblace_mpl.so
LACE:-backend();     # "native"
?LACE

To update, extract the new archive over the old one, in a closed Maple session. To uninstall, remove the directory ~/maple/toolbox/2026/LACE.

The archive must match the Maple that loads it: an archive for Maple 2026 does not load in another version of Maple.

Troubleshooting

LACE:-library() returns only a file name, or the first call fails with an error about an external library: the toolbox is not on libname. Check libname in a new session and the location of the directory LACE (the year in the path must be the version of Maple).
The library is found but refused: remove the quarantine with xattr -cr as above.
?LACE finds nothing: check that LACE.help is in ~/maple/toolbox/2026/LACE/lib, then quit Maple entirely and start it again; Maple reads the help databases when it starts.
The library can be taken elsewhere: LACEBinDir := "/some/dir": before the first call, or the environment variable MAPLELDPATH, take precedence over the toolbox.
Call LACE:-finish() before quit in scripts: Maple does not always release the objects held by the library at exit.

First steps

f := x^3 - 7*x + 6:
LACE:-rs_isolate_uni_classical(f, precision = 64);         # the roots -3, 1, 2 in intervals
LACE:-rur([x^2 + y^2 - 5, x - y - 1], [x, y]);             # a RUR of the system
LACE:-real_solutions([x^2 + y^2 - 5, x - y - 1], [x, y]);  # its two real solutions
with(LACE):                                                # the short names

Long computations can be interrupted as usual in Maple.

Conventions

Polynomials are ordinary Maple polynomials with rational coefficients; each one is scaled to integer coefficients by a positive factor before it is passed to the library.
An interval is a list [lo, hi] of rationals. Two equal bounds denote an exact value; otherwise the open interval contains exactly one root, neither bound being a root.
Intervals are returned in increasing order of the root (of the eliminant, for systems).
precision is a number of significant bits (a relative precision), except for descartes_isolate, where it is an absolute width.
threads is the number of workers; 0, the default, takes the library’s default: ACE_NB_THREADS (read when the library is loaded), else OMP_NUM_THREADS, else the performance cores of the machine.
Errors of the library are raised as Maple errors.

Module functions

function	effect
`LACE:-backend()`	the arithmetic the library was built with (`"native"`, `"flint"`)
`LACE:-library()`	the file the external functions are bound to
`LACE:-set_verbose(v)`	0: silent; 1: a summary of each computation; 2: details
`LACE:-reinit()`	initialises the library if needed
`LACE:-finish()`	releases the objects held by the library; call it before `quit`

Univariate polynomials

`rs_isolate_uni_classical`

LACE:-rs_isolate_uni_classical(f, precision = 2, intervalLeft = -infinity,
                               intervalRight = infinity, constraints = [],
                               verbose = 0, threads = 0, squarefree = false)

The real roots of the univariate polynomial f, each in an interval of precision significant bits. The square-free part of f is isolated unless squarefree = true says that f is square-free; a multiple root is returned once.

intervalLeft, intervalRight keep the roots of that range only (a root lying on a bound is returned as the point [q, q]).
constraints is a list of polynomials in the variable of f. The intervals are then such that each constraint has a constant sign on them, and the result is the pair [roots, values], values[i][j] an interval containing the value of constraint j at root i (the point [0, 0] when the constraint vanishes at that root).

f := x^3 - 7*x + 6:                                   # (x - 1)(x - 2)(x + 3)
LACE:-rs_isolate_uni_classical(f, precision = 64);    # three intervals, around -3, 1, 2
LACE:-rs_isolate_uni_classical(f, intervalLeft = 0, precision = 64);   # the roots 1 and 2
roots, vals := op(LACE:-rs_isolate_uni_classical(f, precision = 64,
                                                 constraints = [x - 1]));
# vals[i][1] encloses the value of x - 1 at root i; it is [0, 0] at x = 1

`descartes_isolate`

LACE:-descartes_isolate(f, precision = 16, threads = 0, squarefree = false)

The real roots of f by the Descartes method alone, in intervals with dyadic bounds of width at most 2^(-precision). It is the cheapest way to count the real roots of a polynomial.

nops(LACE:-descartes_isolate(x^3 - 7*x + 6));         # 3

`rs_isolate_rur`

LACE:-rs_isolate_rur(rext, rden, [num_1, ..., num_m], precision = 64,
                     exactinterval = FAIL, verbose = 0, threads = 0,
                     squarefree = false)

The real points of a parameterization in one variable T: rext(T) = 0, x_k = num_k(T) / rden(T), where rden is coprime with rext (a constant is allowed). The result has one element per real root of rext, the list of the intervals of x_1, ..., x_m, each with precision significant bits. exactinterval = [lo, hi] keeps only the root of rext that this interval isolates.

LACE:-rs_isolate_rur(T^2 - 2, 1, [T, T^2], precision = 64);
# two points: x_1 around -sqrt(2) and sqrt(2), x_2 an interval containing 2
LACE:-rs_isolate_rur(T^2 - 2, 1, [T, T^2], exactinterval = [1, 2]);
# the point with x_1 = sqrt(2) only

Zero-dimensional systems

`rur`

LACE:-rur(sys, vars, tvar = _T, sep = 0, strategy = 0, nbits = 28,
          maxprimes = 0, threads = 0)

The Rational Univariate Representation of a zero-dimensional system sys with rational coefficients in the variables vars. The Groebner bases are computed by the library. The result is a list of components

[f, g, [n_1, ..., n_n], tvar = form, mult]

with vars[k] = n_k(tvar) / g(tvar) at the roots of f(tvar), form the separating linear form in vars and mult the multiplicity. The result is [] when the system has no solution; a system that is not zero-dimensional raises an error.

option	meaning
`tvar`	the name of the parameter
`sep`	`0`: the library chooses the separating element; a name of `vars`, or its rank, imposes that variable
`strategy`	the search of the separating element: 0 sparse (default), 1 random, 2 variables only, 3 incremental
`nbits`	the primes are taken below `2^nbits`
`maxprimes`	the lifting fails beyond that many primes; 0: 200000

LACE:-rur([x^2 + y^2 - 5, x - y - 1], [x, y]);
# [[_T^2 + _T - 2, 2*_T + 1, [_T + 5, 2*_T^2 + _T], _T = y, 1]]

that is _T = y, _T^2 + _T - 2 = 0, x = (_T + 5) / (2 _T + 1): the points (2, 1) and (-1, -2).

When no variable separates the solutions, the form is a genuine linear combination:

R := LACE:-rur([x^2 - 1, y^2 - 1], [x, y]):
R[1][4];                                      # _T = -2*x + y

sep imposes a variable:

LACE:-rur([x^2 - 2, y - x - 1/3, z - x*y], [x, y, z], sep = z)[1][4];   # _T = z

`real_solutions`

LACE:-real_solutions(sys, vars, precision = 53, sep = 0, strategy = 0,
                     nbits = 28, maxprimes = 0, threads = 0)

The real solutions of the zero-dimensional system sys: one list of intervals [lo, hi] per solution, in the order of vars, each with precision significant bits; [] when there is none. The options are those of rur, which is computed first.

B := LACE:-real_solutions([x^2 + y^2 - 5, x - y - 1], [x, y], precision = 64):
nops(B);                                      # 2
map(s -> map(b -> evalf((b[1] + b[2]) / 2), s), B);
# [[-1., -2.], [2., 1.]]

Bivariate systems

The functions below take two polynomials p1, p2 in exactly two variables and the variable v1 to eliminate; the other variable, v2, is found from the polynomials. The polynomials in the results are polynomials in v2 (or in the parameter).

`bz_biv_resultant`

LACE:-bz_biv_resultant(p1, p2, v1, threads = 0)

The resultant of p1 and p2 with respect to v1, a polynomial in v2 (defined up to a constant factor).

`bz_biv_decomposition`

res, asymp, res_gen, res_non_gen := LACE:-bz_biv_decomposition(p1, p2, v1,
                                        nbits = 62, threads = 0)

The solutions split by level, the level k of a value u of v2 being the degree of gcd(p1(v1, u), p2(v1, u)). With S_k = s_0 + s_1 v1 + ... + s_k v1^k the subresultant of index k:

res: the resultant with respect to v1;
asymp: the polynomial of the values of v2 above which there are solutions at infinity, 1 when there are none;
res_gen[k] = [s_(k-1) + k s_k v1, univ]: at the roots of univ there is one solution, v1 being the root of the first polynomial, which is linear in v1;
res_non_gen[k] = [S_k, rest]: at the roots of rest, the values of v1 are the roots of S_k.

An empty component is [0, 0].

c := g^2 + o^2 - 1:
res, asymp, gen, nongen := LACE:-bz_biv_decomposition(c, diff(c, g), g):
# gen[1] = [2*g, o^2 - 1] up to constant factors: g = 0 above o = -1 and o = 1

bz_biv_is_generic(res_non_gen) is true when every non-generic component is empty; bz_biv_is_solved(res, res_gen, res_non_gen, v2) is true when, in addition, the generic components describe the solutions.

`bz_biv_rur`

LACE:-bz_biv_rur(p1, p2, v1, nbits = 62, threads = 0)

A RUR with parameter v2: a list of components [k, rext, rden, num_v1, num_v2], k the multiplicity, rext(v2) = 0, v1 = num_v1 / rden and num_v2 = v2 * rden. An error is raised when v2 does not separate the solutions; use bz_biv_rur_shear then.

`bz_biv_rur_shear`

LACE:-bz_biv_rur_shear(p1, p2, v1, tvar = _T, nbits = 62, threads = 0,
                       sep = 0, a = FAIL)

A RUR with parameter tvar = v2 + a v1, the integer a being chosen by the library. The result is [a, tvar, comps], each component [mult, rext, rden, num_v1, num_v2] with rext(tvar) = 0, v1 = num_v1 / rden, v2 = num_v2 / rden. a = 0 imposes tvar = v2; another imposed value of a is refused.

c2 := g^2 - o^3:
a, T, comps := op(LACE:-bz_biv_rur_shear(c2, diff(c2, g), g, tvar = _T)):

`bz_biv_decomposition_shear`

a, t, res, asymp, res_gen, res_non_gen :=
    LACE:-bz_biv_decomposition_shear(p1, p2, v1, a = FAIL, tvar = T,
                                     nbits = 62, threads = 0)

The decomposition in the coordinates (v1, t), v2 = t - a v1. Without an imposed a: when bz_biv_decomposition already solves the system, a = 0 and t = v2; otherwise a is the shear of bz_biv_rur_shear and t = tvar.