In this article, we consider the problem of computing polynomial solutions of general linear systems of ordinary integro-differential equations with polynomial coefficients. This algorithmic problem is a key step for many computations with matrices having linear integro-differential operator entries such as the computation of left/right syzygies, left/right inverses, left/right factorizations, and thus, for the development of an effective algebraic analysis approach for linear systems of ordinary integro-differential systems using effective elimination methods and effective homological algebra. The linear systems that appear in the above problems are generally rectangular and inhomogeneous. The contribution of this paper is to provide the first algorithm for computing polynomial solutions of inhomogeneous rectangular systems of linear integro-differential equations with polynomial coefficients. Our algorithm is implemented in the freely available Maple package Bavula.

Bavula proved that the ring \({\mathbb {I}}_1\) of polynomial ordinary integro-differential operators over a field \(\mathbb {k}\) of characteristic zero is coherent in the sense that the left/right kernel of any rectangular matrix with entries in \({\mathbb {I}}_1\) is a finitely generated left/right \({\mathbb {I}}_1\)-module. Unfortunately, his proof is not algorithmic. The contribution of this paper is to give an algorithmic proof of the coherence property of \({\mathbb {I}}_1\). We show that the kernel computation can be reduced to a kernel computation in a certain ring of skew Laurent polynomials and the computation of polynomial solutions of linear polynomial integro-differential systems. These two problems are shown to be effective. The algorithmic proof of the coherence of \({\mathbb {I}}_1\) allows us to develop an algorithmic elimination theory for linear systems of polynomial integro-differential equations with separable polynomial kernels. Finally, the algorithms presented in the paper are implemented in the freely available Maple package Bavula.

This paper provides a step forward to developing an algorithmic study of linear systems of polynomial ordinary integro-differential equations over a field <?TeX $\mathbb {k}$?> Math 1 of characteristic zero. Such a study can be achieved by first obtaining a constructive proof of the coherence property of the ring <?TeX ${\mathbb {I}}_1(\mathbb {k})$?> Math 2 of linear ordinary integro-differential operators with coefficients in <?TeX $\mathbb {k}[t]$?> Math 3 . To do that, the finiteness of the intersection of two finitely generated ideals has to be algorithmically studied. Three cases must be considered: first when evaluation operators generate the two ideals; second, when only one ideal is generated by evaluation operators; and third, when none is generated by evaluation operators. In this paper, we first explicitly characterize the intersection of two finitely generated ideals defined by evaluation operators. As for the second case, a key result is that the ideals generated by evaluations are semisimple <?TeX ${\mathbb {I}}_1$?> Math 4 -modules. We develop an algorithmic proof of this result. In particular, we show how a finite set of generators, defined by “simple” evaluations, can be obtained, that characterizes the class of finitely generated evaluation ideals of <?TeX ${\mathbb {I}}_1$?> Math 5 as finitely generated <?TeX $\mathbb {k}[t]$?> Math 6 -modules. Due to lack of space, the second and third cases will be developed in other publications.

This paper exposes some effective aspects of the algebra of linear ordinary integro-differential operators with polynomial coefficients. More precisely, we prove that the annihilator of an evaluation operator is a finitely generated ideal which can be explicitly characterized and computed. This is an advance towards the development of an effective elimination theory for ordinary integro-differential operators and an effective study of linear systems of integro-differential equations with polynomial coefficients.

In this paper, we first provide a unified algorithm for computing simple forms for systems of pseudo-linear equations. We prove that the existing methods for linear differential and difference systems can be extended to handle more general pseudo-linear systems. We explain how the reduction to a simple form can be used to compute efficiently local data for a system of pseudo-linear equations. We then propose an alternative, again based on simple forms, to previous algorithms for computing rational solutions of pseudo-linear systems. Moreover we develop a new algorithm for computing rational solutions of systems in two variables composed of linear differential and difference equations. Finally, we show that this algorithm can be generalized to the case of a system of partial pseudo-linear equations. All the algorithms described in this paper have been implemented in Maple and some examples of computations are provided.

We consider a linear differential system [A] : y'=A, y}, where A has with coefficients in C(x). The differential Galois group G of [A] is a linear algebraic group which measures the algebraic relations among solutions. Although there exist general algorithms to compute $G$, none of them is either practical or implemented. This paper proposes an algorithm to compute the Lie algebra g of G when [A] is absolutely irreducible. The algorithm is implemented in Maple.

The local analysis of formal meromorphic linear differential systems with coefficients in C((z)) has been widely studied in the literature and there exist various computer algebra algorithms for computing formal solutions of such systems. In the present paper we extend the algorithm presented in [3] to allow more general systems. More precisely, we give an algorithm for computing a formal fundamental matrix of solutions around z=0 of systems with coefficients in C((z))[[X]], where X is transcendental and hyperexponential over C((z)).

We present algorithms for computing rational and hyperexponential solutions of linear D-finite partial differential systems written as integrable connections. We show that these types of solutions can be computed recursively by adapting existing algorithms handling ordinary linear differential systems. We provide an arithmetic complexity analysis of the algorithms that we develop. A Maple implementation is available and some examples and applications are given.

International audience

Many algorithms for computing the reliability of linear or circular consecutive-k-out-of-n:F systems appeared in this Transactions. The best complexity estimate obtained for solving this problem is O(k3log(n/k)) operations in the case of i.i.d. components. Using fast algorithms for computing a selected term of a linear recurrence with constant coefficients, we provide an algorithm having arithmetic complexity O(k log (k) log(log(k)) log(n)+komega) where 2<omega< 3 is the exponent of linear algebra. This algorithm holds generally for linear, and circular consecutive-k-out-of-n:F systems with independent but not necessarily identical components.

We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer N (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in N. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree N. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in O(√N log2 N) bit operations; a deterministic one that computes a compact representation of the solution in O(N log3 N) bit operations. Similar speedups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

We investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzero polynomial solutions, the determination of the dimension of the vector space of polynomial solutions, the computation of a basis of this space. Previous algorithms have a bit complexity that is at least quadratic in the largest integer valuation N of formal Laurent series solutions at infinity, even for merely detecting the existence of nonzero polynomial solutions. We give a deterministic algorithm that computes a compact representation of a basis of polynomial solutions in O(Nlog3N) bit operations. We also give a probabilistic algorithm that computes the dimension of the space of polynomial solutions in O(√Nlog2N) bit operations. In general, the integer N is not polynomially bounded in the bit size of the input differential equation. We isolate a class of equations for which detecting nonzero polynomial solutions can be performed in polynomial complexity. We discuss implementation issues and possible extensions.

We present an algorithm for factoring differential systems with coefficients in Fp(z). Such an algorithm has already been given by van der Put in [20], [24, 13.1] and [22]. We recast his ideas to handle systems directly and we add some comparisons of strategies, an implementation in Maple1 and a complexity analysis. The central tool for factoring in characteristic p is the p curvature. We prove the links between the p-curvature and the eigenring and we show how to use these to obtain another algorithm following the exposition of Barkatou in [1].