Polyhedral affinoid algebras have been introduced by Einsiedler, Kapranov and Lind in [5] to connect rigid analytic geometry (analytic geometry over non-archimedean fields) and tropical geometry. In this article, we present a theory of Gröbner bases for polytopal affinoid algebras that extends both Caruso et al.’s theory of Gröbner bases on Tate algebras of [1] and Pauer et al.’s theory of Gröbner bases on Laurent polynomials of [9].

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.

It is well known that for a first order system of linear difference equations with rational function coefficients, a solution that is holomorphic in some left half plane can be analytically continued to a meromorphic solution in the whole complex plane. The poles stem from the singularities of the rational function coefficients of the system. Just as for differential equations, not all of these singularities necessarily lead to poles in solutions, as they might be what is called removable. In our work, we show how to detect and remove these singularities and further study the connection between poles of solutions and removable singularities. We describe two algorithms to (partially) desingularize a given difference system and present a characterization of removable singularities in terms of shifts of the original system.

We give a new algorithm for the formal reduction of linear differential systems with Laurent series coefficients. We show how to obtain a decomposition of Balser, Jurkat and Lutz using eigenring techniques. We establish structural information on the obtained indecomposable subsystems and retrieve information on their invariants such as ramification. We show why classical algorithms then perform well on these subsystems. We also give precise estimates of the precision on the power series which is required in each step of our algorithm. The algorithm is implemented in Maple. We give examples in [14].

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

In this paper we present a new algorithm which, given a system of first order linear differential equations with rational function coefficients, constructs an equivalent system with rational function coefficients, whose finite singularities are exactly the non-apparent singularities of the original system. This algorithm is implemented in the computer algebra system Maple and is illustrated by examples.

In this paper, we present an algorithm for computing a fundamental matrix of formal solutions of completely integrable Pfaffian systems with normal crossings in two variables. First, we associate to the Pfaffian system a singular linear system of ordinary differential equations from which its formal invariants can be efficiently derived. After that, we give a generalization of the Moser-based rank reduction algorithm of [5]. These two items allow us to construct formal solutions by following the recursive algorithm given in [4] for singular linear systems of ordinary differential equations. Our algorithm builds upon the package ISOLDE [9] and is implemented in the computer algebra system Maple.

In this article, we treat the turning points of singularly-perturbed linear differential systems and reduce their parameter singularity's rank to its minimal integer value. Our approach is Moser-based, i.e. it is based on the reduction criterion introduced for singular linear differential systems by Moser [21]. Such algorithms have proved their utility in the symbolic resolution of the systems of linear functional equations [5, 6, 8], giving rise to the package ISOLDE [7], as well as in the perturbed algebraic eigenvalue problem [13]. In particular, we generalize the Moser-based algorithm described in [4]. Our algorithm, implemented in the computer algebra system Maple, paves the way for efficient symbolic resolution of singularly-perturbed linear differential systems as well as further applications of Moser-based reduction over bivariate (differential) fields [1].

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.

Let F be a differential field generated from the rational functions over some constant field by one hyperexponential extension. We present an algorithm to compute the solutions in Fn of systems of n first-order linear ODEs. Solutions in F of a scalar ODE of higher order can be determined by an algorithm of Bronstein and Fredet. Our approach avoids reduction to the scalar case. We also give examples to show how this can be applied to integration.

We consider an analytic vector field x = X(x\right) and study, via a variational approach, whether it may possess analytic first integrals. We assume one solution Γ is known and we study the successive variational equations along Γ. Constructions in [MRRS07] show that Taylor expansion coefficients of first integrals appear as rational solutions of the dual linearized variational equations. We show that they also satisfy linear "filter" conditions. Using this, we adapt the algorithms from [Bar99, vHW97] to design new ones optimized to this effect and demonstrate their use. Part of this work stems from the first author's Ph.D. thesis1 [AM10].

The main purpose of this tutorial is to present and explain symbolic methods for studying systems of linear ordinary differential equations with emphasis on direct methods and their implementation in computer algebra systems.

In this paper, we investigate the local analysis of systems of linear differential-algebraic equations (DAEs) and second-order linear differential systems. In the first part of the paper, we show how one can transform an input linear DAE into a reduced form that allows for the decoupling of the differential and algebraic components of the system. Classification of singularities of linear DAEs are defined and discussed. In the second part of the paper, we extend this approach to second-order linear differential systems and discuss two applications: the classification of singularities and the computation of regular solutions. The present paper is the first step towards a generalisation of the formal reduction of first-order ODEs to higher-order systems. Our algorithm has been implemented in the computer algebra system Maple as part of the ISOLDE package.

International audience

The algorithmic classification of singularities of linear differential systems via the computation of Moser- and super-irreducible forms as introduced in [21] and [16] respectively has been widely studied in Computer Algebra ([8, 12, 22, 6, 10]). Algorithms have subsequently been given for other forms of systems such as linear difference systems [4, 3] and the perturbed algebraic eigenvalue problem [18]. In this paper, we extend these concepts to the general class of systems of linear functional equations. We derive a definition of regularity for these type of equations, and an algorithm for recognizing regular systems. When specialised to q-difference systems, our results lead to new algorithms for computing polynomial solutions and regular formal solutions.

The notion of irreducible forms of systems of linear differential equations as defined by Moser [14 ] and its generalisation, the super-irreducible forms introduced by Hilali/Wazner in [9 ] are important concepts in the context of the symbolic resolution of systems of linear differential equations [3,15,16 ]. In this paper, we give a new algorithm for computing, given an arbitrary linear differential system with formal power series coefficients as input, an equivalent system which is super-irreducible. Our algorithm is optimal in the sense that it computes transformation matrices which obtain a maximal reduction of rank in each step of the algorithm. This distinguishes it from the algorithms in [9,14,2] and generalises [7].

Several algorithms exist to reduce the rank of an ordinary linear differential system at a point, say 0, to its minimal value, the Poincaré rank (also, sometimes called true Poincaré rank). We extend Levelt algorithm, based on the existence of stationary sequences of free lattices, to completely integrable Pfaffian systems with normal crossings in two variables dY = (1/xp+1 A(x, y)dx + 1/yq+1B(x, y)dy)Y where A, B are m×m matrices with entries in C[[x, y]] and p, q are non negative integers. The algorithm returns a completely integrable Pfaffian system with normal crossings dZ = (1/xp+1 A(x, y)dx + 1/yq+1 B(x, y)dy)Z equivalent to the initial one through a formal meromorphic gauge transformation at the origin 0, the integers p, q being simultaneously and individually the smallest possible. We, thus, set up a first step towards the explicit calculation of formal solutions of such systems.The particular case of a regular singular point at 0 is equivalent to p = q = 0, a condition easily checked by applying the algorithm.

Given two linear dierential systems with rational function coecients, we give an algorithm to decide whether these two systems are equivalent and to compute the corresponding transformation matrices.In the second part of the paper, we use this for computing factorizations of completely reducible systems.In [20] algorithms for solving these problems in the case of scalar dierential equations have been given.They are based upon the local analysis of the singularities of the equation.Our method uses local methods as well, but it avoids converting to the scalar case.The algorithms are implemented and available 1 .

It is importantto know whether a linear system of differential equations haa a regular or an irregular singularity at a given point zo of the complex domain C. Moser has given an algorithm to solve this problem.His algorithm needs to compute with the individual singularities of the system and requires computations in algebraic extensions of the constant field for the coefficients of the system.This may represents an important drawback from a practical point of view.This paper describes a rational version of Moser's algorithm which has been implemented in the Maple computer algebra system for systems of differential equations with coefficients in Q(z).It never needs to compute with the individual singularities of the system and avoids any algebraic extensions.In addition, our algorithm reduces a linear system of differential equations with coefficients in Q(x) to an "irreducible" form which is particularly convenient if one wishes to compute invariants at singularities.

This paper deals with linear systems of difference equations whose coefficients admit generalized factorial series representations at z = ∞. We shall give a criterion by which a given system is determined to have a regular singularity.