2026-07-21T20:02:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1351 2024-03-06T10:32:59Z ddc:004 open_access

Convergence Thresholds of Newton's Method for Monotone Polynomial Equations Esparza, Javier Kiefer, Stefan Luttenberger, Michael Newton's Method Fixed-Point Equations Formal Verification of Software Probabilistic Pushdown Systems Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations $X_1 = f_1(X_1, ldots, X_n),$ $ldots, X_n = f_n(X_1, ldots, 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 $vec X = vec f(vec X)$ arises naturally in the analysis of stochastic models such as 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 of a threshold $k_{vec f}$ for strongly connected MSPEs, such that after $k_{vec 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_{vec f}$ as a function of the minimal component of the least fixed-point $muvec f$ of $vec f(vec X)$. Using this result we show that $k_{vec 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Javier Esparza and Stefan Kiefer and Michael Luttenberger 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1351 urn:nbn:de:0030-drops-13516 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1351 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode