Found 8 document(s)
Page 1 of 1
-
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem was that of Brent and Kung (1978). Recen...
-
We study the complexity of Gr¨obner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomi...
-
We present algorithms to perform modular polynomial multiplication or modular dot product efficiently in a single machine word. We pack polynomials into integers and perform several modular operations with machine intege...
-
Many identities involving special functions can be proved using the theory of D-finite or holonomic sequences and functions. This theory applies in particular to numerous combinatorial identities. This work presents a th...
-
We give an algorithm to compute asymptotic expansions of exp-log functions. This algorithm automatically computes the necessary asymptotic scale and does not suffer from problems of indefinite cancellation. In particular...
-
A number of recent papers have been concerned with algorithms to decide the limiting behaviour of functions of a single variable. Here we make a corresponding study of a class of functions of two variables, namely the ex...
-
These seminar notes represent the proceedings (some in French) of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorial models and random generation, symbolic comp...
-
Many probabilistic properties of elementary discrete combinatorial structures of interest for the average-case analysis of algorithms prove to be decidable. This paper presents a general framework in which such decision ...