On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
James Renegar · SIAM Journal on Computing · 1989
Let $d_1 , \cdots ,d_n $ be positive integers. Let $\mathcal{P}$ denote the set of systems of polynomials $f:\mathbb{C}^n \to \mathbb{C}^n $ that have only finitely many zeros, including those “at infinity,” and that satisfy degree $(f_i ) = d_i $ for all i. Let $0 < \varepsilon \leqq R$. It is shown for fixed $d_1 , \cdots ,d_n $, that with respect to a certain model of computation, the worst-case computational complexity of obtaining $\varepsilon $-approximations to at least those zeros $\xi $ satisfying $|\xi | \leqq R$ for arbitrary $f \in \mathcal{P}$ is $\Theta (\log \log (({ R / \varepsilon }))$; that is to say, both upper and lower bounds are proved. An algorithm for proving the upper bound is introduced. The number of operations required by this algorithm is \[O\left[ {n\mathcal{D}^4 (\log \mathcal{D})(\log \log ( { R / \varepsilon } )) + n^2 \mathcal{D}^4 \left( \begin{array}{*{20}c} {1 + \Sigma d_i} \\ n \\ \end{array} \right)^4 } \right],\quad {\text{where }}\mathcal{D} = \prod\limits_{i = 1}^n {d_i .} \]