Full Papers
The program committee has accepted the 53 papers below.
Click on the plus symbol to view a paper's abstract.
List of Accepted Papers
-
[+]
Przemysław Koprowski.
Solving Sums of Squares in Global FieldsAbstract:The problem of writing a totally positive element as a sum of squares has a long history in mathematics, going back to Bachet and Lagrange. While for some specific rings (like integers or polynomials over the rationals), there are known methods for decomposing an element into a sum of squares, in general, for many other important rings and fields, the problem is still widely open. In this paper, we present an explicit algorithm for decomposing an element of an arbitrary global field (either a number field or a global function field) into a sum of squares of minimal length.
-
[+]
Cheng-Chao Huang.
Explicit Bounds for Linear Forms in the Exponentials of Algebraic NumbersAbstract:In this paper, we study linear forms \[ \lambda = \beta_1 e^{\alpha_1}+\cdots+\beta_m e^{\alpha_m}, \] where $\alpha_i$ and $\beta_i$ are algebraic numbers. An explicit lower bound for $|\lambda|$ is proved, which is derived from “théoréme de Lindemann--Weierstrass effectif” via constructive methods in algebraic computation. Besides, the existence of $\lambda$ with an explicit upper bound is established on the result of counting algebraic numbers.
-
[+]
Tobias Boege, Sonja Petrović and Bernd Sturmfels.
Marginal Independence ModelsAbstract:We impose rank one constraints on marginalizations of a tensor, given by a simplicial complex. Following work of Kirkup and Sullivant, such marginal independence models can be made toric by a linear change of coordinates. We study their toric ideals, with emphasis on random graph models and independent set polytopes of matroids. We develop the numerical algebra of parameter estimation, using both Euclidean distance and maximum likelihood, and we present a comprehensive database of small models.
-
[+]
Klara Nosan, Amaury Pouly, Sylvain Schmitz, Mahsa Shirmohammadi and James Worrell.
On the Computation of the Algebraic Closure of Finitely Generated Groups of MatricesAbstract:We investigate the complexity of computing the Zariski closure of a finitely generated group of matrices. The Zariski closure was previously shown to be computable by Derksen, Jeandel, and Koiran, but the termination argument for their algorithm appears not to yield any complexity bound. In this paper we follow a different approach and obtain a bound on the degree of the polynomials that define the closure. Our bound shows that the closure can be computed in elementary time. We also obtain upper bounds on the length of chains of linear algebraic groups.
-
[+]
Sergei Abramov, Marko Petkovsek and Anna Ryabenko.
On Linear Dependence of Rows and Columns in Matrices over Non-commutative DomainsAbstract:Some well-known correspondences between sets of linearly independent rows and columns of matrices over fields carry over to matrices over non-commutative rings without nontrivial zero divisors.
-
[+]
Dong Lu, Dingkang Wang, Fanghui Xiao and Xiaopeng Zheng.
A Property of Modules Over a Polynomial Ring With an Application in Multivariate Polynomial Matrix FactorizationsAbstract:This paper is concerned with a property of modules over a polynomial ring and its application in multivariate polynomial matrix factorizations. We construct a specific polynomial such that the product of the polynomial and a nonzero vector in a module over a polynomial ring can be represented by the elements in a maximum linearly independent vector set of the module over the polynomial ring. Based on this property, a relationship between a rank-deficient matrix and any of its full row rank submatrices is presented. By this result, we show that the problem for general factorizations of rank-deficient matrices can be translated into that of any of their full row rank submatrices in the regular case. Then many results on factorizations of full row rank matrices, such as zero prime factorizations, minor prime factorizations and factor prime factorizations, can be extended to the rank-deficient case. We implement the algorithm of general factorizations for rank-deficient matrices on the computer algebra system Maple, and two examples are given to illustrate the algorithm.
-
[+]
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray and Daniel Roche.
Sparse Polynomial Interpolation and Division in Soft-linear TimeAbstract:Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. These methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover an polynomial $f(x)$ with integer coefficients given a way to evaluate $f(a) \text{ mod } m$ for for any chosen integers $a$ and $m$. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with soft-linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents.
-
[+]
Alperen Ergür, Josué Tonelli-Cueto and Elias Tsigaridas.
Beyond Worst-Case Analysis for Root Isolation AlgorithmsAbstract:Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. We develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of Descartes solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is $\tilde{O}_B(d^2 + d \tau)$, where $d$ is the degree of the polynomial and $\tau$ the bitsize of the coefficients.
-
[+]
Philipp Nuspl and Veronika Pillwein.
Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite SequencesAbstract:A sequence is called $C$-finite, if it satisfies a linear recurrence with constant coefficients and holonomic, if it satisfies a linear recurrence with polynomial coefficients. The class of $C^2$-finite sequences is a natural generalization of holonomic sequences and consists of sequences satisfying a linear recurrence with $C$-finite coefficients whose leading coefficient has no zero terms. Recently, we investigated computational properties of $C^2$-finite sequences: we showed that these sequences form a difference ring and provided methods to compute in this ring. From an algorithmic point of view, some of these results were not as far reaching as we hoped for. In this paper, we define the class of simple $C^2$-finite sequences and show that it satisfies the same computational properties, but does not share the same technical issues. In particular, we are able to derive bounds for the asymptotic behavior, can compute closure properties more efficiently, and have a characterization via the generating function.
-
[+]
Dingkang Wang, Jingjing Wei, Fanghui Xiao and Xiaopeng Zheng.
Rational Univariate Representation of Zero-Dimensional Ideals with ParametersAbstract:An algorithm for computing the rational univariate representation of zero-dimensional ideals with parameters is presented in the paper. Different from the rational univariate representation of zero-dimensional ideals without parameters, the number of zeros of zero-dimensional ideals with parameters under various specializations is different, which leads to choosing and checking the separating element, the key to computing the rational univariate representation, is difficult. In order to pick out the separating element, by partitioning the parameter space we can ensure that under each branch the ideal has the same number of zeros. Subsequently based on the extended subresultant theorem for parametric cases, the separating element corresponding to each branch is chosen with the further partition of parameter space. Finally, with the help of parametric greatest common divisor theory a finite set of the rational univariate representation of zero-dimensional ideals with parameters can be obtained.
-
[+]
Hiroshi Kera.
Border Basis Computation with Gradient-weighted NormalizationAbstract:Normalization of polynomials plays a vital role in the approximate basis computation of vanishing ideals. Coefficient normalization, which normalizes a polynomial with its coefficient norm, is the most common method in computer algebra. This study proposes the gradient-weighted normalization method for the approximate border basis computation of vanishing ideals, inspired by recent developments in machine learning. The data-dependent nature of gradient-weighted normalization leads to better stability against perturbation and consistency in the scaling of input points, which cannot be attained by coefficient normalization. Only a subtle change is needed to introduce gradient normalization in the existing algorithms with coefficient normalization. The analysis of algorithms still works with a small modification, and the time complexity of algorithms remains unchanged. We also prove that, with coefficient normalization, which does not provide the scaling consistency property, scaling of points (e.g., as a preprocessing) can cause an approximate basis computation to fail. This study is the first to theoretically highlight the crucial effect of scaling in approximate basis computation and presents the utility of data-dependent normalization.
-
[+]
Yuki Ishihara.
Modular Techniques for Intermediate Primary DecompositionAbstract:In Commutative Algebra and Algebraic Geometry, “Primary decomposition” is well-known as a fundamental and important tool. Although algorithms for primary decomposition have been studied by many researchers, the development of fast algorithms still remains a challenging problem. In this paper, we devise an algorithm for “Strong Intermediate Primary Decomposition" via maximal independent sets by using modular techniques. In the algorithm, we utilize double ideal quotients to check whether a candidate from modular computations is an intersection of prime divisors or not. As an application, we can compute the set of associated prime divisors from the strong intermediate prime decomposition. In a naive computational experiments, we see the effectiveness of our methods.
-
[+]
Rodrigo Iglesias, Patricia Pascual-Ortigosa and Eduardo Saenz-De-Cabezon.
An Algebraic Version of the Sum-of-disjoint-products Method for Multi-state System Reliability AnalysisAbstract:The evaluation of system reliability is an NP-hard problem even in the binary case. There exist several general methodologies to analyze and compute system reliability. The two main ones are the sum-of-disjoint-products (SDP), which expresses the logic function of the system as a union of disjoint terms, and the Improved Inclusion-Exclusion (IIE) formulas. On the other hand the algebraic approach to system reliability, assigns a monomial ideal to the system and computes its reliability in terms of the Hilbert series of the corresponding ideal, providing an algebraic version of the IIE method. In this paper we make use of this monomial ideal framework and present a new algebraic version of the SDP method, based on a combinatorial decomposition of the system's ideal. Such a decomposition is obtained from an involutive basis of the ideal. This algebraic version is suitable for binary and multi-state systems. We include computer experiments on the performance of this approach using the C++ computer algebra library CoCoALib and a discussion on which of the algebraic methods can be more efficient depending on the type of system under analysis.
-
[+]
Adrien Poteaux and Martin Weimann.
Local Polynomial Factorisation: Improving the Montes AlgorithmAbstract:We improve significantly the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring A. Our first contribution is to extend the Hensel lemma in the context of generalised Newton polygon, from which we derive a new divide and conquer strategy. Also, if A has characteristic zero or high enough, we prove that approximate roots are convenient representatives of types, leading finally to an almost optimal complexity both for irreducibility and factorisation issues (not counting the cost of factorisations over the residue field).
-
[+]
André Galligo.
Modeling Complex Root Motion of Real Random Polynomials under DifferentiationAbstract:We consider nonlocal, nonlinear partial differential equations to model dynamics of complex root sets of random polynomials under differentiation. These equations aim to generalise the recent PDE obtained by Stefan Steinerberger (2019) in the real case , and the PDE obtained by Sean O'Rourke and Stefan Steinerberger (2020) in the radial case (which amounts to work in 1D). These PDEs describe dynamics of the complex roots for random polynomials of sufficiently high degree $n$. The unit of the time $t$ corresponds to $n$ differentiations, and the increment $\Delta t$ corresponds to $\frac{1}{n}$. The general situation in 2D, in particular for complex roots of real polynomials, was not yet addressed. The purpose of this paper is to present a first attempt in that direction. We propose a generalisation of Steinerberger method and assume that the roots are distributed according to a regular distribution with a local homogeneity property (defined in the text), and that this property is maintained under differentiation. The paper is illustrated with examples computed with the Maple system.
-
[+]
Michael Figelius and Markus Lohrey.
Exponent Equations in HNN-extensionsAbstract:We consider exponent equations in finitely generated groups. These are equations, where the variables appear as exponents of group elements and take values from the natural numbers. Solvability of such (systems of) equations has been intensively studied for various classes of groups in recent years. In many cases, it turns out that the set of all solutions on an exponent equation is a semilinear set that can be constructed effectively. Such groups are called knapsack semilinear. Examples of knapsack semilinear groups are hyperbolic groups, virtually special groups, co-context-free groups and free solvable groups. Moreover, knapsack semilinearity is preserved by many group theoretic constructions, e.g., finite extensions, graph products, wreath products, amalgamated free products with finite amalgamated subgroups, and HNN-extensions with finite associated subgroups. On the other hand, arbitrary HNN-extensions do not preserve knapsack semilinearity. In this paper, we consider the knapsack semilinearity of HNN-extensions, where the stable letter t acts trivially by conjugation on the associated subgroup A of the base group G. We show that under some additional technical conditions, knapsack semilinearity transfers from base group G to the HNN-extension H. These additional technical conditions are satisfied in many cases, e.g., when A is a centralizer in G or A is a quasiconvex subgroup of the hyperbolic group G.
-
[+]
Weifeng Shang, Chenqi Mou and Deepak Kapur.
Algorithms for Testing Membership in Univariate Quadratic Modules over the RealsAbstract:Quadratic modules in real algebraic geometry are akin to polynomial ideals in algebraic geometry, and have been found useful in the theory of Positivstellensatz to study Hilbert's 17th problem. Algorithms are presented in this paper for testing membership in univariate finitely generated quadratic modules over the reals and inclusion of two quadratic modules. For an unbounded quadratic module, an explicit upper bound on the degrees of sums of squares to construct any given polynomial is proved, and this bound is used to design an algorithm for testing membership in such a module by using quantifier elimination. For a bounded quadratic module, a unique signature is associated with it based on the real values on which its finite basis is nonnegative, and the signatures are used to furnish a criterion for inclusion of two quadratic modules and a corresponding algorithm which solves the membership problem as a special case. It is also proved that a bounded quadratic module can be transformed to an equivalent one with a basis of two polynomials; an algorithm for performing this transformation is presented. All the presented algorithms have been implemented.
-
[+]
Nuwan Herath Mudiyanselage, Guillaume Moroz and Marc Pouget.
Fast High-Resolution Drawing of Algebraic CurvesAbstract:We address the problem of computing a drawing of high resolution of a plane curve defined by a bivariate polynomial equation $P(x,y)=0$. Given a grid of fixed resolution, a drawing is a subset of pixels. Our goal is to compute an approximate drawing that (i) contains all the parts of the curve that intersect the pixel edges, (ii) excludes a pixel when the evaluation of $P$ with interval arithmetic on each of its four edges is far from zero. One of the challenges for computing drawings on a high-resolution grid is to minimize the complexity due to the evaluation of the input polynomial. Most state-of-the-art approaches focus on bounding the number of independent evaluations. Using state-of-the-art Computer Algebra techniques, we design new algorithms that amortize the evaluations and improve the complexity for computing such drawings. Our main contribution is to use a non-uniform grid based on the Chebyshev nodes to take advantage of multipoint evaluation techniques via the Discrete Cosine Transform. We propose two new algorithms that compute drawings and compare them experimentally on several classes of high degree polynomials. Notably, one of those approaches is faster than state-of-the-art drawing software.
-
[+]
Victor Magron, Mohab Safey El Din, Markus Schweighofer and Trung Hieu Vu.
Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian CoefficientsAbstract:Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejéz spectral factorization theorem that any trigonometric univariate polynomial positive on the unit circle can be decomposed as a Hermitian square with complex coefficients. Here we focus on the case of polynomials with Gaussian integer coefficients, i.e., with real and imaginary parts being integers. We design, analyze and compare, theoretically and practically, three hybrid numeric-symbolic algorithms computing weighted sums of Hermitian squares decompositions for trigonometric univariate polynomials positive on the unit circle with Gaussian coefficients. The numerical steps the first and second algorithm rely on are complex root isolation and semidefinite programming, respectively. An exact sum of Hermitian squares decomposition is obtained thanks to compensation techniques. The third algorithm, also based on complex semidefinite programming, is an adaptation of the rounding and projection algorithm by Peyrl and Parrilo. For all three algorithms, we prove bit complexity and output size estimates that are polynomial in the degree of the input and linear in the maximum bitsize of its coefficients. We compare their performance on randomly chosen benchmarks, and further design a certified finite impulse filter.
-
[+]
Péter Kutas, Mickaël Montessinos, Gergely Zábrádi and Tímea Csahók.
Finding nontrivial zeros of quadratic forms over rational function fields of characteristic 2Abstract:We propose polynomial-time algorithms for finding nontrivial zeros of quadratic forms with four variables over rational function fields of characteristic 2. We apply these results to find prescribed quadratic subfields of quaternion division division algebras and zero divisors in $M_2(D)$, the full matrix algebra over a division algebra, given by structure constants. We also provide an implementation of our results in MAGMA which shows that the algorithms are truly practical.
-
[+]
Klara Nosan, Amaury Pouly, Mahsa Shirmohammadi and James Worrell.
The Membership Problem for Hypergeometric Sequences with Rational ParametersAbstract:We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence $\langle u_n \rangle_{n=0}^\infty$ of rational numbers and a target $t \in \mathbb{Q}$, decide whether $t$ occurs in the sequence. We show decidability of this problem under the assumption that in the defining recurrence $p(n)u_{n+1}=q(n)u_n$, the roots of the polynomials $p(x)$ and $q(x)$ are all rational numbers. Our proof relies on bounds on the density of primes in arithmetic progressions. We also observe a relationship between the decidability of the Membership problem (and variants) and the Rohrlich-Lang conjecture in transcendence theory.
-
[+]
Robert Corless, George Labahn, Dan Piponi and Leili Rafiee Sevyeri.
Bohemian Matrix GeometryAbstract:A Bohemian matrix family is a set of matrices all of whose entries are drawn from a fixed, usually discrete and hence bounded, subset of a field of characteristic zero. Originally these were integers (hence the name, from the acronym BOunded HEight Matrix of Integers (BOHEMI)) but other kinds of entries are also interesting. Some kinds of questions about Bohemian matrices can be answered by numerical computation, but sometimes exact computation is better. In this paper we explore some Bohemian families (symmetric, upper Hessenberg, or Toeplitz) computationally, and answer some open questions posed about the distributions of eigenvalue densities.
-
[+]
Garrett Paluck and Michael Monagan.
Linear Hensel Lifting for $\mathbb Z_p[x,y]$ for $n$ Factors with Cubic CostAbstract:We present a new algorithm for performing linear Hensel lifting on bivariate polynomials over the finite field $\mathbb Z_p$ for some prime $p$. Our algorithm lifts $n$ monic, univariate polynomials to recover the factors of a polynomial $A(x,y)$ in $\mathbb Z_p[x,y]$ which is monic in $x$, and bounded by degrees $d_x = deg(A,x)$ and $d_y = deg(A,y)$. Our algorithm improves upon Bernardin's algorithm and reduces the number of arithmetic operations in $\mathbb Z_p$ from $O(d_x^2 d_y^2)$ to $O(d_x^2d_y + d_xd_y^2)$ for $p \geq d_x$. Experimental results in C verify that our algorithm compares favorably with Bernardin's for large degree polynomials. Moreover, we've implemented a Quadratic Hensel lifting algorithm in Magma to show that our cubic Linear Hensel lifting algorithm outperforms Magma's Quadratic Hensel lifting for a wide range of input sizes.
-
[+]
François Ollivier.
Extending Flat Motion Planning to Non-flat Systems. Experiments on Aircraft Models Using MapleAbstract:Aircraft models may be considered as flat if one neglects some terms associated to aerodynamics. However some maneuvers may be hard or even impossible to achieve with this flat approximation. Computational experiments in Maple show that in some cases a suitably designed feedback allows to follow such trajectories, when applied to the non-flat model. In this paper, we propose an iterated process to compute a more achievable trajectory, starting from the flat reference trajectory. More precisely, the unknown neglected terms in the flat model are iteratively re-evaluated using the values obtained at the previous step. This process may be interpreted as a new trajectory parametrization using an infinite number of derivatives, a property that may be called generalized flatness. We illustrate the pertinence of this approach in flight conditions of increasing difficulties, from power-off gliding flight to aerobatics.
-
[+]
Carles Checa Nualart and Ioannis Emiris.
A Greedy Approach to the Canny-Emiris FormulaAbstract:The Canny-Emiris formula gives the sparse resultant as a ratio between the determinant of a Sylvester-type matrix and a minor of it, by a subdivision algorithm. The most complete proof of the formula was given by D'Andrea et al. under general conditions on the underlying mixed subdivision. Before the proof, Canny and Pedersen had proposed a greedy algorithm which provides smaller matrices, in general. The goal of this paper is to give an explicit class of mixed subdivisions for the greedy approach such that the formula holds, and the dimensions of the matrices are reduced compared to the subdivision algorithm. We measure this reduction for the case when the Newton polytopes are zonotopes generated by n line segments (where n is the rank of the underlying lattice), and for the case of multihomogeneous systems. This article comes with a JULIA implementation of the treated cases.
-
[+]
Thi Xuan Vu.
Computing Critical Points for Algebraic Systems Defined by Hyperoctahedral Invariant PolynomialsAbstract:Let $K$ be a field and $K[x_1, \dots, x_n]$ be a multivariate polynomial ring. Given a sequence of polynomials $f = (f_1, \dots, f_n)$ and a polynomial $\phi$ in $K[x_1, \dots, x_n]$ with $s
-
[+]
Andrew Ferguson and Huu Phuoc Le.
Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal IdealsAbstract:Polynomial matrices and ideals generated by their minors appear in various domains such as cryptography, polynomial optimization and effective algebraic geometry. When the given matrix is symmetric, this additional structure, on top of the determinantal structure, affects computations on the derived ideals. Thus, understanding the complexity of these computations is important. Moreover, this study serves as a stepping stone towards further understanding the effects of structure in determinantal systems, such as those coming from moment matrices. In this paper, we focus on the Sparse-FGLM algorithm, the state-of-the-art for changing ordering of Gr\"obner bases of zero-dimensional ideals. Under a variant of Fr\"oberg's conjecture, we study its complexity for symmetric determinantal ideals and identify the gain of exploiting sparsity in the Sparse-FGLM algorithm compared with the classical FGLM algorithm. For an $n\times n$ symmetric matrix with polynomial entries of degree $d$, we show that the complexity of Sparse-FGLM for zero-dimensional determinantal ideals obtained from this matrix over that of the FGLM algorithm is at least $O(1/d)$. Moreover, for some specific sizes of minors we prove finer results of at least $O(1/nd)$ and $O(1/n^3d)$.
-
[+]
Erich Kaltofen.
The GKR Protocol Revisited: Nearly Optimal Prover-Complexity For Polynomial-Time Wiring Algorithms and For Primality Testing in $n^{1/2+o(1)}$ RoundsAbstract:The proof-of-work interactive protocol by Shafi Goldwasser, Yael T. Kalai and Guy N. Rothblum (GKR) [STOC 2008, JACM 2015] certifies the execution of an algorithm via the evaluation of a corresponding boolean or arithmetic circuit whose structure is known to the verifier by circuit wiring algorithms that define the uniformity of the circuit. Here we study protocols whose prover time- and space-complexities are within a poly-logarithmic factor of the time- and space-complexity of the algorithm; we call those protocols `prover-nearly-optimal.' We show that the uniformity assumptions can be relaxed from LOGSPACE to polynomial-time in the bit-lengths of the labels which enumerate the nodes in the circuit. Our protocol applies GKR recursively to the arising sumcheck problems on each level of the circuit whose values are verified, and deploys any of the prover-nearly-optimal versions of GKR on the constructed shallow sorting and prefix circuits. The verifier time-complexity of GKR grows linearly in the depth of the circuit. For deep circuits such as the Miller-Rabin integer primality test of an n-bit integer, the added complexity interferes with the possible application of recent generalizations of the Fiat-Shamir heuristic to the multi-round GKR protocol: the verifier time grows to quadratic in n, which is essentially the prover time. We re-arrange the circuit evaluation problem by the baby-steps/giant-steps method to achieve a depth of $n^{1/2+o(1)}$. We obtain a proof for integer primality/compositeness which the prover can compute in $n^{2+o(1)}$ bit complexity and preserve for later verification, which then costs $n^{3/2+o(1)}$ bit complexity to the verifier. The soundness of the proof is guaranteed by the cryptographic hardness assumptions in the used hash functions.
-
[+]
Barbara Giunti, Guillaume Houry and Michael Kerber.
Average Complexity of Matrix Reduction for Clique FiltrationsAbstract:We study the algorithmic complexity of computing persistent homology of a randomly chosen filtration. Specifically, we prove upper bounds for the average fill-up (number of non-zero entries) of the boundary matrix on Erdös-Renyi and Vietoris-Rips filtrations after matrix reduction. Our bounds show that, in both cases, the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our method is based on previous results on the expected first Betti numbers of corresponding complexes. We establish a link between these results to the fill-up of the boundary matrix. Our bound for Vietoris-Rips complexes is asymptotically tight up to logarithmic factors. We also provide an Erdös-Renyi filtration realizing the worst-case fill-up and complexity.
-
[+]
Damien Chablat, Rémi Prebet, Mohab Safey El Din, Durgesh Salunkhe and Philippe Wenger.
Deciding Cuspidality of Manipulators through Computer Algebra and Algorithms in Real Algebraic GeometryAbstract:Cuspidal robots are robots with at least two inverse kinematic solutions that can be connected by a singularity-free path. Deciding the cuspidality of a generic 3R robots has been studied in the past, but extending the study to six-degree-of-freedom robots can be a challenging problem. Many robots can be modeled as a polynomial map together with a real algebraic set so that the notion of cuspidality can be extended to these data. In this paper we design an algorithm that, on input a polynomial map in $n$ indeterminates, and $s$ polynomials in the same indeterminates describing a real algebraic set of dimension $d$, decides the cuspidality of the restriction of the map to the real algebraic set under consideration. Moreover, if $D$ and $\tau$ are respectively the maximum degree and a bound on the bit size of the coefficients of the input polynomials, this algorithm runs in time polynomial in $\tau s^n (ndD)^{n^2}$. It relies on many high-level algorithms in computer algebra which use advanced methods on real algebraic sets and critical loci of polynomial maps. As far as we know, this is the first algorithm that tackles the cuspidality problem from a general point of view.
-
[+]
Alexander Levin.
Reduction with respect to the Effective Order and a New Type of Dimension Polynomials of Difference ModulesAbstract:We introduce a new type of reduction in a free difference module over a difference field that uses a generalization of the concept of effective order of a difference polynomial. Then we define the concept of a generalized characteristic set of such a module, establish some properties of these characteristic sets and use them to prove the existence, outline a method of computation and find invariants of a dimension polynomial in two variables associated with a finitely generated difference module. As a consequence of these results, we obtain a new type of bivariate dimension polynomials of finitely generated difference field extensions. We also explain the relationship between these dimension polynomials and the concept of Einstein's strength of a system of difference equations.
-
[+]
Haomin Li and Arne Storjohann.
Computing a Basis for an Integer Lattice: a Special CaseAbstract:Consider an integer matrix $A \in \mathbb Z^{n \times (n-1)}$ that has full column rank $n-1$. The set of all $\mathbb Z$-linear combinations of the rows of $A$ generates a (row) lattice, denoted by $L(A)$. An algorithm is given that computes a matrix $C \in \mathbb Z^{(n-1) \times n}$ such that $B := C A \in \mathbb Z^{(n-1) \times (n-1)}$ satisfies $L(B) = L(A)$. The matrix $C$ will satisfy $||C|| \leq n^4 ||A||^2$ (where $|| \cdot ||$ denotes the maximum entry in absolute value) and will have at most $n (1+\log_2 n)$ nonzero entries. The cost of the algorithm to compute $C$ is about the same as that that required to multiply together two square integer matrices of dimension $n$ that have magnitude of entries bounded by $||A||$.
-
[+]
Shaoshi Chen.
Stability Problems in Symbolic IntegrationAbstract:This paper aims at initializing a dynamical aspect of symbolic integration by studying stability problems in differential fields. We first show some basic properties of stable elementary functions and then characterize three special families of stable elementary functions including rational functions, logarithmic functions, and exponential functions. We prove that all D-finite power series are eventually stable. Some problems for future studies are proposed towards deeper dynamical studies in differential algebra.
-
[+]
Sebastian Falkensteiner.
Puiseux Series Solutions with Real or Rational Coefficients of First Order Autonomous AODEsAbstract:Given an autonomous first order algebraic ordinary differential equation $F(y,y')=0$, we provide algorithms for computing formal Puiseux series solutions of $F(y,y')=0$ with real or rational coefficients. For this purpose we give necessary and sufficient conditions on the existence of such solutions by combining classical methods from algebraic geometry and the study of an associated differential equation. Since all formal Puiseux series solutions of such differential equations are convergent in a certain neighborhood, the solutions also define real solution functions.
-
[+]
Carlos Arreche and Yi Zhang.
Mahler Discrete Residues and Summability for Rational FunctionsAbstract:We construct Mahler discrete residues for rational functions and show that they comprise a complete obstruction to the Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $g(x^p)-g(x)$ for some rational function $g(x)$ and an integer $p > 1$. This extends to the Mahler case the analogous notions, properties, and applications of discrete residues (in the shift case) and $q$-discrete residues (in the $q$-difference case) developed by Chen and Singer. Along the way we define several additional notions that promise to be useful for addressing related questions involving Mahler difference fields of rational functions, including in particular telescoping problems and problems in the (differential) Galois theory of Mahler difference equations.
-
[+]
Frédéric Chyzak, Alexandre Goyer and Marc Mezzarobba.
Symbolic-Numeric Factorization of Differential OperatorsAbstract:We present a symbolic-numeric Las Vegas algorithm for factoring Fuchsian ordinary differential operators with rational function coefficients. The new algorithm combines ideas of van Hoeij's “local-to-global” method and of the “analytic” approach proposed by van der Hoeven. It essentially reduces to the former in “easy” cases where the local-to-global method succeeds, and to an optimized variant of the latter in the “hardest” cases, while handling intermediate cases more efficiently than both.
-
[+]
Manuel Kauers and Christoph Koutschan.
Guessing with Little DataAbstract:Reconstructing a hypothetical recurrence equation from the first terms of an infinite sequence is a classical and well-known technique in experimental mathematics. We propose a variation of this technique which can succeed with fewer input terms.
-
[+]
Hui Huang, Manuel Kauers and Gargi Mukherjee.
Order-Degree-Height Surfaces for Linear OperatorsAbstract:It is known for annihilating linear operators with polynomial coefficients that there is a trade-off between order and degree. Raising the order may give room for lowering the degree. The relationship between order and degree is typically described by a hyperbola known as the order-degree curve. In this paper, we add the height into the picture, i.e., a measure for the size of the coefficients in the polynomial coefficients. For certain situations, we derive relationships between order, degree, and height that can be viewed as order-degree-height surfaces.
-
[+]
Francois Morain.
Implementing the Thull-Yap Algorithm for Computing Euclidean Remainder SequencesAbstract:There are two types of integer gcd algorithms: those which compute the sequence of remainders of Euclid's algorithm and those which build different sequences. The former are more difficult to validate and analyse, whereas the latter are simpler and more efficient. When one wants the euclidean remainders (for instance if one wants to compute continued fractions), only the former can be used. Our main focus is the subquadratic time Thull-Yap GCD algorithm, and in fact on its core computing a half gcd (TYHGCD). This algorithm is tricky due to the difficulty in correcting the remainder sequence that comes back from a recursive call. The aim of this work is to revise TYHGCD in order to implement it using GMP. We clarify some points of the algorithm, in particular the stopping conditions that are always difficult to set correctly. We add a base case to speed up the whole algorithm, using Jebelean's quadratic algorithm with a stopping condition. We give our own modified version and add the proofs where needed. We insist on the test phase for this algorithm, giving families of hard cases for all branches, some of which are rarely activated. We give some details on our implementation in GMP using low-level functions, adding some remarks on the use of fast multiplications techniques. We pay attention to the data structure needed to store partial quotients, enabling to navigate rapidly back and forth in the sequence of Euclidean remainders. Benchmarks are provided. Some comments are made on Lichtblau'salgorithm, which is close in spirit to the Thull-Yap algorithm.
-
[+]
Erich Kaltofen.
Sparse Polynomial Hermite InterpolationAbstract:We present Hermite polynomial interpolation algorithms that for a sparse univariate polynomial $f$ with coefficients from a field compute the polynomial from fewer points than the classical algorithms. If the interpolating polynomial $f$ has $t$ terms, our algorithms, which use randomization, require argument/value triples $(w^i,f(w^i),f'(w^i))$ for $i = 0,\ldots, t + \lceil (t + 1)/2 \rceil - 1$, where $w$ is randomly sampled and the probability of a correct output is determined from a degree bound for $f$. With $f'$ we denote the derivative of $f$. Our algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases. We have algorithms that can correct errors in the points by oversampling at a limited number of good values. If an upper bound $B \geq t$ for the number of terms is given, our algorithms use a randomly selected $w$ and, with high probability, $\lceil t/2 \rceil + B$ triples, but then never return an incorrect output. The algorithms are based on Prony's sparse interpolation algorithm. While Prony's algorithm and its variants use fewer values, namely $2t + 1$ and $t + B$ values $f(w^i)$ respectively, they need more arguments $w^i$. The situation mirrors that in algebraic error correcting codes, where the Reed-Solomon code requires fewer values than the multiplicity code, which is based on Hermite interpolation, but the Reed-Solomon code requires more distinct arguments. Our sparse Hermite interpolation algorithms can interpolate polynomials over finite fields and over the complex numbers, and from floating point data. Our Prony-based approach does not encounter the Birkhoff phenomenon of Hermite interpolation, when a gap in the derivative values causes multiple interpolants. We can interpolate from $t + 1$ values of $f$ and $2t - 1$ values of $f'$.
-
[+]
Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio and Mohab Safey El Din.
Algorithms for Discrete Differential Equations of Order 1Abstract:Discrete differential equations of order 1 are equations relating polynomially $F(t,u)$, a power series in $t$ with polynomial coefficients in a “catalytic” variable $u$, and one of its specializations, say $F(t,1)$. Such equations are ubiquitous in combinatorics, notably in the enumeration of maps and walks. When the solution $F$ is unique, a celebrated result by Bousquet-M\'elou, reminiscent of Popescu's theorem in commutative algebra, states that $F$ is \emph{algebraic}. We address algorithmic and complexity questions related to this result. In generic situations, we first revisit and analyze known algorithms, based either on polynomial elimination or on the guess-and-prove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guess-and-prove. In the general case (no genericity assumptions), we prove that the total arithmetic size of the algebraic equations for $F(t,1)$ is bounded polynomially in the size of the input discrete differential equation, and that one can compute such equations in polynomial time.
-
[+]
Evangelos Bartzos, Ioannis Emiris, Ilias S. Kotsireas and Charalambos Tzamos.
Bounding the number of Roots for Multi-Homogeneous SystemsAbstract:Determining the number of solutions of a multi-homogeneous polynomial system is a fundamental problem in algebraic geometry. The multi-homogeneous Bézout (m-Bézout) number bounds from above the number of non-singular solutions of a multi-homogeneous system, but its computation is a #P-hard problem. Recent work related the m-Bézout number of certain multi-homogeneous systems derived from rigidity theory with graph orientations, cf Bartzos et al. A first generalization applied graph orientations for bounding the root count of a multi-homogeneous system that can be modeled by simple undirected graphs, as shown by three of the authors. Here, we prove that every multi-homogeneous system can be modeled by hypergraphs and the computation of its m-Bézout bound is related to constrained hypergraph orientations. Thus, we convert the algebraic problem of bounding the roots of a polynomial system to a purely combinatorial problem of analyzing the structure of a hypergraph. We also provide a formulation of the orientation problem as a constraint satisfaction problem (CSP), hence leading to an algorithm that computes the multi-homogeneous bound by finding constrained hypergraph orientations.
-
[+]
George Labahn, Vincent Neiger, Thi Xuan Vu and Wei Zhou.
Rank-Sensitive Computation of the Rank Profile of a Polynomial MatrixAbstract:Consider a matrix $\mathbf{F} \in \mathbb{K}^{m \times n}$ of univariate polynomials over a field $\mathbb{K}$. We study the problem of computing the column rank profile of $\mathbf{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 $\mathbf{F}$ with a rank-sensitive complexity of $\tilde O(r^{\omega-2} n (m+D))$ operations in $\mathbb{K}$. Here, $D$ is the sum of row degrees of $F$, $\omega$ is the exponent of matrix multiplication, and $\tilde O(\cdot)$ hides logarithmic factors.
-
[+]
Jérémy Berthomieu, Vincent Neiger and Mohab Safey El Din.
Faster change of order algorithm for Gröbner bases under shape and stability assumptionsAbstract:Solving polynomial systems whose solution set is finite is usually done in two main steps: compute a Gröbner basis for the degree reverse lexicographic order, and perform a change of order to find the lexicographic Gröbner basis. The second step is generally considered as better understood, in terms of algorithms and complexity. Yet, after two decades of progress on the first step, it turns out that the change of order now takes a large part of the solving time for many instances, including those that are generic or reached after applying a random change of variables. Like the fastest known change of order algorithms, this work focuses on the latter situation, where the ideal defined by the system satisfies structural properties. First, the ideal has a shape lexicographic Gröbner basis. Second, the set of leading terms with respect to the degree reverse lexicographic order has a stability property; in particular, the multiplication matrix of the smallest variable is computed for free from the input Gröbner basis. The current fastest algorithms rely on the sparsity of this multiplication matrix to find its minimal polynomial efficiently using Wiedemann's approach. This paper starts from the observation that this sparsity is a consequence of an algebraic structure, which can be exploited to represent the matrix concisely as a univariate polynomial matrix. We show that the Hermite normal form of that matrix yields the sought lexicographic Gröbner basis, under assumptions which cover the shape position case. This leads to an improved complexity bound for the second step. The practical benefit is also confirmed via implementations based on the state-of-the-art software libraries msolve and PML.
-
[+]
Xavier Caruso, Tristan Vaccon and Thibaut Verron.
On Polynomial Ideals And Overconvergence In Tate AlgebrasAbstract: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. We prove that ideals which are spanned by polynomials admit a Tate Gröbner basis made of polynomials, and we propose an algorithm, leveraging Mora's weak normal form algorithm, for computing it. As a result, the size of the output of this algorithm grows linearly with the precision. Following the same ideas, we propose an algorithm which computes an overconvergent basis for an ideal spanned by overconvergent series. Finally, we prove the existence of a universal analytic Gröbner basis for polynomial ideals in Tate algebras, compatible with all convergence radii.
-
[+]
Yi Zhou and Mark van Hoeij.
Desingularization and p-Curvature of Linear Recurrence OperatorsAbstract:Linear recurrence operators in characteristic $p$ are classified by their $p$-curvature. For a recurrence operator $L$, denote by $\chi(L)$ the characteristic polynomial of its $p$-curvature. We can obtain information about the factorization of $L$ by factoring $\chi(L)$. The main theorem of this paper gives an unexpected relation between $\chi(L)$ and true singularities of $L$. An application is to speed up the current best algorithm for computing $\chi(L)$ by first desingularizing $L$. Another contribution of this paper is faster desingularization.
-
[+]
Christian Eder, Viktor Levandovskyy, Julien Schanz, Simon Schmidt, Andreas Steenpass and Moritz Weber.
Existence of Quantum Symmetries for Graphs on up to Seven Vertices: a Computer Based ApproachAbstract:The symmetries of a finite graph are described by its automorphism group; in the setting of Woronowicz's quantum groups, a notion of a quantum automorphism group has been defined by Banica capturing the quantum symmetries of the graph. In general, there are more quantum symmetries than symmetries and it is a non-trivial task to determine when this is the case for a given graph: The question is whether or not the algebra associated to the quantum automorphism group is commutative. We use Gröbner bases in order to tackle this problem; the implementation uses GAP and the SINGULAR package LETTERPLACE. We determine the existence of quantum symmetries for all connected, undirected graphs without multiple edges and without self-edges, for up to seven vertices. As an outcome, we infer within our regime that a classical automorphism group of order one or two is an obstruction for the existence of quantum symmetries.
-
[+]
Apostolos Chalkis, Christina Katsamaki and Josue Tonelli-Cueto.
On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric CurvesAbstract:Given a parametric polynomial curve $\gamma:[a,b]\rightarrow \mathbb{R}^n$, how can we sample a random point $\mathfrak{x}\in \mathrm{im}(\gamma)$ in such a way that it is distributed uniformly with respect to the arc-length? Unfortunately, we cannot sample exactly such a point—even assuming we can perform exact arithmetic operations. So we end up with the following question: how does the method we choose affect the quality of the approximate sample we obtain? In practice, there are many answers. However, in theory, there are still gaps in our understanding. In this paper, we address this question from the point of view of complexity theory, providing bounds in terms of the size of the desired error.
-
[+]
Dmitrii Pavlov and Gleb Pogudin.
On Realizing Differential-Algebraic Equations by Rational Dynamical SystemsAbstract:Real-world phenomena can often be conveniently described by dynamical systems (that is, ODE systems in the state-space form). However, if one observes the state of the system only partially, the observed quantities (outputs) and the inputs of the system can typically be related by more complicated differential-algebraic equations (DAEs). Therefore, a natural question (referred to as the realizability problem) is: given a differential-algebraic equation (say, fitted from data), does it come from a partially observed dynamical system? A special case in which the functions involved in the dynamical system are rational is of particular interest. For a single differential-algebraic equation in a single output variable, Forsman has shown that it is realizable by a rational dynamical system if and only if the corresponding hypersurface is unirational, and he turned this into an algorithm in the first-order case. In this paper, we study a more general case of single-input-single-output equations. We show that if a realization by a rational dynamical system exists, the system can be taken to have the dimension equal to the order of the DAE. We provide a complete algorithm for first-order DAEs. We also show that the same approach can be used for higher-order DAEs using several examples from the literature.
-
[+]
Reinhold Burger.
Enumerating Denumerable Sets in Polynomial Time via the Schröder-Bernstein TheoremAbstract:We give methods to develop efficiently computable bijections between the rational numbers and the positive integers. That is, given a rational number in the standard representation a/b, where a,b are integers, we can compute n, its position in the enumeration, in time polynomial in the bit lengths of a and b. Conversely, given a position n in the enumeration, we can compute the corresponding rational number a/b at that position in time polynomial in the bit length of n. This is not the first such bijection to have appeared in the literature. However, we submit that the method presented here, which uses König's proof of the Schröder-Bernstein Theorem, is relatively simple to understand, and has a broad application. It can be applied to enumerating other denumerable sets. As an example, we use it to give a polynomial-time bijection between the algebraic numbers and the positive integers.
-
[+]
Yuan Chang, Jesús De Loera and William Wesley.
Rado Numbers and SAT ComputationsAbstract:Given a linear equation $\mathcal{E}$, the $k$-color Rado number $R_k(\mathcal{E})$ is the smallest integer $n$ such that every $k$-coloring of $\{1,2,3,\dots,n\}$ contains a monochromatic solution to $\mathcal E$. The degree of regularity of $\mathcal E$, denoted $dor(\mathcal E)$, is the largest value $k$ such that $R_k(\mathcal E)$ is finite. In this article we present new theoretical and computational results about the Rado numbers $R_3(\mathcal{E})$. We use SAT solvers to compute many new values of the three-color Rado numbers $R_3(ax+by+cz = 0)$ for fixed integers $a,b,$ and $c$. We also give a SAT-based method to compute infinite families of these numbers. In particular, we show that the value of $R_3(x-y = (m-2) z)$ is equal to $m^3-m^2-m-1$ for $m\ge 3$. This resolves a conjecture of Myers and implies the conjecture that the generalized Schur numbers $S(m,3) = R_3(x_1+x_2 + \dots x_{m-1} = x_m)$ equal $m^3-m^2-m-1$ for $m\ge 3$. Our SAT solver computations, combined with our new combinatorial results, give improved bounds on $dor(ax+by = cz)$ and exact values for $1\le a,b,c\le 5 $. We also give counterexamples to a conjecture of Golowich.
-
[+]
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray and Daniel Roche.
Random Primes without Primality TestingAbstract:Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate the total running time. We propose a new variant of dynamic evaluation, applied to a randomly-chosen (composite) integer. The transformation we propose can apply to any algorithm in the algebraic RAM model, even allowing randomization. The resulting transformed algorithm avoids any primality tests and will, with constant positive probability, have the same result as the original computation modulo a randomly-chosen prime. As an application, we demonstrate how to compute the exact number of nonzero terms in an unknown integer polynomial in quasi-linear time. We also show how the same algorithmic transformation technique can be used for computing modulo random irreducible polynomials over a finite field.
-
[+]
Michela Ceria and Ferdinando Mora.
A Degroebnerization Approach to Algebraic Statistics.Abstract:Gröbner bases are one of the most employed tools in Algebraic Statistics. However, the same supporters of Gröbner bases in Algebraic Statistics pointed out a weakness of their use, namely that in Example 7 [of Pistone–Riccomango–Rogantin] the model $\{1, x_1 , x_1^2 , x_2 , x_2^2 \}$ is the most symmetric of the models in the statistical fan. [However, in that setting Gröbner bases fail.] In fact, to destroy symmetry is a feature of Gröbner basis computation, as term orderings intrinsically do not preserve symmetries, which are often preferred in statistical models. The aim of this paper is to show how Degroebnerization can give a complete symmetric solution to the problem posed in Example 7. The paper further investigates the potential applications of our new algorithm to describe design ideals into different algebraic settings: in fact the degré zero de Möller allows to describe a (finite) vector space V as a k-module over a (not-necessarily commutative) polynomial ring over a finite set of the variables $x_1, \ldots, x_n$ by giving a linear basis $\{v_1 , \ldots , v_N \}$ of it and describing the action of variables by classical Auzinger-Stetter matrices Under this description a design can therefore be described as a design ideal $I \subset P$ with either $P = k[x_1 , \ldots , x_n ]$ with Tamari arithmetics or $P = k\langle x_1 , \ldots , x_n \rangle$. Theorem 1.1 holds, a fraction of a design can be described as an ideal of $V = P/I = \text{Span}_k \{v_1 , \ldots , v_N \}$ and normal forms can be obtained via Lundqvist's approach.