|
Zapiski Nauchnykh Seminarov LOMI, 1989, Volume 176, Pages 68–103
(Mi znsl4534)
|
|
|
|
Complexity of factoring and GCD calculating for linear ordinary differential operators
D. Yu. Grigor'ev
Abstract:
Let $L=\sum\limits_{0\leqslant k\leqslant n}f_k(X)\frac{d^k}{dX^k}\in F(X)\left[\frac d{dX}\right]$ be a linear ordinary
differential operator, where the field $F\simeq\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]/(\varphi)$, here
$T_1,\dots,T_\varepsilon$ are algebraically independent over $\mathbb{Q}$ and the polynomial
$\varphi\in\mathbb{Q}[T_1,\dots,T_\varepsilon][Z]$ is irreducible. Assume that
$\mathrm{deg}_X(f_k)<d$, $\mathrm{deg}_Z(\varphi)<d_1$;
$\mathrm{deg}_{T_1,\dots,T_\varepsilon}(\varphi)$, $\mathrm{deg}_{T_1,\dots,T_\varepsilon}(f_k)<d_2$
and the bit-size of each rational coefficient occurring in $L$ and in $\varphi$ is less than $M$.
Define an integer $N$ such that for any representation $L=Q_1Q_2Q_3$, where $Q_1$, $Q_2$,
$Q_3\in\overline{F}(X)\left[\frac d{dx}\right]$ and $Q_2$, $Q_3$ are monic, holds $\mathrm{deg}_X(Q_2)\leqslant N$.
THEOREM. 1) One can factor $L=L_1\dots L_s$ in a product of irreducible
in the ring $\overline{F}(X)\left[\frac d{dx}\right]$ operators $L_1,\dots,L_s\in F_1(X)\left[\frac d{dx}\right]$
and construct an irreducible polynomial $\varphi_1\in\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]$ such
that $F\simeq\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]/(\varphi_1)$ in time
$(M((Ndn)^{n^2\log(n)}d_1^{\,\log(n)}d_2)^{n^2+\varepsilon})^{O(1)}$;
2) $N\leqslant\exp((M+\varepsilon d_2)(d2^n)^{o(d2^{2n})}d_1^{\,o(2^n)})$.
Define the greatest common right divisor $G=GCRD(Q_1,\dots,Q_s)$
of a family $Q_1,\dots,Q_s\in F(X)\left[\frac d{dx}\right]$ in such a way that $Q_1=\widetilde{Q}_1G,\dots,Q_s=\widetilde{Q}_sG$
and $G$ is of the maximal possible order. Assume that $Q_1,\dots,Q_s$
satisfy the same bounds as Li above.
THEOREM 3). One can yield $GCRD(Q_1,\dots,Q_s)$ in time $(Md(d_1nsd_2)^{\varepsilon+1})^{O(1)}$.
Citation:
D. Yu. Grigor'ev, “Complexity of factoring and GCD calculating for linear ordinary differential operators”, Computational complexity theory. Part 4, Zap. Nauchn. Sem. LOMI, 176, "Nauka", Leningrad. Otdel., Leningrad, 1989, 68–103; J. Soviet Math., 59:3 (1992), 823–841
Linking options:
https://www.mathnet.ru/eng/znsl4534 https://www.mathnet.ru/eng/znsl/v176/p68
|
|