Convergence thresholds of Newton's method for monotone polynomial equations

Monotone systems of polynomial equations (MSPEs) are systems of fixedpoint equations X₁ = f₁(X₁,...,X_n),..., X_n = f_n(X₁,...,X_n) where each f _i is a polynomial with positive real coefficients. The question of computing the least non-negative solution of a given MSPE X = f(X) arises naturally in the analysis of stochastic models such as stochastic context-free grammars, probabilistic pushdown automata, and backbutton processes. Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs. In a previous paper we have proved the existence of a threshold k_f for strongly connected MSPEs, such that after k_f iterations of Newton's method each new iteration computes at least 1 new bit of the solution. However, the proof was purely existential. In this paper we give an upper bound for k_f as a function of the minimal component of the least fixed-point μf of f(X). Using this result we show that k_f is at most single exponential resp. linear for strongly connected MSPEs derived from probabilistic pushdown automata resp. from back-button processes. Further, we prove the existence of a threshold for arbitrary MSPEs after which each new iteration computes at least 1/w2^h new bits of the solution, where w and h are the width and height of the DAG of strongly connected components.