Introduction to LFsys package


An algorithm to put linear recurrent systems in the form convenient for using the systems for the search for polynomial, power and Laurent series and other solutions of various linear functional systems (differential, difference and q-difference) is implemented.

Some algorithms to search solutions of functional systems are also implemented.

All proposed algorithms do not require preliminary uncoupling of linear systems.


Linear recurrent systems with variable coefficients are of interest for combinatorics and numeric computation. Additionaly they give an useful auxiliary tool for constructing solutions of linear functional equations (differential, difference and q-difference). We mean mainly solutions in the form of polynomials, power and Laurent series, rational functions and so on. If we consider the search for such solutions of linear functional systems then we will deal with recurrent systems. But operating with recurrent systems is much more complicated than operating with scalar recurrences.

Solving some computer algebra problems one faces the situation when it is necessary to transform such a system into an equivalent system with nonsingular leading (or analogously, trailing) matrix.

We implement transformations based on a special process of EG-eliminations by S.A.Abramov in the explicit matrix of the system. EG-eliminations bear similarities to the Euclid algorithm and the Gauss method (E = Euclidean, G = Gaussian), they either allow one to recognize the dependence of the recurrences, or else lead to a system of the desired form. It is possible that the transformation additionally results in a finite set of relations for the initial values of each of the solutions of the new system.

It is shown that EG-eliminations can be used to construct polynomial solutions and series solutions for linear functional systems with polynomial coefficients. The approach based on EG-eliminations allows one find rational solutions of differential systems. EG-eliminations are an alternative (in the contex of these problems) for reducing differential or difference system to super-irreducible form. But EG-eliminations has the advantage of simplicity.

The LFsys package

The LFsys package is the implementation of the algorithm of EG-elimination and algorithms for finding rational and polynomial solutions of the Linear Functional systems of the equations with polynomial coefficients.

The package has a number of functions. The main function implementing the process of EG-eliminations is mat_triang.

The following table shoes the role of the EG-eliminations in finding solution by cases:


Differential case

Difference case

q-Difference case

Finding of the universal denominator EG-eliminations (leading matrix) in singular points Dispersion algorithm by S.A.Abramov q-Dispersion algorithm and EG-eliminations (leading matrix) in 0
Bounding the degree of polynomial solution EG-eliminations (trailing matrix) EG-eliminations (trailing matrix) EG-eliminations (trailing matrix)
Building the polynomial solution EG-eliminations (leading matrix) EG-eliminations (leading matrix) EG-eliminations (leading matrix)

So as it can be seen that other functions of the package uses mat_triang to find different charcteristics of the solutions.

The package is implemented under Maple V Release 4 but seems to work under Maple V Release 5 as well.

Implemented by Denis Khmelnov.