Consider formal power series \(f_1, \ldots , f_k \in \mathbb {Q} [[z]]\) that are defined as the solutions of a system of polynomial differential equations together with a sufficient number of initial conditions. Given \(P \in \mathbb {Q} [F_1, \ldots , F_k]\), several algorithms have been proposed in order to test whether P(f1, …, fk) = 0. In this paper, we present such an algorithm for the case where f1, …, fk are so-called transseries instead of power series.

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.

Working in the multitape Turing model, we show how to reduce the problem of matrix transposition to the problem of integer multiplication. If transposing an $n \times n$ binary matrix requires $\Omega\left(n^{2} \log n\right)$ steps on a Turing machine, then our reduction implies that multiplying n-bit integers requires $\Omega(n \log n)$ steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected. Index Terms-matrix transposition, integer multiplication, lower bounds

What is the most efficient way to compute the exponential function when allowing for the precomputation of lookup tables? In this paper we study this question as a function of the working precision and analyze both classical and asymptotically fast approaches. We present new complexity results, discuss efficient parameter choices and point out improvements that lead to speedups over existing implementations.

In this paper, we survey various basic and higher level tasks in computer algebra from the complexity perspective. Particular attention is paid to problems that are fundamental from this point of view and interconnections between other problems.

Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than \( n \) over a finite field \( \mathbb {F}_q \) with \( q \) elements can be multiplied in time \( O (n \log q \log (n \log q)) \) , uniformly in \( q \) . Under the same hypothesis, we show how to multiply two \( n \) -bit integers in time \( O (n \log n) \) ; this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [ 22 ]. Our results hold in the Turing machine model with a finite number of tapes.

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.

One fundamental problem in symbolic computation is zero testing of expressions that involve special functions. Several such zero tests have been designed for the case when such special functions satisfy algebraic differential equations or linear difference equations. In this paper, we present an algorithm for the case of power series solutions to certain non-linear difference equations.

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.

We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main algorithms do not require any additional information or encoding other than the original inputs and the erroneous output. Their running time is softly linear in the dimension times the number of errors when there are few errors, smoothly growing to the cost of fast matrix multiplication as the number of errors increases. We also present applications to general linear system solving.

Let G be the reduced Grö bner basis of a zero-dimensional ideal I ⊆ K[X, Y] of bivariate polynomials over an effective field K. Modulo suitable regularity assumptions on G and suitable precomputations as a function of G , we prove the existence of a quasi-optimal algorithm for the reduction of polynomials in K [X, Y] with respect to G . Applications include fast algorithms for multiplication in the quotient algebra A=K[X, Y] / I and for conversions due to changes of the term ordering.

Current general purpose libraries for multiple precision floating-point arithmetic such as MPFR suffer from a large performance penalty with respect to hard-wired instructions. The performance gap tends to become even larger with the advent of wider SIMD arithmetic in both CPUs and GPUs. In this paper, we present efficient algorithms for multiple precision floating- point arithmetic that are suitable for implementations on SIMD processors. A.C.M. subject classification: G.1.0 Computer-arithmetic A.M.S. subject classification: 65Y04, 65T50, 68W30.

Let Fq be the finite field with q elements and let ω be a primitive n-th root of unity in an extension field Fqd of Fq. Given a polynomial P ∈ Fq [x] of degree less than n, we will show that its discrete Fourier transform (P (ω0), ..., P (ωn - 1)) ∈ Fqdn can be computed essentially d times faster than the discrete Fourier transform of a polynomial Q ∈ Fqd [x] of degree less than n, in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of Fqd over Fq.

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 previous work, we have introduced several fast algorithms for relaxed power series multiplication (also known under the name on-line multiplication) up to a given order n. The fastest currently known algorithm works over an effective base field K with sufficiently many 2p-th roots of unity and has algebraic time complexity O(n log ne2[EQUATION]). In this paper, we will generalize this algorithm to the cases when K is replaced by an effective ring of positive characteristic or by an effective ring of characteristic zero, which is also torsion-free as a Z-module and comes with an additional algorithm for partial division by integers. In particular, we may take K to be any effective field. We will also present an asymptotically faster algorithm for relaxed multiplication of p-adic numbers.

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 paper, we consider the problem of efficient computations with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for multiplying polynomials supported on a lattice.

We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

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.

Until now, the area of symbolic computation has mainly focused on the manipulation of algebraic expressions. Based on earlier, theoretical work, the author has started to develop a systematic C++ library Mmxlib for mathematically correct computations with more analytic objects, like complex numbers and analytic functions. While implementing the library, we found that several of our theoretical ideas had to be further improved or adapted. In this paper, we report on the current implementation, we present several new results and suggest directions for future improvements.

In this paper, we present a truncated version of the classical Fast Fourier Transform. When applied to polynomial multiplication, this algorithm has the nice property of eliminating the "jumps" in the complexity at powers of two. When applied to the multiplication of multivariate polynomials or truncated multivariate power series, we gain a logarithmic factor with respect to the best previously known algorithms.

In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. In this paper, we present a new relaxed multiplication algorithm for the resolution of linear equations. The algorithm has the same asymptotic time complexity as our previous algorithms, but we improve the space overhead in the divide and conquer model and the constant factor in the F.F.T. model.

In this paper, we present a new zero-test for expressions which are constructed from formal power solutions to algebraic differential equations using the ring operations and differentiation. We also provide a survey of all existing methods that we know of and a detailed comparison of these methods with our approach.

Generalized polylogarithms (in our sense) are de ned as iterated integrals with respect to the two dierential forms !0 = dz=z and !1 = dz=(1 , z).We prove a n algorithm which computes the monodromy of these special functions.This algorithm, implemented in Axiom, is based on the Lyndon basis.The monodromy formulae involve special constants, called multiple zeta values.We prove that the algebra of polylogarithms is isomorphic to a shue algebra.

For most fast algorithms to manipulate formal power series, a fzustmultiplication algorithm is essential.If one desires to compute all coefficients of a product of two power series up to a given order, then several efficient algorithms are available, such as fast Fourier multiplication.However, one often needs a lazy multiplication algorithm, for instance when the product computation is part of the computation of the coefficients of an implicitly defined power series.In this paper, we describe two lazy multiplication algorithms, which are faster than the naive method.In articular, we Y give analgorithm oftimecomplexity O(nlog n). Key words: Imwer series, multiplication, algorithm.I'ermission to make rfigital/hard copy of all or part of this work for personal or classroom use is granted without fee provided that copies are not niade or dist rihuted for profit or commercial advantage, the

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, an asymptotic equivalent can always be computed for a given exp-log function.