Given a system of ordinary differential equations represented by a straight-line program, we show how to compute an equivalent ordinary differential system represented by a straight-line program which only uses ring operations. Under mild assumptions, our method essentially runs in linear time.

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Efficient algorithms for this kind of "amortized" multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.

We revisit the seminal Brill-Noether algorithm in the rather generic situation of smooth divisors over a nodal plane projective curve. Our approach takes advantage of fast algorithms for polynomials and structured matrices. We reach sub-quadratic time for computing a basis of a Riemann-Roch space. This improves upon previously known complexity bounds.

Let K be a fixed effective field. The most straightforward approach to compute with an element in the algebraic closure of K is to compute modulo its minimal polynomial. The determination of a minimal polynomial from an arbitrary annihilator requires an algorithm for polynomial factorization over K . Unfortunately, such algorithms do not exist over generic effective fields. They do exist over fields that are explicitly generated over their prime sub-field, but they are often expensive. The dynamic evaluation paradigm, introduced by Duval and collaborators in the eighties, offers an alternative algorithmic solution for computations in the algebraic closure of K . This approach does not require an algorithm for polynomial factorization, but it still suffers from a non-trivial overhead due to suboptimal recomputations. For the first time, we design another paradigm, called directed evaluation, which combines the conceptual advantages of dynamic evaluation with a good worst case complexity bound.

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.

Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M p ( n ) denote the bit complexity of multiplying two polynomials in F p [ X ] of degree less than n . For n large compared to p , we establish the bound M p ( n ) = O ( n log n 8 log* n log p ), where log * n = min{ k ϵ N: log … k × … log n ≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M p ( n ) = O ( n log n log log n log p ), which essentially goes back to the 1970s.

Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster “transient” variant of ball arithmetic.

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

Modular integer arithmetic occurs in many algorithms for computer algebra, cryptography, and error correcting codes. Although recent microprocessors typically offer a wide range of highly optimized arithmetic functions, modular integer operations still require dedicated implementations. In this article, we survey existing algorithms for modular integer arithmetic and present detailed vectorized counterparts. We also describe several applications, such as fast modular Fourier transforms and multiplication of integer polynomials and matrices. The vectorized algorithms have been implemented in C++ inside the free computer algebra and analysis system M athemagix . The performance of our implementation is illustrated by various benchmarks.

In this paper, we show how to speed up the computation of fast Fourier transforms over complex numbers for "medium" precisions, typically in the range from 100 until 400 bits. On the one hand, such precisions are usually not supported by hardware. On the other hand, asymptotically fast algorithms for multiple precision arithmetic do not pay off yet. The main idea behind our algorithms is to develop efficient vectorial multiple precision fixed point arithmetic, capable of exploiting SIMD instructions in modern processors.

Consider a finite field Fq whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over Fq, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the MATHEMAGIX computer algebra system, confirming that our ideas gain by a factor ten at least in practice, for sufficiently large inputs.

In this paper, we give a detailed description of the interface between the MATHEMAGIX language and C++. In particular, we describe the mechanism which allows us to import a C++ template library (which only permits static instantiation) as a fully generic MATHEMAGIX template library.

In this article, we study the problem of multiplying two multivariate polynomials which are somewhat but not too sparse, typically like polynomials with convex supports. We design and analyze an algorithm which is based on blockwise decomposition of the input polynomials, and which performs the actual multiplication in an FFT model or some other more general so called "evaluated model". If the input polynomials have total degrees at most d, then, under mild assumptions on the coefficient ring, we show that their product can be computed with O (s1.5337) ring operations, where s denotes the number of all the monomials of total degree at most 2d.

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.

Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

Let ƒ1, … , ƒs be polynomials in n variables over a field of characteristic zero and d be the maximum of their total degree. We propose a new probabilistic algorithm for computing a geometric resolution of each equidimensional part of the variety defined by the system ƒ1 = ··· = ƒs = 0. The returned resolutions are encoded by means of Straight-Line Programs and the complexity of the algorithm is polynomial in a geometric degree of the system. In the worst case this complexity is asymptotically polynomial in sdn.