Full papers

Details on the ISSAC 2016 Paper Review Process were published published here. Following this process the program committee has accepted the papers below. Click on the plus symbol to view a paper's abstract.
The full papers will appear in the ACM Digital Library soon. Conference participants will receive USB proceedings at registration.

List of Accepted Papers

  1. [+] Juan Gerardo Alcazar, Carlos Hermoso and Georg Muntingh. Detecting Similarities of Rational Space Curves.

    We provide an algorithm to check whether two rational space curves are related by a similarity. The algorithm exploits the relationship between the curvatures and torsions of two similar curves, which is formulated in a computer algebra setting. Helical curves, where curvature and torsion are proportional, need to be distinguished as a special case. The algorithm is easy to implement, as it involves only standard computer algebra techniques, such as greatest common divisors and resultants, and Gröbner bases for the special case of helical curves.

  2. [+] Xavier Allamigeon, Stéphane Gaubert and Mateusz Skomra. Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms.

    A general issue in computational optimization is to develop combinatorial algorithms for semidefinite programming. We address this issue when the base field is nonarchimedean. We provide a solution for a class of semidefinite feasibility problems given by generic matrices with a Metzler type sign pattern. Our approach is based on tropical geometry. We define tropical spectrahedra as the images by the valuation of nonarchimedean spectrahedra, and provide an explicit description of the tropical spectrahedra arising from the aforementioned class of problems. We deduce that the tropical semidefinite feasibility problems obtained in this way are equivalent to stochastic mean payoff games, which have been well studied in algorithmic game theory. This allows us to solve nonarchimedean semidefinite feasibility problems using algorithms for stochastic games. These algorithms are of a combinatorial nature and work for large instances.

  3. [+] Parisa Alvandi, Mahsa Kazemi and Marc Moreno Maza. Computing Limits of Real Multivariate Rational Functions.

    We present an algorithm for determining the existence of the limit of a real multivariate rational function at a given point. When the limit exists, the algorithm computes it, without making any assumptions on the number of variables.

    We rely on triangular decomposition of semi-algebraic systems and multivariate Puiseux series for isolating the branches of a real algebraic set that are passing through a point. Then, a process, which extends the work of Cadavid, Molina and Velez, reduces the multivariate setting to computing limits of bivariate rational functions.

  4. [+] Eric Bach and Rex Fernando. Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test.

    We study a variant of the Miller-Rabin primality test, which only looks at the last $z + 1$ powers of the base. This test is betweeen Miller-Rabin and Fermat in terms of strength. For $z = 1$ the test can be thought of as a variant of the Solovay-Strassen test. We show that for every $z \leq 0$ this test has infinitely many "Carmichael" numbers. We also give empirical results on the rate of growth of the test's "Carmichael" numbers, noting that the growth rate decreases geometrically with increasing $z$. We provide some heuristic evidence for this pattern. We also extend our existence result to some generalizations of Miller-Rabin that use $b$-th powers instead of squares.

  5. [+] Eric Bach and Bryce Sandlund. Baby-Step Giant-Step Algorithms for the Symmetric Group.

    We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$. When $a,b \in S$, a solution $g \in G$ to $a^g = b$ can be thought of as a kind of logarithm. In this paper, we study the case where $G = S_n$, and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets $A, B \subseteq S_n$ such that every $\sigma \in S_n$ can be written as a product $ab$ of elements $a \in A$ and $b \in B$. Our deterministic procedure is close to optimal, in the sense that $A$ and $B$ can be computed efficiently and $|A|$ and $|B|$ are not too far from $\sqrt n!$ in size. We also analyze randomized "collision" algorithms for the same problem.

  6. [+] Moulay Barkatou, Thomas Cluzeau, Jacques-Arthur Weil and Lucia Di Vizio. Computing the Lie Algebra of the Differential Galois Group of a Linear Differential System.

    We consider a linear differential system $[A] : {\bf y}'=A \, {\bf y}$, where $A$ has coefficients in the differential field $\mathbb{C}(x)$. The differential Galois group $G$ of $[A]$ is a linear algebraic group which measures the algebraic relations among solutions. Although there exist general algorithms to compute $G$, none of them is either practical or implemented. This paper proposes an algorithm, of probabilistic nature, to compute the Lie algebra $\mathfrak{g}$ of $G$. The algorithm is implemented in Maple.

  7. [+] Ruben Becker, Michael Sagraloff, Vikram Sharma, Juan Xu and Chee Yap Complexity Analysis of Root Clustering for a Complex Polynomial.

    Let $F(z)$ be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural $\varepsilon$-clusters of roots of $F(z)$ in some box region $B_0$ in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters.

    Our computational model assumes that arbitrarily good approximations of the coefficients of $F$ are provided by means of an oracle at the cost of reading the coefficients. Our algorithmic techniques come from a companion paper [3] and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Schönhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice.

  8. [+] Matías R. Bender, Jean-Charles Faugère, Ludovic Perret and Elias Tsigaridas. A Superfast Randomized Algorithm to Decompose Binary Forms.

    Symmetric Tensor Decomposition is a major problem that arises in areas such as signal processing, statistics, data analysis and computational neuroscience. It is equivalent to write a homogeneous polynomial in $n$ variables of degree $D$ as a sum of $D$-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We consider the decomposition of binary forms, that corresponds to the decomposition of symmetric tensors of dimension $2$ and order $D$. This problem has its roots in Invariant Theory, where the decompositions are known as canonical forms. As part of that theory, different algorithms were proposed for the binary forms. In recent years, those algorithms were extended for the general symmetric tensor decomposition problem.

    We present a new randomized algorithm that enhances the previous approaches with results from structured linear algebra and techniques from linear recurrent sequences. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have quadratic complexity bounds. We compute a symbolic minimal decomposition in $O(\mathtt{M}(D) \log(D))$ arithmetic operations, where $\mathtt{M}(D)$ is the complexity of multiplying two polynomials of degree $D$. We approximate the terms of the decomposition with an error of $2^{-\varepsilon}$, in $O\big(D \log^2(D)\big(\log^2(D) + \log(\epsilon)\big)\big)$ arithmetic operations. To bound the size of the representation of the coefficients involved in the decomposition, we bound the algebraic degree of the problem by $\min(\mathrm{rank}, D-\mathrm{rank}+1)$. When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, $\widetilde{O}_B(D \ell + D^4 + D^3 \tau)$ bit operations, where $\tau$ is the maximum bitsize of the coefficients and $2^{-\ell}$ is the relative error of the terms in the decomposition.

  9. [+] Valérie Berthé, Loick Lhote and Brigitte Vallée. Analysis of the Brun Gcd algorithm.

    We introduce and study a multiple Gcd algorithm that is a natural extension of the usual Euclid algorithm, and coincides with it for two entries; it performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun. We perform the average-case analysis of this algorithm, and prove that the mean number of steps is linear with respect to the size of the entry. The method relies on dynamical analysis, and is based on the study of the underlying Brun dynamical system. The dominant constant of the analysis is related to the entropy of this dynamical system. We also compare this average-case behavior to another extension of the Euclid algorithm, proposed by Knuth, and already analyzed by the authors.

  10. [+] Jérémy Berthomieu and Jean-Charles Faugère. Linear Algebra Solver for Linear Recurrence Relations of Sequences Tuples and P-Recursive Sequences.

    First, we present an algorithm for computing the Gröbner basis of the submodule of linear recurrence relations with constant coefficients of multiple $n$-dimensional sequences. This algorithm is a straightforward generalization of Scalar-FGLM, designed in 2015, which computes the ideal of relations of one $n$-dimensional sequence. It relies on extracting a full-rank submatrix of a concatenation of multi-Hankel matrices.

    P-recursive sequences, as defined by Stanley in 1980, are a greater class of sequences satisfying linear recurrence relations with polynomial coefficients. From a P-recursive sequence $(u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}$, one can make the tuple of sequences $(\mathbf{i}^{\mathbf{j}}\,u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}$ and call the aforementioned generalization of Scalar-FGLM for computing the relations. However, this strategy yields useless relations and the module of relations of a P-recursive sequence has an extra structure of $0$-dimensional right ideal of an Ore algebra; Hence, in order to take advantage of this extra structure we design then a more efficient algorithm for computing the ideal of relations.

    Finally, we show how to incorporate Gröbner bases computations in an Ore algebra $\mathbb{K}\left\langle t_1,\ldots,t_n,x_1,\ldots,x_n\right\rangle$, with commutators $x_k\,x_{\ell}-x_{\ell}\,x_k=t_k\,t_{\ell}-t_{\ell}\,t_k= t_k\,x_{\ell}-x_{\ell}\,t_k=0$ for $k\neq\ell$ and $t_k\,x_k-x_k\,t_k=x_k$, into the algorithm designed for $P$-recursive sequences. This allows us to compute faster the elements of the Gröbner basis which are in the ideal spanned by the first relations.

  11. [+] Bernard Bonnard, Jean-Charles Faugère, Alain Jacquemard, Mohab Safey El Din and Thibaut Verron. Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery.

    Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures.

    Geometric optimal control leads us here to analyze meromorphic vector fields depending upon physical parameters, and having their singularities defined by a determinantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in some prescribed semi-algebraic set.

    We develop a dedicated algorithm for real root classification of the singularities of the rank defects of a polynomial matrix, cut with a given semi-algebraic set. The algorithm works under some genericity assumptions which are easy to check. These assumptions are not so restrictive and are satisfied in the aforementioned application. As more general strategies for real root classification do, our algorithm needs to compute the critical loci of some maps, intersections with the boundary of the semi-algebraic domain, etc. In order to compute these objects, the determinantal structure is exploited through a stratification by the rank of the polynomial matrix. This speeds up the computations by a factor 100. Furthermore, our implementation is able to solve the application in medical imagery, which was out of reach of more general algorithms for real root classification. For instance, computational results show that the contrast problem where one of the matters is water is partitioned into three distinct classes.

  12. [+] Alin Bostan, Xavier Caruso and Éric Schost. Computation of the Similarity Class of the $p$-Curvature.

    The $p$-curvature of a system of linear differential equations in positive characteristic $p$ is a matrix that measures how far the system is from having a fundamental matrix of polynomial solutions. We show that the similarity class of the p-curvature can be determined without computing the $p$-curvature itself. More precisely, we design an algorithm for computing the invariant factors of the $p$-curvature in time quasi-linear in $\sqrt{p}$. This is much less than the size of the p-curvature, which is generally linear in $p$. The new algorithm allows to answer a question originating from the study of the Ising model in statistical physics.

  13. [+] Alin Bostan, Gilles Christol and Philippe Dumas. Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field.

    We address the question of computing one selected term of an algebraic power series. In characteristic zero, the best algorithm currently known for computing the $N$th coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in $\sqrt{N}$. We show that over a prime field of positive characteristic $p$, the complexity can be lowered to $O(\log N)$. The mathematical basis for this dramatic improvement is a classical theorem stating that a formal power series with coefficients in a finite field is algebraic if and only if the sequence of its coefficients can be generated by an automaton. We revisit and enhance two constructive proofs of this result for finite prime fields. The first proof uses Mahler equations, whose sizes appear to be prohibitively large. The second proof relies on diagonals of rational functions; we turn it into an efficient algorithm, of complexity linear in $\log N$ and quasi-linear in $p$.

  14. [+] Alin Bostan, Louis Dumont and Bruno Salvy. Efficient Algorithms for Mixed Creative Telescoping.

    Creative telescoping is a powerful computer algebra paradigm —initiated by Doron Zeilberger in the 90's— for dealing with definite integrals and sums with parameters. We address the mixed continuous-discrete case, and focus on the integration of bivariate hypergeometric-hyperexponential terms. We design a new creative telescoping algorithm operating on this class of inputs, based on a Hermite-like reduction procedure. The new algorithm has two nice features: it is efficient and it delivers, for a suitable representation of the input, a minimal-order telescoper. Its analysis reveals tight bounds on the sizes of the telescoper it produces.

  15. [+] Daniel Brake, Jonathan Hauenstein and Alan Liddell. Numerically Validating the Completeness of the Real Solution Set of a System of Polynomial Equations.

    Computing the real solutions to a system of polynomial equations is a challenging problem, particularly verifying that all solutions have been computed. We describe a method, combining numerical algebraic geometry and sums of squares programming, which tests whether a given set of real solutions is "complete". Specifically, we test whether the Zariski closure of that given set is the solution set of the real radical of the ideal generated by the given polynomials. Examples with finitely and infinitely many real solutions are provided, along with an example having polynomial inequalities.

  16. [+] Cornelius Brand and Michael Sagraloff. On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection.

    Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the system as well as a corresponding separating linear form l with coefficients of small bit size. For computing l, we need to project the solutions into one dimension along O(n) distinct directions but no further algebraic manipulations. The solutions are then directly reconstructed from the considered projections. The first step is deterministic, whereas the second step uses randomization, thus being Las-Vegas.

    The theoretical analysis of our approach shows that the overall cost for the two problems considered above is dominated by the cost of carrying out the projections. We also give bounds on the bit complexity of our algorithms that are exclusively stated in terms of the number of variables, the total degree and the bitsize of the input polynomials.

  17. [+] Xavier Caruso, David Roe and Tristan Vaccon. Division and Slope Factorization of $p$-Adic Polynomials.

    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.

  18. [+] Shaoshi Chen, Qing-Hu Hou, George Labahn and Rong-Hua Wang. Existence Problem of Telescopers: Beyond the Bivariate Case.

    In this paper, we solve the existence problem of telescopers for rational functions in three discrete variables. We reduce the problem to that of deciding the summability of bivariate rational functions, which has been solved recently. The existence criteria we present is needed for detecting the termination of Zeilberger's algorithm to the function classes studied in this paper.

  19. [+] Shaoshi Chen, Manuel Kauers and Christoph Koutschan. Reduction-Based Creative Telescoping for Algebraic Functions.

    Continuing a series of articles in the past few years on creative telescoping using reductions, we develop a new algorithm to construct minimal telescopers for algebraic functions. This algorithm is based on Trager's Hermite reduction and on polynomial reduction, which was originally designed for hyperexponential functions and extended to the algebraic case in this paper.

  20. [+] Mohab Safey El Din and Pierre-Jean Spaenlehauer. Critical Point Computations on Smooth Varieties: Degree and Complexity Bounds.

    Let $V\subset \mathbb{C}^n$ and $g$ be an $n$-variate polynomial with rational coefficients. Computing the critical points of the map that evaluates $g$ at the points of $V$ is a cornerstone of several algorithms in real algebraic geometry and optimization.

    Under the assumption that the critical locus is finite and that the projective closure of $V$ is smooth, we provide sharp upper bounds on these degrees which depend only on $\deg(g)$ and the degrees of the generic polar varieties associated to $V$.

    Hence, in some special cases where the degrees of the generic polar varieties do not reach the worst-case bounds, this implies that the number of critical points of the evaluation map of $g$ is less than the currently known degree bounds.

    We show that, given a lifting fiber of $V$, a slight variant of an algorithm due to Bank, Giusti, Heintz, Matera, Lecerf and Solerno allows to compute these critical points in time which is quadratic in this bound up to logarithmic factors, linear in the complexity of evaluating the input system and polynomial in the number of variables and the maximum degree of the input polynomials.

  21. [+] Leo Ducas and Thomas Prest. Fast Fourier Orthogonalization.

    The classical fast Fourier transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring $R[x]/(x^d -1)$ — a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant.

    In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of matrices with circulant blocks of size $d\times d$. We show that, when $d$ is composite, it is possible to proceed to the orthogonalization in an inductive way —up to an appropriate re-indexation of rows and columns. This leads to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the nearest plane algorithm. The complexity of both algorithms may be brought down to $O(n \log n)$.

    Our results easily extend to cyclotomic rings, and can be adapted to Gaussian samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

  22. [+] Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé and Gilles Villard. Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix.

    Certificates to a linear algebra computation are additional data structures for each output, which can be used by a—possibly randomized—verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that compute a certificate for the minimal polynomial of sparse or structured nxn matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.

  23. [+] Wayne Eberly. Selecting Algorithms for Black Box Matrices: Checking for Matrix Properties That Can Simplify Computations.

    Processes to automate the selection of appropriate algorithms for various matrix computations are described. In particular, processes to check for, and certify, various matrix properties for black-box matrices are presented. These include sparsity patterns and structural properties that allow "superfast" algorithms to be used in place of black-box algorithms. Matrix properties that hold generically, and allow the use of matrix preconditioning to be reduced or eliminated, can also be checked for and certified - notably including in the small-field case, where this presently has the greatest impact on the efficiency of the computation.

  24. [+] Christian Eder, Brice Boyer, Jean-Charles Faugère, Sylvian Lachartre and Fayssal Martani. GBLA - Gröbner Basis Linear Algebra Package.

    This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea of Faugère and Lachartre (GB reduction). We further exploit underlying structures in matrices generated during Gröbner basis computations in algo- rithms like F4 or F5 taking advantage of block patterns by using a special data structure called multilines. Moreover, we discuss a new order of operations for the reduction process. In various different experimental results we show that GBLA performs better than GB reduction or Magma in sequential computations (up to 40% faster) and scales much better than GB reduction for a higher number of cores: On 32 cores we reach a scaling of up to 26. GBLA is up to 7 times faster than GB reduction. Further, we compare different parallel schedulers GBLA can be used with. We also developed a new advanced storage format that exploits the fact that our matrices are coming from Gröbner basis computations, shrinking storage by a factor of up to 4. A huge database of our matrices is freely avail- able with GBLA.

  25. [+] Ioannis Z. Emiris, Angelos Mantzaflaris and Elias Tsigaridas. On the Bit Complexity of Solving Bilinear Polynomial Systems.

    We bound the Boolean complexity of computing isolating hyperboxes for all complex roots of systems of bilinear polynomials. The resultant of such systems admits a family of determinantal Sylvester-type formulas, which we make explicit by means of homological complexes. The computation of the determinant of the resultant matrix is a bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector products, corresponding to multivariate polynomial multiplication. For zero-dimensional systems, we arrive at a primitive element and a rational univariate representation of the roots. The overall bit complexity of our probabilistic algorithm is $\widetilde{O}_B(n^4 D^4 + n^2D^4 \tau)$, where $n$ is the number of variables, $D$ equals the bilinear Bézout bound, and $\tau$ is the maximum coefficient bitsize. Finally, a careful infinitesimal symbolic perturbation of the system allows us to treat degenerate and positive dimensional systems, thus making our algorithms and complexity analysis applicable to the general case.

  26. [+] Jean-Charles Faugère, Pierre-Jean Spaenlehauer and Jules Svartz. Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems.

    Bézout's theorem states that dense generic systems of $n$ multivariate quadratic equations in $n$ variables have $2^n$ solutions over algebraically closed fields. When only a small subset $\mathrm{M}$ of monomials appear in the equations (fewnomial systems), the number of solutions may decrease dramatically. We focus in this work on subsets of quadratic monomials $\mathrm{M}$ such that generic systems with support $\mathrm{M}$ do not admit any solution at all. For these systems, Hilbert's Nullstellensatz ensures the existence of algebraic certificates of inconsistency. However, up to our knowledge all known bounds on the sizes of such certificates —including those which take into account the Newton polytopes of the polynomials— are exponential in $n$. Our main results show that if the inequality $2\lvert \mathrm{M}\rvert-2n \leq \sqrt{1+8\nu}-1$ holds for a quadratic fewnomial system — where $\nu$ is the matching number of a graph associated with $\mathrm{M}$ — then there exists generically a certificate of inconsistency of linear size (measured as the number of coefficients in the ground field $\mathrm{K}$). Moreover this certificate can be computed within a polynomial number of arithmetic operations. Next, we evaluate how often this inequality holds, and we give evidence that the probability that the inequality is satisfied depends strongly on the number of squares. More precisely, we show that if $\mathrm{M}$ is picked uniformly at random among the subsets of $n+k+1$ quadratic monomials containing at least $\Omega(n^{1/2+\varepsilon})$ squares, then the probability that the inequality holds tends to $1$ as $n$ grows. Interestingly, this phenomenon is related with the matching number of random graphs in the Erdős-Renyi model. Finally, we provide experimental results showing that certificates in inconsistency can be computed for systems with more than 10000 variables and equations.

  27. [+] Hao Fu and Guoniu Han. Computer Assisted Proof for Apwenian Sequences.

    An infinite $\pm 1$-sequence is called Apwenian if its Hankel determinant of order n divided by $2n-1$ is an odd number for every positive integer n. In 1998, Allouche, Peyrière, Wen and Wen discovered and proved that the Thue-Morse sequence is an Apwenian sequence by direct determinant manipulations. Recently, Bugeaud and Han re-proved the latter result by means of an appropriate combinatorial method. By significantly improving the combinatorial method, we find several new Apwenian sequences with Computer Assistance. This research has application in Number Theory to determining the irrationality exponents of some transcendental numbers.

  28. [+] Richard Gustavson, Alexey Ovchinnikov and Gleb Pogudin. Bounds for Orders of Derivatives in Differential Elimination Algorithms.

    We compute an upper bound for the orders of derivatives in the Rosenfeld-Groebner algorithm. This algorithm computes a regular decomposition of a radical differential ideal in the ring of differential polynomials over a differential field of characteristic zero with an arbitrary number of commuting derivations. This decomposition can then be used to test for membership in the given radical differential ideal. In particular, this algorithm allows us to determine whether a system of polynomial PDEs is consistent.

    Previously, the only known order upper bound was given by Golubitsky, Kondratieva, Moreno Maza, and Ovchinnikov for the case of a single derivation. We achieve our bound by associating to the algorithm antichain sequences whose lengths can be bounded using the results of Leon Sanchez and Ovchinnikov.

  29. [+] Zhiwei Hao, Erich L Kaltofen and Lihong Zhi. Numerical Sparsity Determination and Early Termination.

    Ankur Moitra in his paper at STOC 2015 has given an in-depth analysis of how oversampling improves the conditioning of the arising Prony systems for sparse interpolation and signal recovery from numeric data. Moitra assumes that oversampling is done for a number of samples beyond the actual sparsity of the polynomial/signal. We give an algorithm that can be used to compute the sparsity and estimate the minimal number of samples needed in numerical sparse interpolation. The early termination strategy of polynomial interpolation has been incorporated in the algorithm: by oversampling at a small number of extra sample points we can diagnose that the sparsity has not been reached.

    Our algorithm still has to make a guess, the number $\zeta$ of oversamples, and we show by example that if $\zeta$ is guessed too small, premature termination can occur, but our criterion is numerically more accurate than that by Kaltofen, Lee and Yang [Proc. SNC 2011]. For heuristic justification one has available the multivariate early termination theorem by Kaltofen and Lee [JSC 2003] for exact arithmetic, and the numeric Schwartz-Zippel Lemma by Kaltofen, Yang, Zhi [Proc. SNC 2007]. A main contribution here is a modified proof of the Theorem by Kaltofen and Lee that permits starting the sequence at the point $(1,...,1)$, for scalar fields of characteristic not equal to 2 (in characteristic 2 counter-examples are known).

  30. [+] David Harvey, Joris van der Hoeven and Gregoire Lecerf. Fast Polynomial Multiplication over $F_{2^{60}}$.

    Can post-Schönhage—Strassen multiplication algorithms be competitive in practice for large input sizes? So far, the GMP library still outperforms all implementations of the recent, asymptotically more efficient algorithms for integer multiplication by Fürer, De—Kurur—Sah—Saptharishi, and ourselves. In this paper, we show how central ideas of our recent asymptotically fast algorithms turn out to be of practical interest for multiplication of polynomials over finite fields of characteristic two. Our Mathemagix implementation is based on the automatic generation of assembly codelets. It outperforms existing implementations in large degree, especially for polynomial matrix multiplication over finite fields.

  31. [+] Albert Heinle and Viktor Levandovskyy. A Factorization Algorithm for $G$-Algebras and Applications.

    It has been recently discovered by Bell, Heinle and Levandovskyy that a large class of algebras, including the ubiquitous $G$-algebras, are finite factorization domains (FFD for short). Utilizing this result, we contribute an algorithm to find all distinct factorizations of a given element $f \in \mathcal{G}$, where $\mathcal{G}$ is any $G$-algebra, with minor assumptions on the underlying field. Moreover, the property of being an FFD, in combination with the factorization algorithm, enables us to propose an analogous description of the factorized Gröbner basis algorithm for $G$-algebras. This algorithm is useful for various applications, e.g. in analysis of solution spaces of systems of linear partial functional equations with polynomial coefficients, coming from $\mathcal{G}$. Additionally, it is possible to include inequality constraints for ideals in the input.

  32. [+] Jiaxiong Hu and Michael Monagan. A Fast Parallel Sparse Polynomial GCD Algorithm.

    We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented the algorithm in Cilk C for 31, 63 and 127 bit primes. We compare it with Maple and Magma's implementations of Zippel's GCD algorithm.

  33. [+] Hui Huang. New Bounds for Hypergeometric Creative Telescoping.

    Based on a modified version of Abramov-Petkovsek reduction, a new algorithm to compute minimal telescopers for bivariate hypergeometric terms was developed last year. We investigate further in this paper and present a new argument for the termination of this algorithm, which provides an independent proof of the existence of telescopers and even enables us to derive lower as well as upper bounds for the order of telescopers for hypergeometric terms. Compared to the known bounds in the literature, our bounds are sometimes better, and never worse than the known ones.

  34. [+] Ming-Deh Huang and Lian Liu. Constructing Small Generating Sets for the Multiplicative Groups of Algebras over Finite Fields.

    We consider computational problems concerning algebras over finite fields. In particular, we propose an algorithm for finding a small generating set for the multiplicative group of $\mathrm{GF}(p)[x]/F$, where $p$ is a prime number and $F$ is an arbitrary polynomial in $\mathrm{GF}(p)[x]$. Based on this result, a new set of expander graphs can be explicitly constructed. In addition, we present algorithms for basis construction and decomposition of a given element with respect to the basis.

  35. [+] Claude-Pierre Jeannerod, Vincent Neiger, Éric Schost and Gilles Villard. Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts.

    In this paper, we focus on computing bases of solutions for a general interpolation problem, a particular case of which is Hermite-Padé approximation. This problem asks to find univariate polynomial relations between $m$ vectors of size $\sigma$; these relations should have small degree with respect to an input degree shift $s \in Z^m$. We recently proposed an algorithm to solve this problem using $\tilde{O}(m^{w-1} (\sigma+\xi))$ operations in the base field, where $\xi$ is the sum of the components of $s-\min(s)$, $w$ is the exponent of matrix multiplication, and the notation $\tilde{O}{\cdot}$ indicates that we omit logarithmic terms; the output basis of relations is $s$-reduced. That result is satisfactory when $\xi=\mathrm{O}(\sigma)$, since the cost is then $\tilde{O}(m^{w-1} \sigma)$, but leaves open the question of handling arbitrary shifts in the same complexity. In this paper, we solve this problem using a divide-and-conquer approach: from the bases computed recursively, we obtain information on the degrees in the output basis; we deduce another shift whose properties allow us to find the output using our previous result. For an arbitrary input shift, this algorithm computes the basis in shifted Popov form using a total of $\tilde{O}(m^{w-1} \sigma)$ operations. In particular, this improves over previous work by Zhou and Labahn in the case of order basis computation.

  36. [+] Alexander Kobel, Fabrice Rouillier and Michael Sagraloff. Computing Real Roots of Real Polynomials ... and Now for Real!.

    Very recent work introduces an asymptotically fast subdivision algorithm, denoted ANewDsc, for isolating the real roots of a univariate real polynomial. The method combines Descartes' Rule of Signs to test intervals for the existence of roots, Newton iteration to speed up convergence against clusters of roots, and approximate computation to decrease the required precision. It achieves record bounds on the worst-case complexity for the considered problem, matching the complexity of Pan's method for computing all complex roots and improving upon the complexity of other subdivision methods by several magnitudes. In the article at hand, we report on an implementation of ANewDsc on top of the RS root isolator. RS is a highly efficient realization of the classical Descartes method and currently serves as the default real root solver in Maple. We describe crucial design changes within ANewDsc and RS that led to a high-performance implementation without harming the theoretical complexity of the underlying algorithm. With an excerpt of our collection of benchmarks, available at http://anewdsc.mpi-inf.mpg.de/, we illustrate that the theoretical gain in performance of ANewDsc over other subdivision methods also transfers into practice. These experiments also show that our new implementation outperforms both RS and mature competitors by magnitudes for notoriously hard instances with clustered roots. For all other instances, we avoid almost any overhead by integrating additional optimizations and heuristics.

  37. [+] Robert Krone. Equivariant Gröbner Bases of Symmetric Toric Ideals.

    It has been shown previously that a large class of monomial maps equivariant under the action of an infinite symmetric group have finitely generated kernels up to the symmetric action. We prove that these symmetric toric ideals also have finite Gröbner bases up to symmetry for certain monomial orders. An algorithm is presented for computing equivariant Gröbner bases that terminates whenever a finite basis exists, improving on previous algorithms that only guaranteed termination in rings Noetherian up to symmetry. This algorithm can be used to compute equivariant Gröbner bases of the above toric ideals, given the monomial map.

  38. [+] Jing-Cao Li, Cheng-Chao Huang, Ming Xu and Zhi-Bin Li. Positive Root Isolation for Poly-Powers.

    This paper studies a class of univariate real functions—poly-powers—that extend that extend integer exponents to real algebraic exponents for polynomials. Our purpose is to isolate positive roots of such a function into disjoint intervals, which can be further easily computed up to any desired precision. To this end, we first classify poly-powers into simple and non-simple ones, depending on the number of linearly independent exponents. For the former, we present a complete isolation method based on Gelfond—Schneider theorem. For the latter, the completeness depends on Schanuel's conjecture. Finally experiential results demonstrate the effectivity of the proposed method.

  39. [+] Stephen Melczer and Bruno Salvy. Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables.

    Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal—a property governed by inequalities on the moduli of the coordinates—typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the `combinatorial case') and under regularity conditions, we utilize this Kronecker representation to determine the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.

  40. [+] Guillaume Moroz and Éric Schost. A Fast Algorithm for Computing the Truncated Resultant.

    Let $P$ and $Q$ be two polynomials of $\mathbb K[x,y]$ of degree at most $d$, where $K$ is a field. Denoting by $R\in \mathbb K[x]$ the resultant of $P$ and $Q$ with respect to $y$, we present an algorithm to compute $R \mod x^k$ in $\tilde O(kd)$ arithmetic operations in $K$, up to log factors. This is an improvement over state-of-the-art algorithms that require to compute $R$ in $\tilde O(d^3)$ operations before computing its first $k$ coefficients.

  41. [+] Katsusuke Nabeshima, Katsuyoshi Ohara and Shinichi Tajima. Comprehensive Groebner Systems in Rings of Differential Operators, Holonomic D-modules and B-functions.

    An algorithm for computing comprehensive Gröbner systems (CGS) is introduced in rings of linear partial differential operators. Their applications to b-functions are considered. The resulting algorithm designed for a wide use of computing comprehensive Gröbner systems can be used to compute all the roots of b-function and relevant holonomic D-modules. Furthermore, effective methods are illustrated, with our implementation, for computing holonomic D-modules associated with hypersurface singularities. It is shown that the proposed algorithm is full of versatility.

  42. [+] Simone Naldi. Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic.

    We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix is fixed, the complexity is polynomial in the number of variables. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We also implement it in Maple and discuss practical experiments.

  43. [+] Vincent Neiger. Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations.

    We give a Las Vegas algorithm which computes the shifted Popov form of a nonsingular polynomial matrix $A \in \mathbb{K}[X]^{m x m}$ in expected $O (m^{w-1} \sigma) \subseteq O (m^w \deg(A))$ operations in $\mathbb{K}$, where $\deg(A)$ is the degree of $A$, $\sigma$ is some quantity such that $\sigma / m$ is bounded from above by both the average row degree and the average column degree of $A$, $w$ is the exponent of matrix multiplication, and $O {\cdot}$ indicates that logarithmic factors are omitted. This improves upon the cost bound of the fastest known algorithms for row reduction and Hermite form computation, which are deterministic. This is the first algorithm for shifted row reduction with cost bound $O(m^w \deg(A))$ for an arbitrary shift.

    This algorithm uses partial linearization to reduce to the case $\deg(A) \le \sigma$, and builds a system of modular equations whose solution set is the row space of $A$. It remains to find the basis in shifted Popov form of this solution set: we give a deterministic algorithm for this problem in $O(m^{w-1} \sigma)$ operations, where $m$ is the number of unknowns and $\sigma$ is the sum of the degrees of the moduli. This extends previous results with the same cost bound in the specific cases of order basis computation and M-Padé approximation, in which the moduli are products of known linear factors.

  44. [+] Arnold Neumaier and Damien Stehlé. Faster LLL-type Reduction of Lattice Bases.

    We describe a fast variant of the LLL lattice reduction algorithm. Our algorithm takes as input a basis $\vec{B} \in \mathbb{Z}^{n \times n}$ of a Euclidean lattice $L$ and returns a (reduced) basis $\vec{C}$ of $L$, whose first vector satisfies $\|\vec{c}_1\| \leq (1+c) (4/3)^{(n-1)/4} (\det L)^{1/n}$ for any fixed $c>0$. It terminates within $O(n^{4+\varepsilon} \beta^{1+\varepsilon})$ bit operations for any $\varepsilon >0$, with $\beta = \max_i \|\vec{b}_i\|$. It does rely on fast integer arithmetic but does not make use of fast matrix multiplication.

  45. [+] Johan S. R. Nielsen and Arne Storjohann. Algorithms for Simultaneous Padé Approximations.

    We describe how to solve simultaneous Padé approximations over a power series ring $\mathbb{K}[[x]]$ for a field $\mathbb{K}$ using $\tilde{O}(n^{\omega - 1} d)$ operations in $\mathbb{K}$, where $d$ is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches and with different advantages. Both algorithms return reduced bases for the complete set of solutions to the input approximation problem. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

  46. [+] Masayuki Noro. Computation of a System of Partial Differential Equations Satisfied by the Hypergeometric Function ${}_1F_1$ of a Matrix Argument on Diagonal Regions.

    The hypergeometric function ${}_1F_1$ of a matrix argument $Y$ is a symmetric entire function in the characteristic roots $y_1,\ldots,y_m$ of $Y$. It appears in the distribution function of the largest root of a Wishart matrix and its numerical evaluation is important in multivariate distribution theory. Hashiguchi et al. [HNTT13] proposed an efficient algorithm for evaluating the matrix ${}_1F_1$ by the holonomic gradient method (HGM) [NOST11]. The algorithm is based on the system of partial differential equations (PDEs) satisfied by the matrix ${}_1F_1$ given by Muirhead [M70] and it cannot be applied to the diagonal cases, i.e. the cases where several yi's are equal because the system of PDEs has singularities over the diagonal region. In [HNTT13] an ordinary differential equation (ODE) satisfied by ${}_1F_1(y,y)$ in the bivariate case is derived from some relations which are obtained by applying l'Hopital rule to the system of PDEs for ${}_1F_1(y_1,y_2)$. In this paper we generalize this approach for computing systems of PDEs satisfied by the matrix ${}_1F_1$ for various diagonalization patterns. We show that the existence of a system of PDEs for a diagonalized ${}_1F_1$ is reduced to the non-singularity of the matrices systematically derived from the diagonalization pattern. By checking the non-singularity, we show that there exists a system of PDEs for a diagonalized ${}_1F_1$ if the size of each diagonal block $\leq 36$. We have computed an ODE for ${}_1F_1$(y,...,y) up to $m=22$. We made a test implementation of HGM for diagonal cases and we show some numerical results.

    [M70] R. J. Muirhead. System of partial differential equations for hypergeometric functions of matrix argument. Ann. Math. Statist., 41:991—1001, 1970.

    [NOST11] H. Nakayama, K. Nishiyama, M. Noro, K. Ohara, T. Sei, N. Takayama, and A. Takemura. Holonomic gradient descent and its application to the Fisher-Bingham integral. Adv. Appl. Math., 47:639—658, 2011.

    [HNTT13] H. Hashiguchi, Y. Numata, N. Takayama, and A. Takemura. Holonomic gradient method for the distribution function of the largest root of a wishart matrix. J. Multivariate Analysis, 117:296—312, 2013.

  47. [+] Clément Pernet. Computing with Quasiseparable Matrices.

    The class of quasiseparable matrices is defined by a pair of bounds, called the quasiseparable orders, on the ranks of the maximal sub-matrices entirely located in their strictly lower and upper triangular parts. These arise naturally in applications, as e.g. the inverse of band matrices, and are widely used for they admit structured representations allowing to compute with them in time linear in the dimension and quadratic with the quasiseparable order. We show, in this paper, the connection between the notion of quasiseparability and the rank profile matrix invariant, presented in [Dumas et al. ISSAC'15]. This allows us to propose an algorithm computing the quasiseparable orders $(r_L,r_U)$ in time $O(n^2s^{\omega-2})$ where $s=\max(r_L,r_U)$ and $\omega$ the exponent of matrix multiplication. We then present two new structured representations, a binary tree of PLUQ decompositions, and the Bruhat generator, using respectively $O(ns\log\frac{n}{s})$ and $O(ns)$ field elements instead of $O(ns^2)$ for the previously known generators. We present algorithms computing these representations in time $O(n^2s^{\omega-2})$. These representations allow a matrix-vector product in time linear in the size of their representation. Lastly we show how to multiply two such structured matrices in time $O(n^2s^{\omega-2})$.

  48. [+] Jamal Hossein Poor, Clemens G. Raab and Georg Regensburger. Algorithmic Operator Algebras via Normal Forms for Tensors.

    We propose a general algorithmic approach to noncommutative operator algebras generated by linear operators. Ore algebras are a well-established tool covering many cases arising in applications. For example, integro-differential operators, however, do not fit this structure. Instead of using (parametrized) Gröbner bases in free algebras as has been used so far in the literature, we use Bergman's basis-free analog in tensor algebras. This allows for a finite reduction system with unique normal forms. To have a smaller reduction system, we develop a refinement of Bergman's setting. This refinement also makes the algorithmic verification of the confluence criterion more efficient. We provide an implementation in Mathematica and we illustrate both versions of the tensor setting using integro-differential operators as an example.

  49. [+] Tristan Vaccon and Pierre Lairez. On $p$-adic Differential Equations with Separation of Variables.

    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.

  50. [+] Yi Zhang. Contraction of Ore Ideals with Applications.

    Ore operators form a common algebraic abstraction of linear ordinary differential and recurrence equations. Given an Ore operator $L$ with polynomial coefficients in $x$, it generates a left ideal $I$ in the Ore algebra over the field $\mathbf{k}(x)$ of rational functions. We present an algorithm for computing a basis of the contraction ideal of $I$ in the Ore algebra over the ring $R[x]$ of polynomials, where $R$ may be either $\mathbf{k}$ or a domain with $\mathbf{k}$ as its fraction field. This algorithm is based on recent work on desingularization for Ore operators by Chen, Jaroschek, Kauers and Singer. Using a basis of the contraction ideal, we compute a completely desingularized operator for $L$ whose leading coefficient not only has minimal degree in $x$ but also has minimal content. Completely desingularized operators have interesting applications such as certifying integer sequences and checking special cases of a conjecture of Krattenthaler.