10.4230/LIPICS.STACS.2008.1351
Esparza, Javier
Javier
Esparza
Kiefer, Stefan
Stefan
Kiefer
Luttenberger, Michael
Michael
Luttenberger
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Newton's Method
Fixed-Point Equations
Formal Verification of Software
Probabilistic Pushdown Systems
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13516
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
26
289
300
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
205765 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 289-300