Complexity of irreducibility testing for a system of linear ordinary differential equations

D. Yu. Grigor'ev

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 60-68

Résumé

Let a system ofdlinear ordinary differential equations of the first order $Y'=AY$ bе given, where $A$ is $n\times n$ matrix over a field $F(X)$, assume that the degree $\mathrm{deg}_X(A)<d$ and the size of any coefficient occurring in $A$ is at most $M$. The system $Y'=AY$ is called reducible if it is equivalent (over the field $\overline{F}(X)$) to a system $Y_1'=A_1Y_1$ with a matrix $A_1$ of the form $$ A_1= \begin{pmatrix} A_{1,1}& 0\\ A_{2,1}& A_{2,2} \end{pmatrix}. $$ An algorithm is described for testing irreducibility of the system with the running time $\exp(M(d2^n)^{d2^{n}})$.