We study the problem of computing the isolated regular solutions of a system (f1, …, fn) of n polynomial equations in n variables (X1, …, Xn) over a field of characteristic zero k. We focus on systems with a composable structure, where each polynomial fi can be expressed as a composition fi = hi(g1, …, gn). Exploiting this structure allows us to reduce the original system to one in the gj variables, thereby significantly improving the efficiency of symbolic solution algorithms. We present a probabilistic algorithm that computes all isolated regular solutions, with arithmetic complexity being polynomial in the input size and in the number of solutions.

Let \(\mathcal {R}= \mathbb {K}[x_1, \dots , x_n]\) be a multivariate polynomial ring over a field \(\mathbb {K}\) of characteristic 0. Consider n algebraically independent elements g1, …, gn in \(\mathcal {R}\). Let \(\mathcal {S}\) denote the subring of \(\mathcal {R}\) generated by g1, …, gn, and let h be an element of \(\mathcal {S}\). Then, there exists a unique element \({f} \in \mathbb {K}[u_1, \dots , u_n]\) such that h = f(g1, …, gn). In this paper, we provide an algorithm for computing f, given h and g1, …, gn. The complexity of our algorithm is linear in the size of the input, h and g1, …, gn, and polynomial in n when the degree of f is fixed. Previous works are mostly known when f is a symmetric polynomial and g1, …, gn are elementary symmetric, homogeneous symmetric, or power symmetric polynomials.

A semi-algebraic set is a subset of the real space defined by polynomial equations and inequalities. In this paper, we consider the problem of deciding whether two given points in a semi-algebraic set are connected. We restrict to the case when all equations and inequalities are invariant under the action of the symmetric group and of degree at most d < n, where n is the number of variables. Additionally, we assume that the two points are in the same fundamental domain of the action of the symmetric group, by assuming that the coordinates of two given points are sorted in non-decreasing order. We construct and analyze an algorithm that solves this problem, by taking advantage of the group action, and has a complexity being polynomial in n.

In this paper, we consider the problem of deciding the existence of real solutions to a system of polynomial equations having real coefficients, and which are invariant under the action of the symmetric group. We construct and analyze a Monte Carlo probabilistic algorithm which solves this problem, under some regularity assumptions on the input, by taking advantage of the symmetry invariance property.

Consider a matrix F ε K [x]^mxn of univariate polynomials over a field K. We study the problem of computing the column rank profile of F. To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of F with a rank-sensitive complexity of O~ (rw-2n(m+d)) operations in K. Here, D is the sum of row degrees of F, w is the exponent of matrix multiplication, and O~ (.) hides logarithmic factors.

Let K be a field of characteristic zero and K[x1,...,xn] the corresponding multivariate polynomial ring. Given a sequence of s polynomials f = (f_1,...,f_s) and a polynomial φ, all in K[x1,...,xn] with s>n, we consider the problem of computing the set W(φ,f ) of points at which f vanishes and the Jacobian matrix of f, φ with respect to x1,...,xn does not have full rank. This problem plays an essential role in many application areas.

We study the computation of canonical bases of sets of univariate relations (p1,...,pm) ∈ K[x]m such that p1 f1 + ⋯ + pm fm = 0; here, the input elements f1,...,fm are from a quotient K[x]n/M, where M is a K[x]-module of rank n given by a basis M ∈ K[x]n x n in Hermite form. We exploit the triangular shape of M to generalize a divide-and-conquer approach which originates from fast minimal approximant basis algorithms. Besides recent techniques for this approach, we rely on high-order lifting to perform fast modular products of polynomial matrices of the form P F mod M.