TY - GEN

T1 - Convergence thresholds of Newton's method for monotone polynomial equations

AU - Esparza, Javier

AU - Kiefer, Stefan

AU - Luttenberger, Michael

PY - 2008

Y1 - 2008

N2 - Monotone systems of polynomial equations (MSPEs) are systems of fixedpoint equations X1 = f1(X1,...,Xn),..., Xn = fn(X1,...,Xn) 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 kf for strongly connected MSPEs, such that after kf 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 kf as a function of the minimal component of the least fixed-point μf of f(X). Using this result we show that kf 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/w2h new bits of the solution, where w and h are the width and height of the DAG of strongly connected components.

AB - Monotone systems of polynomial equations (MSPEs) are systems of fixedpoint equations X1 = f1(X1,...,Xn),..., Xn = fn(X1,...,Xn) 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 kf for strongly connected MSPEs, such that after kf 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 kf as a function of the minimal component of the least fixed-point μf of f(X). Using this result we show that kf 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/w2h new bits of the solution, where w and h are the width and height of the DAG of strongly connected components.

KW - Fixed-point equations

KW - Formal verification of software

KW - Newton's method

KW - Probabilistic pushdown systems

UR - http://www.scopus.com/inward/record.url?scp=45749104075&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:45749104075

SN - 9783939897064

T3 - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

SP - 289

EP - 300

BT - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

PB - IBFI Schloss Dagstuhl

T2 - 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

Y2 - 21 February 2008 through 23 February 2008

ER -