|
Zapiski Nauchnykh Seminarov LOMI, 1991, Volume 192, Pages 60–68
(Mi znsl4946)
|
|
|
|
Complexity of irreducibility testing for a system of linear ordinary differential equations
D. Yu. Grigor'ev
Abstract:
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}})$.
Citation:
D. Yu. Grigor'ev, “Complexity of irreducibility testing for a system of linear ordinary differential equations”, Computational complexity theory. Part 5, Zap. Nauchn. Sem. LOMI, 192, Nauka, Leningrad, 1991, 60–68; J. Math. Sci., 70:4 (1994), 1881–1886
Linking options:
https://www.mathnet.ru/eng/znsl4946 https://www.mathnet.ru/eng/znsl/v192/p60
|
|