We present two algorithms for computing what we call the absolute factorization of a difference operator. We also give an algorithm for solving third order difference equations in terms of second order equations, together with applications to OEIS sequences. The latter algorithm is similar to existing algorithms for differential equations in [4, 11], except that there is an additional order one symmetric product.

Linear recurrence operators in characteristic p are classified by their p-curvature. For a recurrence operator L, denote by χ(L) the characteristic polynomial of its p-curvature. We can obtain information about the factorization of L by factoring χ(L). The main theorem of this paper gives an unexpected relation between χ(L) and the true singularities of L. An application is to speed up a fast algorithm for computing χ(L) by desingularizing L first. Another contribution of this paper is faster desingularization.

Let f ∈ K(t) be a univariate rational function. It is well known that any non-trivial decomposition g o h, with g,h ∈ K(t), corresponds to a non-trivial subfield K(f(t)) ⊊ L ⊊ K(t) and vice-versa. In this paper we use the idea of principal subfields and fast subfield-intersection techniques to compute the subfield lattice of K(t)/K(f(t)). This yields a Las Vegas type algorithm with improved complexity and better run times for finding all non-equivalent complete decompositions of f.

Finding closed form solutions of differential equations has a long history in computer algebra. For example, the Risch algorithm (1969) decides if the equation y' = f can be solved in terms of elementary functions. These are functions that can be written in terms of exp and log, where "in terms of" allows for field operations, composition, and algebraic extensions. More generally, functions are in closed form if they are written in terms of commonly used functions. This includes not only exp and log, but other common functions as well, such as Bessel functions or the Gauss hypergeometric function. Given a differential equation L, to find solutions written in terms of such functions, one seeks a sequence of transformations that sends the Bessel equation, or the Gauss hypergeometric equation, to L. Although random equations are unlikely to have closed form solutions, they are remarkably common in applications. For example, if y = ∑n=0∞ an xn has a positive radius of convergence, integer coefficients an, and satisfies a second order homogeneous linear differential equation L with polynomial coefficients, then L is conjectured to be solvable in closed form. Such equations are common, not only in combinatorics, but in physics as well. The talk will describe recent progress in finding closed form solutions of differential and difference equations, as well as open questions.

Let L be a second order differential equation with coefficients in C(x). The goal of this paper is to find solutions of L in the form exp(∫r dx#8226;2; F1(a1a2b1; f)(1) where r; f Ε Q(x), and a1; a2; b1 ΕQ.

This tutorial will explain the algorithm behind the currently fastest implementations for univariate factorization over the rationals. The complexity will be analyzed; it turns out that modifications were needed in order to prove a polynomial time complexity while preserving the best practical performance.

Let L be a second order linear homogeneous differential equation with rational function coefficients. The goal in this paper is to solve L in terms of hypergeometric function 2F1(a,b;c|f) where f is a rational function of degree 3.

Let L be a second order linear ordinary differential equation with coefficients in C(x). The goal in this paper is to reduce L to an equation that is easier to solve. The starting point is an irreducible L, of order two, and the goal is to decide if L is projectively equivalent to another equation L that is defined over a subfield C(f) of C(x).

State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (less Hensel lifting) for these more common polynomials. In addition, factoring has suffered from a 25 year complexity gap because the best implementations are much faster in practice than their complexity bounds. We illustrate that this complexity gap can be closed by providing an implementation which is comparable to the best current implementations and for which competitive complexity results can be proved.

Given a field extension K/k of degree n we are interested in finding the subfields of K containing k. There can be more than polynomially many subfields. We introduce the notion of generating subfields, a set of up to n subfields whose intersections give the rest. We provide an efficient algorithm which uses linear algebra in k or lattice reduction along with factorization. Our implementation shows that previously difficult cases can now be handled.

The goal in this paper is to find closed form solutions for linear recurrence equations, by transforming an input equation L to an equation Ls with known solutions. The main problem is how to find a solved equation Ls to which L can be reduced. We solve this problem by computing local data at singularities, data that remains invariant under the transformations used.

In this paper we give a new algorithm to compute Liouvillian solutions of linear difference equations. The first algorithm for this was given by Hendriks in 1998, and Hendriks and Singer in 1999. Several improvements have been published, including a paper by Cha and van Hoeij that reduces the combinatorial problem. But the number of combinations still depended exponentially on the number of singularities. For irreducible second order equations, we give a short and very efficient algorithm; the number of combinations is 1.

A linear differential equation with rational function coefficients has a Bessel type solution when it is solvable in terms of Bν(f), Bν+1(f). For second order equations, with rational function coefficients, f must be a rational function or the square root of a rational function. An algorithm was given by Debeerst, van Hoeij, and Koepf, that can compute Bessel type solutions if and only if f is a rational function. In this paper we extend this work to the square root case, resulting in a complete algorithm to find all Bessel type solutions. 1.

In this paper we give a new algorithm to compute Liouvillian solutions of linear difference equations. Compared to the prior algorithm by Hendriks and Singer, our main contribution consists of two theorems that significantly reduce the number of combinations that the algorithm will check.

For differential operators of order 2, this paper presents a new method that combines generalized exponents to find those solutions that can be represented in terms of Bessel functions.

This paper presents a simplified version of a method by Michael Singer for reducing a third order linear ode to a second order linear ode whenever possible. An implementation is available as well.

Given a second order linear differential equations with coefficients in a field k=C(x), the Kovacic algorithm finds all Liouvillian solutions, that is, solutions that one can write in terms of exponentials, logarithms, integration symbols, algebraic extensions, and combinations thereof. A theorem of Klein states that, in the most interesting cases of the Kovacic algorithm (i.e when the projective differential Galois group is finite), the differential equation must be a pullback (a change of variable) of a standard hypergeometric equation. This provides a way to represent solutions of the differential equation in a more compact way than the format provided by the Kovacic algorithm. Formulas to make Klein's theorem effective were given in [4, 2, 3]. In this paper we will give a simple algorithm based on such formulas. To make the algorithm more easy to implement for various differential fields k, we will give a variation on the earlier formulas, namely we will base the formulas on invariants of the differential Galois group instead of semi-invariants.

We consider the problem of finding closed form solutions of linear differential equations having coefficients which are elliptic functions. For second order equations we show how to solve such an ode in terms of doubly periodic functions of the second kind. The method depends on two procedures, the first using a second symmetric power of an ode along with a decision procedure for determining when such equations have elliptic function solutions while the second involves the computation of exponential solutions.

Let L be an algebraic function field in k ≥ 0 parameters t;1;, ..., t;k;. Let f;1;, f;2; be non-zero polynomials in L[x]. We give two algorithms for computing their gcd. The first, a modular GCD algorithm, is an extension of the modular GCD algorithm of Brown for Z[x;1;,...,x;n;] and Encarnacion for Q(α)[x] to function fields. It is uses rational number and rational function reconstruction and trial division. The second, a fraction-free algorithm, is a modification of the Moreno Maza and Rioboo algorithm for computing gcds over triangular sets. The modification reduces coefficient growth in L to be linear. We show how to extend the modular GCD algorithm to work when the minimal polynomial for L is not irreducible. We give an empirical comparison of the two algorithms using implementations in Maple.

We consider the problem of computing the monic gcd of two polynomials over a number field L = ℚ(α1,…,αn). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over ℚ can be modified to work for ℚ(α).Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n > 1 without converting to a single field extension. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test.Our third contribution is the design of a data structure for representing multivariate polynomials over number fields with multiple field extensions. We have a complete implementation of the modular GCD algorithm using it. We provide details of some practical improvements.

A new algorithm is presented for factoring bivariate approximate polynomials over C[x, y]. Given a particular polynomial, the method constructs a nearby composite polynomial, if one exists, and its irreducible factors. Subject to a conjecture, the time to produce the factors is polynomial in the degree of the problem. This method has been implemented in Maple, and has been demonstrated to be efficient and numerically robust.

This paper presents a new and sharper bound for denominators of rational solutions of linear dierence and q-dierence equations.This can be used to compute rational solutions more eciently.

We introduce the notion of the adjoint Ore ring and give a definition ofadjoint polynomial, operator andequation.We apply thk for integrating solutions of Ore equations.

The topic of this paper is a fast method to compute the rational solutions of a certain differential equation that will be called the mixed differential equation.This can be applied to speed up the factorization of completely reducible linear differential operators with rational functions coefficients.

Contains fulltext : 223293.pdf (Author’s version preprint ) (Closed access)

In this paper I want to present a new method for computing parametrizations of algebraic curves. Basically this method is a direct application of integral basis computation. Examples show that this method is faster than older methods.