Séminaire Calcul Formel

On a kind of non-arithmetic complexity of reduction algorithms for matrices of scalar linear differential or difference operators

by Prof. Sergei, A. Abramov

Salle XR203 (Bâtiment XLIM)

Salle XR203

Bâtiment XLIM


This talk is prepared jointly with M.Barkatou.
It is well known that if the leading matrix of a linear ordinary differential or difference system is nonsingular, then the determinant of this matrix contains some useful information on solutions of the system. We investigate a kind of complexity of known algorithms for transforming a matrix of scalar operators to an equivalent matrix which after representing it in the expanded form has non-singular frontal, or, leading matrix. The fact is that very often only the arithmetic complexity is taken into account. However, this does not give an adequate information on an algorithm. The differentiation in the differential case and the shift in the difference case are also valuable and are not usually cheap (at least, they are not for free). We try to ?ll this gap in the complexity analysis.