Full papers

Details on the ISSAC 2017 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.

List of Accepted Papers

[+] Ignacio Garcia Marco, Pascal Koiran and Timothee Pecatte. Reconstruction algorithms for sums of affine powers.
Abstract:
A sum of affine powers is a linear combination of terms of the form (x-a)^e.
The shifts a and the exponents e may differ from term to term.
Although quite simple, this model is a generalization of
two well-studied models: Waring decomposition and Sparsest Shift.
For these three models there are natural extensions to several variables,
but this paper is mostly focused on univariate polynomials.
We propose algorithms that find the smallest decomposition in the first model (sums of affine powers) of an input polynomial f(x) given in dense representation.

The same material (and a little more) can be found in the arxiv preprint: https://arxiv.org/abs/1607.05420.
[+] Alexandre Gelin, Thorsten Kleinjung and Arjen Lenstra. Parametrizations for families of ECM-friendly curves.
Abstract:
We provide a new family of elliptic curves that results in a one to two percent performance improvement of the elliptic curve integer factorization method. The speedup is confirmed by extensive tests for factors ranging from 15 to 63 bits.
[+] Dong Lu, Xiaodong Ma and Dingkang Wang. A New Algorithm for General Factorizations of Multivariate Polynomial Matrices.
Abstract:
We investigate how to factorize a multivariate polynomial matrix into the product of two matrices. There are two major ingredients. The first is a factorization theorem, which asserts that a multivariate polynomial matrix whose lower order minors satisfy certain conditions admits a matrix factorization. Our theory is a generalization to the previous results by Lin et.al \cite{Lin2001Factorizations} and Liu et.al \cite{Liu2011On}. The second part is the implementation for factoring polynomial matrices. According to the proof of factorization theorem, we construct a main algorithm which extends the range of polynomial matrices that can be factorized. How to compute a zero left prime matrix and a unimodular matrix are two critical steps in main algorithm. Using the famous Quillen-Suslin theorem, we present a new sub-algorithm to obtain a zero left prime matrix by calculating the syzygies of two low-order polynomial matrices. Experiments show that our new sub-algorithm is more efficient than the algorithm by Wang and Kwong \cite{Mingsheng2005On}. Furthermore, we use some auxiliary information which provided by the above new sub-algorithm to construct a unimodular matrix. As a consequence, the main algorithm extends the application range of the constructive algorithm in \cite{Lin2001Factorizations}. We implement all these algorithms on computer algebra system {\em Singular} and give a nontrivial example to show the process of the main algorithm.
[+] Jonas Szutkoski, Mark van Hoeij, Luiz E. Allem and Juliane G. Capaverde. Functional Decomposition using Principal Subfields.
Abstract:
Let f \in K(t) be a univariate rational function. It is well known that any non-trivial decomposition g \circ h, with g,h \in K(t), corresponds to a non-trivial subfield K(f(t)) \subsetneq L \subsetneq K(t) and vice-versa. In this paper, we use the idea of principal subfields and fast subfield-intersection techniques to compute the subfield lattice of K(t)/K(f(t)). This yields a Las Vegas algorithm with improved complexity and better run times for finding all non-equivalent complete decompositions of f.
[+] Jean-Guillaume Dumas, David Lucas and Clément Pernet. Certificates for triangular equivalence and rank profiles.
Abstract:
In this paper, we give novel certificates for triangular equivalence
and rank profiles.
These certificates enable to verify the row or column rank profiles or the
whole rank profile matrix faster than
recomputing them, with a negligible overall overhead.
We first provide quadratic time and space non-interactive certificates
saving the logarithmic factors of previously known ones.
Then we propose interactive certificates for the same problems
whose Monte Carlo verification complexity requires a small constant
number of matrix-vector
multiplications, a linear space, and a linear number of extra field operations.
As an application we also give an interactive protocol, certifying the
determinant of dense matrices, faster than the best previously known one.
[+] Sidi-Mohamed Sedjelmaci. Two fast parallel GCD algorithms of many integers.
Abstract:
We present two new parallel algorithms which compute the GCD of $n$ integers of $O(n)$ bits in $O(n/\log n)$ time with $O(n^{2+\epsilon})$ processors in the worst case, for any $\epsilon >0$ in CRCW PRAM model.
More generally, we prove that computing the GCD of $m$ integers of $O(n)$ bits
can be achieved in $O(n\,/\log n)$ parallel time with $O(m\,n^{1+\epsilon}\,)$ processors, for any $2 \leq m \leq n^{3/2}/\log n$, i.e. the parallel time does not depend on the number $m$ of integers considered in this range.
To our knowledge, it is the first time that we find deterministic algorithms which compute the GCD of many integers with this parallel performance and polynomial work.
We suggest an extended GCD version for many integers as well as an algorithm to solve linear Diophantine equations.

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.
[+] Claus Fieker, William Hart, Tommy Hofmann and Fredrik Johansson. Nemo/Hecke: computer algebra and number theory packages for the Julia programming language.
Abstract:
We introduce two new packages, Nemo and Hecke, written in the Julia programming language for computer algebra and number theory. We demonstrate that high performance generic algorithms can be implemented in Julia, without the need to resort to a low-level C implementation. For specialised algorithms, we use Julia's efficient native C interface to wrap existing C/C++ libraries such as Flint, Arb, Antic and Singular. We give examples of how to use Hecke and Nemo and discuss some algorithms that we have implemented to provide high performance basic arithmetic.
[+] Xavier Dahan. Gcd modulo a primary triangular set of dimension zero.
Abstract:
Computing gcd over a triangular set is the core routine of the machinery
of some triangular decomposition methods, in the relam of
polynomial ideal theory. As such it has been studied intensively
and is well-understood and implemented in several situations, especially
on the case of radical ideals. This paper focuses on dening
gcd notions in the case of a zero-dimensional triangular set T that
is not radical, but for simplicity, that is assumed primary. After
establishing a unique factorization property for monic univariate
polynomials modulo T , we introduce the new concept of gcd chain
associated to two monic univariate polynomials a and b dened
modulo T.
[+] Georg Grasegger and N. Thieu Vo. An Algebraic-Geometric Method for Computing Zolotarev Polynomials.
Abstract:
In this paper we study a differential equation which arises from the theory of Zolotarev polynomials. By extending a symbolic algorithm for finding rational solutions of algebraic ordinary differential equations, we construct a method for computing explicit expressions for Zolotarev polynomials. This method is an algebraic geometric one and works subject to (radical) parametrization of algebraic curves. As a main application we compute the explicit form of the proper Zolotarev polynomial of degree 5.
[+] Christian Eder, Gerhard Pfister and Adrian Popescu. On Signature-based Gröbner Bases over Euclidean Rings.
Abstract:
In this paper we present first steps in using signature-based Gröb-
ner basis algorithms like Faugère's F5 or GVW for computation
over Euclidean rings. We present problems appearing when having
to deal with coefficients and zero divisors and give practical solu-
tion techniques. A hybrid algorithm is presented trying to combine
the advantages of signature-based and non-signature-based Gröb-
ner basis computation. For some examples speedups are achieved
due to faster finding good reducers with the hybrid technique.
[+] Yu-Ao Chen and Xiao-Shan Gao. Criteria for Finite Difference Groebner Bases of Normal Binomial Difference Ideals.
Abstract:
In this paper, we give decision criteria for normal binomial
difference polynomial ideals in the univariate difference
polynomial ring F{y} to have finite difference Groebner bases
and an algorithm to compute the finite difference Groebner bases
if these criteria are satisfied. The novelty of these criteria
lies in the fact that complicated properties about difference
polynomial ideals are reduced to elementary properties of
univariate polynomials in Z[x].
[+] Manuel Kauers and Gleb Pogudin. Bounds for D-finite Substitution.
Abstract:
It is well-known that the composition of a D-finite function with an algebraic function is again D-finite.
We give the first estimates for the orders and the degrees of annihilating operators for the compositions.
We find that the analysis of removable singularities leads to an order-degree curve which is much more accurate than the order-degree curve obtained from the usual linear algebra reasoning.
[+] Xavier Caruso and Jérémy Le Borgne. Fast multiplication for skew polynomials.
Abstract:
We describe an algorithm for fast multiplication of skew polynomials. It is based on fast modular multiplication of such skew polynomials, for which we give an algorithm relying on evaluation and interpolation on normal bases. Our algorithms improve the best known complexity for these problems, and reach the optimal asymptotic complexity bound for large degree. We also give an adaptation of our algorithm for polynomials of small degree. Finally, we use our methods to improve on the best known complexities for various arithmetics problems.
[+] David Roe, Xavier Caruso and Tristan Vaccon. Characteristic polynomials of p-adic matrices.
Abstract:
We analyze the precision of the characteristic polynomial f(A) of
an n by n p-adic matrix A using differential precision methods
developed previously. When A is integral with precision O(p^k),
we give a criterion (checkable in time O~(n^\omega)) for
f(A) to have precision exactly O(p^k). We also give a O~(n^3)
algorithm for determining the optimal precision when the criterion is not
satisfied, and give examples when the precision is larger than O(p^k).
[+] Johannes Middeke. Denominator Bounds and Polynomial Solutions for Systems of q-Recurrences over K(t) for Constant K.
Abstract:
We consider systems A_\ell(t) y(q^\ell t) + ... + A_0(t) y(t) = b(t) of higher order q-recurrence equations with rational coefficients. We extend a method for finding a bound on the maximal power of t in the denominator of arbitrary rational solutions y(t) as well as a method for bounding the degree of polynomial solutions from the scalar case to the systems case. The approach is direct and does not rely on uncoupling or reduction to a first order system. Unlike in the scalar case this usually requires an initial transformation of the system.
[+] Vishwas Bhargava, Gabor Ivanyos, Rajat Mittal and Nitin Saxena. Irreducibility and deterministic r-th root finding over finite fields.
Abstract:
Constructing $r$-th non-residue over a finite field is a fundamental
computational problem. A related problem is to construct an irre-
ducible polynomial of degree $r^e$ (where $r$ is a prime) over a given
finite field $F_q$ of characteristic $p$ (equivalently, constructing the
bigger field $F_{q^{r^e}}$). Both these problems have famous randomized
algorithms but the derandomization is an open question. We give
some new connections between these two problems and their vari-
ants.

In 1897, Stickelberger proved that if a polynomial has an odd
number of even degree factors, then its discriminant is a quadratic
nonresidue in the field. We give an extension of Stickelberger's
Lemma to $r$-th nonresidues from a polynomial $f$ for which there is
a $d$ such that $r|d$ and $r$ does not divide #(irreducible factors of $f(x)$ of degree $d$).
Our theorem has the following interesting consequences: (1) we
can construct $F_{q^{m}}$ in deterministic $poly(deg(f), m log q)$-time if $m$
is an $r$-power and $f$ is known; (2) we can find $r$-th roots in $F_{p^m}$ in
deterministic $poly(m log p)$-time if $r$ is constant and $r|gcd(m, p-1)$.

We also discuss a conjecture significantly weaker than the Gen-
eralized Riemann hypothesis to get a deterministic poly-time algo-
rithm for $r$-th root finding.
[+] Kosaku Nagasaka. Parametric Greatest Common Divisors using Comprehensive Gröbner Systems.
Abstract:
Computing the greatest common divisor (GCD) of
polynomials can be done by computing the Gröbner basis
instead of the well-known Euclidean algorithm,
studied by Gianni and Trager in 1985, and
Sasaki and Suzuki in 1992.
In this paper, we extend their theories to polynomials
with parameters. That is the theory of parametric
greatest common divisors by means of comprehensive
Gröbner systems (CGS). Moreover,
this can be considered as an indirect extension of
known parametric GCD algorithms to those for
several multivariate polynomials with parameters.
[+] Russell Bradford, James H. Davenport, Matthew England, Hassan Errami, Vladimir Gerdt, Dima Grigoriev, Charles Hoyt, Marek Kosta, Ovidiu Radulescu, Thomas Sturm and Andreas Weber. A Case Study on the Parametric Occurrence of Multiple Steady States.
Abstract:
The determination of multiple steady states for positive values is very
important in the analysis of biological networks. The investigation of the
potential of models of the mitogen-activated protein kinases (MAPK) network for
such multistationarity has consumed considerable effort using special insights
into the structure of corresponding models. We apply combinations of symbolic
computation methods for mixed equality/inequality systems, specifically virtual
substitution, lazy real triangularization and cylindrical algebraic
decomposition. We demonstrate that the determination of multistationarity of an
11-dimensional MAPK network with can be achieved by currently available methods
when numeric values are known for all but potentially one parameter. More
precisely, our considered model has 11 equations in 11 variables and 19
parameters and furthermore positivity conditions on all variables and
parameters.
[+] Maximilian Jaroschek, Andreas Humenberger and Laura Kovacs. Automated Generation of Non-Linear Loop Invariants Utilizing Hypergeometric Sequences.
Abstract:
Analyzing and reasoning about safety properties of software systems becomes an
especially challenging task for programs with complex flow and, in particular,
with loops or recursion. For such programs one needs additional information,
for example in the form of loop invariants, expressing properties to hold at
intermediate program points. In this paper we study program loops with
non-trivial arithmetic, implementing addition and multiplication among numeric
program variables. We present a new approach for automatically generating all
polynomial invariants of a class of such programs. Our approach turns programs
into linear ordinary recurrence equations and computes closed form solutions
of these equations. The computed closed forms express the most precise
inductive property, and hence invariant. We apply Gröbner basis computation
to compute a basis of the polynomial invariant ideal, yielding thus a finite
representation of all polynomial invariants. Our work significantly extends
the class of so-called P-solvable loops by handling multiplication with the
loop counter variable. We implemented our method in the Mathematica package
Aligator and showcase the practical use of our approach.
[+] Amir Hashemi and Werner M. Seiler. Dimension-Dependent Upper Bounds for Grobner Bases.
Abstract:
We improve certain degree bounds for Grobner bases of polynomial ideals in generic position. We work exclusively in deterministically verifiable and achievable generic positions of a combinatorial nature, namely either strongly stable position or quasi stable position. Furthermore, we exhibit new dimension- (and depth-)dependent upper bounds for the Castelnuovo-Mumford regularity and the degrees of the elements of the reduced Grobner basis (w.r.t. the degree reverse lexicographical ordering) of a homogeneous ideal in these positions.
[+] Hongbo Li, Zhang Li and Yang Li. Riemann Tensor Polynomial Canonicalization by Graph Algebra Extension.
Abstract:
Tensor expression simplification is an "ancient" topic in computer algebra, a representative of which is the canonicalization of Riemann tensor polynomials.
Practically fast algorithms exist for monoterm canonicalization, but not for
multiterm canonicalization. Targeting the multiterm difficulty,
in this paper we establish the extension theory of graph algebra, and propose a
canonicalization algorithm for Riemann tensor polynomials based on this theory.
[+] Dmitry Lyakhov, Vladimir Gerdt and Dominik Michels. Algorithmic Verification of Linearizability for Ordinary Differential Equations.
Abstract:
For a nonlinear ordinary differential equation solved with respect to the highest order derivative and rational in the other derivatives and in the independent variable, we devise two algorithms to check if the equation can be reduced to a linear one by a point transformation of the dependent and independent variables. The first algorithm is based on a construction of the Lie point symmetry algebra and on the computation of its derived algebra. The second algorithm exploits the differential Thomas decomposition and allows not only to test the linearizability, but also to generate a system of nonlinear partial differential equations that determines the point transformation and the coefficients of the linearized equation. Both algorithms have been implemented in Maple and their application is illustrated using several examples.
[+] Hidenao Iwane and Hirokazu Anai. Formula Simplification for Real Quantifier Elimination using Geometric Invariance.
Abstract:
Formulating a simple and adequate quantified
first-order formula is crucial for applying real quantifier elimination (QE) efficiently. In general, generating simple
formulas or simplifying formulas for efficient QE involves
human interaction. In this paper, we present simplification
algorithms for quantified first-order formulas over the real numbers to speed up QE.
We present experimental results for more than 10,000 benchmark problems
to examine the effectiveness of our simplification algorithms.
[+] Michael Clausen and Paul Hühne. Linear time Fourier transforms of S_{n-k}-invariant functions on the symmetric group S_n.
Abstract:
This paper introduces new techniques for the efficient computation of Fourier transforms of S_{n-k}-invariant functions on the symmetric group S_n.
We uncover diamond- and leaf-rake-like structures in Young's seminormal and orthogonal representations. Combining this with both a multiresolution scheme and an anticipation technique for saving scalar multiplications leads to linear time partial FFTs. Following the inductive version of Young's branching rule we obtain a global FFT-algorithm that computes a DFT of S_{n-k}-invariant functions on S_n in at most c_k*[S_n:S_{n-k}] scalar multiplications and additions, where c_k denotes a positive constant depending only on k. This run-time, which is linear in the index [S_n:S_{n-k}], is order optimal and improves Maslen's algorithm. For example, it takes less than one second on a standard notebook to run our FFT algorithm for an S_{n-2}-invariant real-valued function on S_n, n=5,000.
[+] Ioannis Z. Emiris, Christos Konaxis, Clement Laroche and Ilias Kotsireas. Matrix representations by means of interpolation.
Abstract:
We examine implicit representations of parametric or point cloud models, based on interpolation matrices, which are not sensitive to base points.

We show how interpolation matrices can be used for ray shooting of a parametric ray with a surface patch, including the case of high-multiplicity intersections. Most matrix operations are executed during pre-processing since they solely depend on the surface. For a given ray, the bottleneck is equation solving. Our Maple code handles bicubic patches in less than 1 second, though numerical issues might arise.

Our second contribution is to extend the method to parametric space curves and, generally, to codimension higher than 1, by computing the equations of (hyper)surfaces intersecting precisely at the given object. By means of Chow forms, we propose a new, practical, randomized algorithm that always produces correct output but possibly with a non-minimal number of surfaces. For space curves, we typically obtain up to 3 surfaces whose polynomials are of near-optimal degree; in this case, computation reduces to a Sylvester resultant.
Our Maple prototype is not faster but yields fewer equations and seems more robust than Maple's implicitize.
[+] Tristan Vaccon and Kazuhiro Yokoyama. A Tropical F5 algorithm.
Abstract:
Let $K$ be a field equipped with a valuation. Tropical varieties over $K$ can be defined with a theory of Gröbner bases taking into account the valuation of $K$.
While generalizing the classical theory of Gröbner bases, it is not clear how modern algorithms for computing Gröbner bases
can be adapted to the tropical case.
Among them, one of the most efficient is the celebrated F5 Algorithm of Faugère.

In this article, we prove that, for homogeneous ideals, it can be adapted to the tropical case. We prove termination and correction.

Because of the use of the valuation, the theory of tropical Gröbner bases is promising for stable computations over polynomial rings over a $p$-adic field. We provide numerical examples to illustrate
time-complexity and $p$-adic stability of this tropical F5 algorithm.
[+] Swaroop N Prabhakar and Vikram Sharma. Improved Bounds on Absolute Positiveness of Multivariate Polynomials.
Abstract:
A multivariate polynomial F (x1 , x2 , . . . , xn ) is said to be ab-
solutely positive from a real number B if F and all its non-
zero partial derivatives are positive for x1 , x2 , . . . , xn $\ge$ B.
One of the well known bounds on absolute positiveness in
the literature is due to Hong. His bound is dependent on the
first maximum of a certain sequence of radicals defined using
the absolute value of the coefficients of the polynomial. In
the univariate setting, a bound due to Lagrange considers
the first and the second maximum in the same radical se-
quence and is better than Hong's bound. Westerfield further
improved on both these bounds in the univariate setting, by
considering every value in the same radical sequence. In this
paper, we provide a generalization of Westerfield's bound to
the multivariate setting. As a specialization of this bound,
we also derive a generalization of Lagrange's bound, which
is a strict improvement upon Hong's bound. Finally, we give
an algorithm to compute this improved bound. The running
time of this algorithm matches the running time of the best
known algorithm to compute Hong's bound.
[+] Bernard Mourrain. Fast algorithm for border bases of Artinian Gorenstein algebras.
Abstract:
Given a multi-index sequence $\sigma$, we present a new efficient algorithm
to compute generators of the linear recurrence relations between the terms
of $\sigma$. We transform this problem into an algebraic one, by identifying
multi-index sequences, multivariate formal power series and linear
functionals on the ring of multivariate polynomials. In this setting, the
recurrence relations are the elements of the kernel $I_{\sigma}$ of the
Hankel operator $H_{\sigma}$ associated to $\sigma$. We describe the
correspondance between multi-index sequences with an Hankel operator of
finite rank and Artinian Gorenstein Algebras. We show how the algebraic
structure of the Artinian Gorenstein algebra $\mathcal{A}_{\sigma}$
associated to the sequence $\sigma$ yields the structure of the terms
$\sigma_{\alpha}$ for all $\alpha \in \mathbb{N}^n$. This structure is
explicitly given by a border basis of $\mathcal{A}_{\sigma}$, which is
presented as a quotient of the polynomial ring $\mathbb{K} [x_1, \ldots,
x_n]$ by the kernel $I_{\sigma}$ of the Hankel operator $H_{\sigma}$. The
algorithm provides generators of $I_{\sigma}$ constituting a border basis,
pairwise orthogonal bases of $\mathcal{A}_{\sigma}$ and the tables of
multiplication by the variables in these bases. It is an extension of
Berlekamp-Massey-Sakata (BMS) algorithm, with improved complexity bounds. We
present applications of the method to different problems such as the
decomposition of functions into weighted sums of exponential functions,
sparse interpolation, fast decoding of algebraic codes, computing the
vanishing ideal of points, and tensor decomposition. Some benchmarks
illustrate the practical behavior of the algorithm.
[+] Joris van der Hoeven and Robin Larrieu. The Frobenius FFT.
Abstract:
Let F_q be the finite field with q elements and let $\omega$ be a primitive n-th root of unity in an extension field F_(q^d) of F_q. Given a polynomial P \in F_q[x] of degree less than n, we will show that its discrete Fourier transform (P(1), P($\omega$),\ldots, P($\omega$^(n-1))) \in F_(q^d)^n can be computed essentially d times faster than the discrete Fourier transform of a polynomial Q \in F_(q^d)[x] of degree less than n, in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of F_(q^d) over F_q.
[+] Joris van der Hoeven and Gregoire Lecerf. Composition modulo powers of polynomials.
Abstract:
Modular composition is the problem to compose two univariate polynomials modulo a third one. For polynomials with coefficients in a finite field, Kedlaya and Umans proved in 2008 that the theoretical bit complexity for performing this task could be made arbitrarily close to linear. Unfortunately, beyond its major theoretical impact, this result has not led to practically faster implementations yet. In this paper, we study the more specific case of composition modulo the power of a polynomial. First we extend previously known algorithms for power series composition to this context. We next present a fast direct reduction of our problem to power series composition.
[+] Laurent Busé and Ibrahim Nonkané. Discriminants of complete intersection space curves.
Abstract:
In this paper, we develop a new approach to the discriminant of a complete intersection curve in the 3-dimensional projective space. By relying on the resultant theory, we first prove a new formula that allows us to define this discriminant without ambiguity and over any commutative ring, in particular in any characteristic. This formula also provides a new method for evaluating and computing this discriminant efficiently, without the need to introduce new variables as with the well-known Cayley trick. Then, we obtain new properties and computational rules such as the covariance and the invariance formulas. Finally, we show that our definition of the discriminant satisfies to the expected geometric property and hence yields an effective smoothness criterion for complete intersection space curves. Actually, we show that in the generic setting, it is the defining equation of the discriminant scheme if the ground ring is assumed to be a unique factorization domain.
[+] Robin Larrieu. The Truncated Fourier Transform for mixed radices.
Abstract:
The standard version of the Fast Fourier Transform (FFT) is applied to problems of size n = 2^k. For this reason, FFT-based evaluation/interpolation schemes often reduce a problem of size l to a problem of size n, where n is the smallest power of two with l < n. However, this method presents "jumps" in the complexity at powers of two; and on the other hand, n-l values are computed that are actually unnecessary for the interpolation. To mitigate this problem, a truncated variant of the FFT was designed to avoid the computation of these unnecessary values. In the initial formulation, it is assumed that n is a power of two, but some use cases (for example in finite fields) may require more general values of n. This paper presents a generalization of the Truncated Fourier Transform (TFT) for arbitrary orders. This allows to benefit from the advantages of the TFT in the general case.
[+] Koen de Boer and Carlo Pagano. Calculating the power residue symbol and ibeta - Applications of computing the group structure of the principal units of a $\mathfrak{p}$-adic number field completion
Abstract:
In the recent PhD thesis of Bouw, an algorithm is examined that computes the group structure of the principal units of a $\mathfrak{p}$-adic number field completion. In the same thesis, this algorithm is used to compute Hilbert norm residue symbols. In the present paper, we will demonstrate two other applications. The first application is the computation of an important invariant of number field completions, called ibeta. The algorithm that computes ibeta is deterministic and runs in polynomial time. The second application uses Hilbert norm residue symbols and yields a probabilistic algorithm that computes the $m$-th power residue symbol $\left(\frac{\alpha}{\mathfrak{b}}\right)_m$ in arbitrary number fields $K$. This probabilistic algorithm relies on LLL-reduction and sampling of near-primes. Using heuristics, we analyse its complexity to be polynomial expected time in $n = [K:\mathbb{Q}]$, $\log |\Delta_K|$ and the input bit size -- a tentative conclusion corroborated by timing experiments. An implementation of the algorithm in Magma will be available at https://github.com/kodebro/powerresiduesymbol.
[+] Rusydi H. Makarim and Marc Stevens. M4GB: An efficient Grobner-basis algorithm.
Abstract:
This paper introduces a new efficient algorithm for computing Grobner-bases named M4GB.
Like Faugère's algorithm F4 it is an extension of Buchberger's algorithm that describes:
how to store already computed (tail-)reduced multiples of basis polynomials to prevent redundant work in the reduction step; and how to exploit fast linear algebra for the reduction step.
In comparison to F4 it removes further redundant work in the processing of reducible monomials.
Furthermore, instead of translating the reduction of many critical pairs into the row reduction of some large matrix, our algorithm is described more natively and is efficient while processing critical pairs one by one. This feature implies that typically M4GB has to process fewer critical pairs than F4, and reduces the time and data complexity `staircase' related to the increasing degree of regularity for a sequence of problems one observes for F4.

To achieve high efficiency, M4GB has been designed specifically to operate strictly on tail-reduced polynomials, i.e., polynomials of which all terms except the leading term are non-reducible.
This allows it to perform full-reduction directly in the computation of a term polynomial multiplication, where all computations are done over vectors of field coefficients corresponding to the non-reducible monomials.

We have implemented a version of our new algorithm tailored for dense overdefined polynomial systems as a proof of concept and made our source code publicly available. We have made a comparison of our implementation against the implementations of FGbLib, Magma and OpenF4 on various dense Fukuoka MQ challenge problems that we were able to compute in reasonable time and memory. We observed that M4GB uses the least total CPU time and the least memory of all these implementations for those MQ problems, often by a significant factor.

In the Fukuoka MQ challenges, the starting challenges of Type V and Type VI have 16 equations which was chosen based on an extrapolated computational runtime of more than a month using Magma. M4GB allowed us to set new records for these Fukuoka MQ challenges breaking Type V ($\mathbb{F}_{2^8}$) up to 18 equations and Type VI ($\mathbb{F}_{31}$) up to 19 equations, each can be computed within up to 8 days on our dual Xeon system.
[+] Daniel Bahrdt and Martin P. Seybold. Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions.
Abstract:
Given a point in R^d identifying its closest point x on the unit sphere.
We are interested in computing an $\epsilon$-approximation y $\in$ Q^d for x, that is `exactly' on S^{d-1} and has low bit size. We revise lower bounds on rational approximations and provide explicit, spherical instances.

We prove that floating-point numbers can only provide trivial solutions to the sphere equation in R^2 and R^3. Moreover, we show how to construct a rational point with denominators of at most 32(d-1)^2/$\epsilon$^2 for any given $\epsilon$, improving on a previous result.
The method further benefits from algorithms for simultaneous Diophantine approximation.

Our open-source implementation and experiments demonstrate the practicality of our approach in the context of massive data sets Geo-referenced by latitude and longitude values.
[+] Jean-Guillaume Dumas, Erich Kaltofen, Gilles Villard and Lihong Zhi. Polynomial Time Interactive Proofs For Linear Algebra with Exponential Matrix Dimensions And Scalars Given by Polynomial Time Circuits.
Abstract:
We present an interactive probabilistic proof protocol that certifies in (log N)^{O(1)} arithmetic and Boolean operations for the verifier the determinant, for example, of an N x N matrix over a field whose entries a(i,j) are given by a single (log N)^{O(1)}-depth arithmetic circuit, which contains (log N)^{O(1)} field constants and which is polynomial time uniform, for example, which has size (log N)^{O(1)}. The prover can produce the interactive certificate within a (log N)^{O(1)} factor of the cost of computing the determinant. Our protocol is a version of the proofs for muggles protocol by Goldwasser, Kalai and Rothblum [STOC 2008, J. ACM 2015]. An application is the following: suppose in a system of k homogeneous polynomials of total degree <= d in the k variables y_1,...,y_k the coefficient of the term y_1^{e_1} ... y_k^{e_k} in the i-th polynomial is the (hypergeometric) value ((i+e_1 + ... +e_k)!)/((i!)(e_1!)...(e_k!)), where e! is the factorial of e. Then we have a probabilistic protocol that certifies (projective) solvability or inconsistency of such a system in (k log(d))^{O(1)} bit complexity for the verifier, that is, in polynomial time in the number of variables k and and the logarithm of the total degree, log(d).
[+] Adam Strzebonski. CAD Adjacency Computation Using Validated Numerics.
Abstract:
We present an algorithm for computation of cell adjacencies for well-based cylindrical algebraic decomposition. Cell adjacency information can be used to compute topological operations e.g. closure, boundary, connected components, and topological properties e.g. homology groups. Other applications include visualization and path planning. Our algorithm determines cell adjacency information using validated numerical methods similar to those used in CAD construction, thus computing CAD with adjacency information in time comparable to that of computing CAD without adjacency information. We report on implementation of the algorithm and present empirical data.
[+] Vincent Neiger, Johan Rosenkilde and Éric Schost. Fast computation of roots of polynomials over the ring of power series.
Abstract:
We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field $\mathbb{K}$.
More precisely, given a precision $d$, and a polynomial $Q$ whose coefficients are power series in $x$, the algorithm computes a representation of all power series $f(x)$ such that $Q(f(x)) = 0 \bmod x^d$.
The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails.
Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled.

The cost bound for our algorithm matches the worst-case input and output size $d \deg Q$, up to logarithmic factors.
This improves upon previous algorithms which were quadratic in at least one of $d$ and $\deg Q$.
Our algorithm is a refinement of a divide & conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.
[+] John Perry. Exploring the Dynamic Buchberger Algorithm.
Abstract:
"Static" Buchberger algorithms to compute a Groebner basis require as input both a set of polynomials and a term ordering. "Dynamic" Buchberger algorithms dispense with the ordering, computing instead a Groebner basis with respect to a "discovered" ordering. A good heuristic usually results in a basis that is relatively small, a desirable property for many applications. This article uses a new C++ implementation to explore variants of the original algorithm. While the implementation is preliminary, and in general much slower than well-known static implementations, it still succeeds at computing some bases more quickly.
[+] Toru Aoyama. An Algorithm for Computing Minimal Associated Primes of Binomial Ideals without Producing Redundant Components.
Abstract:
This paper proposes a new algorithm for computing the minimal associated primes of a binomial ideal
in a polynomial ring over a field.
We utilize the cellular decomposition as an intermediate decomposition.
It is defined by Eisenbud-Strumfels and improved by Kahle.
In addition, following some parts of the algorithm by Laplagne, a new algorithm for
an intermediate decomposition is constructed.
Our algorithm decomposes an ideal into cellular ideals whose sets of
minimal associated primes are disjoint.
It needs neither extensions of the coefficient field nor reductions to the zero-dimensional case.
Most of the computations are saturations.
We observe by this intermediate decomposition, binomial ideals are decomposed into components whose
radicals correspond to the minimal associated primes in many cases.
This algorithm executes nilpotency checks, radical membership tests and computations of saturations
many times.
Therefore, we try to speed up the check of I = I : f (f is a polynomial) which is necessary for above computations.
As a result, we obtain efficient algorithms including heuristic and optional methods.
[+] Erich Kaltofen, Clement Pernet, Arne Storjohann and Cleveland Waddell. Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction.
Abstract:
Consider solving a black box linear system, A(u) x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = 1/g(u) f(u), where g is the least common monic denominator of the entries in x, can be found by evaluating the system at distinct points \xi_\ell in K. The solution can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. It is possible that the degree bounds used in their algorithm grossly overestimate the actual degrees. We describe an algorithm that given the same parameters, uses fewer evaluations to compute the solution.

We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count.

Incorporating our two counts we develop a combined early termination algorithm. We then specialize the algorithm in [Boyer and Kaltofen, Proc. SNC 2014] for parametric linear system solving to the recovery of a vector of rational functions, 1/g(u) f(u) from its evaluations. Thus, if the rational function vector is the solution to a full rank linear system our early termination strategy applies and we may recover it from fewer evaluations than generalized Welch/Berlekamp decoding. If we allow evaluations at poles (roots of g) there are examples where the Cabay count is not sufficient to recover the rational function vector from just its evaluations. This problem is solved if in addition to indicating that an evaluation point is a pole the black box gives information about the numerators of the solution at the evaluation point.
[+] Angelos Mantzaflaris and Elias Tsigaridas. Resultants and Discriminants for Bivariate Tensor-product Polynomials.
Abstract:
Optimal resultant formulas have been systematically constructed
mostly for unmixed polynomial systems, that is, systems of
polynomials which all have the same support. However, such condition
is restrictive, since mixed systems of equations arise
frequently in practical problems.

We present a square, Koszul-type, matrix expressing the
resultant of arbitrary (mixed) bivariate tensor-product systems.
The formula generalizes the classical Sylvester matrix
of two univariate polynomials, since it expresses a map of degree one,
that is, the entries of the matrix are simply coefficients of
the input polynomials.

Interestingly, the matrix expresses a primal-dual multiplication
map, that is , the tensor product of a univariate multiplication map
with a map expressing derivation in a dual space. Moreover, for
tensor-product systems with more than two (affine) variables, we
prove an impossibility result: no universal degree-one formulas are
possible, unless the system is unmixed.

We present applications of the new construction in the computation
of discriminants and mixed discriminants as well as in solving
systems of bivariate polynomials with tensor structure.
[+] Carlo Sircana. Factorization of polynomials over $\mathbb Z/(p^n)$.
Abstract:
In this paper, we deal with the problem of finding a factorization of a
monic polynomial $f\in \mathbb Z/(p^n)[x]$ into irreducible factors. This task
has been completely solved when $p^n$ does not divide the discriminant
of $f$, while there is not an efficient method of determining a
factorization when this happens and finding an explicit factorization
can be really hard for polynomials of high degree. We discuss
some techniques to speed up the computation, focusing in particular
on the case $n = 3$.
[+] Joseph Haraldson, Mark Giesbrecht and George Labahn. Computing the Nearest Singular Matrix Polynomial.
Abstract:
Matrix polynomials appear in many areas of computational algebra, control
systems theory, differential equations, and mechanics, typically with real or
complex coefficients. Because of numerical error and instability, a matrix
polynomial may appear of considerably higher rank (i.e., generically full rank),
while being very close to a rank deficient matrix. ``close'' is defined
naturally under the Frobenius norm on the underlying coefficient matrices of the
matrix polynomial. In this paper we consider the problem of finding the nearest
matrix polynomial of non-full rank to an input matrix polynomial, I.e. the
nearest singular matrix polynomial for square matrices. We prove that such
singular matrices at minimal distance always exist (and we are never in the
awkward situation having an infimum but no actual matrix polynomial at minimal
distance). We also show that singular matrices at minimal distance are all
isolated, and are surrounded by a convex neighborhood of attraction of non-minimal solutions.
We then present a iterative algorithm which, on given input sufficiently close
to a rank-deficient matrix, produces that matrix. The algorithm is efficient
and is proven to converge quadratically given a sufficiently good starting
point. An implementation demonstrates the effectiveness and numerical
robustness in practice.
[+] Johannes Hoffmann and Viktor Levandovskyy. A constructive approach to arithmetics in Ore localizations.
Abstract:
Classical results of Ore from the 1930's tell, that for a domain R, a localization with respect to a multiplicatively closed set S exists if S satisfies left Ore property. We investigate the arithmetics of the localized ring S^{-1}R from both theoretical and practical points of view. We show that effective computations in S^{-1}R require a specialization of the type of S and distill three most frequently occuring types of Ore sets. We provide an implementation of arithmetics over ubiquitous G-algebras in Singular:Plural and discuss algorithmic and theoretic questions in this context.
[+] Mohamed Khochtali, Johan Sebastian Heesemann Rosenkilde and Arne Storjohann. Popov Form Computation for Matrices of Ore Polynomials.
Abstract:
Let $K[\partial; \sigma, \delta]$ be a ring of Ore polynomials
over a field or a skew field $K$. We give a new deterministic
algorithm for computing the Popov form $P$ of a nonsingular matrix
$A \in K[\partial; \sigma, \delta]^{n \times n}$. Our main focus
is to ensure controlled growth in the size of coefficients from
$K$ in the case $K = F(z)$, and even $F = Q$. Our algorithms
are based on constructing from $A$ a linear system over $K$ and
performing a structured fraction-free Gaussian elimination. A
reduction to matrix multiplication allows incorporation of a
homomorphic imaging scheme. The algorithm is output sensitive,
with a cost that depends on the orthogonality defect of the input
matrix: the sum of the row degrees in $A$ minus the sum of the row
degrees in $P$. The resulting bit-complexity for the differential
and shift polynomial case over $Q(z)$ improves upon the previous
best.
[+] Christopher W. Brown. Projection and Quantifier Elimination using Non-uniform Cylindrical Algebraic Decomposition.
Abstract:
Cylindrical Algebraic Decomposition (CAD) is an established tool in the computer algebra community for computing with semi-algebraic sets / Tarski formulas. The key property of CAD is that it provides a representation in which geometric projection and set complement (the analogues of the logical operations of quantifier elimination and negation for Tarski formulas) are trivial. However, constructing a CAD often requires an impractical amount of time and space. Non-uniform CAD (NuCAD) was introduced with the goal of providing a more practically efficient alternative to CAD for computing with semi-algebraic sets / Tarski formulas. As a first step towards that goal, previous work has shown that Open NuCADs do provide a much more efficient representation than Open CADs. However, it hasn't been shown that the key operation of projection can be computed efficiently in the NuCAD representation, because while set complement is trivial for NuCADs (as it is for CADs) projection, in contrast to the CAD case, is not. This paper provides another step by showing how projection can be done efficiently in the Open NuCAD representation.

The importance of this contribution is not restricted to Open NuCADs, since the same approach to projection will carry over to the general case for NuCADs where, we hope, the practical benefits of the much smaller representation NuCAD provides will be even greater.
[+] Gorav Jindal and Michael Sagraloff A Polynomial Time Algorithm for Computing Real Roots of Sparse Real Polynomials.
Abstract:
We propose the first polynomial time algorithm to compute $L$-bit approximations of
the real roots of a sparse polynomial $f\in \mathbb{R}[x]$ with arbitrary real
coefficients. We assume that $f$ is a polynomial of degree $n$ with
only $k$ non-zero coefficients, and that arbitrarily good approximations
of all non-zero coefficients are given by means of a coefficient oracle.
For a given positive integer $L$, our algorithm returns disjoint
disks $\Delta_{1},\ldots,\Delta_{s}\subset \mathbb{C}$ centered at the real
axis and of radius less than $2^{-L}$ together with positive integers
$\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains
exactly $\mu_{i}$ roots of $f$ counted with multiplicity. In addition,
it is ensured that each real root of $f$ is contained in one of the disks.

We show that the bit complexity of our algorithm is polynomial in
$k$ and $\log n$, and even near-linear in $L$ and $\tau$, where $2^{-\tau}$
and $2^{\tau}$ constitute lower and upper bounds on the absolute
values of the non-zero coefficients of $f$. If $f$ has only simple
real roots, our algorithm can also be used to isolate all real roots,
in which case the bit complexity is polynomial in $k$ and $\log n$,
and near-linear in $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes
the separation of the real roots.

This paper extends our previous work \cite{Sagraloff14} on the subject,
where we considered the sub-problem of isolating the real roots of
a sparse integer polynomial. For this task,
our novel approach achieves comparable complexity bounds, in particular,
it also performs near-optimal for $k$ of size $(\log(n\tau))^{O(1)}$.
[+] Angelos Mantzaflaris, Éric Schost and Elias Tsigaridas Sparse Rational Univariate Representation.
Abstract:
We present explicit worst case degree and height bounds for the
rational univariate representation of the isolated roots of
polynomial systems based on mixed volume. We base our
estimations on height bounds of resultants and we consider the case
of 0-dimensional, positive dimensional, and parametric polynomial systems.
[+] Michael Burr, Shuhong Gao and Elias Tsigaridas The Complexity of an Adaptive Subdivision Method for Approximating Curves.
Abstract:
In this paper, we present the first complexity analysis of the algorithm published by Plantinga and Vegter for approximating real implicit curves and surfaces. This approximation algorithm certifies the topological correctness of the output using both subdivision and interval arithmetic. In practice, this algorithm has been seen to be quite efficient; the goal of this paper is to provide justification for this efficiency.

In this paper, we focus on the subdivision step (and not the approximation step) of the Plantinga and Vegter algorithm. We begin by extending the subdivision step to arbitrary dimensions. We provide a priori worst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and the bit complexity for the construction. Then, we use continuous amortization to derive adaptive bounds on the complexity of the subdivided region. Finally, we provide examples illustrating the tightness of our bounds.
[+] Dmitri Piontkovski. Growth in varieties of multioperator algebras and Groebner bases in operads.
Abstract:
Consider a variety of multioperator algebras, that is, the class of algebras with several multilinear operations satisfying certain identities. To each such a variety one can assign a numerical sequence called a sequence of codimensions, which is extensively studied in various aspects. The n-th codimension is equal to the dimension of the vector space of all n-linear operations in the free algebra of the variety. In the last one or two decades, a new approach to such a sequence appears based on the fact that the union of the above vector space carries the structure of algebraic operad, so that the generating function of the codimension sequence is equal to the generating series of the operad.

We show that, in general, there does not exist an algorithm to decide whether the sequence of codimensions of the variety defined by given finite sets of operations and identities is equal to a given sequence neither to decide if the exponent of the growth of the codimension sequence is equal to a given rational number. Nevertheless, we show that in many cases there exist effective algorithms which calculate the generating functions of the codimension series in the form of defining functional or differential equations. The first stage of the algorithm is the construction of the Groebner basis of the operad. If it occurs to be finite and satisfy mild restrictions, a recent theorem by the author and Anton Khoroshkin guarantees that the desired generating function satisfy either an algebraic equation or a differential algebraic equation with polynomial coefficients. We describe algorithms producing such equations for generating functions and give corresponding estimates. Examples (including the codimension series of varieties of non-associative algebras) are presented. Connections with enumeration of trees avoiding given patterns are also discussed.
[+] Vincent Neiger and Thi Xuan Vu. Computing canonical bases of modules of univariate relations.
Abstract:
We study the computation of relations between elements of a
finite-dimensional $\mathbb{K}[x]$-module. The latter is a quotient
$\mathbb{K}[x]^n/\mathcal{M}$ specified by a basis $\mathbf{M}\in\mathbb{K}[x]^{n\times n}$ of $\mathcal{M}$. Then, on input
$\mathbf{F} \in \mathbb{K}[x]^{m\times n}$, we seek canonical bases of the
set of relations $\mathbf{p} \in \mathbb{K}[x]^{1\times m}$ such that
$\mathbf{p} \mathbf{F} = 0 \bmod \mathbf{M}$. This generalizes the
computation of approximant bases, where the basis $\mathbf{M}$ is a diagonal
of powers of $x$.

Focusing on a Hermite basis $\mathbf{M}$, our algorithm exploits the
triangular shape to follow the divide-and-conquer approach used in fast
approximant basis computation. Besides recent techniques for this approach,
we rely on high-order lifting to perform fast modular products of the form
$\mathbf{P}\mathbf{F} \bmod \mathbf{M}$.

Our algorithm has a cost bound of $\mathcal{O}\tilde{~}(m^{\omega-1}D +
n^{\omega} D/m)$ operations in $\mathbb{K}$,
where $D =\deg(\det(\mathbf{M}))$ is the dimension of $\mathbb{K}[x]^n/\mathcal{M}$,
$\mathcal{O}\tilde{~}(\cdot)$ indicates that logarithmic factors are omitted,
and $\omega$ is the exponent of matrix multiplication. To the best of our
knowledge, this had previously only been achieved for a diagonal matrix $\mathbf{M}$.

As a particular case, our algorithm computes the shifted Popov form of
$\mathbf{M}$ within the same cost bound, up to logarithmic factors, as the
previously fastest known algorithm, which is randomized.
[+] Liangyu Chen, Svyatoslav Covanov, Davood Mohajerani and Marc Moreno Maza. Big Prime Field FFT on the GPU.
Abstract:
Prime field arithmetic plays a central role in computer algebra and
are essential to coding theory and cryptography algorithms. The prime
fields that are used in computer algebra systems, in particular in the
implementation of modular methods, are often of small characteristic,
that is, based on prime numbers that fit on a machine word.
Increasing precision beyond the machine word size can be done via the
Chinese Remainder Theorem or Hensel's Lemma.

In this paper, we consider prime fields of large characteristic,
typically fitting on $n$ machine words, where $n$ is a power of $2$.
When the characteristic of these fields is restricted to a subclass of
the generalized Fermat numbers, we show that arithmetic operations in
such fields offer attractive performance both in terms of algebraic
complexity and parallelism. In particular, these operations can be
vectorized, leading to efficient implementation of fast Fourier
transforms on graphics processing units.
[+] Parisa Alvandi, Masoud Ataei and Marc Moreno Maza. On the Extended Hensel Construction and its Application to the Computation of Limit Points.
Abstract:
The Extended Hensel Construction (EHC) is a procedure which, for an
input bivariate polynomial with complex coefficients, can serve the
same purpose as the Newton-Puiseux algorithm, and, for the multivariate
case, can be seen as an effective variant of Jung-Abhyankar Theorem.

In this paper, we show that the EHC requires only linear algebra and
univariate polynomial arithmetic. We deduce complexity estimates and
report on an software implementation together with experimental
results. This work is motivated and illustrated by the computation of
real branches of space curves as well as the computation of limit
points of constructible sets.
[+] Seung Gyu Hyun, Romain Lebreton and Éric Schost. Algorithms for structured linear systems solving and their implementation.
Abstract:
There exists a vast literature dedicated to algorithms for
structured matrices, but relatively few descriptions of actual
implementations and their practical performance. In this paper, we
consider the problem of solving Cauchy-like systems, and its
application to mosaic Toeplitz systems, in two contexts: first in
the unit cost model (which is a good model for computations over
finite fields), then over $\mathbb{Q}$. We introduce new variants of
previous algorithms and describe an implementation of these
techniques and its practical behavior. We pay a special attention to
particular cases such as the computation of algebraic approximants.

ISSAC

International Symposium on Symbolic and Algebraic Computation

Sponsored by:

Full papers

List of Accepted Papers