Computer Science - Symbolic Computation Publications (50)

Search

Computer Science - Symbolic Computation Publications

This paper is concerned with the computation of representation matrices for the action of Frobenius to the cohomology groups of algebraic varieties. Specifically we shall give an algorithm to compute the matrices for arbitrary algebraic varieties with defining equations over perfect fields of positive characteristic, and estimate its complexity. Moreover, we propose a specific efficient method, which works for complete intersections. Read More


A special homotopy continuation method, as a combination of the polyhedral homotopy and the linear product homotopy, is proposed for computing all the isolated solutions to a special class of polynomial systems. The root number bound of this method is between the total degree bound and the mixed volume bound and can be easily computed. The new algorithm has been implemented as a program called LPH using C++. Read More


We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the 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}$, with $s<2k$, 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. Read More


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


In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evaluation of f(a) for a sufficiently large number a. In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to the univariate case. Read More


In this note, we extend modular techniques for computing Gr\"obner bases from the commutative setting to the vast class of noncommutative $G$-algebras. As in the commutative case, an effective verification test is only known to us in the graded case. In the general case, our algorithm is probabilistic in the sense that the resulting Gr\"obner basis can only be expected to generate the given ideal, with high probability. Read More


With the emergence of cloud computing services, computationally weak devices (Clients) can delegate expensive tasks to more powerful entities (Servers). This raises the question of verifying a result at a lower cost than that of recomputing it. This verification can be private, between the Client and the Server, or public, when the result can be verified by any third party. Read More


New solution method for the systems of linear equations in commutative integral domains is proposed. Its complexity is the same that the complexity of the matrix multiplication. Read More


In 1969, V. Strassen improves the classical~2x2 matrix multiplication algorithm. The current upper bound for 3x3 matrix multiplication was reached by J. Read More


We show a method for constructing a polynomial interpolating roots' multiplicities of another polynomial, that does not use companion matrices. This leads to a modification to Guersenzvaig--Szechtman square-free decomposition algorithm that is more efficient both in theory and in practice. Read More


The problem to decide whether a given multivariate (quasi-)rational function has only positive coefficients in its power series expansion has a long history. It dates back to Szego in 1933 who showed certain quasi-rational function to be positive, in the sense that all the series coefficients are positive, using an involved theory of special functions. In contrast to the simplicity of the statement, the method was surprisingly difficult. Read More


We present a new insight into the systematic generation of minimal solvers in computer vision, which leads to smaller and faster solvers. Many minimal problem formulations are coupled sets of linear and polynomial equations where image measurements enter the linear equations only. We show that it is useful to solve such systems by first eliminating all the unknowns that do not appear in the linear equations and then extending solutions to the rest of unknowns. Read More


We introduce orbital graphs and discuss some of their basic properties. Then we focus on their usefulness for search algorithms for permutation groups, including finding the intersection of groups and the stabilizer of sets in a group. Read More


For matrices with displacement structure, basic operations like multiplication, inversion, and linear system solving can all be expressed in terms of the following task: evaluate the product $\mathsf{A}\mathsf{B}$, where $\mathsf{A}$ is a structured $n \times n$ matrix of displacement rank $\alpha$, and $\mathsf{B}$ is an arbitrary $n\times\alpha$ matrix. Given $\mathsf{B}$ and a so-called "generator" of $\mathsf{A}$, this product is classically computed with a cost ranging from $O(\alpha^2 \mathscr{M}(n))$ to $O(\alpha^2 \mathscr{M}(n)\log(n))$ arithmetic operations, depending on the type of structure of $\mathsf{A}$; here, $\mathscr{M}$ is a cost function for polynomial multiplication. In this paper, we first generalize classical displacement operators, based on block diagonal matrices with companion diagonal blocks, and then design fast algorithms to perform the task above for this extended class of structured matrices. Read More


We write a procedure for constructing noncommutative Groebner bases. Reductions are done by particular linear projectors, called reduction operators. The operators enable us to use a lattice construction to reduce simultaneously each S-polynomial into a unique normal form. Read More


We present new algorithms for computing the low n bits or the high n bits of the product of two n-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full 2n-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences. Read More


A characteristic pair is a pair (G,C) of polynomial sets in which G is a reduced lexicographic Groebner basis, C is the minimal triangular set contained in G, and C is normal. In this paper, we show that any finite polynomial set P can be decomposed algorithmically into finitely many characteristic pairs with associated zero relations, which provide representations for the zero set of P in terms of those of Groebner bases and those of triangular sets. The algorithm we propose for the decomposition makes use of the inherent connection between Ritt characteristic sets and lexicographic Groebner bases and is based essentially on the structural properties and the computation of lexicographic Groebner bases. Read More


The Butler-Portugal algorithm for obtaining the canonical form of a tensor expression with respect to slot symmetries and dummy-index renaming suffers, in certain cases with a high degree of symmetry, from $O(n!)$ explosion in both computation time and memory. We present a modified algorithm which alleviates this problem in the most common cases---tensor expressions with subsets of indices which are totally symmetric or totally antisymmetric---in polynomial time. We also present an implementation of the label-renaming mechanism which improves upon that of the original Butler-Portugal algorithm, thus providing a significant speed increase for the average case as well as the highly-symmetric special case. Read More


The aim of this paper is to present a new algorithm for proving mixed trigonometric-polynomial inequalities by reducing to polynomial inequalities. Finally, we show the great applicability of this algorithm and as examples, we use it to analyze some new rational (Pade) approximations of the function $\cos^2(x)$, and to improve a class of inequalities by Z.-H. Read More


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


We propose and implement an algorithm for solving an overdetermined system of partial differential equations in one unknown. Our approach relies on Bour-Mayer method to determine compatibility conditions via Jacobi-Mayer brackets. We solve compatible systems recursively by imitating what one would do with pen and paper: Solve one equation, substitute the solution into the remaining equations and iterate the process until the equations of the system are exhausted. 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


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


2017Feb

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