Computer Science - Symbolic Computation Publications (50)


Computer Science - Symbolic Computation Publications

Given a zero-dimensional ideal I in a polynomial ring, many computations start by finding univariate polynomials in I. Searching for a univariate polynomial in I is a particular case of considering the minimal polynomial of an element in P/I. It is well known that minimal polynomials may be computed via elimination, therefore this is considered to be a "resolved problem". Read More

Deterministic recursive algorithms for the computation of generalized Bruhat decomposition of the matrix in commutative domain are presented. This method has the same complexity as the algorithm of matrix multiplication. Read More

Deterministic recursive algorithms for the computation of matrix triangular decompositions with permutations like LU and Bruhat decomposition are presented for the case of commutative domains. This decomposition can be considered as a generalization of LU and Bruhat decompositions, because they both may be easily obtained from this triangular decomposition. Algorithms have the same complexity as the algorithm of matrix multiplication. Read More

The deterministic recursive pivot-free algorithms for the computation of generalized Bruhat decomposition of the matrix in the field and for the computation of the inverse matrix are presented. This method has the same complexity as algorithm of matrix multiplication and it is suitable for the parallel computer systems. Read More

We provide an algorithm for computing semi-Fourier sequences for expressions constructed from arithmetic operations, exponentiations and integrations. The semi-Fourier sequence is a relaxed version of Fourier sequence for polynomials (expressions made of additions and multiplications). Read More

Computations over the rational numbers often suffer from intermediate coefficient swell. One solution to this problem is to apply the given algorithm modulo a number of primes and then lift the modular results to the rationals. This method is guaranteed to work if we use a sufficiently large set of good primes. Read More

For a wide variety of problems, creating detailed continuous models of (continuous) physical systems is, at the very least, impractical. Hybrid models can abstract away short transient behaviour (thus introducing discontinuities) in order to simplify the study of such systems. For example, when modelling a bouncing ball, the bounce can be abstracted as a discontinuous change of the velocity, instead of resorting to the physics of the ball (de-)compression to keep the velocity signal continuous. Read More

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. Read More

In this paper, we develop a new approach to the discrimi-nant 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 discrimi-nant without ambiguity and over any commutative ring, in particular in any characteristic. This formula also provides a new method for evaluating and computing this discrimi-nant efficiently, without the need to introduce new variables as with the well-known Cayley trick. Read More

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. Read More


We analyze the precision of the characteristic polynomial of an $n\times n$ p-adic matrix A using differential precision methods developed previously. When A is integral with precision O(p^N), we give a criterion (checkable in time O~(n^omega)) for $\chi$(A) to have precision exactly O(p^N). 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^N). Read More

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. Read More

This paper proposes a totally constructive approach for the proof of Hilbert's theorem on ternary quartic forms. The main contribution is the ladder technique, with which the Hilbert's theorem is proved vividly. Read More

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. Read More

This document contains the notes of a lecture I gave at the "Journ\'ees Nationales du Calcul Formel" (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for p-adic numbers. It is divided into two main parts: first, we present various implementations of p-adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations. Read More

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]. Read More

Laman graphs model planar frameworks that are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. Such realizations can be seen as solutions of systems of quadratic equations prescribing the distances between pairs of points. Read More

We device a new method to calculate a large number of Mellin moments of single scale quantities using the systems of differential and/or difference equations obtained by integration-by-parts identities between the corresponding Feynman integrals of loop corrections to physical quantities. These scalar quantities have a much simpler mathematical structure than the complete quantity. A sufficiently large set of moments may even allow the analytic reconstruction of the whole quantity considered, holding in case of first order factorizing systems. Read More

We introduce a "workable" notion of degree for non-homogeneous polynomial ideals and formulate and prove ideal theoretic B\'ezout Inequalities for the sum of two ideals in terms of this notion of degree and the degree of generators. We compute probabilistically the degree of an equidimensional ideal. Read More

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))$. Read More

The \emph{Orbit Problem} consists of determining, given a linear transformation $A$ on $\mathbb{Q}^d$, together with vectors $x$ and $y$, whether the orbit of $x$ under repeated applications of $A$ can ever reach $y$. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s. In this paper, we are concerned with the problem of synthesising suitable \emph{invariants} $\mathcal{P} \subseteq \mathbb{R}^d$, \emph{i. Read More

Differential (Ore) type polynomials with "approximate" polynomial coefficients are introduced. These provide an effective notion of approximate differential operators, with a strong algebraic structure. We introduce the approximate Greatest Common Right Divisor Problem (GCRD) of differential polynomials, as a non-commutative generalization of the well-studied approximate GCD problem. Read More

The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank, namely below a bound called the order of quasiseparability. These matrices arise naturally in solving PDE's for particle interaction with the Fast Multi-pole Method (FMM), or computing generalized eigenvalues. From these application fields, structured representations and algorithms have been designed in numerical linear algebra to compute with these matrices in time linear in the matrix dimension and either quadratic or cubic in the quasiseparability order. Read More

We present a variation of the modular algorithm for computing the Hermite normal form of an $\mathcal O_K$-module presented by Cohen, where $\mathcal O_K$ is the ring of integers of a number field $K$. An approach presented in (Cohen 1996) based on reductions modulo ideals was conjectured to run in polynomial time by Cohen, but so far, no such proof was available in the literature. In this paper, we present a modification of the approach of Cohen to prevent the coefficient swell and we rigorously assess its complexity with respect to the size of the input and the invariants of the field $K$. Read More

We develop algorithms to turn quotients of rings of rings of integers into effective Euclidean rings by giving polynomial algorithms for all fundamental ring operations. In addition, we study normal forms for modules over such rings and their behavior under certain quotients. We illustrate the power of our ideas in a new modular normal form algorithm for modules over rings of integers, vastly outperforming classical algorithms. Read More

We examine several matrix layouts based on space-filling curves that allow for a cache-oblivious adaptation of parallel TU decomposition for rectangular matrices over finite fields. The TU algorithm of \cite{Dumas} requires index conversion routines for which the cost to encode and decode the chosen curve is significant. Using a detailed analysis of the number of bit operations required for the encoding and decoding procedures, and filtering the cost of lookup tables that represent the recursive decomposition of the Hilbert curve, we show that the Morton-hybrid order incurs the least cost for index conversion routines that are required throughout the matrix decomposition as compared to the Hilbert, Peano, or Morton orders. Read More

We propose a new algorithm for multiplying dense polynomials with integer coefficients in a parallel fashion, targeting multi-core processor architectures. Complexity estimates and experimental comparisons demonstrate the advantages of this new approach. Read More

The complexity of matrix multiplication (hereafter MM) has been intensively studied since 1969, when Strassen surprisingly decreased the exponent 3 in the cubic cost of the straightforward classical MM to log 2 (7) $\approx$ 2.8074. Applications to some fundamental problems of Linear Algebra and Computer Science have been immediately recognized, but the researchers in Computer Algebra keep discovering more and more applications even today, with no sign of slowdown. Read More

Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. Read More

This work is a comprehensive extension of Abu-Salem et al. (2015) that investigates the prowess of the Funnel Heap for implementing sums of products in the polytope method for factoring polynomials, when the polynomials are in sparse distributed representation. We exploit that the work and cache complexity of an Insert operation using Funnel Heap can be refined to de- pend on the rank of the inserted monomial product, where rank corresponds to its lifetime in Funnel Heap. Read More

We consider the extension of the method of Gauss-Newton from complex floating-point arithmetic to the field of truncated power series with complex floating-point coefficients. With linearization we formulate a linear system where the coefficient matrix is a series with matrix coefficients. The structure of the linear system leads in the regular case to a block triangular system. Read More

Current techniques for formally verifying circuits implemented in Galois field (GF) arithmetic are limited to those with a known irreducible polynomial P(x). This paper presents a computer algebra based technique that extracts the irreducible polynomial P(x) used in the implementation of a multiplier in GF(2^m). The method is based on first extracting a unique polynomial in Galois field of each output bit independently. Read More

We extend the notion of $\mathcal{A}$-discriminant, and Kapranov's parametrization of $\mathcal{A}$-discriminant varieties, to complex exponents. As an application, we focus on the special case where $\mathcal{A}$ is a set of $n+3$ points in $\mathbb{R}^n$ with non-defective Gale dual, $g$ is a real $n$-variate exponential sum with spectrum $\mathcal{A}$ and sign vector $s$, and prove the following: For fixed $A$ and $s$, the number of possible isotopy types for the real zero set of $g$ is $O(n^2)$. We are unaware of any earlier such upper bound, except for an $O(n^6)$ bound when all the points of $\mathcal{A}$ lie in $\mathbb{Z}^n$. Read More

We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$. When $r,s \in S$, a solution $g \in G$ to $r^g = s$ can be thought of as a kind of logarithm. Read More

We provide an illustrative implementation of an analytic, infinitely-differentiable virtual machine, implementing infinitely-differentiable programming spaces and operators acting upon them, as constructed in the paper Operational calculus on programming spaces. Implementation closely follows theorems and derivations of the paper, intended as an educational guide for those transitioning from automatic differentiation to this general theory. Read More

This article is intended to an introductory lecture in material physics, in which the modern computational group theory and the electronic structure calculation are in collaboration. The effort of mathematicians in field of the group theory, have ripened as a new trend, called "computer algebra", outcomes of which now can be available as handy computational packages, and would also be useful to physicists with practical purposes. This article, in the former part, explains how to use the computer algebra for the applications in the solid-state simulation, by means of one of the computer algebra package, the GAP system. Read More

This paper uses the Continued Fraction Expansion (CFE) method for analog realization of fractional order differ-integrator and few special classes of fractional order (FO) controllers viz. Fractional Order Proportional-Integral-Derivative (FOPID) controller, FO[PD] controller and FO lead-lag compensator. Contemporary researchers have given several formulations for rational approximation of fractional order elements. Read More

Continuing a series of articles in the past few years on creative telescoping using reductions, we adapt Trager's Hermite reduction for algebraic functions to fuchsian D-finite functions and develop a reduction-based creative telescoping algorithm for this class of functions, thereby generalizing our recent reduction-based algorithm for algebraic functions, presented at ISSAC 2016. Read More

We present a survey on the developments on Groebner bases showing explicit examples in CoCoA. The CoCoA project dates back to 1987: its aim was to create a mathematician-friendly laboratory for studying Commutative Algebra, most especially Groebner bases. Since then, always maintaining this "friendly" tradition, it has evolved and has been completely rewritten. Read More

Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations. Read More

We develop a characterization for the existence of symmetries of canal surfaces defined by a rational spine curve and rational radius function. This characterization leads to a method for constructing rational canal surfaces with prescribed symmetries, and it inspires an algorithm for computing the symmetries of such canal surfaces. For Dupin cyclides in canonical form, we apply the characterization to derive an intrinsic description of their symmetries and symmetry groups, which gives rise to a method for computing the symmetries of a Dupin cyclide not necessarily in canonical form. Read More

We show that a linear-time algorithm for computing Hong's bound for positive roots of a univariate polynomial, described by K. Mehlhorn and S. Ray in an article "Faster algorithms for computing Hong's bound on absolute positiveness", is incorrect. Read More

D-finite functions and P-recursive sequences are defined in terms of linear differential and recurrence equations with polynomial coefficients. In this paper, we introduce a class of numbers closely related to D-finite functions and P-recursive sequences. It consists of the limits of convergent P-recursive sequences. Read More

Galois field (GF) arithmetic is used to implement critical arithmetic components in communication and security-related hardware, and verification of such components is of prime importance. Current techniques for formally verifying such components are based on computer algebra methods that proved successful in verification of integer arithmetic circuits. However, these methods are sequential in nature and do not offer any parallelism. Read More

Arb is a C library for arbitrary-precision interval arithmetic using the midpoint-radius representation, also known as ball arithmetic. It supports real and complex numbers, polynomials, power series, matrices, and evaluation of many special functions. The core number types are designed for versatility and speed in a range of scenarios, allowing performance that is competitive with non-interval arbitrary-precision types such as MPFR and MPC floating-point numbers. Read More

We describe an algorithm to factor sparse multivariate polynomials using O(d) bivariate factorizations where d is the number of variables. This algorithm is implemented in the Giac/Xcas computer algebra system. Read More

This document describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities with symbolic computation in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. Read More

We propose a randomized polynomial time algorithm for computing nontrivial zeros of quadratic forms in 4 or more variables over $\mathbb{F}_q(t)$, where $\mathbb{F}_q$ is a finite field of odd characteristic. The algorithm is based on a suitable splitting of the form into two forms and finding a common value they both represent. We make use of an effective formula on the number of fixed degree irreducible polynomials in a given residue class. Read More

In this paper, we study the number of times it is sufficient to differentiate the equations of a system of algebraic ODEs $F=0$ in several unknowns in order to eliminate a given subset of the unknowns and obtain equations in the rest of the unknowns. This is called differential elimination. One way to do this is to find a uniform (independent of the coefficients of $F$) upper bound N so that, after differentiating N times, the remaining computation becomes polynomial elimination. Read More

In this article algebraic constructions are introduced in order to study the variety defined by a radical parametrization (a tuple of functions involving complex numbers, $n$ variables, the four field operations and radical extractions). We provide algorithms to implicitize radical parametrizations and to check whether a radical parametrization can be reparametrized into a rational parametrization. Read More