RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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)}$.

UDC: 518.5 + 512.46


 English version:
Journal of Soviet Mathematics, 1992, 59:3, 823–841

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024