Arnold Schönhage, Universität Bonn, Institut für Informatik II

Computing Reciprocals of Power Series

Given \[B(x)=b_0+b_1x+\dots+b_nx^n+\cdots\ \in F[[x]]\] with $b_0\neq0$ and``precision''~$x^n$, we discuss various aspects of the computation of \[C(x)=c_0+c_1x+\dots+c_nx^n\equiv1/B(x)\mod x^{n+1},\] namely: {\em{(i)\/}} algebraic complexity bounds on total cost counting all operations $+$, $-$, $*$, $/$ in domain $F(b_0,b_1,\dots)$, in particular for the field $F=\mathbb C$; {\em{(ii)\/}} a new approach for this task by (Graeffe) root squaring steps; {\em{(iii)\/}} its bit complexity for the case of integral coefficients $b_0=1$, \ $b_j\in\mathbb Z$; {\em{(iv)\/}} bit complexity bounds for the main numerical case $F=\mathbb C$.

Virginie Collette
Last modified: Wed Jan 24 15:38:40 MET 2001