A complete reduction ϕ for derivatives in a differential field is a linear operator on the field over its constant subfield. The reduction enables us to decompose an element f as the sum of a derivative and the remainder ϕ(f). A direct application of ϕ is that f is in-field integrable if and only if ϕ(f) = 0.

We present two evaluation-based algorithms: one for computing logarithmic parts and the other for determining complete logarithmic parts in transcendental function integration. Empirical results illustrate that the new algorithms are markedly faster than those based respectively on resultants, the contraction of ideals, subresultants and Gröbner bases. They may be used to accelerate Risch’s algorithm for transcendental integrands, and help us to compute elementary integrals over logarithmic towers efficiently.

We consider the additive decomposition problem in primitive towers and present an algorithm to decompose a function in a certain kind of primitive tower which we call S-primitive, as a sum of a derivative in the tower and a remainder which is minimal in some sense. Special instances of S-primitive towers include differential fields generated by finitely many logarithmic functions and logarithmic integrals. A function in an S-primitive tower is integrable in the tower if and only if the remainder is equal to zero. The additive decomposition is achieved by viewing our towers not as a traditional chain of extension fields, but rather as a direct sum of certain subrings. Furthermore, we can determine whether or not a function in an S-primitive tower has an elementary integral without the need to deal with differential equations explicitly. We also show that any logarithmic tower can be embedded into a particular extension where we can further decompose the given function. The extension is constructed using only differential field operations without introducing any new constants.

This paper extends the classical Hermite-Ostrogradsky reduction for rational functions to more general functions in primitive extensions of certain types. For an element f in such an extension K , the extended reduction decomposes f as the sum of a derivative in K and another element r such that f has an antiderivative in K if and only if r=0; and f has an elementary antiderivative over K if and only if r is a linear combination of logarithmic derivatives over the constants when K is a logarithmic extension. Moreover, r is minimal in some sense. Additive decompositions may lead to reduction-based creative-telescoping methods for nested logarithmic functions, which are not necessarily D -finite.

The Abramov-Petkovsek reduction computes an additive decomposition of a hypergeometric term,which extends the functionality of the Gosper algorithm for indefinite hypergeometric summation. We modify the Abramov-Petkovsek reduction so as to decompose a hypergeometric term as the sum of a summable term and a non-summable one. The outputs of the Abramov-Petkovsek reduction and our modified version share the same required properties. The modified reduction does not solve any auxiliary linear difference equation explicitly. It is also more efficient than the original reduction according to computational experiments. Based on this reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. The new algorithm can avoid the costly computation of certificates.

Parallel telescoping is a natural generalization of differential creative-telescoping for single integrals to line integrals. It computes a linear ordinary differential operator L, called a parallel telescoper, for several multivariate functions, such that the application of L to the functions yields partial derivatives of a single function. We present a necessary and sufficient condition guaranteeing the existence of parallel telescopers for differentially finite functions, and develop an algorithm to compute minimal ones for compatible hyperexponential functions. Besides computing annihilators of parametric line integrals, we use the parallel telescoping for determining Galois groups of parameterized partial differential systems of first order.

We present a new reduction algorithm that simultaneously extends Hermite's reduction for rational functions and the Hermite-like reduction for hyperexponential functions. It yields a unique additive decomposition that allows to decide hyperexponential integrability. Based on this reduction algorithm, we design a new algorithm to compute minimal telescopers for bivariate hyperexponential functions. One of its main features is that it can avoid the costly computation of certificates. Its implementation outperforms Maple's function DEtools[Zeilberger]. We also derive an order bound on minimal telescopers that is tighter than the known ones.

We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyse the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.

A finite number of rational functions are compatible if they satisfy the compatibility conditions of a first-order linear functional system involving differential, shift and q-shift operators. We present a theorem that describes the structure of compatible rational functions. The theorem enables us to decompose a solution of such a system as a product of a rational function, several symbolic powers, a hyperexponential function, a hypergeometric term, and a q-hypergeometric term. We outline an algorithm for computing this product, and present an application.

The long-term goal initiated in this work is to obtain fast algorithms and implementations for definite integration in Almkvist and Zeilberger's framework of (differential) creative telescoping. Our complexity-driven approach is to obtain tight degree bounds on the various expressions involved in the method. To make the problem more tractable, we restrict to bivariate rational functions. By considering this constrained class of inputs, we are able to blend the general method of creative telescoping with the well-known Hermite reduction. We then use our new method to compute diagonals of rational power series arising from combinatorics.

The paper describes an algebraic construction of the inversive difference field associated with a discrete-time rational nonlinear control system under the assumption that the system is submersive. We prove that a system is submersive iff its associated difference ideal is proper, prime and reflexive. Next, we show that Kähler differentials of the above inversive field define a module over the corresponding ring of Ore operators, and relate its torsion submodule to the vector space of autonomous one-forms, introduced elsewhere. The above results allow us to check accessibility property and simplify transfer functions with computer algebra techniques.

We present a method for determining the one-dimensional submodules of a Laurent-Ore module. The method is based on a correspondence between hyperexponential solutions of associated systems and one-dimensional submodules. The hyperexponential solutions are computed recursively by solving a sequence of first-order ordinary matrix equations. As the recursion proceeds, the matrix equations will have constant coefficients with respect to the operators that have been considered.

Picard-Vessiot extensions for ordinary differential and difference equations are well known and are at the core of the associated Galois theories. In this paper, we construct fundamental matrices and Picard-Vessiot extensions for systems of linear partial functional equations having finite linear dimension. We then use those extensions to show that all the solutions of a factor of such a system can be completed to solutions of the original system.

We describe differential rational normal forms of a rational function and their properties. Based on these normal forms, we present an algorithm which, given a hyperexponential function T(x), constructs two hyperexponential functions T;1;(x) and T;2;(x) such that T(x) = T;1;'(x) + T;2;(x) and T;2;(x) is minimal in some sense. The algorithm can be used to accelerate the differential Gosper's algorithm and to compute right factors of the telescopers.

An orthogonal Ore ring is an abstraction of common properties of linear partial differential, shift and q-shift operators. Using orthogonal Ore rings, we present an algorithm for finding hyperexponential solutions of a system of linear differential, shift and q-shift operators, or any mixture thereof, whose solution space is finite-dimensional. The algorithm is applicable to factoring modules over an orthogonal Ore ring when the modules are also finite-dimensional vector spaces over the field of rational functions.

We present an algorithm for factoring a zero-dimensional left ideal in the ring Q(x, y) [∂x, ∂y], i.e. factoring a linear homogeneous partial differential system whose coefficients belong to Q(x, y), and whose solution space is finite-dimensional over Q. The algorithm computes all the zero-dimensional left ideals containing the given ideal. It generalizes the Beke-Schlesinger algorithm for factoring linear ordinary differential operators, and uses an algorithm for finding hyperexponential solutions of such ideals.

The subresultant theory for univariate commutative polynomials is generalized to Ore polynomials.The generalization includes: the subresultant theorem, gap structure, and subresultant algorithm.Using this generalization, we de ne Sylvester's resultant o f t w o Ore polynomials, derive the respective determinantal formulas for the greatest common right divisor and least common left multiple of two Ore polynomials, and present a fraction-free version of the noncommutative extended Euclidean algorithm.

Abstract. This paper presents a modular algorithm for computing the greatest common right divisor (gcrd) of two univariate Ore polynomials over Z[t]. The subresultants of Ore polynomials are used to compute the evaluation homomorphic images of the gcrd. Rational number and rational function reconstructions are used to recover coefficients. The experimental results illustrate that the present algorithm is markedly superior to the Euclidean algorithm and the subresultant algorithm for Ore polynomials. 1.

We present an efficient algorithm for testing whether a given integral polynomial has two distinct roots a, B such that fflp is a root of unity.The test is based on results obtained by investigation of the structure of the splitting field of the polynomial.By this investigate ion, we found also an improved bound for the least common multiple of the orders of roots of unity appearing as quotients of distinct roots.