Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Convergence thresholds of Newton's method for monotone polynomial equations. Technical report, Technische Universität München, Institut für Informatik, October 2007.

Abstract:

Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., 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 like stochastic context-free grammars, probabilistic pushdown automata, and back-button processes. Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs. In a previous paper we have proved the existence for strongly connected MSPEs (scMSPEs) of a threshold k_f 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 maximal and minimal components of f. Using this result we show that k_f is at most single exponential resp. linear for scMSPEs 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/(w 2^h) new bits of the solution, where w, h are the width and height of the DAG of strongly connected components.

Suggested BibTeX entry:

@techreport{EKL08:stacsTechRep,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {October},
    title = {Convergence Thresholds of {N}ewton's Method for Monotone Polynomial Equations},
    year = {2007}
}