




Publications  Convergence Thresholds of Newton's Method for Monotone Polynomial Equations





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 fixedpoint 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 nonnegative solution of a given MSPE X = f(X) arises naturally in the analysis of stochastic models like stochastic contextfree 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 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 backbutton 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}
}




