LCM decomposition of linear differential operators in positive characteristic

We present an algorithm to compute $\mathrm{L}\mathrm{C}\mathrm{L}\mathrm{M}$-decompositions for linear differentials operators with coefficients in the rational function field of characteristic $p$, ${\mathbb{F}}_{p^n}(t)$. We show that for an operator $L$ of order $r$ with coefficients of degree $d$, it finishes in polynomial time in $r$, $d$ and $p$. This algorithm proceeds in three steps. We begin by showing that the ‘‘shape’’ of the factorisation of $L$ can be easily obtained from the Frobenius normal form of its $p$-curvature, which can be efficiently computed an algorithm from Bostan, Caruso and Schost. Using results from the thesis of the author, we are then able to construct an operator $L^{\ast }$ in the same equivalence class as $L$ for which an $\mathrm{L}\mathrm{C}\mathrm{L}\mathrm{M}$-decomposition is known. Finally, by computing an isomorphism between the quotient modules ${\mathbb{F}}_q(t)⟨\mathrm{\partial }⟩\mathrm{/}{\mathbb{F}}_q(t)⟨\mathrm{\partial }⟩L^{\ast }$ and ${\mathbb{F}}_q(t)⟨\mathrm{\partial }⟩\mathrm{/}{\mathbb{F}}_q(t)⟨\mathrm{\partial }⟩L$, we find a corresponding $\mathrm{L}\mathrm{C}\mathrm{L}\mathrm{M}$-decomposition of $L$.