Polyhedra and spectrahedra over the real numbers, or more generally their images under linear maps, are respectively the feasible sets of linear and semidefinite programming, and form the family of semidefinite-representable sets. This paper studies analogues of these sets, as well as the associated optimization problems, when the data are taken over a valued field K. For K-polyhedra and linear programming over K we present an algorithm based on the computation of Smith normal forms. We prove that fundamental properties of semidefinite-representable sets extend to the valued setting. In particular, we exhibit examples of non-polyhedral K-spectrahedra, as well as sets that are semidefinite-representable over K but are not K-spectrahedra.

Where are the roots of approximate polynomials? By combining the OM algorithm, cluster pictures, Berkovich skeletons and Brink’s continuity of roots inequality, we produce balls enclosing the roots of all the approximations at a given precision of a given univariate polynomial over a complete field with discrete valuation. Those balls can be presented in an approximate cluster picture or Berkovich skeleton. We present and showcase an algorithm to compute them.

In this paper, we study the connection between the OM-factorization of a polynomial and its cluster pictures, which is a representation of the relative configuration of the roots. Our contribution is threefold, assuming that the residual characteristic is zero or large enough (i.e. the field extension is tame) :(1)We provide and showcase an implementation of the OM algorithms.(2)We make explicit and constructive the connection between the valuative tree of a polynomial, the cluster picture of its roots and the Berkovich skeleton of its roots. As such, we provide a complexity result on the computation of cluster pictures.(3)We elaborate on this connection to provide and showcase an algorithm to compute cluster pictures based on the OM algorithms.

Polyhedral affinoid algebras have been introduced by Einsiedler, Kapranov and Lind in [5] to connect rigid analytic geometry (analytic geometry over non-archimedean fields) and tropical geometry. In this article, we present a theory of Gröbner bases for polytopal affinoid algebras that extends both Caruso et al.’s theory of Gröbner bases on Tate algebras of [1] and Pauer et al.’s theory of Gröbner bases on Laurent polynomials of [9].

Solving a polynomial system, or computing an associated Gröbner basis, has been a fundamental task in computational algebra. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gröbner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gröbner basis, raising two novel algebraic problems: random generation of Gröbner bases and transforming them into non-Gröbner ones, termed as backward Gröbner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gröbner bases, and Gröbner computation is learnable in a particular class.

Pourchet proved in 1971 that every nonnegative univariate polynomial with rational coefficients is a sum of five or fewer squares. Nonetheless, there are no known algorithms for constructing such a decomposition. The sole purpose of the present paper is to present a set of algorithms that decompose a given nonnegative polynomial into a sum of six (five under some unproven conjecture or when allowing weights) squares of polynomials. Moreover, we prove that the binary complexity can be expressed polynomially in terms of classical operations of computer algebra and algorithmic number theory.

A universal analytic Gröbner basis (UAGB) of an ideal of a Tate algebra is a set containing a local Gröbner basis for all suitable convergence radii. In a previous article, the authors proved the existence of finite UAGB’s for polynomial ideals, leaving open the question of how to compute them. In this paper, we provide an algorithm computing a UAGB for a given polynomial ideal, by traversing the Gröbner fan of the ideal. As an application, it offers a new point of view on algorithms for computing tropical varieties of homogeneous polynomial ideals, which typically rely on lifting the computations to an algebra of power series.

In this paper, we study ideals spanned by polynomials or overconvergent series in a Tate algebra. With state-of-the-art algorithms for computing Tate Gröbner bases, even if the input is polynomials, the size of the output grows with the required precision, both in terms of the size of the coefficients and the size of the support of the series.

Tate introduced in [18] the notion of Tate algebras to serve, in the context of analytic geometry over the p-adics, as a counterpart of polynomial algebras in classical algebraic geometry. In [6,7] the formalism of Gröbner bases over Tate algebras has been introduced and advanced signature-based algorithms have been proposed. In the present article, we extend the FGLM algorithm of [8] to Tate algebras. Beyond allowing for fast change of ordering, this strategy has two other important benefits. First, it provides an efficient algorithm for changing the radii of convergence which, in particular, makes effective the bridge between the polynomial setting and the Tate setting and may help in speeding up the computation of Gröbner basis over Tate algebras. Second, it gives the foundations for designing a fast algorithm for interreduction, which could serve as a basic primitive in our previous algorithms and accelerate them significantly.

Introduced by Tate in [Ta71], Tate algebras play a major role in the context of analytic geometry over the p-adics, where they act as a counterpart to the use of polynomial algebras in classical algebraic geometry. In [CVV19] the formalism of Gröbner bases over Tate algebras has been introduced and effectively implemented. One of the bottlenecks in the algorithms was the time spent on reduction, which are significantly costlier than over polynomials. In the present article, we introduce two signature-based Gröbner bases algorithms for Tate algebras, in order to avoid many reductions. They have been implemented in SageMath. We discuss their superiority based on numerical evidence.

Newton's method is an ubiquitous tool to solve equations, both in the archimedean and non-archimedean settings --- for which it does not really differ. Broyden was the instigator of what is called "quasi-Newton methods". These methods use an iteration step where one does not need to compute a complete Jacobian matrix nor its inverse. We provide an adaptation of Broyden's method in a general non-archimedean setting, compatible with the lack of inner product, and study its Q and R convergence. We prove that our adapted method converges at least Q-linearly and R-superlinearly with R-order [EQUATION] in dimension m. Numerical data are provided.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Gröbner bases. In this article, we investigate how the FGLM change of ordering algorithm can be adapted to the tropical setting.

Tate algebras are fundamental objects in the context of analytic geometry over the p-adics. Roughly speaking, they play the same role as polynomial algebras play in classical algebraic geometry. In the present article, we develop the formalism of Gröbner bases for Tate algebras. We prove an analogue of the Buchberger criterion in our framework and design a Buchberger-like and a F4-like algorithm for computing Gröbner bases over Tate algebras. An implementation in SageMath is also discussed.

We present a new package ZpL for the mathematical software system SageMath. It implements a sharp tracking of precision on p-adic numbers, following the theory of ultrametric precision introduced in a previous paper by the same authors. The underlying algorithms are mostly based on automatic differentiation techniques. We introduce them, study their complexity and discuss our design choices. We illustrate the benefits of our package (in comparison with previous implementations) with a large sample of examples coming from linear algebra, commutative algebra and differential equations.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K . Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p -adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We provide numerical examples to illustrate time-complexity and p -adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p -adics.

We analyze the precision of the characteristic polynomial XM of an nxn p-adic matrix M using differential precision methods developed previously. When M is an integral matrix whose entries are all given at the same precision O(pN), we give a criterion (checkable within Õ(nω) operations in Fp) for the existence of a coefficient of XM with more accuracy than O(pN). In general, we provide two algorithms for determining the optimal precision of the coefficients of XM and of M's eigenvalues. We provide evidence showing that classical algorithms do not reach this optimal precision in general.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. While generalizing the classical theory of Gröbner bases, it is not clear how modern algorithms for computing Gröbner bases can be adapted to the tropical case. Among them, one of the most efficient is the celebrated F5 Algorithm of Faugère.

We study two important operations on polynomials defined over complete discrete valuation fields: Euclidean division and factorization. In particular, we design a simple and efficient algorithm for computing slope factorizations, based on Newton iteration. One of its main features is that we avoid working with fractional exponents. We pay particular attention to stability, and analyze the behavior of the algorithm using several precision models.

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.

Using the differential precision methods developed previously by the same authors, we study the p-adic stability of standard operations on matrices and vector spaces. We demonstrate that lattice-based methods surpass naive methods in many applications, such as matrix multiplication and sums and intersections of subspaces. We also analyze determinants, characteristic polynomials and LU factorization using these differential methods. We supplement our observations with numerical experiments.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a p-adic fields.

Let (f1,..., fs) ∈ Qp [X1,..., Xn]s be a sequence of homogeneous polynomials with p-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since Ap is not an effective field, classical algorithm does not apply.