We introduce monomial divisibility diagrams (MDDs), a data structure for monomial ideals that supports insertion of new generators and fast membership tests. MDDs stem from a canonical tree representation by maximally sharing equal subtrees, yielding a directed acyclic graph. We establish basic complexity bounds for membership and insertion, and study empirically the size of MDDs. As an application, we integrate MDDs into the signature Gröbner basis implementation of the Julia package AlgebraicSolving.jl. Membership tests in monomial ideals are used to detect some reductions to zero, and the use of MDDs leads to substantial speed-ups compared to the existing representation by lists of generators with divmasks.

Using validated numerical methods, interval arithmetic and Taylor models, we propose a certified predictor-corrector loop for tracking zeros of polynomial systems with a parameter. We provide a Rust implementation which shows tremendous improvement over existing software for certified path tracking.

No abstract available.

We describe a recursive algorithm that decomposes an algebraic set into locally closed equidimensional sets, i.e. sets which each have irreducible components of the same dimension. At the core of this algorithm, we combine ideas from the theory of triangular sets, a.k.a. regular chains, with Gröbner bases to encode and work with locally closed algebraic sets. Equipped with this, our algorithm avoids projections of the algebraic sets that are decomposed and certain genericity assumptions frequently made when decomposing polynomial systems, such as assumptions about Noether position. Thus our algorithm has a chance to produce fine decompositions on more structured systems where ensuring genericity assumptions often prohibits exploiting the structure of the system at hand. Practical experiments demonstrate its efficiency compared to state-of-the-art implementations.

Let V be the set of real common solutions to F = (f1, …, fs) in ℜ[x1, …;, xn] and D be the maximum total degree of the fi's. We design an algorithm which on input F computes the dimension of V. Letting L be the evaluation complexity of F and s=1, it runs using O∼ (L D n(d+3)+1) arithmetic operations in 𝒬 and at most Dn(d+1) isolations of real roots of polynomials of degree at most Dn.

Let S\subset \bR^n be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining S and an integer p\geq 0 and returns the n-dimensional volume of S at absolute precision 2^-p . Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations. The algorithm runs in essentially linear time with respect to~p. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in n and polynomial in the maximum degree of the input.

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets that works in weak exponential time. That is, of a set of exponentially small measure in the space of data, the cost of the algorithm is exponential in the size of the data. All algorithms previously proposed for this problem have a complexity that is doubly exponential (and this is so for almost all data).

Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.

Several algorithms in computer algebra involve the computation of a power series solution of a given ordinary differential equation. Over finite fields, the problem is often lifted in an approximate $p$-adic setting to be well-posed. This raises precision concerns: how much precision do we need on the input to compute the output accurately? In the case of ordinary differential equations with separation of variables, we make use of the recent technique of differential precision to obtain optimal bounds on the stability of the Newton iteration. The results apply, for example, to algorithms for manipulating algebraic numbers over finite fields, for computing isogenies between elliptic curves or for deterministically finding roots of polynomials in finite fields. The new bounds lead to significant speedups in practice.

Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is single exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.